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_init_empty(Stringpool *ss)
  43 {
  44   const char *emptystrs[] = {
  45     "<NULL>",
  46     "",
  47     0,
  48   };
  49   stringpool_init(ss, emptystrs);
  50 }
  51
  52 void
  53 stringpool_clone(Stringpool *ss, Stringpool *from)
  54 {
  55   memset(ss, 0, sizeof(*ss));
  56   ss->strings = sat_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK);
  57   memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset));
  58   ss->stringspace = sat_extend_resize(0, from->sstrings, 1, STRINGSPACE_BLOCK);
  59   memcpy(ss->stringspace, from->stringspace, from->sstrings);
  60   ss->nstrings = from->nstrings;
  61   ss->sstrings = from->sstrings;
  62 }
  63
  64 Id
  65 stringpool_strn2id (Stringpool *ss, const char *str, unsigned len, int create)
  66 {
  67   Hashval h;
  68   unsigned int hh;
  69   Hashmask hashmask;
  70   int i, space_needed;
  71   Id id;
  72   Hashtable hashtbl;
  73
  74   // check string
  75   if (!str)
  76     return STRID_NULL;
  77   if (!*str)
  78     return STRID_EMPTY;
  79
  80   hashmask = ss->stringhashmask;
  81   hashtbl = ss->stringhashtbl;
  82
  83   // expand hashtable if needed
  84   //
  85   //
  86   if (ss->nstrings * 2 > hashmask)
  87     {
  88       sat_free(hashtbl);
  89
  90       // realloc hash table
  91       ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK);
  92       ss->stringhashtbl = hashtbl = (Hashtable)sat_calloc(hashmask + 1, sizeof(Id));
  93
  94       // rehash all strings into new hashtable
  95       for (i = 1; i < ss->nstrings; i++)
  96         {
  97           h = strhash(ss->stringspace + ss->strings[i]) & hashmask;
  98           hh = HASHCHAIN_START;
  99           while (hashtbl[h] != 0)  // follow overflow chain
 100             h = HASHCHAIN_NEXT(h, hh, hashmask);
 101           hashtbl[h] = i;
 102         }
 103     }
 104
 105   // compute hash and check for match
 106
 107   h = strnhash(str, len) & hashmask;
 108   hh = HASHCHAIN_START;
 109   while ((id = hashtbl[h]) != 0)  // follow hash overflow chain
 110     {
 111       // break if string already hashed
 112       if(!memcmp(ss->stringspace + ss->strings[id], str, len)
 113          && ss->stringspace[ss->strings[id] + len] == 0)
 114         break;
 115       h = HASHCHAIN_NEXT(h, hh, hashmask);
 116     }
 117   if (id || !create)    // exit here if string found
 118     return id;
 119
 120   // generate next id and save in table
 121   id = ss->nstrings++;
 122   hashtbl[h] = id;
 123
 124   ss->strings = sat_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK);
 125   // 'pointer' into stringspace is Offset of next free pos: sstrings
 126   ss->strings[id] = ss->sstrings;
 127
 128   space_needed = len + 1;
 129   // make room in string buffer
 130   ss->stringspace = sat_extend(ss->stringspace, ss->sstrings, space_needed, 1, STRINGSPACE_BLOCK);
 131   // copy new string into buffer
 132   memcpy(ss->stringspace + ss->sstrings, str, space_needed - 1);
 133   // add the sentinel, we can't rely on it being in the source string (in
 134   // case the LEN is not really strlen(str))
 135   ss->stringspace[ss->sstrings + space_needed - 1] = 0;
 136   // next free pos is behind new string
 137   ss->sstrings += space_needed;
 138
 139   return id;
 140 }
 141
 142 Id
 143 stringpool_str2id (Stringpool *ss, const char *str, int create)
 144 {
 145   unsigned len = strlen (str);
 146   return stringpool_strn2id (ss, str, len, create);
 147 }
 148
 149 void
 150 stringpool_shrink (Stringpool *ss)
 151 {
 152   ss->stringspace = sat_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK);
 153   ss->strings = sat_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK);
 154 }