summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ckcapi-builtin.c23
-rw-r--r--ckcapi-cert.c23
-rw-r--r--ckcapi-key.c28
-rw-r--r--ckcapi-object.h10
-rw-r--r--ckcapi-session.c26
-rw-r--r--ckcapi-token.c43
-rw-r--r--ckcapi-trust.c20
-rw-r--r--ckcapi-util.c138
-rw-r--r--ckcapi-util.h25
9 files changed, 218 insertions, 118 deletions
diff --git a/ckcapi-builtin.c b/ckcapi-builtin.c
index 1be3ccc..21115a3 100644
--- a/ckcapi-builtin.c
+++ b/ckcapi-builtin.c
@@ -73,12 +73,6 @@ static CK_ULONG num_builtins = 0;
typedef struct _BuiltinObject
{
CkCapiObject obj;
-
- /*
- * Together these form the unique key. Must be
- * laid out together in memory.
- */
- unsigned int otype;
CK_ATTRIBUTE_PTR attr;
}
BuiltinObject;
@@ -154,6 +148,18 @@ builtin_load_data(CkCapiSession* sess, CkCapiObject* obj, CkCapiObjectData** obj
return CKR_OK;
}
+static unsigned int
+builtin_hash_func(CkCapiObject* obj)
+{
+ return ckcapi_hash_pointer(((BuiltinObject*)obj)->attr);
+}
+
+static int
+builtin_equal_func(CkCapiObject* one, CkCapiObject* two)
+{
+ return ((BuiltinObject*)one)->attr == ((BuiltinObject*)two)->attr;
+}
+
static void
builtin_object_release(void* data)
{
@@ -164,6 +170,8 @@ builtin_object_release(void* data)
static const CkCapiObjectVtable builtin_object_vtable = {
builtin_load_data,
+ builtin_hash_func,
+ builtin_equal_func,
builtin_object_release,
};
@@ -177,13 +185,10 @@ register_builtin_object(CkCapiSession* sess, CK_ATTRIBUTE_PTR attr, CkCapiObject
if(!bobj)
return CKR_HOST_MEMORY;
- bobj->otype = OBJECT_BUILTIN;
bobj->attr = attr;
bobj->obj.id = 0;
bobj->obj.obj_funcs = &builtin_object_vtable;
- bobj->obj.unique_key = UNIQUE_KEY_AT(bobj, otype);
- bobj->obj.unique_len = UNIQUE_KEY_LEN(bobj, otype, attr);
ret = ckcapi_token_register_object(sess->slot, &(bobj->obj));
if(ret != CKR_OK)
diff --git a/ckcapi-cert.c b/ckcapi-cert.c
index fb3603a..4fe1d41 100644
--- a/ckcapi-cert.c
+++ b/ckcapi-cert.c
@@ -354,6 +354,25 @@ cert_load_data(CkCapiSession* sess, CkCapiObject* obj, CkCapiObjectData** objdat
return CKR_OK;
}
+static unsigned int
+cert_hash_func(CkCapiObject* obj)
+{
+ CertObject* cobj = (CertObject*)obj;
+ return ckcapi_hash_data(cobj->issuer.pbData, cobj->issuer.cbData) ^
+ ckcapi_hash_data(cobj->serial.pbData, cobj->serial.cbData);
+}
+
+static int
+cert_equal_func(CkCapiObject* a, CkCapiObject* b)
+{
+ CertObject* ca = (CertObject*)a;
+ CertObject* cb = (CertObject*)b;
+ return ca->issuer.cbData == cb->issuer.cbData &&
+ memcmp(ca->issuer.pbData, cb->issuer.pbData, ca->issuer.cbData) == 0 &&
+ ca->serial.cbData == cb->serial.cbData &&
+ memcmp(ca->serial.pbData, cb->serial.pbData, ca->serial.cbData) == 0;
+}
+
static void
cert_object_release(void* data)
{
@@ -364,6 +383,8 @@ cert_object_release(void* data)
static const CkCapiObjectVtable cert_object_vtable = {
cert_load_data,
+ cert_hash_func,
+ cert_equal_func,
cert_object_release,
};
@@ -585,8 +606,6 @@ register_cert_object(CkCapiSession* sess, PCCERT_CONTEXT cert, CkCapiObject** ob
cobj->otype = OBJECT_CERT;
cobj->obj.id = 0;
- cobj->obj.unique_key = UNIQUE_KEY_AT(cobj, otype);
- cobj->obj.unique_len = UNIQUE_KEY_VAR_LEN(cobj, otype, otype, len);
cobj->obj.obj_funcs = &cert_object_vtable;
/* Copy Issuer data in */
diff --git a/ckcapi-key.c b/ckcapi-key.c
index 7618e1e..5cf60ba 100644
--- a/ckcapi-key.c
+++ b/ckcapi-key.c
@@ -80,10 +80,7 @@ typedef struct _KeyObject
/* The raw key identifier */
CRYPT_HASH_BLOB key_identifier;
-
- /* Together these form the unique key. Must be contiguous */
CK_OBJECT_CLASS object_class;
- BYTE tail_data[1];
}
KeyObject;
@@ -733,6 +730,24 @@ key_load_data(CkCapiSession* sess, CkCapiObject* obj, CkCapiObjectData** objdata
return CKR_OK;
}
+static unsigned int
+key_hash_func(CkCapiObject* obj)
+{
+ KeyObject* kobj = (KeyObject*)obj;
+ return ckcapi_hash_data(kobj->key_identifier.pbData, kobj->key_identifier.cbData) ^
+ ckcapi_hash_integer((int)kobj->object_class);
+}
+
+static int
+key_equal_func(CkCapiObject* a, CkCapiObject* b)
+{
+ KeyObject* ka = (KeyObject*)a;
+ KeyObject* kb = (KeyObject*)b;
+ return ka->object_class == kb->object_class &&
+ ka->key_identifier.cbData == kb->key_identifier.cbData &&
+ memcmp(ka->key_identifier.pbData, kb->key_identifier.pbData, ka->key_identifier.cbData) == 0;
+}
+
static void
key_object_release(void* data)
{
@@ -743,6 +758,8 @@ key_object_release(void* data)
static const CkCapiObjectVtable key_object_vtable = {
key_load_data,
+ key_hash_func,
+ key_equal_func,
key_object_release,
};
@@ -763,12 +780,9 @@ register_key_object(CkCapiSession* sess, CK_OBJECT_CLASS cls,
kobj->obj.id = 0;
kobj->obj.obj_funcs = &key_object_vtable;
- kobj->obj.unique_key = UNIQUE_KEY_AT(kobj, object_class);
- kobj->obj.unique_len = UNIQUE_KEY_VAR_LEN(kobj, object_class, tail_data,
- key_identifier->cbData);
kobj->object_class = cls;
- kobj->key_identifier.pbData = kobj->tail_data;
+ kobj->key_identifier.pbData = (BYTE*)(kobj + 1);
kobj->key_identifier.cbData = key_identifier->cbData;
memcpy(kobj->key_identifier.pbData, key_identifier->pbData,
kobj->key_identifier.cbData);
diff --git a/ckcapi-object.h b/ckcapi-object.h
index 98451f6..9a664d1 100644
--- a/ckcapi-object.h
+++ b/ckcapi-object.h
@@ -30,6 +30,12 @@
typedef CK_RV (*CkCapiLoadData)(CkCapiSession* sess, struct _CkCapiObject* obj,
CkCapiObjectData** objdata);
+/* Produce a hash code for an object */
+typedef CK_RV (*CkCapiHashObject)(struct _CkCapiObject* obj);
+
+/* Produce a hash code for an object */
+typedef CK_RV (*CkCapiEqualObject)(struct _CkCapiObject* one, struct _CkCapiObject* two);
+
/* A function to free some data */
typedef void (*CkCapiRelease)(void* data);
@@ -37,6 +43,8 @@ typedef void (*CkCapiRelease)(void* data);
typedef struct _CkCapiObjectVtable
{
CkCapiLoadData load_data;
+ CkCapiHashObject hash_object;
+ CkCapiEqualObject equal_object;
CkCapiRelease release;
}
CkCapiObjectVtable;
@@ -48,8 +56,6 @@ struct _CkCapiObject
CK_SLOT_ID slot;
CK_SESSION_HANDLE session;
const CkCapiObjectVtable* obj_funcs;
- void* unique_key;
- size_t unique_len;
};
/* A function to get an attribute from ObjectData */
diff --git a/ckcapi-session.c b/ckcapi-session.c
index 064e477..d1d345c 100644
--- a/ckcapi-session.c
+++ b/ckcapi-session.c
@@ -59,7 +59,7 @@ ckcapi_session_create(CK_SLOT_ID slot, CkCapiSession** ret)
if(!sess)
return CKR_HOST_MEMORY;
- sess->object_data = ckcapi_hash_new();
+ sess->object_data = ckcapi_hash_new(NULL, NULL);
if(!sess->object_data) {
free(sess);
return CKR_HOST_MEMORY;
@@ -505,7 +505,7 @@ ckcapi_session_get_object_data(CkCapiSession* sess, CkCapiObject* obj,
id = obj->id;
- *objdata = ckcapi_hash_get(sess->object_data, &id, sizeof(id));
+ *objdata = ckcapi_hash_get(sess->object_data, ckcapi_hash_key(id));
if(*objdata)
return CKR_OK;
@@ -516,8 +516,7 @@ ckcapi_session_get_object_data(CkCapiSession* sess, CkCapiObject* obj,
newdata->object = id;
ASSERT(newdata->data_funcs);
- if(!ckcapi_hash_set(sess->object_data, &newdata->object,
- sizeof(newdata->object), newdata)) {
+ if(!ckcapi_hash_set(sess->object_data, ckcapi_hash_key(id), newdata)) {
object_data_release(newdata);
return CKR_HOST_MEMORY;
}
@@ -535,7 +534,7 @@ ckcapi_session_clear_object_data(CkCapiSession* sess, CkCapiObject* obj)
ASSERT(sess->object_data);
ASSERT(obj);
- objdata = (CkCapiObjectData*)ckcapi_hash_rem(sess->object_data, &obj->id, sizeof(obj->id));
+ objdata = (CkCapiObjectData*)ckcapi_hash_rem(sess->object_data, ckcapi_hash_key(obj->id));
if(objdata)
object_data_release(objdata);
}
@@ -555,7 +554,7 @@ ckcapi_session_enum_object_data(CkCapiSession* sess,
max = ckcapi_token_get_max_handle();
for(i = 0; i < max; ++i)
{
- objdata = (CkCapiObjectData*)ckcapi_hash_get(sess->object_data, &i, sizeof(i));
+ objdata = (CkCapiObjectData*)ckcapi_hash_get(sess->object_data, ckcapi_hash_key(i));
if(!objdata)
continue;
@@ -593,12 +592,11 @@ ckcapi_session_take_object_data(CkCapiSession* sess, CkCapiObject* obj,
ASSERT(objdata);
objdata->object = obj->id;
- prev = ckcapi_hash_rem(sess->object_data, &obj->id, sizeof(obj->id));
+ prev = ckcapi_hash_rem(sess->object_data, ckcapi_hash_key(obj->id));
if(prev)
object_data_release(prev);
- if(!ckcapi_hash_set(sess->object_data, &objdata->object,
- sizeof(objdata->object), objdata))
+ if(!ckcapi_hash_set(sess->object_data, ckcapi_hash_key(obj->id), objdata))
object_data_release(objdata);
}
@@ -686,24 +684,24 @@ void
purge_duplicate_objects(CkCapiArray* arr)
{
CkCapiHash* checks;
- CK_OBJECT_HANDLE* v;
+ CK_OBJECT_HANDLE v;
size_t i;
- checks = ckcapi_hash_new();
+ checks = ckcapi_hash_new(NULL, NULL);
if(!checks)
return;
for(i = 0; i < arr->len; )
{
- v = &ckcapi_array_index(arr, CK_OBJECT_HANDLE, i);
- if(ckcapi_hash_get(checks, v, sizeof(CK_OBJECT_HANDLE)))
+ v = ckcapi_array_index(arr, CK_OBJECT_HANDLE, i);
+ if(ckcapi_hash_get(checks, ckcapi_hash_key(v)))
{
ckcapi_array_remove_index(arr, i);
/* Look at same i again */
}
else
{
- if(!ckcapi_hash_set(checks, v, sizeof(CK_OBJECT_HANDLE), v))
+ if(!ckcapi_hash_set(checks, ckcapi_hash_key(v), arr))
break;
++i;
}
diff --git a/ckcapi-token.c b/ckcapi-token.c
index 4f0a7a3..0f93a45 100644
--- a/ckcapi-token.c
+++ b/ckcapi-token.c
@@ -172,18 +172,35 @@ ckcapi_token_lookup_object(CK_SLOT_ID slot, CK_OBJECT_HANDLE obj)
return ret;
}
+static unsigned int
+object_hash_func(const void* a)
+{
+ CkCapiObject* obj = (CkCapiObject*)a;
+ unsigned int hash = ckcapi_hash_pointer(obj->obj_funcs);
+ hash ^= (obj->obj_funcs->hash_object)(obj);
+ return hash;
+}
+
+static int
+object_equal_func(const void* a, const void* b)
+{
+ CkCapiObject* ca = (CkCapiObject*)a;
+ CkCapiObject* cb = (CkCapiObject*)b;
+ if(ca == cb)
+ return 1;
+ if(ca->obj_funcs != cb->obj_funcs)
+ return 0;
+ return (ca->obj_funcs->equal_object)(ca, cb);
+}
+
CK_RV
ckcapi_token_register_object(CK_SLOT_ID slot, CkCapiObject* obj)
{
CkCapiObject* prev;
CK_RV ret = CKR_OK;
- void* key;
- size_t klen;
ASSERT(slot);
ASSERT(obj->id == 0);
- ASSERT(obj->unique_key);
- ASSERT(obj->unique_len > 0);
DBG(("registering object"));
@@ -199,8 +216,7 @@ ckcapi_token_register_object(CK_SLOT_ID slot, CkCapiObject* obj)
ckcapi_array_append(object_array, blank);
}
- object_hash = ckcapi_hash_new();
-
+ object_hash = ckcapi_hash_new(object_hash_func, object_equal_func);
if(!object_array || !object_hash)
{
@@ -214,21 +230,14 @@ ckcapi_token_register_object(CK_SLOT_ID slot, CkCapiObject* obj)
ASSERT(object_array);
ASSERT(object_hash);
- /* The type of object is part of the hash */
- key = obj->unique_key;
- klen = obj->unique_len;
-
- /* Sanity check, in case calcs went wrong somewhere */
- ASSERT(klen < 0xFFFFFF);
-
/* Look in the hash and find a previous object */
- prev = ckcapi_hash_get(object_hash, key, klen);
+ prev = ckcapi_hash_get(object_hash, obj);
if(prev)
{
/* Register it in the previous object's place */
obj->id = prev->id;
ASSERT(prev->id < object_array->len);
- if(ckcapi_hash_set(object_hash, key, klen, obj))
+ if(ckcapi_hash_set(object_hash, obj, obj))
{
ckcapi_array_index(object_array, CkCapiObject*, obj->id) = obj;
object_free(prev);
@@ -245,7 +254,7 @@ ckcapi_token_register_object(CK_SLOT_ID slot, CkCapiObject* obj)
/* Register it at the end of the array */
obj->id = object_array->len;
ASSERT(obj->id > 0);
- if(ckcapi_hash_set(object_hash, key, klen, obj))
+ if(ckcapi_hash_set(object_hash, obj, obj))
{
if(ckcapi_array_append(object_array, obj))
{
@@ -256,7 +265,7 @@ ckcapi_token_register_object(CK_SLOT_ID slot, CkCapiObject* obj)
ret = CKR_HOST_MEMORY;
/* Roll back our addition */
- ckcapi_hash_rem(object_hash, key, klen);
+ ckcapi_hash_rem(object_hash, obj);
}
}
else
diff --git a/ckcapi-trust.c b/ckcapi-trust.c
index 8519464..3faa4b2 100644
--- a/ckcapi-trust.c
+++ b/ckcapi-trust.c
@@ -47,9 +47,6 @@
typedef struct _TrustObject
{
CkCapiObject obj;
-
- /* Together these form the unique key. Must be contiguous */
- unsigned int otype;
CK_OBJECT_HANDLE cert_obj;
}
TrustObject;
@@ -266,6 +263,18 @@ trust_date_attribute(CkCapiObjectData* objdata, CK_ATTRIBUTE_PTR attr)
return CKR_ATTRIBUTE_TYPE_INVALID;
}
+static unsigned int
+trust_hash_func(CkCapiObject* obj)
+{
+ return ckcapi_hash_integer(((TrustObject*)obj)->cert_obj);
+}
+
+static int
+trust_equal_func(CkCapiObject* a, CkCapiObject* b)
+{
+ return ((TrustObject*)a)->cert_obj == ((TrustObject*)b)->cert_obj;
+}
+
static void
trust_release(void* data)
{
@@ -440,6 +449,8 @@ trust_object_release(void* data)
static const CkCapiObjectVtable trust_object_vtable = {
trust_load_data,
+ trust_hash_func,
+ trust_equal_func,
trust_object_release,
};
@@ -453,13 +464,10 @@ register_trust_object(CkCapiSession* sess, CkCapiObject* cert, CkCapiObject** ob
if(!tobj)
return CKR_HOST_MEMORY;
- tobj->otype = OBJECT_TRUST;
tobj->cert_obj = cert->id;
tobj->obj.id = 0;
tobj->obj.obj_funcs = &trust_object_vtable;
- tobj->obj.unique_key = UNIQUE_KEY_AT(tobj, otype);
- tobj->obj.unique_len = UNIQUE_KEY_LEN(tobj, otype, cert_obj);
ret = ckcapi_token_register_object(sess->slot, &(tobj->obj));
if(ret != CKR_OK)
diff --git a/ckcapi-util.c b/ckcapi-util.c
index 3bd18a5..80e1b40 100644
--- a/ckcapi-util.c
+++ b/ckcapi-util.c
@@ -260,7 +260,6 @@ typedef struct _HashEntry
struct _HashEntry* next;
unsigned int hash;
const void* key;
- size_t klen;
void* val;
}
HashEntry;
@@ -275,6 +274,8 @@ HashEntry;
struct _CkCapiHash
{
HashEntry** array;
+ CkCapiHashFunc hash_func;
+ CkCapiHashEqual equal_func;
size_t count;
size_t max;
};
@@ -282,6 +283,12 @@ struct _CkCapiHash
#define INITIAL_MAX 15 /* tunable == 2^n - 1 */
+static int
+equal_default(const void* a, const void* b)
+{
+ return a == b;
+}
+
/*
* Hash creation functions.
*/
@@ -293,11 +300,13 @@ alloc_array(CkCapiHash* ht, size_t max)
}
CkCapiHash*
-ckcapi_hash_new()
+ckcapi_hash_new(CkCapiHashFunc hash_func, CkCapiHashEqual equal_func)
{
CkCapiHash* ht = malloc(sizeof(CkCapiHash));
if(ht)
{
+ ht->hash_func = hash_func ? hash_func : ckcapi_hash_pointer;
+ ht->equal_func = equal_func ? equal_func : equal_default;
ht->count = 0;
ht->max = INITIAL_MAX;
ht->array = alloc_array(ht, ht->max);
@@ -379,62 +388,19 @@ expand_array(CkCapiHash* ht)
*/
static HashEntry**
-find_entry(CkCapiHash* ht, const void* key, size_t klen, void* val)
+find_entry(CkCapiHash* ht, const void* key, void* val)
{
HashEntry** hep;
HashEntry* he;
- const unsigned char* p;
unsigned int hash;
- size_t i;
-
- /*
- * 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
- * <27038@mimsy.umd.edu> 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 <rse@engelschall.com>
- */
- hash = 0;
- for(p = key, i = klen; i; i--, p++)
- hash = hash * 33 + *p;
+ hash = (ht->hash_func)(key);
/* scan linked list */
for(hep = &ht->array[hash & ht->max], he = *hep;
he; hep = &he->next, he = *hep)
{
- if(he->hash == hash && he->klen == klen &&
- memcmp(he->key, key, klen) == 0)
+ if(he->hash == hash && (ht->equal_func)(he->key, key))
break;
}
@@ -447,7 +413,6 @@ find_entry(CkCapiHash* ht, const void* key, size_t klen, void* val)
{
/* Key points to external data */
he->key = key;
- he->klen = klen;
he->next = NULL;
he->hash = hash;
@@ -461,9 +426,9 @@ find_entry(CkCapiHash* ht, const void* key, size_t klen, void* val)
}
void*
-ckcapi_hash_get(CkCapiHash* ht, const void *key, size_t klen)
+ckcapi_hash_get(CkCapiHash* ht, const void *key)
{
- HashEntry** he = find_entry(ht, key, klen, NULL);
+ HashEntry** he = find_entry(ht, key, NULL);
if(he && *he)
return (void*)((*he)->val);
else
@@ -471,9 +436,9 @@ ckcapi_hash_get(CkCapiHash* ht, const void *key, size_t klen)
}
int
-ckcapi_hash_set(CkCapiHash* ht, const void* key, size_t klen, void* val)
+ckcapi_hash_set(CkCapiHash* ht, const void* key, void* val)
{
- HashEntry** hep = find_entry(ht, key, klen, val);
+ HashEntry** hep = find_entry(ht, key, val);
if(hep && *hep)
{
/* replace entry */
@@ -493,9 +458,9 @@ ckcapi_hash_set(CkCapiHash* ht, const void* key, size_t klen, void* val)
}
void*
-ckcapi_hash_rem(CkCapiHash* ht, const void* key, size_t klen)
+ckcapi_hash_rem(CkCapiHash* ht, const void* key)
{
- HashEntry** hep = find_entry(ht, key, klen, NULL);
+ HashEntry** hep = find_entry(ht, key, NULL);
void* val = NULL;
if(hep && *hep)
@@ -515,3 +480,66 @@ ckcapi_hash_count(CkCapiHash* ht)
{
return ht->count;
}
+
+unsigned int
+ckcapi_hash_pointer(const void* ptr)
+{
+ return (unsigned int)ptr;
+}
+
+unsigned int
+ckcapi_hash_data(const void* data, size_t n_data)
+{
+ unsigned int hash = 0;
+ const unsigned char* end;
+ const unsigned char* p;
+
+ /*
+ * 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
+ * <27038@mimsy.umd.edu> 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 <rse@engelschall.com>
+ */
+
+ for(p = data, end = p + n_data; p != end; ++p)
+ hash = hash * 33 + *p;
+
+ return hash;
+}
+
+unsigned int
+ckcapi_hash_integer(int integer)
+{
+ return integer;
+}
diff --git a/ckcapi-util.h b/ckcapi-util.h
index 6ae74a0..59e660c 100644
--- a/ckcapi-util.h
+++ b/ckcapi-util.h
@@ -63,18 +63,31 @@ void ckcapi_array_remove_range (CkCapiArray* array, unsigned int index,
struct _CkCapiHash;
typedef struct _CkCapiHash CkCapiHash;
+typedef unsigned int (*CkCapiHashFunc)(const void* key);
+
+typedef int (*CkCapiHashEqual)(const void* a, const void* b);
+
typedef void (*CkCapiHashDestroy)(void* val);
-CkCapiHash* ckcapi_hash_new (void);
+CkCapiHash* ckcapi_hash_new (CkCapiHashFunc hash_func, CkCapiHashEqual equal_func);
+
+void ckcapi_hash_free (CkCapiHash* ht, CkCapiHashDestroy destroy_func);
+
+size_t ckcapi_hash_count (CkCapiHash* ht);
+
+void* ckcapi_hash_get (CkCapiHash* ht, const void* key);
+
+int ckcapi_hash_set (CkCapiHash* ht, const void* key, void* val);
-void ckcapi_hash_free (CkCapiHash* ht, CkCapiHashDestroy destroy_func);
+void* ckcapi_hash_rem (CkCapiHash* ht, const void* key);
-size_t ckcapi_hash_count (CkCapiHash* ht);
+unsigned int ckcapi_hash_pointer (const void* ptr);
-void* ckcapi_hash_get (CkCapiHash* ht, const void* key, size_t klen);
+unsigned int ckcapi_hash_data (const void* data, size_t n_data);
-int ckcapi_hash_set (CkCapiHash* ht, const void* key, size_t klen, void* val);
+unsigned int ckcapi_hash_integer (int integer);
-void* ckcapi_hash_rem (CkCapiHash* ht, const void* key, size_t klen);
+#define ckcapi_hash_key(num) \
+ (((char*)NULL) + (size_t)(num))
#endif /* __CKCAPI_UTIL_H__ */ \ No newline at end of file
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 17:17:49 +0000