rpmio/rpmstrpool.c

   1 #include "system.h"
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <rpm/rpmstring.h>
   5 #include <rpm/rpmstrpool.h>
   6 #include "debug.h"
   7
   8 #define STRDATA_CHUNKS 1024
   9 #define STRDATA_CHUNK 65536
  10 #define STROFFS_CHUNK 2048
  11 /* XXX this is ridiculously small... */
  12 #define STRHASH_INITSIZE 1024
  13
  14 static int pool_debug = 0;
  15
  16 typedef struct poolHash_s * poolHash;
  17 typedef struct poolHashBucket_s poolHashBucket;
  18
  19 struct poolHashBucket_s {
  20     rpmsid keyid;
  21 };
  22
  23 struct poolHash_s {
  24     int numBuckets;
  25     poolHashBucket * buckets;
  26     int keyCount;
  27 };
  28
  29 struct rpmstrPool_s {
  30     char ** offs;               /* pointers into data area */
  31     rpmsid offs_size;           /* largest offset index */;
  32     rpmsid offs_alloced;        /* offsets allocation size */
  33
  34     char ** chunks;             /* memory chunks for storing the strings */
  35     size_t chunks_size;         /* current chunk */
  36     size_t chunks_allocated;    /* allocated size of the chunks array */
  37     size_t chunk_allocated;     /* size of the current chunk */
  38
  39     poolHash hash;              /* string -> sid hash table */
  40     int frozen;                 /* are new id additions allowed? */
  41     int nrefs;                  /* refcount */
  42 };
  43
  44 /* calculate hash and string length on at once */
  45 static inline unsigned int rstrlenhash(const char * str, size_t * len)
  46 {
  47     /* Jenkins One-at-a-time hash */
  48     unsigned int hash = 0xe4721b68;
  49     const char * s = str;
  50
  51     while (*s != '\0') {
  52       hash += *s;
  53       hash += (hash << 10);
  54       hash ^= (hash >> 6);
  55       s++;
  56     }
  57     hash += (hash << 3);
  58     hash ^= (hash >> 11);
  59     hash += (hash << 15);
  60
  61     if (len)
  62         *len = (s - str);
  63
  64     return hash;
  65 }
  66
  67 static inline unsigned int rstrnlenhash(const char * str, size_t n, size_t * len)
  68 {
  69     /* Jenkins One-at-a-time hash */
  70     unsigned int hash = 0xe4721b68;
  71     const char * s = str;
  72
  73     while (*s != '\0' && n-- > 0) {
  74       hash += *s;
  75       hash += (hash << 10);
  76       hash ^= (hash >> 6);
  77       s++;
  78     }
  79     hash += (hash << 3);
  80     hash ^= (hash >> 11);
  81     hash += (hash << 15);
  82
  83     if (len)
  84         *len = (s - str);
  85
  86     return hash;
  87 }
  88
  89 static inline unsigned int rstrnhash(const char * string, size_t n)
  90 {
  91     return rstrnlenhash(string, n, NULL);
  92 }
  93
  94 unsigned int rstrhash(const char * string)
  95 {
  96     return rstrlenhash(string, NULL);
  97 }
  98
  99 static inline unsigned int hashbucket(unsigned int hash, unsigned int number)
 100 {
 101     return hash + number*number;
 102 }
 103
 104 static poolHash poolHashCreate(int numBuckets)
 105 {
 106     poolHash ht;
 107
 108     ht = xmalloc(sizeof(*ht));
 109     ht->numBuckets = numBuckets;
 110     ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
 111     ht->keyCount = 0;
 112     return ht;
 113 }
 114
 115 static void poolHashResize(rpmstrPool pool, int numBuckets)
 116 {
 117     poolHash ht = pool->hash;
 118     poolHashBucket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
 119
 120     for (int i=0; i<ht->numBuckets; i++) {
 121         if (!ht->buckets[i].keyid) continue;
 122         unsigned int keyHash = rstrhash(rpmstrPoolStr(pool, ht->buckets[i].keyid));
 123         for (unsigned int j=0;;j++) {
 124             unsigned int hash = hashbucket(keyHash, j) % numBuckets;
 125             if (!buckets[hash].keyid) {
 126                 buckets[hash].keyid = ht->buckets[i].keyid;
 127                 break;
 128             }
 129         }
 130     }
 131     free((void *)(ht->buckets));
 132     ht->buckets = buckets;
 133     ht->numBuckets = numBuckets;
 134 }
 135
 136 static void poolHashAddHEntry(rpmstrPool pool, const char * key, unsigned int keyHash, rpmsid keyid)
 137 {
 138     poolHash ht = pool->hash;
 139
 140     /* keep load factor inbetween 0.25 and 0.5 */
 141     if (2*(ht->keyCount) > ht->numBuckets) {
 142         poolHashResize(pool, ht->numBuckets * 2);
 143     }
 144
 145     for (unsigned int i=0;;i++) {
 146         unsigned int hash = hashbucket(keyHash, i) % ht->numBuckets;
 147         if (!ht->buckets[hash].keyid) {
 148             ht->buckets[hash].keyid = keyid;
 149             ht->keyCount++;
 150             break;
 151         } else if (!strcmp(rpmstrPoolStr(pool, ht->buckets[hash].keyid), key)) {
 152             return;
 153         }
 154     }
 155 }
 156
 157 static void poolHashAddEntry(rpmstrPool pool, const char * key, rpmsid keyid)
 158 {
 159     poolHashAddHEntry(pool, key, rstrhash(key), keyid);
 160 }
 161
 162 static void poolHashEmpty( poolHash ht)
 163 {
 164     unsigned int i;
 165
 166     if (ht->keyCount == 0) return;
 167
 168     for (i = 0; i < ht->numBuckets; i++) {
 169         ht->buckets[i].keyid = 0;
 170     }
 171     ht->keyCount = 0;
 172 }
 173
 174 static poolHash poolHashFree(poolHash ht)
 175 {
 176     if (ht==NULL)
 177         return ht;
 178     poolHashEmpty(ht);
 179     ht->buckets = _free(ht->buckets);
 180     ht = _free(ht);
 181
 182     return NULL;
 183 }
 184
 185 static void poolHashPrintStats(rpmstrPool pool)
 186 {
 187     poolHash ht = pool->hash;
 188     int i;
 189     int collisions = 0;
 190     int maxcollisions = 0;
 191
 192     for (i=0; i<ht->numBuckets; i++) {
 193         unsigned int keyHash = rstrhash(rpmstrPoolStr(pool, ht->buckets[i].keyid));
 194         for (unsigned int j=0;;j++) {
 195             unsigned int hash = hashbucket(keyHash, i) % ht->numBuckets;
 196             if (hash==i) {
 197                 collisions += j;
 198                 maxcollisions = maxcollisions > j ? maxcollisions : j;
 199                 break;
 200             }
 201         }
 202     }
 203     fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
 204     fprintf(stderr, "Keys: %i\n", ht->keyCount);
 205     fprintf(stderr, "Collisions: %i\n", collisions);
 206     fprintf(stderr, "Max collisions: %i\n", maxcollisions);
 207 }
 208
 209 static void rpmstrPoolRehash(rpmstrPool pool)
 210 {
 211     int sizehint;
 212
 213     if (pool->offs_size < STRHASH_INITSIZE)
 214         sizehint = STRHASH_INITSIZE;
 215     else
 216         sizehint = pool->offs_size * 2;
 217
 218     if (pool->hash)
 219         pool->hash = poolHashFree(pool->hash);
 220
 221     pool->hash = poolHashCreate(sizehint);
 222     for (int i = 1; i < pool->offs_size; i++)
 223         poolHashAddEntry(pool, rpmstrPoolStr(pool, i), i);
 224 }
 225
 226 rpmstrPool rpmstrPoolCreate(void)
 227 {
 228     rpmstrPool pool = xcalloc(1, sizeof(*pool));
 229
 230     pool->offs_alloced = STROFFS_CHUNK;
 231     pool->offs = xcalloc(pool->offs_alloced, sizeof(*pool->offs));
 232
 233     pool->chunks_allocated = STRDATA_CHUNKS;
 234     pool->chunks = xcalloc(pool->chunks_allocated, sizeof(*pool->chunks));
 235     pool->chunks_size = 1;
 236     pool->chunk_allocated = STRDATA_CHUNK;
 237     pool->offs[1] = xcalloc(1, pool->chunk_allocated);
 238     pool->chunks[pool->chunks_size] = pool->offs[1];
 239
 240     rpmstrPoolRehash(pool);
 241     pool->nrefs = 1;
 242     return pool;
 243 }
 244
 245 rpmstrPool rpmstrPoolFree(rpmstrPool pool)
 246 {
 247     if (pool) {
 248         if (pool->nrefs > 1) {
 249             pool->nrefs--;
 250         } else {
 251             if (pool_debug)
 252                 poolHashPrintStats(pool);
 253             poolHashFree(pool->hash);
 254             free(pool->offs);
 255             for (int i=1;i<=pool->chunks_size;i++) {
 256                 pool->chunks[i] = _free(pool->chunks[i]);
 257             }
 258             free(pool->chunks);
 259             free(pool);
 260         }
 261     }
 262     return NULL;
 263 }
 264
 265 rpmstrPool rpmstrPoolLink(rpmstrPool pool)
 266 {
 267     if (pool)
 268         pool->nrefs++;
 269     return pool;
 270 }
 271
 272 void rpmstrPoolFreeze(rpmstrPool pool, int keephash)
 273 {
 274     if (pool && !pool->frozen) {
 275         if (!keephash) {
 276             pool->hash = poolHashFree(pool->hash);
 277         }
 278         pool->offs_alloced = pool->offs_size + 2; /* space for end marker */
 279         pool->offs = xrealloc(pool->offs,
 280                               pool->offs_alloced * sizeof(*pool->offs));
 281         pool->frozen = 1;
 282     }
 283 }
 284
 285 void rpmstrPoolUnfreeze(rpmstrPool pool)
 286 {
 287     if (pool) {
 288         if (pool->hash == NULL) {
 289             rpmstrPoolRehash(pool);
 290         }
 291         pool->frozen = 0;
 292     }
 293 }
 294
 295 static rpmsid rpmstrPoolPut(rpmstrPool pool, const char *s, size_t slen, unsigned int hash)
 296 {
 297     char *t = NULL;
 298     size_t ssize = slen + 1;
 299     size_t chunk_used;
 300
 301     pool->offs_size += 1;
 302     /* need one extra for end of string */
 303     /* and one extra to mark the end of the chunk */
 304     if (pool->offs_alloced <= pool->offs_size + 2) {
 305         pool->offs_alloced += STROFFS_CHUNK;
 306         pool->offs = xrealloc(pool->offs,
 307                               pool->offs_alloced * sizeof(*pool->offs));
 308     }
 309
 310     chunk_used = pool->offs[pool->offs_size] - pool->chunks[pool->chunks_size];
 311     if (ssize + 1 > pool->chunk_allocated - chunk_used) {
 312         /* check size of ->chunks */
 313         pool->chunks_size += 1;
 314         if (pool->chunks_size >= pool->chunks_allocated) {
 315             pool->chunks_allocated += pool->chunks_allocated;
 316             pool->chunks = xrealloc(pool->chunks,
 317                                 pool->chunks_allocated * sizeof(*pool->chunks));
 318         }
 319
 320         /* Check if string is bigger than chunks */
 321         if (ssize > pool->chunk_allocated) {
 322             pool->chunk_allocated = 2 * ssize;
 323         }
 324
 325         /* Dummy entry for end of last string*/
 326         pool->offs_size += 1;
 327
 328         pool->offs[pool->offs_size] = xcalloc(1, pool->chunk_allocated);
 329         pool->chunks[pool->chunks_size] = pool->offs[pool->offs_size];
 330     }
 331
 332     t = memcpy(pool->offs[pool->offs_size], s, slen);
 333     t[slen] = '\0';
 334     pool->offs[pool->offs_size+1] = t + ssize;
 335
 336     poolHashAddHEntry(pool, t, hash, pool->offs_size);
 337
 338     return pool->offs_size;
 339 }
 340
 341 static rpmsid rpmstrPoolGet(rpmstrPool pool, const char * key, size_t keylen,
 342                             unsigned int keyHash)
 343 {
 344     poolHash ht = pool->hash;
 345     const char * s;
 346
 347
 348     for (unsigned int i=0;; i++) {
 349         unsigned int hash = hashbucket(keyHash, i) % ht->numBuckets;
 350
 351         if (!ht->buckets[hash].keyid) {
 352             return 0;
 353         }
 354
 355         s = rpmstrPoolStr(pool, ht->buckets[hash].keyid);
 356         /* pool string could be longer than keylen, require exact matche */
 357         if (strncmp(s, key, keylen) == 0 && s[keylen] == '\0')
 358             return ht->buckets[hash].keyid;
 359     }
 360 }
 361
 362 static inline rpmsid strn2id(rpmstrPool pool, const char *s, size_t slen,
 363                              unsigned int hash, int create)
 364 {
 365     rpmsid sid = 0;
 366
 367     if (pool && pool->hash) {
 368         sid = rpmstrPoolGet(pool, s, slen, hash);
 369         if (sid == 0 && create && !pool->frozen)
 370             sid = rpmstrPoolPut(pool, s, slen, hash);
 371     }
 372     return sid;
 373 }
 374
 375 rpmsid rpmstrPoolIdn(rpmstrPool pool, const char *s, size_t slen, int create)
 376 {
 377     rpmsid sid = 0;
 378
 379     if (s != NULL) {
 380         unsigned int hash = rstrnhash(s, slen);
 381         sid = strn2id(pool, s, slen, hash, create);
 382     }
 383     return sid;
 384 }
 385
 386 rpmsid rpmstrPoolId(rpmstrPool pool, const char *s, int create)
 387 {
 388     rpmsid sid = 0;
 389
 390     if (s != NULL) {
 391         size_t slen;
 392         unsigned int hash = rstrlenhash(s, &slen);
 393         sid = strn2id(pool, s, slen, hash, create);
 394     }
 395     return sid;
 396 }
 397
 398 const char * rpmstrPoolStr(rpmstrPool pool, rpmsid sid)
 399 {
 400     const char *s = NULL;
 401     if (pool && sid > 0 && sid <= pool->offs_size)
 402         s = pool->offs[sid];
 403     return s;
 404 }
 405
 406 size_t rpmstrPoolStrlen(rpmstrPool pool, rpmsid sid)
 407 {
 408     size_t slen = 0;
 409     if (pool && sid <= pool->offs_size) {
 410         slen = pool->offs[sid+1] - pool->offs[sid] - 1;
 411     }
 412     return slen;
 413 }
 414
 415 int rpmstrPoolStreq(rpmstrPool poolA, rpmsid sidA,
 416                     rpmstrPool poolB, rpmsid sidB)
 417 {
 418     if (poolA == poolB)
 419         return (sidA == sidB);
 420     else
 421         return rstreq(rpmstrPoolStr(poolA, sidA), rpmstrPoolStr(poolB, sidB));
 422 }
 423
 424 rpmsid rpmstrPoolNumStr(rpmstrPool pool)
 425 {
 426     return (pool != NULL) ? pool->offs_size : 0;
 427 }