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   // count number and total size of predefined strings
  21   for (count = 0; strs[count]; count++)
  22     totalsize += strlen(strs[count]) + 1;
  23
  24   // alloc appropriate space
  25   ss->stringspace = sat_malloc((totalsize + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK);
  26   ss->strings = sat_malloc2((count + STRING_BLOCK) & ~STRING_BLOCK, sizeof(Offset));
  27
  28   // now copy predefined strings into allocated space
  29   ss->sstrings = 0;
  30   for (count = 0; strs[count]; count++)
  31     {
  32       strcpy(ss->stringspace + ss->sstrings, strs[count]);
  33       ss->strings[count] = ss->sstrings;
  34       ss->sstrings += strlen(strs[count]) + 1;
  35     }
  36   ss->nstrings = count;
  37 }
  38
  39 Id
  40 stringpool_strn2id (Stringpool *ss, const char *str, unsigned len, int create)
  41 {
  42   Hashval h;
  43   unsigned int hh;
  44   Hashmask hashmask;
  45   int i, space_needed;
  46   Id id;
  47   Hashtable hashtbl;
  48
  49   // check string
  50   if (!str)
  51     return STRID_NULL;
  52   if (!*str)
  53     return STRID_EMPTY;
  54
  55   hashmask = ss->stringhashmask;
  56   hashtbl = ss->stringhashtbl;
  57
  58   // expand hashtable if needed
  59   //
  60   //
  61   if (ss->nstrings * 2 > hashmask)
  62     {
  63       sat_free(hashtbl);
  64
  65       // realloc hash table
  66       ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK);
  67       ss->stringhashtbl = hashtbl = (Hashtable)sat_calloc(hashmask + 1, sizeof(Id));
  68
  69       // rehash all strings into new hashtable
  70       for (i = 1; i < ss->nstrings; i++)
  71         {
  72           h = strhash(ss->stringspace + ss->strings[i]) & hashmask;
  73           hh = HASHCHAIN_START;
  74           while (hashtbl[h] != 0)  // follow overflow chain
  75             h = HASHCHAIN_NEXT(h, hh, hashmask);
  76           hashtbl[h] = i;
  77         }
  78     }
  79
  80   // compute hash and check for match
  81
  82   h = strnhash(str, len) & hashmask;
  83   hh = HASHCHAIN_START;
  84   while ((id = hashtbl[h]) != 0)  // follow hash overflow chain
  85     {
  86       // break if string already hashed
  87       if(!memcmp(ss->stringspace + ss->strings[id], str, len)
  88          && ss->stringspace[ss->strings[id] + len] == 0)
  89         break;
  90       h = HASHCHAIN_NEXT(h, hh, hashmask);
  91     }
  92   if (id || !create)    // exit here if string found
  93     return id;
  94
  95   // generate next id and save in table
  96   id = ss->nstrings++;
  97   hashtbl[h] = id;
  98
  99   //
 100   if ((id & STRING_BLOCK) == 0)
 101     ss->strings = sat_realloc2(ss->strings, (ss->nstrings + STRING_BLOCK) & ~STRING_BLOCK, sizeof(Hashval));
 102   // 'pointer' into stringspace is Offset of next free pos: sstrings
 103   ss->strings[id] = ss->sstrings;
 104
 105   space_needed = len + 1;
 106
 107   // resize string buffer if needed
 108   if (((ss->sstrings + space_needed - 1) | STRINGSPACE_BLOCK) != ((ss->sstrings - 1) | STRINGSPACE_BLOCK))
 109     ss->stringspace = sat_realloc(ss->stringspace, (ss->sstrings + space_needed + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK);
 110   // copy new string into buffer
 111   memcpy(ss->stringspace + ss->sstrings, str, space_needed - 1);
 112   // add the sentinel, we can't rely on it being in the source string (in
 113   // case the LEN is not really strlen(str))
 114   ss->stringspace[ss->sstrings + space_needed - 1] = 0;
 115   // next free pos is behind new string
 116   ss->sstrings += space_needed;
 117
 118   return id;
 119 }
 120
 121 Id
 122 stringpool_str2id (Stringpool *ss, const char *str, int create)
 123 {
 124   unsigned len = strlen (str);
 125   return stringpool_strn2id (ss, str, len, create);
 126 }
 127
 128 void
 129 stringpool_shrink (Stringpool *ss)
 130 {
 131   ss->stringspace = (char *)sat_realloc(ss->stringspace, (ss->sstrings + STRINGSPACE_BLOCK) & ~STRINGSPACE_BLOCK);
 132   ss->strings = (Offset *)sat_realloc2(ss->strings, (ss->nstrings + STRING_BLOCK) & ~STRING_BLOCK, sizeof(Offset));
 133 }