Limitations:
* doesn't have a freelist, so deletes aren't reclaimed
* and can't expand it's size (dont know how to implement this with current shared memory system)
* no locking (yet)
It is intended for use in modules having a large config requirements
(Patches inline, extra files attached)
It is intented that apr_shm_hash.c will live in apr/tables apr_shm_hash.h in apr/include & testhash.c in apr/test
Index: tables/Makefile.in =================================================================== RCS file: /home/cvspublic/apr/tables/Makefile.in,v retrieving revision 1.6 diff -u -u -r1.6 Makefile.in --- tables/Makefile.in 2001/01/09 11:06:18 1.6 +++ tables/Makefile.in 2001/07/05 03:53:02 @@ -1,5 +1,5 @@
-TARGETS = apr_tables.lo apr_hash.lo +TARGETS = apr_tables.lo apr_hash.lo apr_shm_hash.lo
# bring in rules.mk for standard functionality
@INCLUDE_RULES@
Index: test/Makefile.in
===================================================================
RCS file: /home/cvspublic/apr/test/Makefile.in,v
retrieving revision 1.57
diff -u -u -r1.57 Makefile.in
--- test/Makefile.in 2001/06/15 20:04:39 1.57
+++ test/Makefile.in 2001/07/05 03:53:02
@@ -25,7 +25,8 @@
[EMAIL PROTECTED]@ \
[EMAIL PROTECTED]@ \
[EMAIL PROTECTED]@ \
- [EMAIL PROTECTED]@
+ [EMAIL PROTECTED]@ \
+ [EMAIL PROTECTED]@TARGETS = $(PROGRAMS)
@@ -125,5 +126,8 @@
[EMAIL PROTECTED]@: teststr.lo $(LOCAL_LIBS)
$(LINK) teststr.lo $(LOCAL_LIBS) $(ALL_LIBS)
+
[EMAIL PROTECTED]@: testhash.lo $(LOCAL_LIBS)
+ $(LINK) testhash.lo $(LOCAL_LIBS) $(ALL_LIBS)# DO NOT REMOVE
/* */ #include "apr.h" #include "apr_strings.h" #include "apr_general.h" #include "apr_pools.h" #include "apr_shm_hash.h" #if APR_HAVE_STDIO_H #include <stdio.h> #endif #if APR_HAVE_STDLIB_H #include <stdlib.h> #endif #if APR_HAVE_STRING_H #include <string.h> #endif
int main(int argc, const char *const argv[])
{
apr_pool_t*cntxt;
apr_shm_hash_t *h;
apr_shm_hash_t *h2;
apr_shm_hash_index_t *hi;
char* val;
char* key;
int i;
int j;
int *k;
int *l;
int sumKeys,sumVal;
int trySumKey,trySumVal;
/* table defaults */
apr_initialize();
atexit(apr_terminate);
apr_pool_create(&cntxt, NULL);
h =apr_shm_hash_make(cntxt,"TEST_SHM_HASH", 10,10*sizeof(char),
100*sizeof(char),15);
if ( h == NULL ) {
fprintf(stderr, "ERROR: can not allocate HASH!\n");
exit(-1);
}
apr_shm_hash_set(h,"OVERWRITE",APR_SHM_HASH_KEY_STRING, "should not see
this");
apr_shm_hash_set(h,"FOO3",APR_SHM_HASH_KEY_STRING, "bar3");
apr_shm_hash_set(h,"FOO3",APR_SHM_HASH_KEY_STRING, "bar3");
apr_shm_hash_set(h,"FOO1",APR_SHM_HASH_KEY_STRING, "bar1");
apr_shm_hash_set(h,"FOO2",APR_SHM_HASH_KEY_STRING, "bar2");
apr_shm_hash_set(h,"FOO4",APR_SHM_HASH_KEY_STRING, "bar4");
apr_shm_hash_set(h,"SAME1",APR_SHM_HASH_KEY_STRING, "same");
apr_shm_hash_set(h,"SAME2",APR_SHM_HASH_KEY_STRING, "same");
apr_shm_hash_set(h,"OVERWRITE",APR_SHM_HASH_KEY_STRING, "Overwrite
key");
fprintf(stdout,"apr_shm_hash_get FOO2 = %s (should be bar2)\n",
apr_shm_hash_get(h,"FOO2", APR_SHM_HASH_KEY_STRING));
fprintf(stdout,"apr_shm_hash_get SAME2 = %s (should be same)\n",
apr_shm_hash_get(h,"SAME2", APR_SHM_HASH_KEY_STRING));
fprintf(stdout,"apr_shm_hash_get OVERWRITE = %s (should be 'Overwrite
key')\n",
apr_shm_hash_get(h,"OVERWRITE",
APR_SHM_HASH_KEY_STRING));
fprintf(stdout,"apr_shm_hash_get NOTTHERE = %s (should be NULL)\n",
apr_shm_hash_get(h,"NOTTHERE",
APR_SHM_HASH_KEY_STRING));
fprintf(stdout,"apr_shm_hash_get FOO3 = %s (should be bar3)\n",
apr_shm_hash_get(h,"FOO3", APR_SHM_HASH_KEY_STRING));
for (hi = apr_shm_hash_first(h); hi; hi = apr_shm_hash_next(hi)) {
apr_shm_hash_this(hi,(void*) &key, NULL,(void*) &val);
fprintf(stdout, "Key %s Value %s\n",key,val);
}
h2 =apr_shm_hash_make(cntxt,"TEST_SHM_HASH2", 100,sizeof(int),
sizeof(int),15);
if ( h2 == NULL ) {
fprintf(stderr, "ERROR: can not allocate HASH!\n");
exit(-1);
}
sumKeys=0;
sumVal=0;
trySumKey=0;
trySumVal=0;
for (i=0;i<100;i++) {
j=i*10+1;
sumKeys+=j;
sumVal+=i;
apr_shm_hash_set(h2,&j,sizeof(int), &i);
}
i=0;
for (hi = apr_shm_hash_first(h2); hi; hi = apr_shm_hash_next(hi)) {
int*k;
int *l;
apr_shm_hash_this(hi,(void*) &k, NULL,(void*) &l);
trySumKey +=*k;
trySumVal +=*l;
i++;
}
if (i==100) {
fprintf(stdout,"All keys accounted for\n");
} else {
fprintf(stderr,"ERROR: Only got %d (out of 100)\n",i);
}
if ( trySumVal != sumVal ) {
fprintf(stderr,"ERROR:Values don't add up Got %d expected
%d\n",trySumVal ,sumVal);
}
if ( trySumKey != sumKeys ) {
fprintf(stderr,"ERROR:Keys don't add up Got %d expected
%d\n",trySumKey,sumKeys);
}
j=891;
trySumKey =891;
trySumVal=89;
apr_shm_hash_set(h2, &j,sizeof(int),NULL);
k= apr_shm_hash_get(h2, &j,sizeof(int));
if (k!=NULL ) {
fprintf(stderr,"ERRROR: Delete not working\n");
} else {
fprintf(stdout,"Delete working\n");
}
i=0;
for (hi = apr_shm_hash_first(h2); hi; hi = apr_shm_hash_next(hi)) {
apr_shm_hash_this(hi,(void*) &k, NULL,(void*) &l);
trySumKey +=*k;
trySumVal+=*l;
i++;
}
if ( i==99) {
fprintf(stdout,"All keys accounted for.. Delete OK\n");
} else {
fprintf(stderr,"Only got %d (out of 99) Delete Not OK\n",i);
}
if ( trySumVal != sumVal ) {
fprintf(stderr,"ERROR:Values don't add up Got %d expected
%d\n",trySumVal ,sumVal);
}
if ( trySumKey != sumKeys ) {
fprintf(stderr,"ERROR:Keys don't add up Got %d expected
%d\n",trySumKey,sumKeys);
}
if ( fork() ==0 ) {
/* Try Child */
i=0;
trySumKey =891;
trySumVal=89;
for (hi = apr_shm_hash_first(h2); hi; hi = apr_shm_hash_next(hi)) {
apr_shm_hash_this(hi,(void*) &k, NULL,(void*) &l);
trySumKey +=*k;
trySumVal+=*l;
i++;
}
if ( i==99) {
fprintf(stdout,"All keys accounted for.. Delete OK (child)\n");
} else {
fprintf(stderr,"Only got %d (out of 99) Delete Not OK (child)\n",i);
}
if ( trySumVal != sumVal ) {
fprintf(stderr,"ERROR:Values don't add up Got %d expected %d
(child)\n",trySumVal ,sumVal);
}
if ( trySumKey != sumKeys ) {
fprintf(stderr,"ERROR:Keys don't add up Got %d expected %d
(child)\n",trySumKey,sumKeys);
}
fprintf(stdout,"apr_shm_hash_get FOO3 = %s (should be bar3) (child)\n",
apr_shm_hash_get(h,"FOO3", APR_SHM_HASH_KEY_STRING));
}
return 0;
}
/* ==================================================================== * The Apache Software License, Version 1.1 * * Copyright (c) 2000-2001 The Apache Software Foundation. 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. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation" must * not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache", * nor may "Apache" appear in their name, without prior written * permission of the Apache Software Foundation. * * 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 APACHE SOFTWARE FOUNDATION 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. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. * * Portions of this software are based upon public domain software * originally written at the National Center for Supercomputing Applications, * University of Illinois, Urbana-Champaign. */ #include "apr_private.h" #include "apr_general.h" #include "apr_pools.h" #include "apr_shmem.h" #include "apr_shm_hash.h" #if APR_HAVE_STDIO_H #include <stdio.h> #endif #if APR_HAVE_STDLIB_H #include <stdlib.h> #endif #if APR_HAVE_STRING_H #include <string.h> #endif /* * The internal form of a hash table. * * The table is an array indexed by the hash of the key; collisions * are resolved by hanging a linked list of hash entries off each * element of the array. Although this is a really simple design it * isn't too bad given that pools have a low allocation overhead. */ typedef struct apr_shm_hash_entry_t apr_shm_hash_entry_t; struct apr_shm_hash_entry_t { int next; /* pointer into the bucket */ int hash; int posn; /* index into key / value */ int arrayPosn; /* index to which array position */ apr_ssize_t klen; }; typedef struct apr_shm_hash_entry_hdr_t apr_shm_hash_entry_hdr_t; struct apr_shm_hash_entry_hdr_t { int count; /* # of entries in this chain of buckets*/ int list; /* pointer into the bucket */ }; /* * info which needs to be shared */ typedef struct apr_shm_hash_hdr_t apr_shm_hash_hdr_t; #define APR_SHM_HASH_NAME_MAX 100 struct apr_shm_hash_hdr_t { /*int bUseLock; * FUTURE: For Locking */ /*int freelist; * FUTURE: To enable deleting */ /*int ref; * FUTURE: To enable refcounting/releasing of hash */ int count; int max; int hashSize; char szName[APR_SHM_HASH_NAME_MAX]; apr_size_t keySize; apr_size_t elemSize; }; /* * The size of the array is always a power of two. We use the maximum * index rather than the size so that we can use bitwise-AND for * modular arithmetic. * The count of hash entries may be greater depending on the chosen * collision rate. * * the apr_shm_hash_t will not be shared, but the hdr/values/keys and * entries will be */ struct apr_shm_hash_t { apr_pool_t *pool; apr_shm_hash_hdr_t *hdr; char *keys; char *elems; apr_shm_hash_entry_hdr_t *array; /* this is indexed by the hash */ apr_shm_hash_entry_t *buckets; /* this is where the bucket chains live */ }; //#define INITIAL_MAX 15 /* tunable == 2^n - 1 */ /* * Data structure for iterating through a hash table. * * We keep a pointer to the next hash entry here to allow the current * hash entry to be freed or otherwise mangled between calls to * apr_shm_hash_next(). */ struct apr_shm_hash_index_t { apr_shm_hash_t *ht; int this; int next; int index; }; /*borrowed from apr_pools.c */ union align { /* * Types which are likely to have the longest RELEVANT alignment * restrictions... */ char *cp; void (*f) (void); long l; FILE *fp; double d; }; #define CLICK_SZ (sizeof(union align)) static apr_status_t cleanup_file_cache(void *h) { #if APR_HAS_SHARED_MEMORY apr_shmem_t *shm=h; if ( shm ) { apr_shm_destroy( shm); } #endif return APR_SUCCESS; } APR_DECLARE(apr_shm_hash_t *) apr_shm_hash_make(apr_pool_t *pool, const char*name, const int nElems, apr_size_t keySize, apr_size_t elemSize, const int hashSize) { apr_shm_hash_t *ht; #if APR_HAS_SHARED_MEMORY apr_shmem_t *shm; apr_status_t s; #endif int i; int realElemSize; /* including alignment */ int realKeySize; /* including alignment */ realElemSize = (CLICK_SZ > elemSize) ? CLICK_SZ : elemSize; realKeySize=(CLICK_SZ > keySize) ? CLICK_SZ : keySize; ht = apr_palloc(pool, sizeof(apr_shm_hash_t)); ht->pool = pool; #if APR_HAS_SHARED_MEMORY s = apr_shm_init( &shm, sizeof(apr_shm_hash_hdr_t) + realKeySize * nElems + realElemSize * nElems + sizeof(apr_shm_hash_entry_hdr_t) * (hashSize+1) + sizeof(apr_shm_hash_entry_t) * (nElems), name,pool); if ( s != APR_SUCCESS ) { fprintf(stderr, "ABORT.. can't allocated shared memory"); return NULL; } apr_pool_cleanup_register( pool, shm,apr_shm_hash_cleanup, apr_pool_cleanup_null ); ht->hdr=apr_shm_malloc(shm, sizeof(apr_shm_hash_hdr_t)); if (ht->hdr == NULL ) { fprintf(stderr, "ABORT.. can't allocated shared header"); return NULL; } ht->keys = apr_shm_malloc(shm, realKeySize * nElems ); if (ht->keys == NULL ) { fprintf(stderr, "ABORT.. can't allocated shared keys"); return NULL; } ht->elems= apr_shm_malloc(shm, realElemSize * nElems ); if (ht->elems == NULL ) { fprintf(stderr, "ABORT.. can't allocated shared elems"); return NULL; } ht->array = apr_shm_malloc(shm, sizeof(apr_shm_hash_entry_hdr_t) * (hashSize+1)); if (ht->array == NULL ) { fprintf(stderr, "ABORT.. can't allocated shared array"); return NULL; } ht->buckets= apr_shm_malloc(shm, sizeof(apr_shm_hash_entry_t) * (nElems)); if (ht->buckets == NULL ) { fprintf(stderr, "ABORT.. can't allocated shared buckets"); return NULL; } #else ht->hdr = apr_palloc(pool, sizeof(apr_shm_hash_hdr_t)); ht->keys = apr_pcalloc(pool, realKeySize * nElems ); ht->elems= apr_pcalloc(pool, realElemSize * nElems ); ht->array = apr_pcalloc(ht->pool, sizeof(apr_shm_hash_entry_hdr_t) * (hashSize+1)); ht->buckets= apr_pcalloc(ht->pool, sizeof(apr_shm_hash_entry_t) * (nElems)); #endif ht->hdr->count = 0; ht->hdr->hashSize = hashSize; ht->hdr->max= nElems; strncpy(ht->hdr->szName,name, APR_SHM_HASH_NAME_MAX); ht->hdr->szName[APR_SHM_HASH_NAME_MAX-1]='\0'; ht->hdr->elemSize = realElemSize; ht->hdr->keySize = realKeySize; for (i=0;i<hashSize+1;i++) { ht->array[i].list=-1; } return ht; } /* * Hash iteration functions. */ APR_DECLARE(apr_shm_hash_index_t *) apr_shm_hash_next(apr_shm_hash_index_t *hi) { hi->this = hi->next; while (hi->this ==-1) { if (hi->index > hi->ht->hdr->hashSize) return NULL; hi->this = hi->ht->array[hi->index++].list; } hi->next = hi->ht->buckets[hi->this].next; return hi; } APR_DECLARE(apr_shm_hash_index_t *) apr_shm_hash_first(apr_shm_hash_t *ht) { apr_shm_hash_index_t *hi; hi = apr_palloc(ht->pool, sizeof(*hi)); hi->ht = ht; hi->index = 0; hi->this = -1; hi->next = -1; return apr_shm_hash_next(hi); } APR_DECLARE(void) apr_shm_hash_this(apr_shm_hash_index_t *hi, const void **key, apr_ssize_t *klen, void **val) { apr_shm_hash_entry_t *me; if (hi->this == -1 ) { *key=NULL; *klen=0; *val=NULL; return; } me = &hi->ht->buckets[ hi->this ]; if (key) *key = (hi->ht->keys )+( hi->ht->hdr->keySize * me->posn); if (klen) *klen = me->klen; if (val) *val = (hi->ht->elems )+( hi->ht->hdr->elemSize * me->posn); } /* * This is where we keep the details of the hash function and control * the maximum collision rate. * * If val is non-NULL it creates and initializes a new hash entry if * there isn't already one there; it returns an updatable pointer so * that hash entries can be removed. */ static int find_entry(apr_shm_hash_t *ht, const void *key, apr_ssize_t klen, const void *val) { // apr_shm_hash_entry_t **hep, *he; const unsigned char *p; int hash; apr_ssize_t i; int index; int current; apr_shm_hash_entry_t *me; char *keyPtr; char *valPtr; if (klen == APR_SHM_HASH_KEY_STRING) klen = strlen(key); /* * This is the popular `times 33' hash algorithm which is used by * perl and also appears in Berkeley DB. This is one of the best * known hash functions for strings because it is both computed * very fast and distributes very well. * * The originator may be Dan Bernstein but the code in Berkeley DB * cites Chris Torek as the source. The best citation I have found * is "Chris Torek, Hash function for text in C, Usenet message * <[EMAIL PROTECTED]> in comp.lang.c , October, 1990." in Rich * Salz's USENIX 1992 paper about INN which can be found at * <http://citeseer.nj.nec.com/salz92internetnews.html>. * * The magic of number 33, i.e. why it works better than many other * constants, prime or not, has never been adequately explained by * anyone. So I try an explanation: if one experimentally tests all * multipliers between 1 and 256 (as I did while writing a low-level * data structure library some time ago) one detects that even * numbers are not useable at all. The remaining 128 odd numbers * (except for the number 1) work more or less all equally well. * They all distribute in an acceptable way and this way fill a hash * table with an average percent of approx. 86%. * * If one compares the chi^2 values of the variants (see * Bob Jenkins ``Hashing Frequently Asked Questions'' at * http://burtleburtle.net/bob/hash/hashfaq.html for a description * of chi^2), the number 33 not even has the best value. But the * number 33 and a few other equally good numbers like 17, 31, 63, * 127 and 129 have nevertheless a great advantage to the remaining * numbers in the large set of possible multipliers: their multiply * operation can be replaced by a faster operation based on just one * shift plus either a single addition or subtraction operation. And * because a hash function has to both distribute good _and_ has to * be very fast to compute, those few numbers should be preferred. * * -- Ralf S. Engelschall <[EMAIL PROTECTED]> */ hash = 0; for (p = key, i = klen; (p!=NULL) && (i>0); i--, p++) hash = hash * 33 + *p; /* scan linked list */ index = hash & ht->hdr->hashSize; current = ht->array[index].list; while (current != -1 ) { /* move down the list and see if it is in there */ if (ht->buckets[current].hash == hash && ht->buckets[current].klen == klen) { keyPtr=ht->keys + ( ht->hdr->keySize * ht->buckets[current].posn); if ( memcmp (keyPtr,key,klen) ==0 ) break; } current = ht->buckets[current].next; } if (current != -1 || !val) return current; /* add a new entry for non-NULL values */ keyPtr = ht->keys; keyPtr+= (ht->hdr->keySize*ht->hdr->count); memcpy( keyPtr, key, klen ); valPtr = ht->elems ; valPtr += (ht->hdr->elemSize *ht->hdr->count ); memcpy(valPtr, val, ht->hdr->elemSize ); me = &ht->buckets[ ht->hdr->count ]; me->hash = hash; me->posn = ht->hdr->count; me->arrayPosn = index; me->klen = klen; me->next= ht->array[index].list; /* new one is put a top of list */ ht->array[index].list=ht->hdr->count; ht->array[index].count++; return ht->hdr->count++; } APR_DECLARE(void *) apr_shm_hash_get(apr_shm_hash_t *ht, const void *key, apr_ssize_t klen) { int he; he = find_entry(ht, key, klen, NULL); if (he != -1) return (void *)(ht->elems +ht->buckets[he].posn*ht->hdr->elemSize ); else return NULL; } APR_DECLARE(void) apr_shm_hash_set(apr_shm_hash_t *ht, const void *key, apr_ssize_t klen, const void *val) { int he; he = find_entry(ht, key, klen, val); if (he!=-1) { if (!val) { /* delete entry */ apr_shm_hash_entry_t *me = &ht->buckets[he]; int current = ht->array[me->arrayPosn].list; if (current == he ) { ht->array[me->arrayPosn].list = me->next; } else { while ( ht->buckets[current].next != he && ht->buckets[current].next !=-1) { current = ht->buckets[current].next; } ht->buckets[current].next = ht->buckets[he].next; } ht->array [ me->arrayPosn ].count--; ht->buckets[he].arrayPosn =-1; ht->buckets[he].posn =-1; ht->buckets[he].next =-1; ht->buckets[he].klen =-1; /* --ht->hdr->count;*/ /*FIXME: entries/keys use 'count' to store info */ } else { /* replace entry */ char *valPtr; valPtr = ht->elems ; valPtr += (ht->hdr->elemSize * ht->buckets[he].posn ); memcpy(valPtr, val, ht->hdr->elemSize ); /* check that the collision rate isn't too high */ if (ht->hdr->count > ht->hdr->hashSize) { /* expand_array(ht);*/ /*FIXME: can't expand shared mem array */ } } } /* else key not present and val==NULL */ } APR_DECLARE(int) apr_shm_hash_count(apr_shm_hash_t *ht) { return ht->hdr->count; }
/* ==================================================================== * The Apache Software License, Version 1.1 * * Copyright (c) 2000-2001 The Apache Software Foundation. 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. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation" must * not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache", * nor may "Apache" appear in their name, without prior written * permission of the Apache Software Foundation. * * 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 APACHE SOFTWARE FOUNDATION 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. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. * * Portions of this software are based upon public domain software * originally written at the National Center for Supercomputing Applications, * University of Illinois, Urbana-Champaign. */ #ifndef APR_SHM_HASH_H #define APR_SHM_HASH_H #ifdef __cplusplus extern "C" { #endif /** * @package Shared Hash Tables */ #include "apr_pools.h" /* * When passing a key to apr_shm_hash_set or apr_shm_hash_get, this value can be * passed to indicate a string-valued key, and have apr_shm_hash compute the * length automatically. * * Note: apr_shm_hash will use strlen(key) for the length. The null-terminator * is not included in the hash value (why throw a constant in?). * Since the hash table merely references the provided key (rather * than copying it), apr_shm_hash_this() will return the null-term'd key. */ #define APR_SHM_HASH_KEY_STRING (-1) /** * Abstract type for hash tables. * @defvar apr_shm_hash_t */ typedef struct apr_shm_hash_t apr_shm_hash_t; /** * Abstract type for scanning hash tables. * @defvar apr_shm_hash_index_t */ typedef struct apr_shm_hash_index_t apr_shm_hash_index_t; /** * Create a hash table. * @param pool The pool to allocate the hash table out of * @return The hash table just created * @deffunc apr_shm_hash_t *apr_shm_hash_make(apr_pool_t *pool) */ APR_DECLARE(apr_shm_hash_t *) apr_shm_hash_make(apr_pool_t *pool,const char*name, const int nElems, apr_size_t keySize, apr_size_t elemSize,const int hashSize); /** * Associate a value with a key in a hash table. * @param ht The hash table * @param key Pointer to the key * @param klen Length of the key. Can be apr_shm_hash_KEY_STRING to use the string length. * @param val Value to associate with the key * @tip If the value is NULL the hash entry is deleted. * @deffunc void apr_shm_hash_set(apr_shm_hash_t *ht, const void *key, apr_size_t klen, const void *val) */ APR_DECLARE(void) apr_shm_hash_set(apr_shm_hash_t *ht, const void *key, apr_ssize_t klen, const void *val); /** * Look up the value associated with a key in a hash table. * @param ht The hash table * @param key Pointer to the key * @param klen Length of the key. Can be apr_shm_hash_KEY_STRING to use the string length. * @return Returns NULL if the key is not present. * @deffunc void *apr_shm_hash_get(apr_shm_hash_t *ht, const void *key, apr_ssize_t klen) */ APR_DECLARE(void *) apr_shm_hash_get(apr_shm_hash_t *ht, const void *key, apr_ssize_t klen); /** * Start iterating over the entries in a hash table. * @param ht The hash table * @return a pointer to the iteration state, or NULL if there are no entries. * @tip Example: * <PRE> * * int sum_values(apr_shm_hash_t *ht) * { * apr_shm_hash_index_t *hi; * void *val; * int sum = 0; * for (hi = apr_shm_hash_first(ht); hi; hi = apr_shm_hash_next(hi)) { * apr_shm_hash_this(hi, NULL, NULL, &val); * sum += *(int *)val; * } * return sum; * } * * There is no restriction on adding or deleting hash entries during an * iteration (although the results may be unpredictable unless all you do * is delete the current entry) and multiple iterations can be in * progress at the same time. * </PRE> * @deffunc apr_shm_hash_index_t *apr_shm_hash_first(apr_shm_hash_t *ht) */ APR_DECLARE(apr_shm_hash_index_t *) apr_shm_hash_first(apr_shm_hash_t *ht); /** * Continue iterating over the entries in a hash table. * @param hi The iteration state * @return a pointer to the updated iteration state. NULL if there are no more * entries. * @deffunc apr_shm_hash_index_t *apr_shm_hash_next(apr_shm_hash_index_t *hi) */ APR_DECLARE(apr_shm_hash_index_t *) apr_shm_hash_next(apr_shm_hash_index_t *hi); /** * Get the current entry's details from the iteration state. * @param hi The iteration state * @param key Return pointer for the pointer to the key. * @param klen Return pointer for the key length. * @param val Return pointer for the associated value. * @tip The return pointers should point to a variable that will be set to the * corresponding data, or they may be NULL if the data isn't interesting. * @deffunc void apr_shm_hash_this(apr_shm_hash_index_t *hi, const void **key, apr_ssize_t *klen, void **val); */ APR_DECLARE(void) apr_shm_hash_this(apr_shm_hash_index_t *hi, const void **key, apr_ssize_t *klen, void **val); /** * Get the number of key/value pairs in the hash table. * @param ht The hash table * @return The number of key/value pairs in the hash table. * @deffunc int apr_shm_hash_count(apr_shm_hash_t *ht); */ APR_DECLARE(int) apr_shm_hash_count(apr_shm_hash_t *ht); #ifdef __cplusplus } #endif #endif /* !APR_SHM_HASH_H */
