A bunch more changes, that implement almost complete find and get support.

1 files changed, 313 insertions, 23 deletions

diff --git a/ckcapi-util.c b/ckcapi-util.c
index d8d182b..6969c2e 100644
--- a/ckcapi-util.c
+++ b/ckcapi-util.c
@@ -1,17 +1,16 @@
 
-#include "cryptoki-capi-util.h"
+#include "ckcapi-util.h"
 
+#include <sys/types.h>
+#include <stdlib.h>
 #include <string.h>
 
 
-
-
-
 #define MIN_ARRAY_SIZE  16
 
 typedef struct _RealArray
 {
-	Array pub;
+	CkCapiArray pub;
 	size_t alloc;
 	size_t elt_size;
 	int zero_terminated : 1;
@@ -44,7 +43,7 @@ maybe_expand(RealArray *array, size_t len)
 									  array->zero_terminated);
 
 	if(want_alloc > array->alloc)
-    {
+	{
 		want_alloc = nearest_pow(want_alloc);
 		want_alloc = want_alloc > MIN_ARRAY_SIZE ? want_alloc : MIN_ARRAY_SIZE;
 
@@ -53,21 +52,21 @@ maybe_expand(RealArray *array, size_t len)
 			return 0;
 		array->pub.data = mem;
 
-        memset((char*)array->pub.data + array->alloc, 0, want_alloc - array->alloc);
+		memset((char*)array->pub.data + array->alloc, 0, want_alloc - array->alloc);
 		array->alloc = want_alloc;
 	}
 
 	return 1;
 }
 
-Array*
-ckcapi_util_array_new(int zero_terminated, int clear, size_t elt_size)
+CkCapiArray*
+ckcapi_array_new(int zero_terminated, int clear, size_t elt_size)
 {
-	return ckcapi_util_array_sized_new(zero_terminated, clear, elt_size, 0);
+	return ckcapi_array_sized_new(zero_terminated, clear, elt_size, 0);
 }
 
-Array* 
-ckcapi_util_array_sized_new(int zero_terminated, int clear, size_t elt_size,
+CkCapiArray* 
+ckcapi_array_sized_new(int zero_terminated, int clear, size_t elt_size,
 							size_t reserved_size)
 {
 	RealArray *array = malloc(sizeof(RealArray));
@@ -87,11 +86,11 @@ ckcapi_util_array_sized_new(int zero_terminated, int clear, size_t elt_size,
 		array_zero_terminate(array);
 	}
 
-	return (Array*)array;
+	return (CkCapiArray*)array;
 }
 
 void*
-ckcapi_util_array_free(Array* array, int free_segment)
+ckcapi_array_free(CkCapiArray* array, int free_segment)
 {
 	void* segment;
 
@@ -99,10 +98,10 @@ ckcapi_util_array_free(Array* array, int free_segment)
 		return NULL;
 
 	if(free_segment)
-    {
+	{
 		free(array->data);
 		segment = NULL;
-    }
+	}
 	else
 		segment = array->data;
 
@@ -111,7 +110,7 @@ ckcapi_util_array_free(Array* array, int free_segment)
 }
 
 int
-ckcapi_util_array_append_vals(Array* parray, const void* data, size_t len)
+ckcapi_array_append_vals(CkCapiArray* parray, const void* data, size_t len)
 {
 	RealArray* array = (RealArray*)parray;
 	if(!maybe_expand(array, len))
@@ -127,7 +126,7 @@ ckcapi_util_array_append_vals(Array* parray, const void* data, size_t len)
 }
 
 void
-ckcapi_util_array_remove_index(Array* parray, unsigned int index)
+ckcapi_array_remove_index(CkCapiArray* parray, unsigned int index)
 {
 	RealArray* array = (RealArray*)parray;
 
@@ -136,16 +135,16 @@ ckcapi_util_array_remove_index(Array* parray, unsigned int index)
 
 	if(index != array->pub.len - 1)
 		memmove(array_elt_pos (array, index),
-			    array_elt_pos (array, index + 1),
-				array_elt_len (array, array->pub.len - index - 1));
+		        array_elt_pos (array, index + 1),
+		        array_elt_len (array, array->pub.len - index - 1));
   
 	array->pub.len -= 1;
 
-    array_elt_zero (array, array->pub.len, 1);
+	array_elt_zero (array, array->pub.len, 1);
 }
 
 void
-ckcapi_util_array_remove_range(Array* parray, unsigned int index, size_t length)
+ckcapi_array_remove_range(CkCapiArray* parray, unsigned int index, size_t length)
 {
 	RealArray *array = (RealArray*)parray;
 
@@ -162,6 +161,297 @@ ckcapi_util_array_remove_range(Array* parray, unsigned int index, size_t length)
 				(array->pub.len - (index + length)) * array->elt_size);
 
 	array->pub.len -= length;
-    array_elt_zero(array, array->pub.len, length);
+	array_elt_zero(array, array->pub.len, length);
+}
+
+
+/*
+ * Originally from apache 2.0
+ * Modifications for general use by <nielsen@memberwebs.com>
+ */
+
+/* Copyright 2000-2004 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *         http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+#define KEY_DATA(he)	((he)->key)
+
+/*
+ * 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 _HashEntry 
+{
+	struct _HashEntry* next;
+	unsigned int hash;
+	const void* key;
+	size_t klen;
+	const void* val;
 }
+HashEntry;
+
+/*
+ * 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.
+ */
+struct _CkCapiHash 
+{
+	HashEntry** array;
+	size_t count;
+	size_t max;
+};
+
 
+#define INITIAL_MAX 15 /* tunable == 2^n - 1 */
+
+/*
+ * Hash creation functions.
+ */
+
+static HashEntry** 
+alloc_array(CkCapiHash* ht, size_t max)
+{
+	return calloc(sizeof(*(ht->array)) * (max + 1), 1);
+}
+
+CkCapiHash* 
+ckcapi_hash_new()
+{
+	CkCapiHash* ht = malloc(sizeof(CkCapiHash));
+	if(ht)
+	{
+		ht->count = 0;
+		ht->max = INITIAL_MAX;
+		ht->array = alloc_array(ht, ht->max);
+		if(!ht->array)
+		{
+			free(ht);
+			ht = NULL;
+		}
+	}
+	return ht;
+}
+
+void 
+ckcapi_hash_free(CkCapiHash* ht)
+{
+	HashEntry* he;
+	HashEntry* next;
+	size_t i;
+
+	for(i = 0; i < ht->max; ++i)
+	{
+		for(he = ht->array[i]; he; )
+		{
+			next = he->next;
+			free(he);
+			he = next;
+		}
+	}
+		
+	if(ht->array)
+		free(ht->array);	
+	free(ht);
+}
+
+/*
+ * Expanding a hash table
+ */
+static int 
+expand_array(CkCapiHash* ht)
+{
+	HashEntry** new_array;
+	size_t new_max;
+	HashEntry* he;
+	size_t i;
+
+	new_max = ht->max * 2 + 1;
+	new_array = alloc_array(ht, new_max);
+	
+	if(!new_array)
+		return 0;
+		
+	for(i = 0; i < ht->max; ++i)
+	{
+		for(he = ht->array[i]; he; he = he->next)
+		{
+			unsigned int i = he->hash & new_max;
+			he->next = new_array[i];
+			new_array[i] = he;
+		}
+	}
+
+	if(ht->array)
+		free(ht->array);
+	
+	ht->array = new_array;
+	ht->max = new_max;
+	return 1;
+}
+
+/*
+ * 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 HashEntry** 
+find_entry(CkCapiHash* ht, const void* key, size_t klen, const 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;
+
+	/* 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(KEY_DATA(he), key, klen) == 0)
+			break;
+	}
+	
+	if(he || !val)
+		return hep;
+
+	/* add a new entry for non-NULL val */
+	he = malloc(sizeof(*he));
+	if(he)
+	{
+		/* Key points to external data */
+		he->key = key;
+		he->klen = klen;
+
+		he->next = NULL;
+		he->hash = hash;
+		he->val	= val;
+	 
+		*hep = he;		
+		ht->count++;
+	}
+	
+	return hep;
+}
+
+void* 
+ckcapi_hash_get(CkCapiHash* ht, const void *key, size_t klen)
+{
+	HashEntry** he = find_entry(ht, key, klen, NULL);
+	if(he && *he)
+		return (void*)((*he)->val);
+	else
+		return NULL;
+}
+
+int 
+ckcapi_hash_set(CkCapiHash* ht, const void* key, size_t klen, void* val)
+{
+	HashEntry** hep = find_entry(ht, key, klen, val);	
+	if(hep && *hep) 
+	{
+		/* replace entry */
+		(*hep)->val = val;
+			
+		/* check that the collision rate isn't too high */
+		if(ht->count > ht->max) 
+		{
+			if(!expand_array(ht))
+				return 0;
+		}
+
+		return 1;
+	}
+	
+	return 0;
+}
+
+void* 
+ckcapi_hash_rem(CkCapiHash* ht, const void* key, size_t klen)
+{
+	HashEntry** hep = find_entry(ht, key, klen, NULL);
+	void* val = NULL;
+
+	if(hep && *hep)
+	{
+		HashEntry* old = *hep;
+		*hep = (*hep)->next;
+		--ht->count;
+		val = (void*)old->val;
+		free(old);
+	}
+	
+	return val;
+}
+		
+size_t 
+ckcapi_hash_count(CkCapiHash* ht)
+{
+	return ht->count;
+}