From 4928a4bff079c140d261cb3fefdc07c60c0bdebf Mon Sep 17 00:00:00 2001 From: Stef Walter Date: Fri, 27 Apr 2007 20:37:40 +0000 Subject: A bunch more changes, that implement almost complete find and get support. --- ckcapi-util.c | 336 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 313 insertions(+), 23 deletions(-) (limited to 'ckcapi-util.c') 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 +#include #include - - - #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 + */ + +/* 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 + * . + * + * 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 + */ + + 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; +} -- cgit v1.2.3