home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / src / common / strtbl.c < prev    next >
C/C++ Source or Header  |  2001-12-12  |  5KB  |  217 lines
  1. /*
  2.  * The functions in this file maintain a hash table of strings and manage
  3.  *   string buffers.
  4.  */
  5. #include "../h/gsupport.h"
  6.  
  7. /*
  8.  * Prototype for static function.
  9.  */
  10. static int streq  (int len, char *s1, char *s2);
  11.  
  12. /*
  13.  * Entry in string table.
  14.  */
  15. struct str_entry {
  16.    char *s;                 /* string */
  17.    int length;              /* length of string */
  18.    struct str_entry *next;
  19.    };
  20.  
  21. #define SBufSize 1024                     /* initial size of a string buffer */
  22. #define StrTblSz 149                      /* size of string hash table */
  23. static struct str_entry **str_tbl = NULL; /* string hash table */
  24.  
  25. /*
  26.  * init_str - initialize string hash table.
  27.  */
  28. void init_str()
  29.    {
  30.    int h;
  31.  
  32.    if (str_tbl == NULL) {
  33.       str_tbl = alloc(StrTblSz * sizeof(struct str_entry *));
  34.       for (h = 0; h < StrTblSz; ++h)
  35.          str_tbl[h] = NULL;
  36.       }
  37.    }
  38.  
  39. /*
  40.  * free_stbl - free string table.
  41.  */
  42. void free_stbl()
  43.    {
  44.    struct str_entry *se, *se1;
  45.    int h;
  46.  
  47.    for (h = 0; h < StrTblSz; ++h)
  48.       for (se = str_tbl[h]; se != NULL; se = se1) {
  49.          se1 = se->next;
  50.          free((char *)se);
  51.          }
  52.  
  53.    free((char *)str_tbl);
  54.    str_tbl = NULL;
  55.    }
  56.  
  57. /*
  58.  * init_sbuf - initialize a new sbuf struct, allocating an initial buffer.
  59.  */
  60. void init_sbuf(sbuf)
  61. struct str_buf *sbuf;
  62.    {
  63.    sbuf->size = SBufSize;
  64.    sbuf->frag_lst = alloc(sizeof(struct str_buf_frag) + (SBufSize - 1));
  65.    sbuf->frag_lst->next = NULL;
  66.    sbuf->strtimage = sbuf->frag_lst->s;
  67.    sbuf->endimage = sbuf->strtimage;
  68.    sbuf->end = sbuf->strtimage + SBufSize;
  69.    }
  70.  
  71. /*
  72.  * clear_sbuf - free string buffer storage.
  73.  */
  74. void clear_sbuf(sbuf)
  75. struct str_buf *sbuf;
  76.    {
  77.    struct str_buf_frag *sbf, *sbf1;
  78.  
  79.    for (sbf = sbuf->frag_lst; sbf != NULL; sbf = sbf1) {
  80.       sbf1 = sbf->next;
  81.       free((char *)sbf);
  82.       }
  83.    sbuf->frag_lst = NULL;
  84.    sbuf->strtimage = NULL;
  85.    sbuf->endimage = NULL;
  86.    sbuf->end = NULL;
  87.    }
  88.  
  89. /*
  90.  * new_sbuf - allocate a new buffer for a sbuf struct, copying the partially
  91.  *   created string from the end of full buffer to the new one.
  92.  */
  93. void new_sbuf(sbuf)
  94. struct str_buf *sbuf;
  95.    {
  96.    struct str_buf_frag *sbf;
  97.    char *s1, *s2;
  98.  
  99.    /*
  100.     * The new buffer is larger than the old one to insure that any
  101.     *  size string can be buffered.
  102.     */
  103. #if IntBits == 16
  104.    unsigned int oldsize = sbuf->size;
  105.    sbuf->size += (sbuf->size/2);
  106.    if (sbuf->size < oldsize) {        /* check for overflow */
  107.       sbuf->size = MaxBlock;
  108.       }
  109. #else                    /* IntBits == 16 */
  110.    sbuf->size *= 2;
  111. #endif                    /* IntBits == 16 */
  112.  
  113.    s1 = sbuf->strtimage;
  114.    sbf = alloc(sizeof(struct str_buf_frag) + (sbuf->size - 1));
  115.    sbf->next = sbuf->frag_lst;
  116.    sbuf->frag_lst = sbf;
  117.    sbuf->strtimage = sbf->s;
  118.    s2 = sbuf->strtimage;
  119.    while (s1 < sbuf->endimage)
  120.       *s2++ = *s1++;
  121.    sbuf->endimage = s2;
  122.    sbuf->end = sbuf->strtimage + sbuf->size;
  123.    }
  124.  
  125. /*
  126.  * spec_str - install a special string (null terminated) in the string table.
  127.  */
  128. char *spec_str(s)
  129. char *s;
  130.    {
  131.    struct str_entry *se;
  132.    register char *s1;
  133.    register int l;
  134.    register int h;
  135.  
  136.    h = 0;
  137.    l = 1;
  138.    for (s1 = s; *s1 != '\0'; ++s1) {
  139.       h += *s1 & 0377;
  140.       ++l;
  141.       }
  142.    h %= StrTblSz;
  143.    for (se = str_tbl[h]; se != NULL; se = se->next)
  144.       if (l == se->length && streq(l, s, se->s))
  145.          return se->s;
  146.    se = NewStruct(str_entry);
  147.    se->s = s;
  148.    se->length = l;
  149.    se->next = str_tbl[h];
  150.    str_tbl[h] = se;
  151.    return s;
  152.    }
  153.  
  154. /*
  155.  * str_install - find out if the string at the end of the buffer is in
  156.  *   the string table. If not, put it there. Return a pointer to the
  157.  *   string in the table.
  158.  */
  159. char *str_install(sbuf)
  160. struct str_buf *sbuf;
  161.    {
  162.    int h;
  163.    struct str_entry *se;
  164.    register char *s;
  165.    register char *e;
  166.    int l;
  167.  
  168.    AppChar(*sbuf, '\0');   /* null terminate the buffered copy of the string */
  169.    s = sbuf->strtimage;
  170.    e = sbuf->endimage;
  171.  
  172.    /*
  173.     * Compute hash value.
  174.     */
  175.    h = 0;
  176.    while (s < e)
  177.       h += *s++ & 0377;
  178.    h %= StrTblSz;
  179.    s = sbuf->strtimage;
  180.    l = e - s;
  181.    for (se = str_tbl[h]; se != NULL; se = se->next)
  182.       if (l == se->length && streq(l, s, se->s)) {
  183.          /*
  184.           * A copy of the string is already in the table. Delete the copy
  185.           *  in the buffer.
  186.           */
  187.          sbuf->endimage = s;
  188.          return se->s;
  189.          }
  190.  
  191.    /*
  192.     * The string is not in the table. Add the copy from the buffer to the
  193.     *  table.
  194.     */
  195.    se = NewStruct(str_entry);
  196.    se->s = s;
  197.    se->length = l;
  198.    sbuf->strtimage = e;
  199.    se->next = str_tbl[h];
  200.    str_tbl[h] = se;
  201.    return se->s;
  202.    }
  203.  
  204. /*
  205.  * streq - compare s1 with s2 for len bytes, and return 1 for equal,
  206.  *  0 for not equal.
  207.  */
  208. static int streq(len, s1, s2)
  209. register int len;
  210. register char *s1, *s2;
  211.    {
  212.    while (len--)
  213.       if (*s1++ != *s2++)
  214.          return 0;
  215.    return 1;
  216.    }
  217.