home *** CD-ROM | disk | FTP | other *** search
/ High Voltage Shareware / high1.zip / high1 / DIR2 / CBUFF09.ZIP / SRC.ZIP / STRTABLE.C < prev    next >
C/C++ Source or Header  |  1993-11-16  |  5KB  |  224 lines
  1. /*  $Id$
  2.  *  
  3.  *  File    strtable.c
  4.  *  Part of    ChessBase utilities file format (CBUFF)
  5.  *  Author    Anjo Anjewierden, anjo@swi.psy.uva.nl
  6.  *  Purpose    Hash table for strings
  7.  *  Works with    GNU CC 2.4.5
  8.  *  
  9.  *  Notice    Copyright (c) 1993  Anjo Anjewierden
  10.  *  
  11.  *  History    17/07/93  (Created)
  12.  *          18/07/93  (Last modified)
  13.  */ 
  14.  
  15.  
  16. /*------------------------------------------------------------
  17.  *  Directives
  18.  *------------------------------------------------------------*/
  19.  
  20. #include "cbuff.h"
  21.  
  22.  
  23. static unsigned long hashStringTable(StringTable, char *);
  24. static unsigned long nextKeyStringTable(StringTable, unsigned long key);
  25. static void    reallocStringTable(StringTable);
  26.  
  27.  
  28. /*------------------------------------------------------------
  29.  *  Initialisation
  30.  *------------------------------------------------------------*/
  31.  
  32. StringTable
  33. newStringTable(long entries)
  34. { StringTable st;
  35.   long n;
  36.  
  37.   st = alloc(sizeof(struct string_table));
  38.   st->count = 0;
  39.   st->allocated = entries;
  40.   st->entries = (char **) alloc(sizeof(char *) * entries);
  41.   st->values = (void **) alloc(sizeof(void *) * entries);
  42.   for (n=0; n<entries; n++)
  43.   { st->entries[n] = (char *) NULL;
  44.     st->values[n] = (void *) NULL;
  45.   }
  46.  
  47.   return st;
  48. }
  49.  
  50.  
  51. void
  52. freeStringTable(StringTable st)
  53. { long n;
  54.  
  55.   for (n=0; n<st->allocated; n++)
  56.   { if (st->entries[n] != (char *) NULL)
  57.       unallocCharp(st->entries[n]);
  58.   }
  59.  
  60.   unalloc(st->entries);
  61.   unalloc(st);
  62. }
  63.  
  64.  
  65. /*------------------------------------------------------------
  66.  *  Private functions
  67.  *------------------------------------------------------------*/
  68.  
  69. static unsigned long
  70. hashStringTable(StringTable st, char *s)
  71. { unsigned long key = 0;
  72.   int shift;
  73.  
  74.   for (shift=0; *s; shift++)
  75.     key += ((unsigned long) *s++) << (shift % 24);
  76.   return key % st->allocated;
  77. }
  78.  
  79.  
  80. static unsigned long
  81. nextKeyStringTable(StringTable st, unsigned long key)
  82. { key++;
  83.   if (key >= st->allocated)
  84.     return 0;
  85.   return key;
  86. }
  87.  
  88.  
  89. static void
  90. reallocStringTable(StringTable st)
  91. { if ((st->count*3) > (st->allocated*2))
  92.   { char **entries;
  93.     void **values;
  94.     long n, k;
  95.     unsigned long key;
  96.     long allocated = st->allocated;
  97.  
  98.     st->allocated = allocated * 2;
  99.     entries = (char **) alloc(sizeof(char *) * st->allocated);
  100.     values = (void **) alloc(sizeof(void *) * st->allocated);
  101.     for (n=0; n<st->allocated; n++)
  102.       entries[n] = (char *) NULL;
  103.     for (n=0; n<allocated; n++)
  104.     { if (st->entries[n])
  105.       { key = hashStringTable(st, st->entries[n]);
  106.  
  107.     if (entries[key] == NULL)
  108.     { entries[key] = st->entries[n];
  109.       values[key] = st->values[n];
  110.       continue;
  111.     }
  112.     for (k=key+1; k<st->allocated; k++)
  113.       if (entries[k] == NULL)
  114.       { entries[k] = st->entries[n];
  115.         values[k] = st->values[n];
  116.         break;
  117.       }
  118.     if (k >= st->allocated)
  119.     { for (k=0; ; k++)
  120.         if (entries[k] == NULL)
  121.         { entries[k] = st->entries[n];
  122.           values[k] = st->values[n];
  123.           break;
  124.         }
  125.     }
  126.       }
  127.     }
  128.     unalloc(st->entries);
  129.     unalloc(st->values);
  130.     st->entries = entries;
  131.     st->values = values;
  132.   }
  133. }
  134.  
  135.  
  136. /*------------------------------------------------------------
  137.  *  Public interface
  138.  *------------------------------------------------------------*/
  139.  
  140. void *
  141. findStringTable(StringTable st, char *s)
  142. { unsigned long key;
  143.  
  144.   for (key=hashStringTable(st,s); ; key=nextKeyStringTable(st,key))
  145.   { if (st->entries[key])
  146.     { if (strcmp(st->entries[key], s) == 0)
  147.     return st->values[key];
  148.       continue;
  149.     }
  150.     return (void *) NULL;
  151.   }
  152. }
  153.  
  154.  
  155. bool
  156. containsStringTableP(StringTable st, char *s)
  157. { unsigned long key;
  158.  
  159.   for (key=hashStringTable(st,s); ; key=nextKeyStringTable(st,key))
  160.   { if (st->entries[key] == NULL)
  161.       return FALSE;
  162.     if (strcmp(st->entries[key], s) == 0)
  163.       return TRUE;
  164.   }
  165. }
  166.  
  167.  
  168. void
  169. editStringTable(StringTable st, char *s, void *p)
  170. { unsigned long key;
  171.  
  172.   for (key=hashStringTable(st,s); ; key=nextKeyStringTable(st,key))
  173.   { if (st->entries[key])
  174.     { if (strcmp(st->entries[key], s) == 0)
  175.       { st->values[key] = p;
  176.     return;
  177.       }
  178.       continue;
  179.     }
  180.     return;
  181.   }
  182. }
  183.  
  184.  
  185. char *
  186. addStringTable(StringTable st, char *s, void *p)
  187. { unsigned long key;
  188.  
  189.   reallocStringTable(st);
  190.   for (key=hashStringTable(st,s); ; key=nextKeyStringTable(st,key))
  191.   { if (st->entries[key] == NULL)
  192.     { st->entries[key] = allocCharp(s);
  193.       st->values[key] = p;
  194.       st->count++;
  195.       return st->entries[key];
  196.     }
  197.   }
  198. }
  199.  
  200.  
  201. void
  202. incStringTable(StringTable st, char *s)
  203. { long count;
  204.  
  205.   if (containsStringTableP(st, s))
  206.   { count = (long) findStringTable(st, s);
  207.     editStringTable(st, s, (void *) (count+1));
  208.   } else
  209.     addStringTable(st, s, (void *) 1L);
  210. }
  211.  
  212.  
  213. void
  214. printStringTable(StringTable st, char *format, FILE *fd)
  215. { unsigned long key;
  216.  
  217.   for (key=0; key<st->allocated; key++)
  218.   { if (st->entries[key])
  219.     { fprintf(fd, format, st->values[key]);
  220.       fprintf(fd, "  %s\n", st->entries[key]);
  221.     }
  222.   }
  223. }
  224.