src/strpool.c

   1 /*
   2  * Copyright (c) 2007, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 #include <string.h>
   9 #include "util.h"
  10 #include "strpool.h"
  11
  12 #define STRING_BLOCK      2047
  13 #define STRINGSPACE_BLOCK 65535
  14
  15 void
  16 stringpool_init(Stringpool *ss, const char *strs[])
  17 {
  18   unsigned totalsize = 0;
  19   unsigned count;
  20
  21   memset(ss, 0, sizeof(*ss));
  22   // count number and total size of predefined strings
  23   for (count = 0; strs[count]; count++)
  24     totalsize += strlen(strs[count]) + 1;
  25
  26   // alloc appropriate space
  27   ss->stringspace = sat_extend_resize(0, totalsize, 1, STRINGSPACE_BLOCK);
  28   ss->strings = sat_extend_resize(0, count, sizeof(Offset), STRING_BLOCK);
  29
  30   // now copy predefined strings into allocated space
  31   ss->sstrings = 0;
  32   for (count = 0; strs[count]; count++)
  33     {
  34       strcpy(ss->stringspace + ss->sstrings, strs[count]);
  35       ss->strings[count] = ss->sstrings;
  36       ss->sstrings += strlen(strs[count]) + 1;
  37     }
  38   ss->nstrings = count;
  39 }
  40
  41 void
  42 stringpool_free(Stringpool *ss)
  43 {
  44   sat_free(ss->strings);
  45   sat_free(ss->stringspace);
  46   sat_free(ss->stringhashtbl);
  47 }
  48
  49 void
  50 stringpool_freehash(Stringpool *ss)
  51 {
  52   ss->stringhashtbl = sat_free(ss->stringhashtbl);
  53   ss->stringhashmask = 0;
  54 }
  55
  56 void
  57 stringpool_init_empty(Stringpool *ss)
  58 {
  59   const char *emptystrs[] = {
  60     "<NULL>",
  61     "",
  62     0,
  63   };
  64   stringpool_init(ss, emptystrs);
  65 }
  66
  67 void
  68 stringpool_clone(Stringpool *ss, Stringpool *from)
  69 {
  70   memset(ss, 0, sizeof(*ss));
  71   ss->strings = sat_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK);
  72   memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset));
  73   ss->stringspace = sat_extend_resize(0, from->sstrings, 1, STRINGSPACE_BLOCK);
  74   memcpy(ss->stringspace, from->stringspace, from->sstrings);
  75   ss->nstrings = from->nstrings;
  76   ss->sstrings = from->sstrings;
  77 }
  78
  79 Id
  80 stringpool_strn2id(Stringpool *ss, const char *str, unsigned int len, int create)
  81 {
  82   Hashval h;
  83   unsigned int hh;
  84   Hashmask hashmask;
  85   int i;
  86   Id id;
  87   Hashtable hashtbl;
  88
  89   // check string
  90   if (!str)
  91     return STRID_NULL;
  92   if (!len)
  93     return STRID_EMPTY;
  94
  95   hashmask = ss->stringhashmask;
  96   hashtbl = ss->stringhashtbl;
  97
  98   // expand hashtable if needed
  99   if (ss->nstrings * 2 > hashmask)
 100     {
 101       sat_free(hashtbl);
 102
 103       // realloc hash table
 104       ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK);
 105       ss->stringhashtbl = hashtbl = (Hashtable)sat_calloc(hashmask + 1, sizeof(Id));
 106
 107       // rehash all strings into new hashtable
 108       for (i = 1; i < ss->nstrings; i++)
 109         {
 110           h = strhash(ss->stringspace + ss->strings[i]) & hashmask;
 111           hh = HASHCHAIN_START;
 112           while (hashtbl[h] != 0)  // follow overflow chain
 113             h = HASHCHAIN_NEXT(h, hh, hashmask);
 114           hashtbl[h] = i;
 115         }
 116     }
 117
 118   // compute hash and check for match
 119   h = strnhash(str, len) & hashmask;
 120   hh = HASHCHAIN_START;
 121   while ((id = hashtbl[h]) != 0)  // follow hash overflow chain
 122     {
 123       // break if string already hashed
 124       if(!memcmp(ss->stringspace + ss->strings[id], str, len)
 125          && ss->stringspace[ss->strings[id] + len] == 0)
 126         break;
 127       h = HASHCHAIN_NEXT(h, hh, hashmask);
 128     }
 129   if (id || !create)    // exit here if string found
 130     return id;
 131
 132   // generate next id and save in table
 133   id = ss->nstrings++;
 134   hashtbl[h] = id;
 135
 136   ss->strings = sat_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK);
 137   ss->strings[id] = ss->sstrings;       /* we will append to the end */
 138
 139   // append string to stringspace
 140   ss->stringspace = sat_extend(ss->stringspace, ss->sstrings, len + 1, 1, STRINGSPACE_BLOCK);
 141   memcpy(ss->stringspace + ss->sstrings, str, len);
 142   ss->stringspace[ss->sstrings + len] = 0;
 143   ss->sstrings += len + 1;
 144   return id;
 145 }
 146
 147 Id
 148 stringpool_str2id(Stringpool *ss, const char *str, int create)
 149 {
 150   if (!str)
 151     return STRID_NULL;
 152   if (!*str)
 153     return STRID_EMPTY;
 154   return stringpool_strn2id(ss, str, (unsigned int)strlen(str), create);
 155 }
 156
 157 void
 158 stringpool_shrink(Stringpool *ss)
 159 {
 160   ss->stringspace = sat_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK);
 161   ss->strings = sat_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK);
 162 }