crccache/rmm_hash.c

   1 /* Licensed to the Apache Software Foundation (ASF) under one or more
   2  * contributor license agreements.  See the NOTICE file distributed with
   3  * this work for additional information regarding copyright ownership.
   4  * The ASF licenses this file to You under the Apache License, Version 2.0
   5  * (the "License"); you may not use this file except in compliance with
   6  * the License.  You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *
  16  * A hash table allocated/maintained in an RMM memory structure, so it can be used
  17  * in shared memory
  18  *
  19  * Based on apr_hash.c
  20  *
  21  *  Created on: 02/08/2010
  22  *      Author: Alex Wulms
  23  */
  24
  25
  26 #if APR_HAVE_STDLIB_H
  27 #include <stdlib.h>
  28 #endif
  29 #if APR_HAVE_STRING_H
  30 #include <string.h>
  31 #endif
  32
  33 #if APR_POOL_DEBUG && APR_HAVE_STDIO_H
  34 #include <stdio.h>
  35 #endif
  36
  37 #include "rmm_hash.h"
  38 /*
  39  * The internal form of a hash table.
  40  *
  41  * The table is an array indexed by the hash of the key; collisions
  42  * are resolved by hanging a linked list of hash entries off each
  43  * element of the array. Although this is a really simple design it
  44  * isn't too bad given that RMM has a low allocation overhead.
  45  */
  46
  47 typedef struct rmm_hash_entry_t rmm_hash_entry_t;
  48
  49 RMM_OFF_T_DECLARE(rmm_hash_entry_t);
  50
  51 struct rmm_hash_entry_t {
  52     RMM_OFF_T(rmm_hash_entry_t) next;
  53     unsigned int      hash;
  54     apr_rmm_off_t      key;
  55     apr_ssize_t       klen;
  56     apr_rmm_off_t     val;
  57 };
  58
  59 /*
  60  * Data structure for iterating through a hash table.
  61  *
  62  * We keep a pointer to the next hash entry here to allow the current
  63  * hash entry to be freed or otherwise mangled between calls to
  64  * apr_hash_next().
  65  */
  66 typedef struct rmm_hash_index_t rmm_hash_index_t;
  67 struct rmm_hash_index_t {
  68     RMM_OFF_T(rmm_hash_index_t) ht;
  69     RMM_OFF_T(rmm_hash_entry_t) this, next;
  70     unsigned int        index;
  71 };
  72
  73 /*
  74  * The size of the array is always a power of two. We use the maximum
  75  * index rather than the size so that we can use bitwise-AND for
  76  * modular arithmetic.
  77  * The count of hash entries may be greater depending on the chosen
  78  * collision rate.
  79  */
  80 RMM_OFF_T_DECLARE(rmm_hash_entry_t_ptr);
  81 typedef struct rmm_hash_t rmm_hash_t;
  82 struct rmm_hash_t {
  83     RMM_OFF_T(rmm_hash_entry_t_ptr)   array;
  84     rmm_hash_index_t     iterator;  /* For apr_hash_first(NULL, ...) */
  85     unsigned int         count, max;
  86     apr_hashfunc_t       hash_func;
  87     RMM_OFF_T(rmm_hash_entry_t)  free;  /* List of recycled entries */
  88 };
  89
  90 #define INITIAL_MAX 15 /* tunable == 2^n - 1 */
  91
  92
  93 /*
  94  * Hash creation functions.
  95  */
  96
  97 static RMM_OFF_T(rmm_hash_entry_t_ptr) alloc_array(apr_rmm_t *rmm, unsigned int max)
  98 {
  99    return apr_rmm_malloc(rmm, sizeof(apr_rmm_off_t) * (max + 1));
 100 }
 101
 102
 103 APR_DECLARE(RMM_OFF_T(rmm_hash_t)) rmm_hash_make(apr_rmm_t *rmm)
 104 {
 105     rmm_hash_t *ht_physical;
 106     RMM_OFF_T(rmm_hash_t) ht_offset;
 107     ht_offset = apr_rmm_malloc(rmm, sizeof(rmm_hash_t));
 108     if (ht_offset == RMM_OFF_NULL) {
 109         return RMM_OFF_NULL;
 110     }
 111     ht_physical = APR_RMM_ADDR_GET(rmm_hash_t, rmm, ht_offset);
 112     ht_physical->free = RMM_OFF_NULL;
 113     ht_physical->count = 0;
 114     ht_physical->max = INITIAL_MAX;
 115     ht_physical->array = alloc_array(rmm, ht_physical->max);
 116     if (ht_physical == RMM_OFF_NULL)
 117     {
 118         apr_rmm_free(rmm, ht_offset);
 119         return RMM_OFF_NULL;
 120     }
 121     ht_physical->hash_func = apr_hashfunc_default;
 122     return ht_offset;
 123 }
 124
 125 APR_DECLARE(RMM_OFF_T(rmm_hash_t)) rmm_hash_make_custom(apr_rmm_t *rmm,
 126                                                apr_hashfunc_t hash_func)
 127 {
 128     RMM_OFF_T(rmm_hash_t) ht_offset = rmm_hash_make(rmm);
 129     if (ht_offset == RMM_OFF_NULL) {
 130         return RMM_OFF_NULL;
 131     }
 132     APR_RMM_ADDR_GET(rmm_hash_t, rmm, ht_offset)->hash_func=hash_func;
 133     return ht_offset;
 134 }
 135
 136
 137 /*
 138  * Hash iteration functions.
 139  */
 140 APR_DECLARE(RMM_OFF_T(rmm_hash_index_t)) rmm_hash_next(apr_rmm_t *rmm, RMM_OFF_T(rmm_hash_index_t)hi)
 141 {
 142         rmm_hash_index_t *hi_physical = APR_RMM_ADDR_GET(rmm_hash_index_t, rmm, hi);
 143         rmm_hash_t *ht_physical = APR_RMM_ADDR_GET(rmm_hash_t, rmm, hi_physical->ht);
 144         RMM_OFF_T(rmm_hash_entry_t) *array_physical = APR_RMM_ADDR_GET(RMM_OFF_T(rmm_hash_entry_t), rmm, ht_physical->array);
 145     hi_physical->this = hi_physical->next;
 146
 147     while (hi_physical->this == RMM_OFF_NULL) {
 148         if (hi_physical->index > ht_physical->max)
 149             return RMM_OFF_NULL;
 150
 151         hi_physical->this = array_physical[hi_physical->index++];
 152     }
 153     hi_physical->next = APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, hi_physical->this)->next;
 154     return hi;
 155 }
 156
 157 APR_DECLARE(RMM_OFF_T(rmm_hash_index_t)) rmm_hash_first(int allocate_hi, apr_rmm_t *rmm, RMM_OFF_T(rmm_hash_t) ht)
 158 {
 159     RMM_OFF_T(rmm_hash_index_t) hi;
 160     rmm_hash_index_t *hi_physical;
 161     if (allocate_hi) {
 162         hi = apr_rmm_calloc(rmm, sizeof(rmm_hash_index_t));
 163         hi_physical = APR_RMM_ADDR_GET(rmm_hash_index_t, rmm, hi);
 164     }
 165     else {
 166         hi_physical = &(APR_RMM_ADDR_GET(rmm_hash_t, rmm, ht)->iterator);
 167         hi = apr_rmm_offset_get(rmm, hi_physical);
 168     }
 169     hi_physical->ht = ht;
 170     hi_physical->index = 0;
 171     hi_physical->this = RMM_OFF_NULL;
 172     hi_physical->next = RMM_OFF_NULL;
 173     return rmm_hash_next(rmm, hi);
 174 }
 175
 176 APR_DECLARE(void) rmm_hash_this(apr_rmm_t *rmm, RMM_OFF_T(rmm_hash_index_t) hi,
 177                                                                 apr_rmm_off_t *key,
 178                                 apr_ssize_t *klen,
 179                                 apr_rmm_off_t *val)
 180 {
 181         rmm_hash_index_t *hi_physical = APR_RMM_ADDR_GET(rmm_hash_index_t, rmm, hi);
 182         rmm_hash_entry_t *this_physical = APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, hi_physical->this);
 183     if (key)  *key  = this_physical->key;
 184     if (klen) *klen = this_physical->klen;
 185     if (val)  *val  = this_physical->val;
 186 }
 187
 188 /*
 189  * Expanding a hash table
 190  */
 191 static void expand_array(apr_rmm_t *rmm, RMM_OFF_T(rmm_hash_t) ht_offset)
 192 {
 193         RMM_OFF_T(rmm_hash_index_t) hi_offset;
 194         rmm_hash_index_t *hi_physical;
 195     RMM_OFF_T(rmm_hash_entry_t_ptr) new_array_offset;
 196     RMM_OFF_T(rmm_hash_entry_t) *new_array_physical;
 197     unsigned int new_max;
 198     rmm_hash_t *ht_physical = APR_RMM_ADDR_GET(rmm_hash_t, rmm, ht_offset);
 199     new_max = ht_physical->max * 2 + 1;
 200     new_array_offset = alloc_array(rmm, new_max);
 201     if (new_array_offset == RMM_OFF_NULL) {
 202         return; // Can't allocate memory to expand the array, keep using the old one
 203     }
 204     new_array_physical = APR_RMM_ADDR_GET(RMM_OFF_T(rmm_hash_entry_t), rmm, new_array_offset);
 205     for (hi_offset = rmm_hash_first(0, rmm, ht_offset); hi_offset; hi_offset = rmm_hash_next(rmm, hi_offset)) {
 206         hi_physical = APR_RMM_ADDR_GET(rmm_hash_index_t, rmm, hi_offset);
 207         rmm_hash_entry_t *this_physical = APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, hi_physical->this);
 208         unsigned int i = this_physical->hash & new_max;
 209         this_physical->next = new_array_physical[i];
 210         new_array_physical[i] = hi_physical->this;
 211     }
 212     apr_rmm_free(rmm, ht_physical->array);
 213     ht_physical->array = new_array_offset;
 214     ht_physical->max = new_max;
 215 }
 216
 217
 218 /*
 219  * This is where we keep the details of the hash function and control
 220  * the maximum collision rate.
 221  *
 222  * If val is non-NULL it creates and initializes a new hash entry if
 223  * there isn't already one there; it returns an updatable pointer so
 224  * that hash entries can be removed.
 225  */
 226 static RMM_OFF_T(rmm_hash_entry_t) *find_entry(apr_rmm_t *rmm, RMM_OFF_T(rmm_hash_t) ht_offset,
 227                                      const void *key_physical,
 228                                      apr_ssize_t klen,
 229                                      apr_rmm_off_t val_offset)
 230 {
 231     RMM_OFF_T(rmm_hash_entry_t) *he_offset_p, he_offset;
 232     rmm_hash_entry_t *he_physical;
 233     unsigned int hash;
 234
 235     rmm_hash_t *ht_physical = APR_RMM_ADDR_GET(rmm_hash_t, rmm, ht_offset);
 236     hash = ht_physical->hash_func(key_physical, &klen);
 237     RMM_OFF_T(rmm_hash_entry_t) *array_physical= APR_RMM_ADDR_GET(RMM_OFF_T(rmm_hash_entry_t), rmm, ht_physical->array);
 238
 239     /* scan linked list */
 240     for (he_offset_p = &array_physical[hash & ht_physical->max], he_offset = *he_offset_p;
 241          he_offset != RMM_OFF_NULL;
 242          he_offset_p = &he_physical->next, he_offset = *he_offset_p) {
 243         he_physical = APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, he_offset);
 244         if (he_physical->hash == hash
 245             && he_physical->klen == klen
 246             && memcmp(APR_RMM_ADDR_GET(void, rmm, he_physical->key), key_physical, klen) == 0)
 247             break;
 248     }
 249     if (he_offset || val_offset == RMM_OFF_NULL)
 250         return he_offset_p;
 251
 252     /* add a new entry for non-NULL values */
 253     if ((he_offset = ht_physical->free) != RMM_OFF_NULL)
 254         ht_physical->free = APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, he_offset)->next;
 255     else
 256         he_offset = apr_rmm_calloc(rmm, sizeof(*he_physical));
 257     he_physical = APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, he_offset);
 258     he_physical->next = RMM_OFF_NULL;
 259     he_physical->hash = hash;
 260     he_physical->key  = apr_rmm_offset_get(rmm, (void *)key_physical);
 261     he_physical->klen = klen;
 262     he_physical->val  = val_offset;
 263     *he_offset_p = he_offset;
 264     ht_physical->count++;
 265     return he_offset_p;
 266 }
 267
 268 /**
 269  * TODO: Migrate from apr_hash (pool-based) structure to rmm_hash (rmm-based) structure
 270  */
 271 #if 0
 272 APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,
 273                                         const apr_hash_t *orig)
 274 {
 275     apr_hash_t *ht;
 276     apr_hash_entry_t *new_vals;
 277     unsigned int i, j;
 278
 279     ht = apr_palloc(pool, sizeof(apr_hash_t) +
 280                     sizeof(*ht->array) * (orig->max + 1) +
 281                     sizeof(apr_hash_entry_t) * orig->count);
 282     ht->pool = pool;
 283     ht->free = NULL;
 284     ht->count = orig->count;
 285     ht->max = orig->max;
 286     ht->hash_func = orig->hash_func;
 287     ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t));
 288
 289     new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) +
 290                                     sizeof(*ht->array) * (orig->max + 1));
 291     j = 0;
 292     for (i = 0; i <= ht->max; i++) {
 293         apr_hash_entry_t **new_entry = &(ht->array[i]);
 294         apr_hash_entry_t *orig_entry = orig->array[i];
 295         while (orig_entry) {
 296             *new_entry = &new_vals[j++];
 297             (*new_entry)->hash = orig_entry->hash;
 298             (*new_entry)->key = orig_entry->key;
 299             (*new_entry)->klen = orig_entry->klen;
 300             (*new_entry)->val = orig_entry->val;
 301             new_entry = &((*new_entry)->next);
 302             orig_entry = orig_entry->next;
 303         }
 304         *new_entry = NULL;
 305     }
 306     return ht;
 307 }
 308 #endif
 309
 310 APR_DECLARE(apr_rmm_off_t) rmm_hash_get(apr_rmm_t *rmm, RMM_OFF_T(rmm_hash_t) ht,
 311                                  const void *key,
 312                                  apr_ssize_t klen)
 313 {
 314     RMM_OFF_T(rmm_hash_entry_t) he_offset;
 315     he_offset = *find_entry(rmm, ht, key, klen, RMM_OFF_NULL);
 316     if (he_offset)
 317         return APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, he_offset)->val;
 318     else
 319         return RMM_OFF_NULL;
 320 }
 321
 322 APR_DECLARE(apr_rmm_off_t) rmm_hash_set(apr_rmm_t *rmm, RMM_OFF_T(rmm_hash_t) ht,
 323                                apr_rmm_off_t key,
 324                                apr_ssize_t klen,
 325                                apr_rmm_off_t val)
 326 {
 327     RMM_OFF_T(rmm_hash_entry_t) *he_offset_p;
 328     apr_rmm_off_t oldval = RMM_OFF_NULL;
 329     he_offset_p = find_entry(rmm, ht, apr_rmm_addr_get(rmm, key), klen, val);
 330     if (*he_offset_p) {
 331         RMM_OFF_T(rmm_hash_entry_t) old = *he_offset_p;
 332         rmm_hash_entry_t *old_physical = APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, old);
 333         oldval = old_physical->val;
 334         rmm_hash_t *ht_physical = APR_RMM_ADDR_GET(rmm_hash_t, rmm, ht);
 335         if (!val) {
 336             /* delete entry */
 337             *he_offset_p = old_physical->next;
 338             old_physical->next = ht_physical->free;
 339             ht_physical->free = old;
 340             --ht_physical->count;
 341         }
 342         else {
 343             /* replace entry */
 344             old_physical->val = val;
 345             /* check that the collision rate doesn't become too high */
 346             if (ht_physical->count > ht_physical->max) {
 347                 // It's too high. Try to re-hash into a larger array
 348                 expand_array(rmm, ht);
 349             }
 350         }
 351     }
 352     /* else key not present and val==NULL */
 353     return oldval;
 354 }
 355
 356 APR_DECLARE(unsigned int) rmm_hash_count(apr_rmm_t *rmm, RMM_OFF_T(rmm_hash_t) ht)
 357 {
 358     return APR_RMM_ADDR_GET(rmm_hash_t, rmm, ht)->count;
 359 }
 360
 361 APR_DECLARE(void) rmm_hash_clear(apr_rmm_t *rmm, int free_keys, int free_values, RMM_OFF_T(rmm_hash_t) ht)
 362 {
 363     RMM_OFF_T(rmm_hash_index_t) hi_offset;
 364     for (hi_offset = rmm_hash_first(0, rmm, ht); hi_offset; hi_offset = rmm_hash_next(rmm, hi_offset)) {
 365         rmm_hash_entry_t *this_physical = APR_RMM_ADDR_GET(rmm_hash_entry_t, rmm, APR_RMM_ADDR_GET(rmm_hash_index_t, rmm, hi_offset)->this);
 366         apr_rmm_off_t key = this_physical->key;
 367         apr_rmm_off_t val = this_physical->val;
 368         rmm_hash_set(rmm, ht, this_physical->key, this_physical->klen, RMM_OFF_NULL);
 369         if (free_keys) {
 370                 apr_rmm_free(rmm, key);
 371         }
 372         if (free_values) {
 373                 apr_rmm_free(rmm, val);
 374         }
 375     }
 376 }
 377
 378 /**
 379  * TODO: Migrate from apr_hash (pool-based) structure to rmm_hash (rmm-based) structure
 380  */
 381 #if 0
 382 APR_DECLARE(apr_hash_t*) apr_hash_overlay(apr_pool_t *p,
 383                                           const apr_hash_t *overlay,
 384                                           const apr_hash_t *base)
 385 {
 386     return apr_hash_merge(p, overlay, base, NULL, NULL);
 387 }
 388 #endif
 389
 390 /**
 391  * TODO: Migrate from apr_hash (pool-based) structure to rmm_hash (rmm-based) structure
 392  */
 393 #if 0
 394 APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
 395                                          const apr_hash_t *overlay,
 396                                          const apr_hash_t *base,
 397                                          void * (*merger)(apr_pool_t *p,
 398                                                      const void *key,
 399                                                      apr_ssize_t klen,
 400                                                      const void *h1_val,
 401                                                      const void *h2_val,
 402                                                      const void *data),
 403                                          const void *data)
 404 {
 405     apr_hash_t *res;
 406     apr_hash_entry_t *new_vals = NULL;
 407     apr_hash_entry_t *iter;
 408     apr_hash_entry_t *ent;
 409     unsigned int i,j,k;
 410
 411 #if APR_POOL_DEBUG
 412     /* we don't copy keys and values, so it's necessary that
 413      * overlay->a.pool and base->a.pool have a life span at least
 414      * as long as p
 415      */
 416     if (!apr_pool_is_ancestor(overlay->pool, p)) {
 417         fprintf(stderr,
 418                 "apr_hash_merge: overlay's pool is not an ancestor of p\n");
 419         abort();
 420     }
 421     if (!apr_pool_is_ancestor(base->pool, p)) {
 422         fprintf(stderr,
 423                 "apr_hash_merge: base's pool is not an ancestor of p\n");
 424         abort();
 425     }
 426 #endif
 427
 428     res = apr_palloc(p, sizeof(apr_hash_t));
 429     res->pool = p;
 430     res->free = NULL;
 431     res->hash_func = base->hash_func;
 432     res->count = base->count;
 433     res->max = (overlay->max > base->max) ? overlay->max : base->max;
 434     if (base->count + overlay->count > res->max) {
 435         res->max = res->max * 2 + 1;
 436     }
 437     res->array = alloc_array(res, res->max);
 438     if (base->count + overlay->count) {
 439         new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) *
 440                               (base->count + overlay->count));
 441     }
 442     j = 0;
 443     for (k = 0; k <= base->max; k++) {
 444         for (iter = base->array[k]; iter; iter = iter->next) {
 445             i = iter->hash & res->max;
 446             new_vals[j].klen = iter->klen;
 447             new_vals[j].key = iter->key;
 448             new_vals[j].val = iter->val;
 449             new_vals[j].hash = iter->hash;
 450             new_vals[j].next = res->array[i];
 451             res->array[i] = &new_vals[j];
 452             j++;
 453         }
 454     }
 455
 456     for (k = 0; k <= overlay->max; k++) {
 457         for (iter = overlay->array[k]; iter; iter = iter->next) {
 458             i = iter->hash & res->max;
 459             for (ent = res->array[i]; ent; ent = ent->next) {
 460                 if ((ent->klen == iter->klen) &&
 461                     (memcmp(ent->key, iter->key, iter->klen) == 0)) {
 462                     if (merger) {
 463                         ent->val = (*merger)(p, iter->key, iter->klen,
 464                                              iter->val, ent->val, data);
 465                     }
 466                     else {
 467                         ent->val = iter->val;
 468                     }
 469                     break;
 470                 }
 471             }
 472             if (!ent) {
 473                 new_vals[j].klen = iter->klen;
 474                 new_vals[j].key = iter->key;
 475                 new_vals[j].val = iter->val;
 476                 new_vals[j].hash = iter->hash;
 477                 new_vals[j].next = res->array[i];
 478                 res->array[i] = &new_vals[j];
 479                 res->count++;
 480                 j++;
 481             }
 482         }
 483     }
 484     return res;
 485 }
 486 #endif
 487
 488 /* This is basically the following...
 489  * for every element in hash table {
 490  *    comp elemeny.key, element.value
 491  * }
 492  *
 493  * Like with apr_table_do, the comp callback is called for each and every
 494  * element of the hash table.
 495  */
 496 /**
 497  * TODO: Migrate from apr_hash (pool-based) structure to rmm_hash (rmm-based) structure
 498  */
 499 #if 0
 500 APR_DECLARE(int) apr_hash_do(apr_hash_do_callback_fn_t *comp,
 501                              void *rec, const apr_hash_t *ht)
 502 {
 503     apr_hash_index_t  hix;
 504     apr_hash_index_t *hi;
 505     int rv, dorv  = 1;
 506
 507     hix.ht    = (apr_hash_t *)ht;
 508     hix.index = 0;
 509     hix.this  = NULL;
 510     hix.next  = NULL;
 511
 512     if ((hi = apr_hash_next(&hix))) {
 513         /* Scan the entire table */
 514         do {
 515             rv = (*comp)(rec, hi->this->key, hi->this->klen, hi->this->val);
 516         } while (rv && (hi = apr_hash_next(hi)));
 517
 518         if (rv == 0) {
 519             dorv = 0;
 520         }
 521     }
 522     return dorv;
 523 }
 524 #endif
 525
 526 /**
 527  * TODO: Migrate from apr_hash (pool-based) structure to rmm_hash (rmm-based) structure
 528  */
 529 #if 0
 530 APR_POOL_IMPLEMENT_ACCESSOR(hash)
 531 #endif