*** /dev/null Sat Nov 23 01:02:23 2024
--- - Sat Nov 23 01:02:31 2024
***************
*** 0 ****
--- 1,491 ----
+ /* ====================================================================
+ * Copyright (c) 1999-2000 Ralf S. Engelschall. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY RALF S. ENGELSCHALL ``AS IS'' AND ANY
+ * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RALF S. ENGELSCHALL OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ * ====================================================================
+ */
+
+ /*
+ ** act_hash_lh.c -- Linear Hashing (dynamic)
+ **
+ ** This module implements a Dynamic Hash Table, based on WITOLD LITWIN
+ ** and PER-AKE LARSON's ``Linear Hashing'' algorithm (1980/1988),
+ ** implemented on top of a two-level virtual array with separate
+ ** collision chains as the backend data structure. Some ideas were
+ ** taken over from MIKAEL PETTERSON's Linear Hashing enhancements
+ ** (1993).
+ */
+
+ #include "act_p.h"
+
+ /* fixed size (number of pointers) of the directory and of each segment */
+ #define INITDIRSIZE 256 /* can be an arbitrary value */
+ #define SEGMENTSIZE 512 /* = 2^9, must be a power of 2 */
+
+ /* calculate index in directory and segments from virtual array index */
+ #define DIRINDEX(addr) ((addr) >> 9) /* == ((addr) / SEGMENTSIZE) */
+ #define SEGINDEX(addr) ((addr) & (512-1)) /* == ((addr) % SEGMENTSIZE) */
+
+ /* load of hash table (maximum should be between 2 and 4) */
+ #define MINLOADFCTR 1
+ #define MAXLOADFCTR 2
+
+ /* the per-element structure (keep this as small as possible!) */
+ typedef struct element_st element_t;
+ struct element_st {
+ element_t *e_next; /* pointer to next element in collision chain */
+ unsigned long e_hash; /* cached hash value of element (rehashing optimization) */
+ void *e_keyptr; /* pointer to key (= also pointer to key+data memory chunk) */
+ void *e_datptr; /* pointer to data in key+data memory chunk */
+ void *e_endptr; /* pointer to end of key+data memory chunk */
+ };
+
+ /* on-the-fly calculate lengths of key and data to reduce memory in element_t */
+ #define el_keylen(el) ((char *)((el)->e_datptr)-(char *)((el)->e_keyptr))
+ #define el_datlen(el) ((char *)((el)->e_endptr)-(char *)((el)->e_datptr))
+
+ /* the hash table segments */
+ typedef struct segment_st segment_t;
+ struct segment_st {
+ element_t *s_element[SEGMENTSIZE]; /* array of pointers to elements */
+ };
+
+ /* the top-level hash table structure */
+ typedef struct act_hash_lh_st act_hash_lh_t;
+ struct act_hash_lh_st {
+ act_ctx_t *h_ctx; /* context structure */
+ act_hash_fct_t h_func; /* hash function (copied from context) */
+ unsigned int h_p; /* pointer to start of unsplit region */
+ unsigned int h_pmax; /* pointer to end of unsplit region */
+ int h_slack; /* grow/shrink indicator */
+ unsigned h_dirsize; /* current size of directory */
+ segment_t **h_dir; /* pointer to directory */
+ };
+
+ /* create the hash table structure */
+ static act_hash_lh_t *act_hash_lh_new(act_ctx_t *ctx)
+ {
+ act_hash_lh_t *h;
+
+ /* allocate hash structure */
+ if ((h = (act_hash_lh_t *)act_mem_alloc_ctx(ctx, sizeof(struct act_hash_lh_st))) == NULL)
+ return NULL;
+ h->h_ctx = ctx;
+
+ /* allocate and clear hash table directory */
+ h->h_dirsize = INITDIRSIZE;
+ if ((h->h_dir = (segment_t **)act_mem_alloc_ctx(ctx, h->h_dirsize * sizeof(segment_t *))) == NULL) {
+ errno_safe( act_mem_free_ctx(ctx, h) );
+ return NULL;
+ }
+ act_mem_set(h->h_dir, 0, h->h_dirsize * sizeof(segment_t *));
+
+ /* allocate and clear first segment of hash table array */
+ if ((h->h_dir[0] = (segment_t *)act_mem_alloc_ctx(ctx, sizeof(segment_t))) == NULL) {
+ errno_safe( act_mem_free_ctx(ctx, h->h_dir); act_mem_free_ctx(ctx, h) );
+ return NULL;
+ }
+ act_mem_set(h->h_dir[0], 0, sizeof(segment_t));
+
+ /* initialize hash table control attributes */
+ h->h_p = 0;
+ h->h_pmax = SEGMENTSIZE;
+ h->h_slack = SEGMENTSIZE * MAXLOADFCTR;
+
+ /* inline values from context (for performance reasons only) */
+ if (!act_ctx_get(ctx, ACT_HASH_FUNC, &h->h_func))
+ h->h_func = act_hash_fct(djbx33a);
+
+ return h;
+ }
+
+ /* expand the hash table */
+ static void act_hash_lh_expand(act_ctx_t *ctx, act_hash_lh_t *h)
+ {
+ unsigned int pmax0;
+ unsigned int newaddr;
+ segment_t *seg;
+ element_t **pelold;
+ element_t *el, *headofold, *headofnew, *next;
+ unsigned int n;
+
+ /* calculate next new address */
+ pmax0 = h->h_pmax;
+ newaddr = pmax0 + h->h_p;
+
+ /* have to enlarge directory? */
+ if (h->h_dirsize <= DIRINDEX(newaddr)) {
+ n = h->h_dirsize * sizeof(segment_t *);
+ h->h_dirsize *= 2;
+ if ((h->h_dir = (segment_t **)act_mem_realloc_ctx(ctx,
+ h->h_dir, h->h_dirsize*sizeof(segment_t *))) == NULL)
+ return;
+ act_mem_set((char *)h->h_dir+n, 0, n);
+ }
+
+ /* have to create a new table segment? */
+ if (SEGINDEX(newaddr) == 0) {
+ if ((seg = (segment_t *)act_mem_alloc_ctx(ctx, sizeof(segment_t))) == NULL)
+ return;
+ act_mem_set(seg, 0, sizeof(segment_t));
+ h->h_dir[DIRINDEX(newaddr)] = seg;
+ }
+
+ /* locate P-element */
+ pelold = &h->h_dir[DIRINDEX(h->h_p)]->s_element[SEGINDEX(h->h_p)];
+
+ /* adjust the state variables */
+ if (++(h->h_p) >= h->h_pmax) {
+ h->h_pmax = (h->h_pmax << 1); /* == h->h_pmax * 2 */
+ h->h_p = 0;
+ }
+ h->h_slack += MAXLOADFCTR;
+
+ /* relocate and split between P-element new element */
+ headofold = NULL;
+ headofnew = NULL;
+ for (el = *pelold; el != NULL; el = next) {
+ next = el->e_next;
+ if (el->e_hash & pmax0) {
+ el->e_next = headofnew;
+ headofnew = el;
+ } else {
+ el->e_next = headofold;
+ headofold = el;
+ }
+ }
+ *pelold = headofold;
+ h->h_dir[DIRINDEX(newaddr)]->s_element[SEGINDEX(newaddr)] = headofnew;
+
+ return;
+ }
+
+ /* shrink hash table */
+ static void act_hash_lh_shrink(act_ctx_t *ctx, act_hash_lh_t *h)
+ {
+ segment_t *lastseg;
+ element_t **pel;
+ unsigned int oldlast;
+ unsigned int dirsize;
+ void *dir;
+
+ /* calculate old last element */
+ oldlast = h->h_p + h->h_pmax - 1;
+
+ /* we cannot shrink below one segment */
+ if (oldlast == 0)
+ return;
+
+ /* adjust the state variables */
+ if (h->h_p == 0) {
+ h->h_pmax = (h->h_pmax >> 1); /* == h->h_pmax / 2 */;
+ h->h_p = h->h_pmax - 1;
+ } else
+ h->h_p--;
+ h->h_slack -= MAXLOADFCTR;
+
+ /* relocate the lost old last element to the end of the P-element */
+ pel = &h->h_dir[DIRINDEX(h->h_p)]->s_element[SEGINDEX(h->h_p)];
+ while (*pel != NULL)
+ pel = &((*pel)->e_next);
+ lastseg = h->h_dir[DIRINDEX(oldlast)];
+ *pel = lastseg->s_element[SEGINDEX(oldlast)];
+ lastseg->s_element[SEGINDEX(oldlast)] = NULL;
+
+ /* if possible, deallocate the last segment */
+ if (SEGINDEX(oldlast) == 0) {
+ h->h_dir[DIRINDEX(oldlast)] = NULL;
+ free(lastseg);
+ }
+
+ /* if possible, deallocate the end of the directory */
+ if (h->h_dirsize > INITDIRSIZE && DIRINDEX(oldlast) < h->h_dirsize/2) {
+ dirsize = (h->h_dirsize >> 1); /* == h->h_dirsize / 2 */
+ if ((dir = (segment_t **)act_mem_realloc_ctx(ctx,
+ h->h_dir, dirsize*sizeof(segment_t *))) != NULL) {
+ h->h_dirsize = dirsize;
+ h->h_dir = dir;
+ }
+ }
+ return;
+ }
+
+ /* insert element into hash table */
+ static int act_hash_lh_insert(act_ctx_t *ctx, act_hash_lh_t *h, void *keyptr, int keylen,
+ void *datptr, int datlen, int override)
+ {
+ unsigned int hash, addr;
+ element_t *el, **pel;
+ int bFound;
+ void *vp;
+
+ /* argument consistency check */
+ if (h == NULL || keyptr == NULL || keylen <= 0)
+ return_errno(FALSE, EINVAL);
+
+ /* calculate hash address */
+ hash = h->h_func(keyptr, keylen);
+ addr = hash % h->h_pmax; /* unsplit region */
+ if (addr < h->h_p)
+ addr = hash % (h->h_pmax << 1); /* split region */
+
+ /* locate hash element's collision list */
+ pel = &h->h_dir[DIRINDEX(addr)]->s_element[SEGINDEX(addr)];
+
+ /* check whether element is already in the hash table */
+ bFound = FALSE;
+ for (el = *pel; el != NULL; el = el->e_next) {
+ if ( el->e_hash == hash
+ && el_keylen(el) == keylen
+ && act_mem_cmp(el->e_keyptr, keyptr, el_keylen(el)) == 0) {
+ bFound = TRUE;
+ break;
+ }
+ }
+
+ /* only override on request */
+ if (bFound && !override)
+ return FALSE;
+
+ /* create a duplicate of key and data */
+ if ((vp = act_mem_alloc_ctx(ctx, keylen+datlen)) == NULL)
+ return FALSE;
+ act_mem_move(vp, keyptr, keylen);
+ act_mem_move((char *)vp+keylen, datptr, datlen);
+ keyptr = vp;
+ datptr = (char *)vp+keylen;
+
+ if (bFound) {
+ /* reuse existing element by freeing old contents */
+ if (el->e_keyptr != NULL)
+ act_mem_free_ctx(ctx, el->e_keyptr);
+ }
+ else {
+ /* allocate new element and chain into list */
+ if ((el = (element_t *)act_mem_alloc_ctx(ctx, sizeof(element_t))) == 0) {
+ act_mem_free_ctx(ctx, vp);
+ return FALSE;
+ }
+ while (*pel != NULL)
+ pel = &((*pel)->e_next);
+ el->e_next = *pel;
+ *pel = el;
+ }
+
+ /* insert contents into element structure */
+ el->e_keyptr = keyptr;
+ el->e_datptr = datptr;
+ el->e_endptr = (char *)datptr+datlen;
+ el->e_hash = hash;
+
+ /* do we need to expand the table now? */
+ if (--(h->h_slack) < 0)
+ act_hash_lh_expand(ctx, h);
+
+ return TRUE;
+ }
+
+ /* lookup an element in hash table */
+ static int act_hash_lh_lookup(act_ctx_t *ctx, act_hash_lh_t *h,
+ void *keyptr, int keylen, void **datptr, int *datlen)
+ {
+ unsigned int hash, addr;
+ element_t *el, **pel;
+
+ /* argument consistency check */
+ if (h == NULL || keyptr == NULL || keylen <= 0)
+ return_errno(FALSE, EINVAL);
+
+ /* calculate hash address */
+ hash = h->h_func(keyptr, keylen);
+ addr = hash % h->h_pmax; /* unsplit region */
+ if (addr < h->h_p)
+ addr = hash % (h->h_pmax << 1); /* split region */
+
+ /* locate hash element collision list */
+ pel = &h->h_dir[DIRINDEX(addr)]->s_element[SEGINDEX(addr)];
+
+ /* search for element in collision list */
+ for (el = *pel; el != NULL; el = el->e_next) {
+ if ( el->e_hash == hash
+ && el_keylen(el) == keylen
+ && act_mem_cmp(el->e_keyptr, keyptr, el_keylen(el)) == 0) {
+ /* provide results */
+ if (datptr != NULL)
+ *datptr = el->e_datptr;
+ if (datlen != NULL)
+ *datlen = el_datlen(el);
+ return TRUE;
+ }
+ }
+ return FALSE;
+ }
+
+ /* delete an element in hash table */
+ static int act_hash_lh_delete(act_ctx_t *ctx, act_hash_lh_t *h, void *keyptr, int keylen)
+ {
+ unsigned int hash, addr;
+ element_t *el, *lel, **pel;
+ int rv;
+
+ /* argument consistency check */
+ if (h == NULL || keyptr == NULL || keylen <= 0)
+ return_errno(FALSE, EINVAL);
+
+ /* calculate hash address */
+ hash = h->h_func(keyptr, keylen);
+ addr = hash % h->h_pmax; /* unsplit region */
+ if (addr < h->h_p)
+ addr = hash % (h->h_pmax << 1); /* split region */
+
+ /* locate hash element collision chain */
+ pel = &h->h_dir[DIRINDEX(addr)]->s_element[SEGINDEX(addr)];
+
+ /* search for element in collision chain */
+ rv = FALSE;
+ for (lel = NULL, el = *pel; el != NULL; lel = el, el = el->e_next) {
+ if ( el->e_hash == hash
+ && el_keylen(el) == keylen
+ && act_mem_cmp(el->e_keyptr, keyptr, el_keylen(el)) == 0) {
+ /* free key+data memory chunk */
+ if (el->e_keyptr != NULL)
+ act_mem_free_ctx(ctx, el->e_keyptr);
+ /* remove element from collision chain */
+ if (lel == NULL)
+ *pel = el->e_next;
+ else
+ lel->e_next = el->e_next;
+ /* deallocate element structure */
+ act_mem_free_ctx(ctx, el);
+ rv = TRUE;
+ break;
+ }
+ }
+
+ /* do we need to shrink the table now? */
+ if (++(h->h_slack) > ((h->h_pmax + h->h_p) * (MAXLOADFCTR-MINLOADFCTR)))
+ act_hash_lh_shrink(ctx, h);
+
+ return rv;
+ }
+
+ /* calculate total size of hash table */
+ static int act_hash_lh_size(act_ctx_t *ctx, act_hash_lh_t *h, long *pbytes, long *pelements)
+ {
+ long bytes, elements;
+ int i, j;
+ element_t *el;
+
+ /* argument consistency check */
+ if (h == NULL)
+ return_errno(FALSE, EINVAL);
+
+ /* start with 0 bytes and elements */
+ bytes = 0;
+ elements = 0;
+
+ /* add bytes for top-level structure and directory */
+ bytes += sizeof(struct act_hash_lh_st);
+ bytes += h->h_dirsize * sizeof(segment_t *);
+
+ /* add size for segments */
+ for (i = 0; i < h->h_dirsize; i++) {
+ if (h->h_dir[i] == NULL)
+ continue;
+ bytes += sizeof(segment_t);
+ /* add size of elements */
+ for (j = 0; j < SEGMENTSIZE; j++) {
+ if (h->h_dir[i]->s_element[j] == NULL)
+ continue;
+ el = h->h_dir[i]->s_element[j];
+ for (; el != NULL; el = el->e_next) {
+ elements++;
+ /* add size of key+data */
+ bytes += sizeof(element_t);
+ bytes += el_keylen(el);
+ bytes += el_datlen(el);
+ }
+ }
+ }
+
+ /* provide results */
+ if (pbytes != NULL)
+ *pbytes = bytes;
+ if (pelements != NULL)
+ *pelements = elements;
+
+ return TRUE;
+ }
+
+ /* destroy the whole hash table */
+ static int act_hash_lh_free(act_ctx_t *ctx, act_hash_lh_t *h)
+ {
+ element_t *el, **pel;
+ unsigned int i, j;
+
+ /* argument consistency check */
+ if (h == NULL)
+ return_errno(FALSE, EINVAL);
+
+ /* deallocate all segment's entries */
+ for (i = 0; i < h->h_dirsize; i++) {
+ if (h->h_dir[i] == NULL)
+ continue;
+ /* deallocate all collision chains */
+ for (j = 0; j < SEGMENTSIZE; j++) {
+ if (h->h_dir[i]->s_element[j] == NULL)
+ continue;
+ /* deallocate all elements in collision chain */
+ pel = &h->h_dir[i]->s_element[j];
+ for (el = *pel; el != NULL; el = el->e_next) {
+ /* deallocate key+data memory chunk */
+ if (el->e_keyptr != NULL)
+ act_mem_free_ctx(ctx, el->e_keyptr);
+ }
+ }
+ act_mem_free_ctx(ctx, h->h_dir[i]);
+ }
+
+ /* deallocate hash table directory */
+ act_mem_free_ctx(ctx, h->h_dir);
+
+ /* deallocate hash table top-level structure */
+ act_mem_free_ctx(ctx, h);
+
+ return TRUE;
+ }
+
+ /* the ACT dispatch structure for the hashing API */
+ intern act_hash_method_t act_hash_lh = {
+ ACT_HASH_METHOD_TAG,
+ (act_hash_new_t) act_hash_lh_new,
+ (act_hash_insert_t) act_hash_lh_insert,
+ (act_hash_lookup_t) act_hash_lh_lookup,
+ (act_hash_delete_t) act_hash_lh_delete,
+ (act_hash_size_t) act_hash_lh_size,
+ (act_hash_free_t) act_hash_lh_free
+ };
+
|
