OSSP CVS Repository

ossp - Check-in [1548]
Not logged in
[Honeypot]  [Browse]  [Home]  [Login]  [Reports
[Search]  [Ticket]  [Timeline
  [Patchset]  [Tagging/Branching

Check-in Number: 1548
Date: 2002-Jan-14 15:49:07 (local)
2002-Jan-14 14:49:07 (UTC)
User:thl
Branch:
Comment: include a stripped down version of OSSP act's linae hashing library
Tickets:
Inspections:
Files:
ossp-pkg/lmtp2nntp/Makefile.in      1.36 -> 1.37     3 inserted, 3 deleted
ossp-pkg/lmtp2nntp/lmtp2nntp_lh.c      added-> 1.1
ossp-pkg/lmtp2nntp/lmtp2nntp_lh.h      added-> 1.1

ossp-pkg/lmtp2nntp/Makefile.in 1.36 -> 1.37

--- Makefile.in  2002/01/10 10:37:38     1.36
+++ Makefile.in  2002/01/14 14:49:07     1.37
@@ -44,9 +44,9 @@
 POD2MAN     = pod2man
 
 PROG = lmtp2nntp
-HDRS = lmtp2nntp_global.h lmtp2nntp_daemon.h lmtp2nntp_lmtp.h lmtp2nntp_nntp.h lmtp2nntp_argz.h lmtp2nntp_shpat.h lmtp2nntp_msg.h lmtp2nntp_popt.h lmtp2nntp_config.h
-SRCS = lmtp2nntp_main.c   lmtp2nntp_daemon.c lmtp2nntp_lmtp.c lmtp2nntp_nntp.c lmtp2nntp_argz.c lmtp2nntp_shpat.c lmtp2nntp_msg.c lmtp2nntp_popt.c lmtp2nntp_config.c lmtp2nntp_version.c 
-OBJS = lmtp2nntp_main.o   lmtp2nntp_daemon.o lmtp2nntp_lmtp.o lmtp2nntp_nntp.o lmtp2nntp_argz.o lmtp2nntp_shpat.o lmtp2nntp_msg.o lmtp2nntp_popt.o lmtp2nntp_config.o lmtp2nntp_version.o
+HDRS = lmtp2nntp_global.h lmtp2nntp_daemon.h lmtp2nntp_lmtp.h lmtp2nntp_nntp.h lmtp2nntp_argz.h lmtp2nntp_shpat.h lmtp2nntp_msg.h lmtp2nntp_popt.h lmtp2nntp_config.h lmtp2nntp_lh.h
+SRCS = lmtp2nntp_main.c   lmtp2nntp_daemon.c lmtp2nntp_lmtp.c lmtp2nntp_nntp.c lmtp2nntp_argz.c lmtp2nntp_shpat.c lmtp2nntp_msg.c lmtp2nntp_popt.c lmtp2nntp_config.c lmtp2nntp_lh.c lmtp2nntp_version.c 
+OBJS = lmtp2nntp_main.o   lmtp2nntp_daemon.o lmtp2nntp_lmtp.o lmtp2nntp_nntp.o lmtp2nntp_argz.o lmtp2nntp_shpat.o lmtp2nntp_msg.o lmtp2nntp_popt.o lmtp2nntp_config.o lmtp2nntp_lh.o lmtp2nntp_version.o
 
 SUBDIRS = @SUBDIR_STR@ @SUBDIR_L2@ @SUBDIR_SA@ @SUBDIR_VAR@
 


ossp-pkg/lmtp2nntp/lmtp2nntp_lh.c -> 1.1

*** /dev/null    Mon Oct  3 22:33:00 2022
--- -    Mon Oct  3 22:35:06 2022
***************
*** 0 ****
--- 1,553 ----
+ 
+ /* 
+ **  Act - Abstract Container Type Library
+ **  Copyright (c) 1999-2002 Ralf S. Engelschall <rse@engelschall.com>
+ **
+ **  This file is part of Act, a library for dealing with Abstract 
+ **  Container Types which can be found at http://www.ossp.org/pkg/act/.
+ **
+ **  Permission to use, copy, modify, and distribute this software for
+ **  any purpose with or without fee is hereby granted, provided that
+ **  the above copyright notice and this permission notice appear in all
+ **  copies.
+ **
+ **  THIS SOFTWARE IS PROVIDED ``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 THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
+ **  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.
+ */
+ 
+ /*
+ **  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).
+ **   
+ **  Linear Hashing can be summarized as following:
+ **
+ **  o drawback of classical hashing is that the hash table is of
+ **    fixed size; if table is filled, the table has to be expanded;
+ **    unfortunately this requires re-hashing of all existing elements.
+ **
+ **  o Extendible Hashing solves this problem by allowing the table
+ **    to grow without complete re-hashing of elements every time;
+ **    unfortunately the table must double in size to grow - not a
+ **    problem for small tables, but a disadvantage for large ones.
+ **
+ **  o Linear Hashing allows the table to grow one bucket at a time:
+ **    table is extended when its load factor passes a critical value; buckets
+ **    are split "in sequence" starting at index 0 and ending at 2^n; two
+ **    hashing functions are always "active" - one for split buckets and one
+ **    for unsplit; when last bucket (the 2^n-th one) is split, the table has
+ **    been doubled in size, and a new cycle of splitting begins starting at
+ **    bucket 0.
+ **
+ **  The internal structure of the linear hashing table is illustrated
+ **  in the following figure:
+ **
+ **  -----BEGIN EMBEDDED OBJECT-----
+ **  Content-type: application/fig
+ **  Description: linear hashing structure layout
+ **  Version: eo/1.0
+ **  H4sIACfenzkCA62WTYvbMBCGz+tfIeixJOhb9rnQsrC3XntxE7ExdZ0ldhf233dG
+ **  sr6aNllRE2K90USPpNGMRx8+P34hYs+bp346zof+xTaf7LTYS/M4HU52bp7sAr8I
+ **  aRile0qbr8P0PNpmxxvGKSW84QQ/jOwYMURRQlFx+CtK9wMb1TwQBlYB3R1NLX6x
+ **  P7TQX0OkK5IbmguNNGdLagXDT/jyzoM5PCLYRC6HzRIJ/+BKZYIJVGhLCoyVXNhm
+ **  4EXFJV15SaG1Eu1Z5UPIsNSk0FDhZt6Gxaq4Aa86JDprUn8su725bIFdTOM68fgz
+ **  1foTLZRWNWgd0UYVqo0xklQVWvKAlkIVCoHemlQduo3oThXKAVtaKI9mKxqOLJwj
+ **  zc8RbbJ5QMGgn2i0EshfTGjIIskV8Y4xmfDRmUXizWnMvVm06/KZHloMSPcakVvs
+ **  gwvYh49vE9PJxCCgmzlMUHSPgdmEKJVWZTz970Q64rtSubDgm00kecBLVSo30VWs
+ **  7djNmfi7fIeK822oyVF6O2rmFb4htY3UNlHD60HQe+9LlzVGpdasRTC01yWJ/RsY
+ **  0m896SBczXS2pGR90XA56EpFplp1/WC0zgnU+c2XikyZUCoyVedfHdFGFSpeLDJV
+ **  hXbp6oCuVGTKhFKRqTp0G9GdKpQJpSJTIYx9KKdjZLU1I5bQKGR5Ldpgji6go/BX
+ **  m3iNkd4L+GAaotU7CMDuPqkZ5BoDjovg43Cxh+V8eftGKbseyfbK0DaM1OFWgzey
+ **  2T7/hHvx/PeB5ZTS1U6fOMv5ZTfaVzveGwgn28FAoXCtuPHDeRyHeThP5HDqh+k9
+ **  E7P19efi/od9+3jsl/4dEzNm0O04EkP9dbgsv/qRnPr5RJb++2gd4zf8ksj2KwwA
+ **  AA==
+ **  -----END EMBEDDED OBJECT-----
+ **
+ **  As you can see, it consists of four classes of memory chunks:
+ **  1. a top-level structure which acts as the primary handle
+ **  2. the virtual hash table consisting of a single (growing) 
+ **     directory and one or more (fixed size) directory segments
+ **  3. the collision chains consisting of element structures
+ **  4. the actual elements consisting of key+value structures
+ */
+ 
+ #include <stdlib.h>
+ #include <string.h>
+ 
+ #ifndef FALSE
+ #define FALSE 0
+ #endif
+ #ifndef TRUE
+ #define TRUE !FALSE
+ #endif
+ 
+ #include "lmtp2nntp_lh.h"
+ 
+ /* fixed size (number of pointers) of the directory and of each segment */
+ #define INITDIRSIZE  256 /* can be an arbitrary value */
+ #define SEGMENTSIZE  512 /* has to be a power of 2 for below arithmetic */
+ 
+ /* the borders for the hash table load */
+ #define MINLOADFCTR  1   /* should be between 0 and 1 */
+ #define MAXLOADFCTR  2   /* should be between 2 and 4 */
+ 
+ /* the per-element structure (keep 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 */
+ };
+ 
+ /* 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 */
+ struct lh_st {
+     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 */
+ };
+ 
+ /* on-the-fly calculate index into directory and segment from virtual array index */
+ #define DIRINDEX(addr) (int)((addr) / SEGMENTSIZE)
+ #define SEGINDEX(addr) (int)((addr) % SEGMENTSIZE)
+ 
+ /* 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))
+ 
+ /*
+  * BJDDJ Hash Function (Bob Jenkins, Dr. Dobbs Journal):
+  * This is a very complex but also very good hash function, as proposed
+  * in the March'97 issue of Dr. Dobbs Journal (DDJ) by Bob Jenkins (see
+  * http://burtleburtle.net/bob/hash/doobs.html for online version). He
+  * showed that this hash function has both very good distribution and
+  * performance and our own hash function comparison confirmed this. The
+  * only difference to the original function of B.J. here is that our
+  * version doesn't provide the `level' (= previous hash) argument for
+  * consistency reasons with the other hash functions (i.e. same function
+  * signature). It can be definetely recommended as a good general
+  * purpuse hash function.
+  */
+ static long 
+ lh_hash(
+     register unsigned char *k,
+     register size_t length)
+ {
+     register long a,b,c,len;
+ 
+     /* some abbreviations */
+ #define ub4 long
+ #define mix(a,b,c) { \
+         a -= b; a -= c; a ^= (c>>13); \
+         b -= c; b -= a; b ^= (a<< 8); \
+         c -= a; c -= b; c ^= (b>>13); \
+         a -= b; a -= c; a ^= (c>>12); \
+         b -= c; b -= a; b ^= (a<<16); \
+         c -= a; c -= b; c ^= (b>> 5); \
+         a -= b; a -= c; a ^= (c>> 3); \
+         b -= c; b -= a; b ^= (a<<10); \
+         c -= a; c -= b; c ^= (b>>15); \
+     }
+ 
+     /* setup the internal state */
+     len = length;
+     a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
+     c = 0;
+ 
+     /* handle most of the key */
+     while (len >= 12) {
+         a += (k[0] +((ub4)k[1]<<8) +((ub4)k[ 2]<<16) +((ub4)k[ 3]<<24));
+         b += (k[4] +((ub4)k[5]<<8) +((ub4)k[ 6]<<16) +((ub4)k[ 7]<<24));
+         c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16) +((ub4)k[11]<<24));
+         mix(a,b,c);
+         k += 12; len -= 12;
+     }
+ 
+     /* handle the last 11 bytes */
+     c += length;
+     switch(len) { 
+         /* all the case statements fall through */
+         case 11: c+=((ub4)k[10]<<24);
+         case 10: c+=((ub4)k[ 9]<<16);
+         case 9 : c+=((ub4)k[ 8]<< 8);
+         /* the first byte of c is reserved for the length */
+         case 8 : b+=((ub4)k[ 7]<<24);
+         case 7 : b+=((ub4)k[ 6]<<16);
+         case 6 : b+=((ub4)k[ 5]<< 8);
+         case 5 : b+=k[4];
+         case 4 : a+=((ub4)k[ 3]<<24);
+         case 3 : a+=((ub4)k[ 2]<<16);
+         case 2 : a+=((ub4)k[ 1]<< 8);
+         case 1 : a+=k[0];
+         /* case 0: nothing left to add */
+     }
+     mix(a,b,c);
+ 
+ #undef ub4
+ #undef mix
+ 
+     /* report the result */
+     return c;
+ }
+ 
+ /* create the hash table structure */
+ lh_t *lh_new(void)
+ {
+     lh_t *h;
+ 
+     /* allocate hash structure */
+     if ((h = (lh_t *)malloc(sizeof(lh_t))) == NULL)
+         return NULL;
+ 
+     /* allocate and clear hash table directory */
+     h->h_dirsize = INITDIRSIZE;
+     if ((h->h_dir = (segment_t **)malloc(h->h_dirsize * sizeof(segment_t *))) == NULL) {
+         free(h);
+         return NULL;
+     }
+     memset(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 *)malloc(sizeof(segment_t))) == NULL) {
+         free(h->h_dir); 
+         free(h);
+         return NULL;
+     }
+     memset(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;
+ 
+     return h;
+ }
+ 
+ /* expand the hash table */
+ static void lh_expand(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 **)realloc(
+                          h->h_dir, h->h_dirsize*sizeof(segment_t *))) == NULL)
+              return;
+         memset((char *)h->h_dir+n, 0, n);
+     }
+     
+     /* have to create a new table segment? */
+     if (SEGINDEX(newaddr) == 0) {
+         if ((seg = (segment_t *)malloc(sizeof(segment_t))) == NULL)
+             return;
+         memset(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 lh_shrink(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 **)realloc(
+                    h->h_dir, dirsize*sizeof(segment_t *))) != NULL) {
+             h->h_dirsize = dirsize;
+             h->h_dir = dir;
+         }
+     }
+     return;
+ }
+ 
+ /* insert element into hash table */
+ int lh_insert(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 FALSE;
+ 
+     /* calculate hash address */
+     hash = lh_hash(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
+             && memcmp(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 = malloc(keylen+datlen)) == NULL)
+         return FALSE;
+     memmove(vp, keyptr, keylen);
+     memmove((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)
+             free(el->e_keyptr);
+     }
+     else {
+         /* allocate new element and chain into list */
+         if ((el = (element_t *)malloc(sizeof(element_t))) == 0) {
+             free(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)
+         lh_expand(h);
+ 
+     return TRUE;
+ }
+ 
+ /* lookup an element in hash table */
+ int lh_lookup(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 FALSE;
+ 
+     /* calculate hash address */
+     hash = lh_hash(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
+             && memcmp(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 */
+ int lh_delete(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 FALSE;
+ 
+     /* calculate hash address */
+     hash = lh_hash(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
+             && memcmp(el->e_keyptr, keyptr, el_keylen(el)) == 0) {
+             /* free key+data memory chunk */
+             if (el->e_keyptr != NULL)
+                 free(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 */
+             free(el);
+             rv = TRUE;
+             break;
+         }
+     }
+ 
+     /* do we need to shrink the table now? */
+     if (++(h->h_slack) > ((h->h_pmax + h->h_p) * (MAXLOADFCTR-MINLOADFCTR)))
+         lh_shrink(h);
+ 
+     return rv;
+ }
+ 
+ /* destroy the whole hash table */
+ int lh_free(lh_t *h)
+ {
+     element_t *el, **pel;
+     unsigned int i, j;
+ 
+     /* argument consistency check */
+     if (h == NULL)
+         return FALSE;
+ 
+     /* 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)
+                     free(el->e_keyptr);
+             }
+         }
+         free(h->h_dir[i]);
+     }
+ 
+     /* deallocate hash table directory */
+     free(h->h_dir);
+ 
+     /* deallocate hash table top-level structure */
+     free(h);
+ 
+     return TRUE;
+ }
+ 


ossp-pkg/lmtp2nntp/lmtp2nntp_lh.h -> 1.1

*** /dev/null    Mon Oct  3 22:33:00 2022
--- -    Mon Oct  3 22:35:06 2022
***************
*** 0 ****
--- 1,40 ----
+ /* 
+ **  Act - Abstract Container Type Library
+ **  Copyright (c) 1999-2002 Ralf S. Engelschall <rse@engelschall.com>
+ **
+ **  This file is part of Act, a library for dealing with Abstract 
+ **  Container Types which can be found at http://www.ossp.org/pkg/act/.
+ **
+ **  Permission to use, copy, modify, and distribute this software for
+ **  any purpose with or without fee is hereby granted, provided that
+ **  the above copyright notice and this permission notice appear in all
+ **  copies.
+ **
+ **  THIS SOFTWARE IS PROVIDED ``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 THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
+ **  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.
+ */
+ 
+ #ifndef __LH_H__
+ #define __LH_H__
+ 
+ struct lh_st;
+ typedef struct lh_st lh_t;
+ 
+ lh_t *lh_new   (void);
+ int   lh_insert(lh_t *h, void *keyptr, int keylen, void  *datptr, int  datlen, int override);
+ int   lh_lookup(lh_t *h, void *keyptr, int keylen, void **datptr, int *datlen);
+ int   lh_delete(lh_t *h, void *keyptr, int keylen);
+ int   lh_free  (lh_t *h);
+ 
+ #endif /* __LH_H__ */
+ 

CVSTrac 2.0.1