home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume28 / xtree / part01 / table.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-05-29  |  2.8 KB  |  133 lines
  1. /******************************************************************************
  2.  *
  3.  * table.c - manipulation routines for the name table
  4.  *
  5.  *   init    - initialize table
  6.  *   addname - put name in table at depth
  7.  *   getname - get next name at depth
  8.  *
  9.  *****************************************************************************/
  10.  
  11. #include <stdio.h>
  12. #include "xtree.h"
  13.  
  14. typedef struct table_entry {
  15.   char *name;
  16.   struct table_entry *next;
  17. } NTent;
  18.  
  19. NTent *name_tbl[ABSMAX_DEPTH][256];
  20. int index[ABSMAX_DEPTH];
  21. extern int max_depth;
  22.  
  23. /* initialize name table */
  24. #ifdef PROTOTYPE
  25. void init(void)
  26. #else
  27. void init()
  28. #endif /* PROTOTYPE */
  29. {
  30.     int i, j;
  31.  
  32.     for(i = 0; i < max_depth; i++)
  33.       {
  34.         for(j = 0; j < 256; j++)
  35.           name_tbl[i][j] = NULL;
  36.         index[i] = 0;
  37.       }
  38.  
  39.     return;
  40. }
  41.  
  42. /* add 'name' to the name table at depth 'depth' */
  43. #ifdef PROTOTYPE
  44. void addname(char *name, int depth)
  45. #else
  46. void addname(name, depth)
  47. char *name;
  48. int depth;
  49. #endif /* PROTOTYPE */
  50. {
  51.     int slot, done;
  52.     NTent *new, *cur, *last;
  53.  
  54.     /* can only go so far */
  55.     if(depth >= max_depth)
  56.       return;
  57.  
  58.     /* build the new node */
  59.     new = (NTent *) malloc(sizeof(NTent));
  60.     new->name = (char *) malloc(strlen(name) + 1);
  61.     strcpy(new->name, name);
  62.  
  63.     /* go to the table slot to start looking */
  64.     slot = (int) *name;
  65.     last = name_tbl[depth][slot];
  66.  
  67.     if(last == NULL)
  68.       {
  69.         new->next = NULL;
  70.         name_tbl[depth][slot] = new;
  71.       }
  72.     else
  73.       { /*
  74.          *  pass over all nodes with names that are alphabetically less then
  75.          *  the new name
  76.          */
  77.     if(strcmp(last->name, name) > 0)
  78.       { /* goes before first node in bucket */
  79.         new->next = last;
  80.         name_tbl[depth][slot] = new;
  81.       }
  82.     else
  83.       {
  84.         for(cur = last->next, done = FALSE; cur != NULL && !done;
  85.         cur = cur->next, last = last->next)
  86.           if(strcmp(cur->name, new->name) > 0) /* lexically g.t. */
  87.         done = TRUE;
  88.         /* we now want to put new between last and cur */
  89.         new->next = last->next;
  90.         last->next = new;
  91.       }
  92.       }
  93. }
  94.  
  95. #ifdef PROTOTYPE
  96. char *getname(int depth)
  97. #else
  98. char *getname(depth)
  99. int depth;
  100. #endif /* PROTOTYPE */
  101. {
  102.     char *ret;
  103.     NTent *n;
  104.  
  105.     /* can only go so far */
  106.     if(depth >= max_depth)
  107.       return NULL;
  108.  
  109.     /* find slot with nodes */
  110.     for(n = name_tbl[depth][index[depth]]; n == NULL && index[depth] < 256; )
  111.       {
  112.         index[depth]++;
  113.         n = name_tbl[depth][index[depth]];
  114.       }
  115.  
  116.     if(n == NULL)  /* nothing at this depth */
  117.       {
  118.         index[depth] = 0; /* performance loss if getname() is called many */
  119.         return NULL;      /* after exhausting at a given depth */
  120.       }
  121.  
  122.     /* get string */
  123.     ret = (char *) malloc(strlen(n->name) + 1);
  124.     strcpy(ret, n->name);
  125.  
  126.     /* delete node */
  127.     name_tbl[depth][index[depth]] = n->next;
  128.     free(n->name);
  129.     free(n);
  130.  
  131.     return(ret);
  132. }
  133.