home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume14 / rn-comments / part01 / stb.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-15  |  6.0 KB  |  233 lines
  1. /* stb.c - symbol table functions */
  2.  
  3. /* By Eamonn McManus <em@dce.ie>.  This file is not copyrighted.
  4.  * $Id: stb.c,v 1.2 90/09/11 23:37:49 em Exp $
  5.  *
  6.  * Functions using a simple binary forest to implement symbol table
  7.  * operations.  Should be recompiled with DATUM defined on the command
  8.  * line as a declaration for variable datum of suitable type.  Default
  9.  * is equivalent to -DDATUM="char *datum".
  10.  */
  11.  
  12. #ifndef DATUM
  13. #define DATUM char *datum
  14. #endif
  15.  
  16. typedef DATUM;
  17.  
  18. #include "stb.h"
  19. #ifdef __STDC__
  20. #include <string.h>    /* For strcpy(). */
  21. #include <stdlib.h>
  22. #else
  23. extern char *malloc();
  24. extern char *strcpy();
  25. extern void free();
  26. #endif
  27.  
  28. #ifndef NULL
  29. # define NULL 0
  30. #endif
  31.  
  32.  
  33. /* Return a new symbol table.  NULL if can't make one. */
  34. stb *stb_new_table()
  35. {
  36.     /* Note that calloc() to get an array of NULLs is not portable. */
  37.     register int i;
  38.     register stb *s = (stb *) malloc(sizeof(stb));
  39.     for (i = 0; i < MAXCHAR; i++)
  40.         (*s)[i] = NULL;
  41.     return s;
  42. }
  43.  
  44.  
  45. /* Free tree rooted at root, using function datumfree. */
  46. static int free_tree(root, datumfree)
  47. register stb_node *root;
  48. register int (*datumfree)();
  49. {
  50.     register stb_node *n;
  51.     for ( ; root != NULL; root = n) {
  52.         if (free_tree(root->link[0], datumfree) < 0)
  53.             return -1;
  54.         n = root->link[1];
  55.         if ((*datumfree)(root->datum) < 0)
  56.             return -1;
  57.         free((char *) root->name);
  58.         free((char *) root);
  59.     }
  60.     return 0;
  61. }
  62.  
  63.  
  64. /* Free a symbol table.  Return 0 if OK, -1 if error.  Datumfree is a
  65.  * routine to free the datum in each node, returning the same error status.
  66.  */
  67. int stb_free_table(table, datumfree)
  68. register stb *table;
  69. register int (*datumfree)();
  70. {
  71.     register int i;
  72.     for (i = 0; i < MAXCHAR; i++)
  73.         if (free_tree((*table)[i], datumfree) < 0)
  74.             return -1;
  75.     free((char *) table);
  76.     return 0;
  77. }
  78.  
  79.  
  80. /* Look up a symbol.  Return pointer to its node or NULL if not found. */
  81. stb_node *stb_lookup(table, name)
  82. stb *table;
  83. register char *name;
  84. {
  85.     register stb_node *n;
  86.     register int order;
  87.     if (name[0] == '\0')
  88.         return (*table)['\0'];    /* Only one null symbol. */
  89.     if ((unsigned char) name[0] >= MAXCHAR)
  90.         return NULL;        /* Invalid. */
  91.     for (n = (*table)[(unsigned char) *name++]; n; n = n->link[order > 0])
  92.         if ((order = strcmp(name, n->name + 1)) == 0)
  93.             return n;
  94.     return NULL;
  95. }
  96.  
  97.  
  98. /* Insert a symbol.  Returns the inserted node, or NULL if there was an
  99.  * error or the symbol was already present.
  100.  */
  101. stb_node *stb_insert(table, name, newdatum)
  102. stb *table;
  103. register char *name;
  104. datum *newdatum;
  105. {
  106.     register stb_node *parent, *n, **link;
  107.     register int order;
  108.     register char *namecpy;
  109.     if ((unsigned char) *name >= MAXCHAR)
  110.         return NULL;        /* Invalid. */
  111.     parent = NULL;
  112.     link = *table + (unsigned char) name[0];
  113.     n = *link;
  114.     if (*name++) {            /* Only one null symbol, no search. */
  115.         while (n != NULL) {
  116.             if ((order = strcmp(name, n->name + 1)) == 0)
  117.                 break;
  118.             link = &n->link[order > 0];
  119.             parent = n; n = *link;
  120.         }
  121.     }
  122.     if (n != NULL)
  123.         return NULL;        /* Already present. */
  124.     if ((namecpy = malloc((unsigned) strlen(--name) + 1)) == NULL)
  125.         return NULL;        /* Out of memory. */
  126.     (void) strcpy(namecpy, name);
  127.     if ((n = (stb_node *) malloc(sizeof(stb_node))) == NULL)
  128.         return NULL;
  129.     n->link[0] = n->link[1] = NULL;
  130.     n->parent = parent; n->name = namecpy; n->datum = *newdatum;
  131.     *link = n;
  132.     return n;
  133. }
  134.  
  135.  
  136. /* Subsequent functions are not used in the rnprejudice code. */
  137. #ifdef UNPREJUDICED
  138.  
  139. /* Return lowest valued descendant of node. */
  140. static stb_node *first(node)
  141. register stb_node *node;
  142. {
  143.     while (node->link[0] != NULL)
  144.         node = node->link[0];
  145.     return node;
  146. }
  147.  
  148.  
  149. /* Return first symbol in table, NULL if table is empty. */
  150. stb_node *stb_first(table)
  151. register stb *table;
  152. {
  153.     register int i;
  154.     for (i = 0; i < MAXCHAR; i++)
  155.         if ((*table)[i] != NULL)
  156.             return first((*table)[i]);
  157.     return NULL;
  158. }
  159.  
  160.  
  161. /* Return the next symbol after the given node, NULL if none. */
  162. stb_node *stb_next(table, node)
  163. stb *table;
  164. register stb_node *node;
  165. {
  166.     register int i;
  167.     /* If there is a right pointer, return its smallest descendant.
  168.      * If this is the left descendant of a node, return that node.
  169.      * Otherwise, we want that node's next.
  170.      */
  171.     if (node->link[1] != NULL)
  172.         return first(node->link[1]);
  173.     for ( ; node->parent != NULL; node = node->parent)
  174.         if (node->parent->link[0] == node)
  175.             return node->parent;
  176.     /* At root for this initial char.  Find next tree. */
  177.     for (i = node->name[0] + 1; i < MAXCHAR; i++)
  178.         if ((*table)[i])
  179.             return first((*table)[i]);
  180.     return NULL;
  181. }
  182.  
  183.  
  184. /* Delete a node.  Return 0 if OK, else -1.  Datumfree is a function to
  185.  * free the datum part of the node, returning the same kind of status.
  186.  */
  187. int stb_delete(table, node, datumfree)
  188. stb *table;
  189. register stb_node *node;
  190. int (*datumfree)();
  191. {
  192.     register stb_node **link, *succ;
  193.     /* Find the link from the parent that we want to change. */
  194.     if (node->parent == NULL)
  195.         link = *table + node->name[0];    /* In the array of roots. */
  196.     else    link = &node->parent->link[node->parent->link[1] == node];
  197.     /* If either descendant is NULL, replace with the other.  Otherwise
  198.      * find the successor and replace with that.
  199.      */
  200.     if (node->link[0] == NULL)
  201.         *link = node->link[1];
  202.     else if (node->link[1] == NULL)
  203.         *link = node->link[0];
  204.     else {
  205.         succ = first(node->link[1]);
  206.         /* Replace the deleted node with its successor, succ.  Succ
  207.          * has no left child (since that would be the successor), so
  208.          * it inherits the original node's left child.
  209.          * If succ is the right child of the original node, that is
  210.          * enough.  Otherwise, succ's parent
  211.          * inherits succ's right child as its left child (which was
  212.          * succ), and succ inherits the original node's right child.
  213.          */
  214.         succ->link[0] = node->link[0]; node->link[0]->parent = succ;
  215.         if (succ->parent != node) {
  216.             succ->parent->link[0] = succ->link[1];
  217.             if (succ->link[1] != NULL)
  218.                 succ->link[1]->parent = succ->parent;
  219.             succ->link[1] = node->link[1];
  220.                 node->link[1]->parent = succ;
  221.         }
  222.         *link = succ;
  223.     }
  224.     if (*link != NULL)
  225.         (*link)->parent = node->parent;
  226.     if ((*datumfree)(node->datum) < 0)
  227.         return -1;
  228.     free((char *)node->name); free((char *)node);
  229.     return 0;
  230. }
  231.  
  232. #endif    /* UNPREJUDICED */
  233.