From e5c536d6eed60217b5c72cfa962db9f7c6dce0ea Mon Sep 17 00:00:00 2001
From: ellson <devnull@localhost>
Date: Sun, 5 Oct 2008 03:22:07 +0000
Subject: [PATCH] put rbtree sources in their own directory, build as a
 convenience library

---
 lib/rbtree/stack.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++
 lib/rbtree/stack.h | 43 ++++++++++++++++++++++++++
 2 files changed, 119 insertions(+)
 create mode 100755 lib/rbtree/stack.c
 create mode 100755 lib/rbtree/stack.h

diff --git a/lib/rbtree/stack.c b/lib/rbtree/stack.c
new file mode 100755
index 000000000..0d9382e98
--- /dev/null
+++ b/lib/rbtree/stack.c
@@ -0,0 +1,76 @@
+#include "stack.h"
+
+int StackNotEmpty(stk_stack * theStack) {
+  return( theStack ? (int) theStack->top : 0);
+}
+
+stk_stack * StackJoin(stk_stack * stack1, stk_stack * stack2) {
+  if (!stack1->tail) {
+    free(stack1);
+    return(stack2);
+  } else {
+    stack1->tail->next=stack2->top;
+    stack1->tail=stack2->tail;
+    free(stack2);
+    return(stack1);
+  }
+}
+
+stk_stack * StackCreate() {
+  stk_stack * newStack;
+  
+  newStack=(stk_stack *) SafeMalloc(sizeof(stk_stack));
+  newStack->top=newStack->tail=NULL;
+  return(newStack);
+}
+
+
+void StackPush(stk_stack * theStack, DATA_TYPE newInfoPointer) {
+  stk_stack_node * newNode;
+
+  if(!theStack->top) {
+    newNode=(stk_stack_node *) SafeMalloc(sizeof(stk_stack_node));
+    newNode->info=newInfoPointer;
+    newNode->next=theStack->top;
+    theStack->top=newNode;
+    theStack->tail=newNode;
+  } else {
+    newNode=(stk_stack_node *) SafeMalloc(sizeof(stk_stack_node));
+    newNode->info=newInfoPointer;
+    newNode->next=theStack->top;
+    theStack->top=newNode;
+  }
+  
+}
+
+DATA_TYPE StackPop(stk_stack * theStack) {
+  DATA_TYPE popInfo;
+  stk_stack_node * oldNode;
+
+  if(theStack->top) {
+    popInfo=theStack->top->info;
+    oldNode=theStack->top;
+    theStack->top=theStack->top->next;
+    free(oldNode);
+    if (!theStack->top) theStack->tail=NULL;
+  } else {
+    popInfo=NULL;
+  }
+  return(popInfo);
+}
+
+void StackDestroy(stk_stack * theStack,void DestFunc(void * a)) {
+  stk_stack_node * x=theStack->top;
+  stk_stack_node * y;
+
+  if(theStack) {
+    while(x) {
+      y=x->next;
+      DestFunc(x->info);
+      free(x);
+      x=y;
+    }
+    free(theStack);
+  }
+} 
+    
diff --git a/lib/rbtree/stack.h b/lib/rbtree/stack.h
new file mode 100755
index 000000000..33264aa09
--- /dev/null
+++ b/lib/rbtree/stack.h
@@ -0,0 +1,43 @@
+#include "misc.h"
+
+/*  CONVENTIONS:  All data structures for stacks have the prefix */
+/*                "stk_" to prevent name conflicts. */
+/*                                                                      */
+/*                Function names: Each word in a function name begins with */
+/*                a capital letter.  An example funcntion name is  */
+/*                CreateRedTree(a,b,c). Furthermore, each function name */
+/*                should begin with a capital letter to easily distinguish */
+/*                them from variables. */
+/*                                                                     */
+/*                Variable names: Each word in a variable name begins with */
+/*                a capital letter EXCEPT the first letter of the variable */
+/*                name.  For example, int newLongInt.  Global variables have */
+/*                names beginning with "g".  An example of a global */
+/*                variable name is gNewtonsConstant. */
+
+/*  if DATA_TYPE is undefined then stack.h and stack.c will be code for */
+/*  stacks of void *, if they are defined then they will be stacks of the */
+/*  appropriate data_type */
+
+#ifndef DATA_TYPE
+#define DATA_TYPE void *
+#endif
+
+typedef struct stk_stack_node {
+  DATA_TYPE info;
+  struct stk_stack_node * next;
+} stk_stack_node;
+
+typedef struct stk_stack { 
+  stk_stack_node * top;
+  stk_stack_node * tail;
+} stk_stack ;
+
+/*  These functions are all very straightforward and self-commenting so */
+/*  I didn't think additional comments would be useful */
+stk_stack * StackJoin(stk_stack * stack1, stk_stack * stack2);
+stk_stack * StackCreate();
+void StackPush(stk_stack * theStack, DATA_TYPE newInfoPointer);
+void * StackPop(stk_stack * theStack);
+int StackNotEmpty(stk_stack *);
+
-- 
2.40.0