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 = solv_extend_resize(0, totalsize, 1, STRINGSPACE_BLOCK);
  28   ss->strings = solv_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   solv_free(ss->strings);
  45   solv_free(ss->stringspace);
  46   solv_free(ss->stringhashtbl);
  47 }
  48
  49 void
  50 stringpool_freehash(Stringpool *ss)
  51 {
  52   ss->stringhashtbl = solv_free(ss->stringhashtbl);
  53   ss->stringhashmask = 0;
  54 }
  55
  56 void
  57 stringpool_init_empty(Stringpool *ss)
  58 {
  59   static const char *emptystrs[] = { "<NULL>", "", 0 };
  60   stringpool_init(ss, emptystrs);
  61 }
  62
  63 void
  64 stringpool_clone(Stringpool *ss, Stringpool *from)
  65 {
  66   memset(ss, 0, sizeof(*ss));
  67   ss->strings = solv_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK);
  68   memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset));
  69   ss->stringspace = solv_extend_resize(0, from->sstrings, 1, STRINGSPACE_BLOCK);
  70   memcpy(ss->stringspace, from->stringspace, from->sstrings);
  71   ss->nstrings = from->nstrings;
  72   ss->sstrings = from->sstrings;
  73 }
  74
  75 void
  76 stringpool_resize_hash(Stringpool *ss, int numnew)
  77 {
  78   Hashval h, hh, hashmask;
  79   Hashtable hashtbl;
  80   int i;
  81
  82   if (numnew <= 0)
  83     return;
  84   hashmask = mkmask(ss->nstrings + numnew);
  85   if (hashmask <= ss->stringhashmask)
  86     return;     /* same as before */
  87
  88   /* realloc hash table */
  89   ss->stringhashmask = hashmask;
  90   solv_free(ss->stringhashtbl);
  91   ss->stringhashtbl = hashtbl = (Hashtable)solv_calloc(hashmask + 1, sizeof(Id));
  92
  93   /* rehash all strings into new hashtable */
  94   for (i = 1; i < ss->nstrings; i++)
  95     {
  96       h = strhash(ss->stringspace + ss->strings[i]) & hashmask;
  97       hh = HASHCHAIN_START;
  98       while (hashtbl[h] != 0)
  99         h = HASHCHAIN_NEXT(h, hh, hashmask);
 100       hashtbl[h] = i;
 101     }
 102 }
 103
 104 Id
 105 stringpool_strn2id(Stringpool *ss, const char *str, unsigned int len, int create)
 106 {
 107   Hashval h, hh, hashmask, oldhashmask;
 108   Id id;
 109   Hashtable hashtbl;
 110
 111   if (!str)
 112     return STRID_NULL;
 113   if (!len)
 114     return STRID_EMPTY;
 115
 116   hashmask = oldhashmask = ss->stringhashmask;
 117   /* expand hashtable if needed */
 118   if ((Hashval)ss->nstrings * 2 > hashmask)
 119     {
 120       stringpool_resize_hash(ss, STRING_BLOCK);
 121       hashmask = ss->stringhashmask;
 122     }
 123   hashtbl = ss->stringhashtbl;
 124
 125   /* compute hash and check for match */
 126   h = strnhash(str, len) & hashmask;
 127   hh = HASHCHAIN_START;
 128   while ((id = hashtbl[h]) != 0)
 129     {
 130       if(!memcmp(ss->stringspace + ss->strings[id], str, len)
 131          && ss->stringspace[ss->strings[id] + len] == 0)
 132         break;
 133       h = HASHCHAIN_NEXT(h, hh, hashmask);
 134     }
 135   if (id || !create)    /* exit here if string found */
 136     return id;
 137
 138   /* this should be a test for a flag that tells us if the
 139    * correct blocking is used, but adding a flag would break
 140    * the ABI. So we use the existance of the hash area as
 141    * indication instead */
 142   if (!oldhashmask)
 143     {
 144       ss->stringspace = solv_extend_resize(ss->stringspace, ss->sstrings + len + 1, 1, STRINGSPACE_BLOCK);
 145       ss->strings = solv_extend_resize(ss->strings, ss->nstrings + 1, sizeof(Offset), STRING_BLOCK);
 146     }
 147
 148   /* generate next id and save in table */
 149   id = ss->nstrings++;
 150   hashtbl[h] = id;
 151
 152   ss->strings = solv_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK);
 153   ss->strings[id] = ss->sstrings;       /* we will append to the end */
 154
 155   /* append string to stringspace */
 156   ss->stringspace = solv_extend(ss->stringspace, ss->sstrings, len + 1, 1, STRINGSPACE_BLOCK);
 157   memcpy(ss->stringspace + ss->sstrings, str, len);
 158   ss->stringspace[ss->sstrings + len] = 0;
 159   ss->sstrings += len + 1;
 160   return id;
 161 }
 162
 163 Id
 164 stringpool_str2id(Stringpool *ss, const char *str, int create)
 165 {
 166   if (!str)
 167     return STRID_NULL;
 168   if (!*str)
 169     return STRID_EMPTY;
 170   return stringpool_strn2id(ss, str, (unsigned int)strlen(str), create);
 171 }
 172
 173 void
 174 stringpool_shrink(Stringpool *ss)
 175 {
 176   ss->stringspace = solv_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK);
 177   ss->strings = solv_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK);
 178 }