From 308a776372eb1560480fbfcb5ef9d918a7a1454f Mon Sep 17 00:00:00 2001 From: Stef Walter Date: Wed, 27 Jul 2011 11:24:55 +0200 Subject: Reimplement and remove apache licensed bits of code. * Reimplement the various bits of the hash table that were still based on the apache apr code. Use different algorithms for hashing, lookup and other stuff. * Use this as an opportunity to cleanup that code and make it more legible. https://bugzilla.redhat.com/show_bug.cgi?id=725905 --- COPYING | 22 +-- p11-kit/Makefile.am | 2 +- p11-kit/conf.c | 50 +++--- p11-kit/conf.h | 12 +- p11-kit/hash.c | 473 ---------------------------------------------------- p11-kit/hash.h | 195 ---------------------- p11-kit/hashmap.c | 372 +++++++++++++++++++++++++++++++++++++++++ p11-kit/hashmap.h | 172 +++++++++++++++++++ p11-kit/modules.c | 62 +++---- p11-kit/pin.c | 6 +- p11-kit/proxy.c | 8 +- tests/conf-test.c | 64 +++---- tests/hash-test.c | 158 +++++++++--------- 13 files changed, 726 insertions(+), 870 deletions(-) delete mode 100644 p11-kit/hash.c delete mode 100644 p11-kit/hash.h create mode 100644 p11-kit/hashmap.c create mode 100644 p11-kit/hashmap.h diff --git a/COPYING b/COPYING index 2a960a4..40fd587 100644 --- a/COPYING +++ b/COPYING @@ -24,24 +24,4 @@ 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. - - - - -================================================================================ - PORTIONS COPYRIGHT: - - 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. +DAMAGE. \ No newline at end of file diff --git a/p11-kit/Makefile.am b/p11-kit/Makefile.am index 9366a05..4164412 100644 --- a/p11-kit/Makefile.am +++ b/p11-kit/Makefile.am @@ -15,7 +15,7 @@ MODULE_SRCS = \ util.c util.h \ conf.c conf.h \ debug.c debug.h \ - hash.c hash.h \ + hashmap.c hashmap.h \ modules.c \ pin.c \ proxy.c \ diff --git a/p11-kit/conf.c b/p11-kit/conf.c index 6b66288..55e0268 100644 --- a/p11-kit/conf.c +++ b/p11-kit/conf.c @@ -206,16 +206,16 @@ read_config_file (const char* filename, int flags) } int -_p11_conf_merge_defaults (hash_t *ht, hash_t *defaults) +_p11_conf_merge_defaults (hashmap *map, hashmap *defaults) { - hash_iter_t hi; + hashiter iter; void *key; void *value; - hash_iterate (defaults, &hi); - while (hash_next (&hi, &key, &value)) { + hash_iterate (defaults, &iter); + while (hash_next (&iter, &key, &value)) { /* Only override if not set */ - if (hash_get (ht, key)) + if (hash_get (map, key)) continue; key = strdup (key); if (key == NULL) { @@ -228,7 +228,7 @@ _p11_conf_merge_defaults (hash_t *ht, hash_t *defaults) errno = ENOMEM; return -1; } - if (!hash_set (ht, key, value)) { + if (!hash_set (map, key, value)) { free (key); free (value); errno = ENOMEM; @@ -241,12 +241,12 @@ _p11_conf_merge_defaults (hash_t *ht, hash_t *defaults) return 0; } -hash_t* +hashmap * _p11_conf_parse_file (const char* filename, int flags) { char *name; char *value; - hash_t *ht = NULL; + hashmap *map = NULL; char *data; char *next; char *end; @@ -261,8 +261,8 @@ _p11_conf_parse_file (const char* filename, int flags) if (!data) return NULL; - ht = hash_create (hash_string_hash, hash_string_equal, free, free); - if (ht == NULL) { + map = hash_create (hash_string_hash, hash_string_equal, free, free); + if (map == NULL) { free (data); errno = ENOMEM; return NULL; @@ -308,7 +308,7 @@ _p11_conf_parse_file (const char* filename, int flags) debug ("config value: %s: %s", name, value); - if (!hash_set (ht, name, value)) { + if (!hash_set (map, name, value)) { free (name); free (value); error = ENOMEM; @@ -319,12 +319,12 @@ _p11_conf_parse_file (const char* filename, int flags) free (data); if (error != 0) { - hash_free (ht); - ht = NULL; + hash_free (map); + map = NULL; errno = error; } - return ht; + return map; } static char* @@ -355,7 +355,7 @@ expand_user_path (const char *path) } static int -user_config_mode (hash_t *config, int defmode) +user_config_mode (hashmap *config, int defmode) { const char *mode; @@ -377,13 +377,13 @@ user_config_mode (hash_t *config, int defmode) } } -hash_t* +hashmap * _p11_conf_load_globals (const char *system_conf, const char *user_conf, int *user_mode) { - hash_t *config = NULL; - hash_t *uconfig = NULL; - hash_t *result = NULL; + hashmap *config = NULL; + hashmap *uconfig = NULL; + hashmap *result = NULL; char *path = NULL; int error = 0; int mode; @@ -459,10 +459,10 @@ finished: } static int -load_config_from_file (const char *configfile, const char *name, hash_t *configs) +load_config_from_file (const char *configfile, const char *name, hashmap *configs) { - hash_t *config; - hash_t *prev; + hashmap *config; + hashmap *prev; char *key; int error = 0; @@ -498,7 +498,7 @@ load_config_from_file (const char *configfile, const char *name, hash_t *configs } static int -load_configs_from_directory (const char *directory, hash_t *configs) +load_configs_from_directory (const char *directory, hashmap *configs) { struct dirent *dp; struct stat st; @@ -566,10 +566,10 @@ load_configs_from_directory (const char *directory, hash_t *configs) return count; } -hash_t* +hashmap * _p11_conf_load_modules (int mode, const char *system_dir, const char *user_dir) { - hash_t *configs; + hashmap *configs; char *path; int error = 0; diff --git a/p11-kit/conf.h b/p11-kit/conf.h index dc48210..dccaebf 100644 --- a/p11-kit/conf.h +++ b/p11-kit/conf.h @@ -36,7 +36,7 @@ #ifndef __CONF_H__ #define __CONF_H__ -#include "hash.h" +#include "hashmap.h" enum { CONF_IGNORE_MISSING = 0x01, @@ -51,19 +51,19 @@ enum { typedef void (*conf_error_func) (const char *message); -int _p11_conf_merge_defaults (hash_t *config, - hash_t *defaults); +int _p11_conf_merge_defaults (hashmap *config, + hashmap *defaults); /* Returns a hash of char *key -> char *value */ -hash_t* _p11_conf_parse_file (const char *filename, +hashmap * _p11_conf_parse_file (const char *filename, int flags); /* Returns a hash of char *key -> char *value */ -hash_t* _p11_conf_load_globals (const char *system_conf, const char *user_conf, +hashmap * _p11_conf_load_globals (const char *system_conf, const char *user_conf, int *user_mode); /* Returns a hash of char* name -> hash_t *config */ -hash_t* _p11_conf_load_modules (int user_mode, const char *system_dir, +hashmap * _p11_conf_load_modules (int user_mode, const char *system_dir, const char *user_dir); #endif /* __CONF_H__ */ diff --git a/p11-kit/hash.c b/p11-kit/hash.c deleted file mode 100644 index d116916..0000000 --- a/p11-kit/hash.c +++ /dev/null @@ -1,473 +0,0 @@ -/* - * Copyright (c) 2004 Stefan Walter - * Copyright (c) 2011 Collabora Ltd. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above - * copyright notice, this list of conditions and the - * following disclaimer. - * * 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. - * * The names of contributors to this software may not be - * used to endorse or promote products derived from this - * software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS 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 - * COPYRIGHT OWNER OR 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. - */ - -/* - * 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. - */ - -#include - -#include -#include -#include - -#include "hash.h" - -/* - * 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 hash_entry hash_entry_t; - -struct hash_entry -{ - hash_entry_t* next; - unsigned int hash; - void* key; - void* val; -}; - -/* - * 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 hash { - hash_entry_t** array; - unsigned int count; - unsigned int max; - hash_hash_func hash_func; - hash_equal_func equal_func; - hash_destroy_func key_destroy_func; - hash_destroy_func value_destroy_func; -}; - -#define INITIAL_MAX 15 /* tunable == 2^n - 1 */ -#define int_malloc malloc -#define int_calloc calloc -#define int_free free - -static hash_entry_t** -alloc_array(hash_t* ht, unsigned int max) -{ - return (hash_entry_t**)int_calloc (sizeof (*(ht->array)), (max + 1)); -} - -hash_t* -hash_create (hash_hash_func hash_func, - hash_equal_func equal_func, - hash_destroy_func key_destroy_func, - hash_destroy_func value_destroy_func) -{ - hash_t* ht; - - assert (hash_func); - assert (equal_func); - - ht = int_malloc (sizeof (hash_t)); - if (ht) { - ht->count = 0; - ht->max = INITIAL_MAX; - ht->hash_func = hash_func; - ht->equal_func = equal_func; - ht->key_destroy_func = key_destroy_func; - ht->value_destroy_func = value_destroy_func; - ht->array = alloc_array (ht, ht->max); - if (!ht->array) { - int_free (ht); - return NULL; - } - } - return ht; -} - -static hash_entry_t* -next_entry (hash_iter_t* hi) -{ - hash_entry_t *he = hi->next; - while (!he) { - if (hi->index > hi->ht->max) - return NULL; - he = hi->ht->array[hi->index++]; - } - hi->next = he->next; - return he; -} - - -int -hash_next (hash_iter_t* hi, void **key, void **value) -{ - hash_entry_t *he = next_entry (hi); - if (he == NULL) - return 0; - if (key) - *key = he->key; - if (value) - *value = he->val; - return 1; -} - -void -hash_iterate (hash_t* ht, hash_iter_t *hi) -{ - hi->ht = ht; - hi->index = 0; - hi->next = NULL; -} - -static int -expand_array (hash_t* ht) -{ - hash_iter_t hi; - hash_entry_t *he; - hash_entry_t **new_array; - unsigned int new_max; - - new_max = ht->max * 2 + 1; - new_array = alloc_array (ht, new_max); - - if(!new_array) - return 0; - - hash_iterate (ht, &hi); - while ((he = next_entry (&hi)) != NULL) { - unsigned int i = he->hash & new_max; - he->next = new_array[i]; - new_array[i] = he; - } - - if(ht->array) - int_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 hash_entry_t** -find_entry (hash_t* ht, const void* key, int create) -{ - hash_entry_t** hep; - hash_entry_t* he; - unsigned int hash; - - /* Perform the hashing */ - 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 && ht->equal_func (he->key, key)) - break; - } - - if(he || !create) - return hep; - - /* add a new entry for non-NULL val */ - he = int_malloc (sizeof (*he)); - - if(he) { - he->key = (void*)key; - he->next = NULL; - he->hash = hash; - he->val = NULL; - - *hep = he; - ht->count++; - } - - return hep; -} - -void* -hash_get (hash_t* ht, const void *key) -{ - hash_entry_t** he = find_entry (ht, key, 0); - if (he && *he) - return (void*)((*he)->val); - else - return NULL; -} - -int -hash_set (hash_t* ht, void* key, void* val) -{ - hash_entry_t** hep = find_entry (ht, key, 1); - if(hep && *hep) { - if ((*hep)->val && ht->value_destroy_func) - ht->value_destroy_func ((*hep)->val); - - /* 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; -} - -int -hash_steal (hash_t *ht, const void *key, void **stolen_key, void **stolen_value) -{ - hash_entry_t** hep = find_entry (ht, key, 0); - - if (hep && *hep) { - hash_entry_t* old = *hep; - *hep = (*hep)->next; - --ht->count; - if (stolen_key) - *stolen_key = old->key; - if (stolen_value) - *stolen_value = old->val; - free (old); - return 1; - } - - return 0; - -} - -int -hash_remove (hash_t *ht, const void *key) -{ - void *old_key; - void *old_value; - - if (!hash_steal (ht, key, &old_key, &old_value)) - return 0; - - if (ht->key_destroy_func) - ht->key_destroy_func (old_key); - if (ht->value_destroy_func) - ht->value_destroy_func (old_value); - return 1; -} - -void -hash_clear (hash_t* ht) -{ - hash_entry_t *he, *next; - int i; - - /* Free all entries in the array */ - for (i = 0; i < ht->max; ++i) { - he = ht->array[i]; - while (he) { - next = he->next; - if (ht->key_destroy_func) - ht->key_destroy_func (he->key); - if (ht->value_destroy_func) - ht->value_destroy_func (he->val); - free (he); - he = next; - } - } - - memset (ht->array, 0, ht->max * sizeof (hash_entry_t*)); - ht->count = 0; -} - -void -hash_free (hash_t* ht) -{ - hash_entry_t *he; - hash_iter_t hi; - - if (!ht) - return; - - hash_iterate (ht, &hi); - while ((he = next_entry (&hi)) != NULL) { - if (ht->key_destroy_func) - ht->key_destroy_func (he->key); - if (ht->value_destroy_func) - ht->value_destroy_func (he->val); - free (he); - } - - if (ht->array) - int_free (ht->array); - - int_free (ht); -} - -unsigned int -hash_count (hash_t* ht) -{ - return ht->count; -} - -unsigned int -hash_string_hash (const void *string) -{ - unsigned int hash; - const unsigned char *p; - - assert (string); - - /* - * 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 = string; *p; p++) - hash = hash * 33 + *p; - - return hash; -} - -int -hash_string_equal (const void *string_one, const void *string_two) -{ - assert (string_one); - assert (string_two); - - return strcmp (string_one, string_two) == 0; -} - -unsigned int -hash_ulongptr_hash (const void *to_ulong) -{ - assert (to_ulong); - return (unsigned int)*((unsigned long*)to_ulong); -} - -int -hash_ulongptr_equal (const void *ulong_one, const void *ulong_two) -{ - assert (ulong_one); - assert (ulong_two); - return *((unsigned long*)ulong_one) == *((unsigned long*)ulong_two); -} - -unsigned int -hash_intptr_hash (const void *to_int) -{ - assert (to_int); - return (unsigned int)*((int*)to_int); -} - -int -hash_intptr_equal (const void *int_one, const void *int_two) -{ - assert (int_one); - assert (int_two); - return *((int*)int_one) == *((int*)int_two); -} - -unsigned int -hash_direct_hash (const void *ptr) -{ - return (unsigned int)(unsigned long)ptr; -} - -int -hash_direct_equal (const void *ptr_one, const void *ptr_two) -{ - return ptr_one == ptr_two; -} diff --git a/p11-kit/hash.h b/p11-kit/hash.h deleted file mode 100644 index 8c3060a..0000000 --- a/p11-kit/hash.h +++ /dev/null @@ -1,195 +0,0 @@ -/* - * Copyright (c) 2004 Stefan Walter - * Copyright (c) 2011 Collabora Ltd. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * * Redistributions of source code must retain the above - * copyright notice, this list of conditions and the - * following disclaimer. - * * 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. - * * The names of contributors to this software may not be - * used to endorse or promote products derived from this - * software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS 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 - * COPYRIGHT OWNER OR 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. - * - * Author: Stef Waler - */ - -/* - * 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. - */ - -#ifndef __HSH_H__ -#define __HSH_H__ - -#include - -/* - * ARGUMENT DOCUMENTATION - * - * ht: The hashtable - * key: Pointer to the key value - * klen: The length of the key - * val: Pointer to the value - * hi: A hashtable iterator - * stamp: A unix timestamp - */ - - -/* ---------------------------------------------------------------------------------- - * TYPES - */ - -/* Abstract type for hash tables. */ -typedef struct hash hash_t; - -/* Type for scanning hash tables. */ -typedef struct hash_iter -{ - hash_t* ht; - struct hash_entry* next; - unsigned int index; -} hash_iter_t; - -typedef unsigned int (*hash_hash_func) (const void *data); - -typedef int (*hash_equal_func) (const void *one, - const void *two); - -typedef void (*hash_destroy_func) (void *data); - -/* ----------------------------------------------------------------------------- - * MAIN - */ - -/* - * hash_create : Create a hash table - * - returns an allocated hashtable - */ -hash_t* hash_create (hash_hash_func hash_func, - hash_equal_func equal_func, - hash_destroy_func key_destroy_func, - hash_destroy_func value_destroy_func); - -/* - * hash_free : Free a hash table - */ -void hash_free (hash_t* ht); - -/* - * hash_count: Number of values in hash table - * - returns the number of entries in hash table - */ -unsigned int hash_count (hash_t* ht); - -/* - * hash_get: Retrieves a value from the hash table - * - returns the value of the entry - */ -void* hash_get (hash_t* ht, - const void *key); - -/* - * hash_set: Set a value in the hash table - * - returns 1 if the entry was added properly - */ -int hash_set (hash_t* ht, - void *key, - void *value); - -/* - * hash_remove: Remove a value from the hash table - * - returns 1 if the entry was found - */ -int hash_remove (hash_t* ht, - const void* key); - -/* - * hash_steal: Remove a value from the hash table without calling destroy funcs - * - returns 1 if the entry was found - */ -int hash_steal (hash_t *ht, - const void *key, - void **stolen_key, - void **stolen_value); - -/* - * hash_first: Start enumerating through the hash table - * - returns a hash iterator - */ -void hash_iterate (hash_t* ht, - hash_iter_t *hi); - -/* - * hash_next: Enumerate through hash table - * - sets key and value to key and/or value - * - returns whether there was another entry - */ -int hash_next (hash_iter_t* hi, - void **key, - void **value); - -/* - * hash_clear: Clear all values from has htable. - */ -void hash_clear (hash_t* ht); - -/* ----------------------------------------------------------------------------- - * HASH FUNCTIONS - */ - -unsigned int hash_string_hash (const void *string); - -int hash_string_equal (const void *string_one, - const void *string_two); - -unsigned int hash_ulongptr_hash (const void *to_ulong); - -int hash_ulongptr_equal (const void *ulong_one, - const void *ulong_two); - -unsigned int hash_intptr_hash (const void *to_int); - -int hash_intptr_equal (const void *int_one, - const void *int_two); - -unsigned int hash_direct_hash (const void *ptr); - -int hash_direct_equal (const void *ptr_one, - const void *ptr_two); - -#endif /* __HASH_H__ */ diff --git a/p11-kit/hashmap.c b/p11-kit/hashmap.c new file mode 100644 index 0000000..9026827 --- /dev/null +++ b/p11-kit/hashmap.c @@ -0,0 +1,372 @@ +/* + * Copyright (c) 2004 Stefan Walter + * Copyright (c) 2011 Collabora Ltd. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * * 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. + * * The names of contributors to this software may not be + * used to endorse or promote products derived from this + * software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS 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 + * COPYRIGHT OWNER OR 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. + */ + +#include "config.h" + +#include "hashmap.h" + +#include + +#include +#include +#include + +struct _hashmap { + hash_hash_func hash_func; + hash_equal_func equal_func; + hash_destroy_func key_destroy_func; + hash_destroy_func value_destroy_func; + + struct _hashbucket **buckets; + unsigned int num_items; + unsigned int num_buckets; +}; + +typedef struct _hashbucket { + void *key; + unsigned int hashed; + void *value; + struct _hashbucket *next; +} hashbucket; + +static hashbucket * +next_entry (hashiter *iter) +{ + hashbucket *bucket = iter->next; + while (!bucket) { + if (iter->index > iter->map->num_buckets) + return NULL; + bucket = iter->map->buckets[iter->index++]; + } + iter->next = bucket->next; + return bucket; +} + + +int +hash_next (hashiter *iter, void **key, void **value) +{ + hashbucket *bucket = next_entry (iter); + if (bucket == NULL) + return 0; + if (key) + *key = bucket->key; + if (value) + *value = bucket->value; + return 1; +} + +void +hash_iterate (hashmap *map, hashiter *iter) +{ + iter->map = map; + iter->index = 0; + iter->next = NULL; +} + +static hashbucket ** +lookup_or_create_bucket (hashmap *map, const void *key, int create) +{ + hashbucket **bucketp; + unsigned int hash; + + /* Perform the hashing */ + hash = map->hash_func (key); + + /* scan linked list */ + for (bucketp = &map->buckets[map->num_buckets & hash]; + *bucketp != NULL; bucketp = &(*bucketp)->next) { + if((*bucketp)->hashed == hash && map->equal_func ((*bucketp)->key, key)) + break; + } + + if ((*bucketp) != NULL || !create) + return bucketp; + + /* add a new entry for non-NULL val */ + (*bucketp) = calloc (sizeof (hashbucket), 1); + + if (*bucketp != NULL) { + (*bucketp)->key = (void*)key; + (*bucketp)->hashed = hash; + map->num_items++; + } + + return bucketp; +} + +void* +hash_get (hashmap *map, const void *key) +{ + hashbucket **bucketp; + + bucketp = lookup_or_create_bucket (map, key, 0); + if (bucketp && *bucketp) + return (void*)((*bucketp)->value); + else + return NULL; +} + +int +hash_set (hashmap *map, void *key, void *val) +{ + hashbucket **bucketp; + hashiter iter; + hashbucket *bucket; + hashbucket **new_buckets; + unsigned int num_buckets; + + bucketp = lookup_or_create_bucket (map, key, 1); + if(bucketp && *bucketp) { + + /* Destroy the previous value */ + if ((*bucketp)->value && map->value_destroy_func) + map->value_destroy_func ((*bucketp)->value); + + /* replace entry */ + (*bucketp)->value = val; + + /* check that the collision rate isn't too high */ + if (map->num_items > map->num_buckets) { + num_buckets = map->num_buckets * 2 + 1; + new_buckets = (hashbucket **)calloc (sizeof (hashbucket *), + num_buckets + 1); + + /* Ignore failures, maybe we can expand later */ + if(new_buckets) { + hash_iterate (map, &iter); + while ((bucket = next_entry (&iter)) != NULL) { + unsigned int i = bucket->hashed & num_buckets; + bucket->next = new_buckets[i]; + new_buckets[i] = bucket; + } + + free (map->buckets); + map->buckets = new_buckets; + map->num_buckets = num_buckets; + } + } + + return 1; + } + + return 0; +} + +int +hash_steal (hashmap *map, const void *key, void **stolen_key, void **stolen_value) +{ + hashbucket **bucketp; + + bucketp = lookup_or_create_bucket (map, key, 0); + if (bucketp && *bucketp) { + hashbucket *old = *bucketp; + *bucketp = (*bucketp)->next; + --map->num_items; + if (stolen_key) + *stolen_key = old->key; + if (stolen_value) + *stolen_value = old->value; + free (old); + return 1; + } + + return 0; + +} + +int +hash_remove (hashmap *map, const void *key) +{ + void *old_key; + void *old_value; + + if (!hash_steal (map, key, &old_key, &old_value)) + return 0; + + if (map->key_destroy_func) + map->key_destroy_func (old_key); + if (map->value_destroy_func) + map->value_destroy_func (old_value); + return 1; +} + +void +hash_clear (hashmap *map) +{ + hashbucket *bucket, *next; + int i; + + /* Free all entries in the array */ + for (i = 0; i < map->num_buckets; ++i) { + bucket = map->buckets[i]; + while (bucket != NULL) { + next = bucket->next; + if (map->key_destroy_func) + map->key_destroy_func (bucket->key); + if (map->value_destroy_func) + map->value_destroy_func (bucket->value); + free (bucket); + bucket = next; + } + } + + memset (map->buckets, 0, map->num_buckets * sizeof (hashbucket *)); + map->num_items = 0; +} + +hashmap * +hash_create (hash_hash_func hash_func, + hash_equal_func equal_func, + hash_destroy_func key_destroy_func, + hash_destroy_func value_destroy_func) +{ + hashmap *map; + + assert (hash_func); + assert (equal_func); + + map = malloc (sizeof (hashmap)); + if (map) { + map->hash_func = hash_func; + map->equal_func = equal_func; + map->key_destroy_func = key_destroy_func; + map->value_destroy_func = value_destroy_func; + + map->num_buckets = 9; + map->buckets = (hashbucket **)calloc (sizeof (hashbucket *), + map->num_buckets + 1); + if (!map->buckets) { + free (map); + return NULL; + } + + map->num_buckets = 0; + } + + return map; +} + +void +hash_free (hashmap *map) +{ + hashbucket *bucket; + hashiter iter; + + if (!map) + return; + + hash_iterate (map, &iter); + while ((bucket = next_entry (&iter)) != NULL) { + if (map->key_destroy_func) + map->key_destroy_func (bucket->key); + if (map->value_destroy_func) + map->value_destroy_func (bucket->value); + free (bucket); + } + + if (map->buckets) + free (map->buckets); + + free (map); +} + +unsigned int +hash_size (hashmap *map) +{ + return map->num_items; +} + +unsigned int +hash_string_hash (const void *string) +{ + const char *p = string; + unsigned int hash = *p; + + if (hash) + for (p += 1; *p != '\0'; p++) + hash = (hash << 5) - hash + *p; + + return hash; +} + +int +hash_string_equal (const void *string_one, const void *string_two) +{ + assert (string_one); + assert (string_two); + + return strcmp (string_one, string_two) == 0; +} + +unsigned int +hash_ulongptr_hash (const void *to_ulong) +{ + assert (to_ulong); + return (unsigned int)*((unsigned long*)to_ulong); +} + +int +hash_ulongptr_equal (const void *ulong_one, const void *ulong_two) +{ + assert (ulong_one); + assert (ulong_two); + return *((unsigned long*)ulong_one) == *((unsigned long*)ulong_two); +} + +unsigned int +hash_intptr_hash (const void *to_int) +{ + assert (to_int); + return (unsigned int)*((int*)to_int); +} + +int +hash_intptr_equal (const void *int_one, const void *int_two) +{ + assert (int_one); + assert (int_two); + return *((int*)int_one) == *((int*)int_two); +} + +unsigned int +hash_direct_hash (const void *ptr) +{ + return (unsigned int)(unsigned long)ptr; +} + +int +hash_direct_equal (const void *ptr_one, const void *ptr_two) +{ + return ptr_one == ptr_two; +} diff --git a/p11-kit/hashmap.h b/p11-kit/hashmap.h new file mode 100644 index 0000000..a9292b7 --- /dev/null +++ b/p11-kit/hashmap.h @@ -0,0 +1,172 @@ +/* + * Copyright (c) 2004 Stefan Walter + * Copyright (c) 2011 Collabora Ltd. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * * 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. + * * The names of contributors to this software may not be + * used to endorse or promote products derived from this + * software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS 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 + * COPYRIGHT OWNER OR 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. + * + * Author: Stef Waler + */ + +#ifndef HASHMAP_H_ +#define HASHMAP_H_ + +#include + +/* + * ARGUMENT DOCUMENTATION + * + * map: The hashmap + * key: Pointer to the key value + * val: Pointer to the value + * iter: A hashmap iterator + */ + + +/* ---------------------------------------------------------------------------------- + * TYPES + */ + +/* Abstract type for hash maps. */ +typedef struct _hashmap hashmap; + +/* Type for scanning hash tables. */ +typedef struct _hashiter { + hashmap *map; + struct _hashbucket *next; + unsigned int index; +} hashiter; + +typedef unsigned int (*hash_hash_func) (const void *data); + +typedef int (*hash_equal_func) (const void *one, + const void *two); + +typedef void (*hash_destroy_func) (void *data); + +/* ----------------------------------------------------------------------------- + * MAIN + */ + +/* + * hash_create : Create a hash table + * - returns an allocated hashtable + */ +hashmap* hash_create (hash_hash_func hash_func, + hash_equal_func equal_func, + hash_destroy_func key_destroy_func, + hash_destroy_func value_destroy_func); + +/* + * hash_free : Free a hash table + */ +void hash_free (hashmap *map); + +/* + * hash_size: Number of values in hash table + * - returns the number of entries in hash table + */ +unsigned int hash_size (hashmap *map); + +/* + * hash_get: Retrieves a value from the hash table + * - returns the value of the entry + */ +void* hash_get (hashmap *map, + const void *key); + +/* + * hash_set: Set a value in the hash table + * - returns 1 if the entry was added properly + */ +int hash_set (hashmap *map, + void *key, + void *value); + +/* + * hash_remove: Remove a value from the hash table + * - returns 1 if the entry was found + */ +int hash_remove (hashmap *map, + const void *key); + +/* + * hash_steal: Remove a value from the hash table without calling destroy funcs + * - returns 1 if the entry was found + */ +int hash_steal (hashmap *map, + const void *key, + void **stolen_key, + void **stolen_value); + +/* + * hash_first: Start enumerating through the hash table + * - returns a hash iterator + */ +void hash_iterate (hashmap *map, + hashiter *iter); + +/* + * hash_next: Enumerate through hash table + * - sets key and value to key and/or value + * - returns whether there was another entry + */ +int hash_next (hashiter *iter, + void **key, + void **value); + +/* + * hash_clear: Clear all values from has htable. + */ +void hash_clear (hashmap *map); + +/* ----------------------------------------------------------------------------- + * HASH FUNCTIONS + */ + +unsigned int hash_string_hash (const void *string); + +int hash_string_equal (const void *string_one, + const void *string_two); + +unsigned int hash_ulongptr_hash (const void *to_ulong); + +int hash_ulongptr_equal (const void *ulong_one, + const void *ulong_two); + +unsigned int hash_intptr_hash (const void *to_int); + +int hash_intptr_equal (const void *int_one, + const void *int_two); + +unsigned int hash_direct_hash (const void *ptr); + +int hash_direct_equal (const void *ptr_one, + const void *ptr_two); + +#endif /* __HASHMAP_H__ */ diff --git a/p11-kit/modules.c b/p11-kit/modules.c index b7adf5e..97fb58f 100644 --- a/p11-kit/modules.c +++ b/p11-kit/modules.c @@ -38,7 +38,7 @@ #include "conf.h" #define DEBUG_FLAG DEBUG_LIB #include "debug.h" -#include "hash.h" +#include "hashmap.h" #include "pkcs11.h" #include "p11-kit.h" #include "private.h" @@ -100,7 +100,7 @@ typedef struct _Module { /* Registered modules */ char *name; - hash_t *config; + hashmap *config; /* Loaded modules */ void *dl_module; @@ -124,8 +124,8 @@ pthread_mutex_t _p11_mutex = PTHREAD_MUTEX_INITIALIZER; * we can audit thread safety easier. */ static struct _Shared { - hash_t *modules; - hash_t *config; + hashmap *modules; + hashmap *config; } gl = { NULL, NULL }; /* ----------------------------------------------------------------------------- @@ -314,7 +314,7 @@ load_module_from_file_unlocked (const char *path, Module **result) } static CK_RV -take_config_and_load_module_unlocked (char **name, hash_t **config) +take_config_and_load_module_unlocked (char **name, hashmap **config) { Module *mod, *prev; const char *path; @@ -383,11 +383,11 @@ take_config_and_load_module_unlocked (char **name, hash_t **config) static CK_RV load_registered_modules_unlocked (void) { - hash_iter_t hi; - hash_t *configs; + hashiter iter; + hashmap *configs; void *key; char *name; - hash_t *config; + hashmap *config; int mode; CK_RV rv; @@ -415,8 +415,8 @@ load_registered_modules_unlocked (void) * Now go through each config and turn it into a module. As we iterate * we steal the values of the config. */ - hash_iterate (configs, &hi); - while (hash_next (&hi, &key, NULL)) { + hash_iterate (configs, &iter); + while (hash_next (&iter, &key, NULL)) { if (!hash_steal (configs, key, (void**)&name, (void**)&config)) assert (0 && "not reached"); @@ -485,7 +485,7 @@ initialize_module_unlocked_reentrant (Module *mod) static void reinitialize_after_fork (void) { - hash_iter_t it; + hashiter iter; Module *mod; /* WARNING: This function must be reentrant */ @@ -494,8 +494,8 @@ reinitialize_after_fork (void) _p11_lock (); if (gl.modules) { - hash_iterate (gl.modules, &it); - while (hash_next (&it, NULL, (void**)&mod)) { + hash_iterate (gl.modules, &iter); + while (hash_next (&iter, NULL, (void **)&mod)) { mod->initialize_count = 0; /* WARNING: Reentrancy can occur here */ @@ -532,11 +532,11 @@ static void free_modules_when_no_refs_unlocked (void) { Module *mod; - hash_iter_t it; + hashiter iter; /* Check if any modules have a ref count */ - hash_iterate (gl.modules, &it); - while (hash_next (&it, NULL, (void**)&mod)) { + hash_iterate (gl.modules, &iter); + while (hash_next (&iter, NULL, (void **)&mod)) { if (mod->ref_count) return; } @@ -593,12 +593,12 @@ static Module* find_module_for_name_unlocked (const char *name) { Module *mod; - hash_iter_t it; + hashiter iter; assert (name); - hash_iterate (gl.modules, &it); - while (hash_next (&it, NULL, (void**)&mod)) + hash_iterate (gl.modules, &iter); + while (hash_next (&iter, NULL, (void **)&mod)) if (mod->ref_count && mod->name && strcmp (name, mod->name) == 0) return mod; return NULL; @@ -608,7 +608,7 @@ CK_RV _p11_kit_initialize_registered_unlocked_reentrant (void) { Module *mod; - hash_iter_t it; + hashiter iter; CK_RV rv; rv = init_globals_unlocked (); @@ -617,8 +617,8 @@ _p11_kit_initialize_registered_unlocked_reentrant (void) rv = load_registered_modules_unlocked (); if (rv == CKR_OK) { - hash_iterate (gl.modules, &it); - while (hash_next (&it, NULL, (void**)&mod)) { + hash_iterate (gl.modules, &iter); + while (hash_next (&iter, NULL, (void **)&mod)) { /* Skip all modules that aren't registered */ if (!mod->name) @@ -685,7 +685,7 @@ CK_RV _p11_kit_finalize_registered_unlocked_reentrant (void) { Module *mod; - hash_iter_t it; + hashiter iter; Module **to_finalize; int i, count; @@ -694,13 +694,13 @@ _p11_kit_finalize_registered_unlocked_reentrant (void) /* WARNING: This function must be reentrant */ - to_finalize = calloc (hash_count (gl.modules), sizeof (Module*)); + to_finalize = calloc (hash_size (gl.modules), sizeof (Module *)); if (!to_finalize) return CKR_HOST_MEMORY; count = 0; - hash_iterate (gl.modules, &it); - while (hash_next (&it, NULL, (void**)&mod)) { + hash_iterate (gl.modules, &iter); + while (hash_next (&iter, NULL, (void **)&mod)) { /* Skip all modules that aren't registered */ if (mod->name) @@ -767,13 +767,13 @@ _p11_kit_registered_modules_unlocked (void) { CK_FUNCTION_LIST_PTR_PTR result; Module *mod; - hash_iter_t it; + hashiter iter; int i = 0; - result = calloc (hash_count (gl.modules) + 1, sizeof (CK_FUNCTION_LIST_PTR)); + result = calloc (hash_size (gl.modules) + 1, sizeof (CK_FUNCTION_LIST_PTR)); if (result) { - hash_iterate (gl.modules, &it); - while (hash_next (&it, NULL, (void**)&mod)) { + hash_iterate (gl.modules, &iter); + while (hash_next (&iter, NULL, (void **)&mod)) { if (mod->ref_count && mod->name) result[i++] = mod->funcs; } @@ -891,7 +891,7 @@ p11_kit_registered_option (CK_FUNCTION_LIST_PTR module, const char *field) { Module *mod = NULL; char *option = NULL; - hash_t *config = NULL; + hashmap *config = NULL; _p11_lock (); diff --git a/p11-kit/pin.c b/p11-kit/pin.c index e0016ec..f24005a 100644 --- a/p11-kit/pin.c +++ b/p11-kit/pin.c @@ -36,7 +36,7 @@ #define DEBUG_FLAG DEBUG_PIN #include "debug.h" -#include "hash.h" +#include "hashmap.h" #include "pkcs11.h" #include "p11-kit.h" #include "pin.h" @@ -146,7 +146,7 @@ typedef struct _PinfileCallback { * we can audit thread safety easier. */ static struct _Shared { - hash_t *pinfiles; + hashmap *pinfiles; } gl = { NULL }; static void* @@ -304,7 +304,7 @@ p11_kit_pin_unregister_callback (const char *pinfile, p11_kit_pin_callback callb } /* When there are no more pinfiles, get rid of the hash table */ - if (hash_count (gl.pinfiles) == 0) { + if (hash_size (gl.pinfiles) == 0) { hash_free (gl.pinfiles); gl.pinfiles = NULL; } diff --git a/p11-kit/proxy.c b/p11-kit/proxy.c index 7069f71..c3c7e80 100644 --- a/p11-kit/proxy.c +++ b/p11-kit/proxy.c @@ -35,7 +35,7 @@ #include "config.h" -#include "hash.h" +#include "hashmap.h" #include "pkcs11.h" #include "p11-kit.h" #include "private.h" @@ -78,7 +78,7 @@ static struct _Shared { Mapping *mappings; unsigned int n_mappings; int mappings_refs; - hash_t *sessions; + hashmap *sessions; CK_ULONG last_handle; } gl = { NULL, 0, 0, NULL, FIRST_HANDLE }; @@ -553,14 +553,14 @@ proxy_C_CloseAllSessions (CK_SLOT_ID id) CK_RV rv = CKR_OK; Session *sess; CK_ULONG i, count = 0; - hash_iter_t iter; + hashiter iter; _p11_lock (); if (!gl.sessions) { rv = CKR_CRYPTOKI_NOT_INITIALIZED; } else { - to_close = calloc (sizeof (CK_SESSION_HANDLE), hash_count (gl.sessions)); + to_close = calloc (sizeof (CK_SESSION_HANDLE), hash_size (gl.sessions)); if (!to_close) { rv = CKR_HOST_MEMORY; } else { diff --git a/tests/conf-test.c b/tests/conf-test.c index ac2a37d..a273c7b 100644 --- a/tests/conf-test.c +++ b/tests/conf-test.c @@ -47,55 +47,55 @@ static void test_parse_conf_1 (CuTest *tc) { - hash_t *ht; + hashmap *map; const char *value; - ht = _p11_conf_parse_file (SRCDIR "/files/test-1.conf", 0); - CuAssertPtrNotNull (tc, ht); + map = _p11_conf_parse_file (SRCDIR "/files/test-1.conf", 0); + CuAssertPtrNotNull (tc, map); - value = hash_get (ht, "key1"); + value = hash_get (map, "key1"); CuAssertStrEquals (tc, "value1", value); - value = hash_get (ht, "with-colon"); + value = hash_get (map, "with-colon"); CuAssertStrEquals (tc, "value-of-colon", value); - value = hash_get (ht, "with-whitespace"); + value = hash_get (map, "with-whitespace"); CuAssertStrEquals (tc, "value-with-whitespace", value); - value = hash_get (ht, "embedded-comment"); + value = hash_get (map, "embedded-comment"); CuAssertStrEquals (tc, "this is # not a comment", value); - hash_free (ht); + hash_free (map); } static void test_parse_ignore_missing (CuTest *tc) { - hash_t *ht; + hashmap *map; - ht = _p11_conf_parse_file (SRCDIR "/files/non-existant.conf", CONF_IGNORE_MISSING); - CuAssertPtrNotNull (tc, ht); + map = _p11_conf_parse_file (SRCDIR "/files/non-existant.conf", CONF_IGNORE_MISSING); + CuAssertPtrNotNull (tc, map); - CuAssertIntEquals (tc, 0, hash_count (ht)); + CuAssertIntEquals (tc, 0, hash_size (map)); CuAssertPtrEquals (tc, NULL, (void*)p11_kit_message ()); - hash_free (ht); + hash_free (map); } static void test_parse_fail_missing (CuTest *tc) { - hash_t *ht; + hashmap *map; - ht = _p11_conf_parse_file (SRCDIR "/files/non-existant.conf", 0); - CuAssertPtrEquals (tc, ht, NULL); + map = _p11_conf_parse_file (SRCDIR "/files/non-existant.conf", 0); + CuAssertPtrEquals (tc, map, NULL); CuAssertPtrNotNull (tc, p11_kit_message ()); } static void test_merge_defaults (CuTest *tc) { - hash_t *values; - hash_t *defaults; + hashmap *values; + hashmap *defaults; values = hash_create (hash_string_hash, hash_string_equal, free, free); defaults = hash_create (hash_string_hash, hash_string_equal, free, free); @@ -122,7 +122,7 @@ static void test_load_globals_merge (CuTest *tc) { int user_mode = -1; - hash_t *config; + hashmap *config; _p11_kit_clear_message (); @@ -144,7 +144,7 @@ static void test_load_globals_no_user (CuTest *tc) { int user_mode = -1; - hash_t *config; + hashmap *config; _p11_kit_clear_message (); @@ -166,7 +166,7 @@ static void test_load_globals_user_sets_only (CuTest *tc) { int user_mode = -1; - hash_t *config; + hashmap *config; _p11_kit_clear_message (); @@ -188,7 +188,7 @@ static void test_load_globals_system_sets_only (CuTest *tc) { int user_mode = -1; - hash_t *config; + hashmap *config; _p11_kit_clear_message (); @@ -210,7 +210,7 @@ static void test_load_globals_system_sets_invalid (CuTest *tc) { int user_mode = -1; - hash_t *config; + hashmap *config; int error; _p11_kit_clear_message (); @@ -230,7 +230,7 @@ static void test_load_globals_user_sets_invalid (CuTest *tc) { int user_mode = -1; - hash_t *config; + hashmap *config; int error; _p11_kit_clear_message (); @@ -249,8 +249,8 @@ test_load_globals_user_sets_invalid (CuTest *tc) static void test_load_modules_merge (CuTest *tc) { - hash_t *configs; - hash_t *config; + hashmap *configs; + hashmap *config; _p11_kit_clear_message (); @@ -281,8 +281,8 @@ test_load_modules_merge (CuTest *tc) static void test_load_modules_user_none (CuTest *tc) { - hash_t *configs; - hash_t *config; + hashmap *configs; + hashmap *config; _p11_kit_clear_message (); @@ -311,8 +311,8 @@ test_load_modules_user_none (CuTest *tc) static void test_load_modules_user_only (CuTest *tc) { - hash_t *configs; - hash_t *config; + hashmap *configs; + hashmap *config; _p11_kit_clear_message (); @@ -341,8 +341,8 @@ test_load_modules_user_only (CuTest *tc) static void test_load_modules_no_user (CuTest *tc) { - hash_t *configs; - hash_t *config; + hashmap *configs; + hashmap *config; _p11_kit_clear_message (); diff --git a/tests/hash-test.c b/tests/hash-test.c index 3349c26..73edeab 100644 --- a/tests/hash-test.c +++ b/tests/hash-test.c @@ -39,16 +39,16 @@ #include #include -#include "hash.h" +#include "hashmap.h" static void test_hash_create (CuTest *tc) { - hash_t *ht; + hashmap *map; - ht = hash_create (hash_direct_hash, hash_direct_equal, NULL, NULL); - CuAssertPtrNotNull (tc, ht); - hash_free (ht); + map = hash_create (hash_direct_hash, hash_direct_equal, NULL, NULL); + CuAssertPtrNotNull (tc, map); + hash_free (map); } static void @@ -74,15 +74,15 @@ destroy_value (void *data) static void test_hash_free_destroys (CuTest *tc) { - hash_t *ht; + hashmap *map; int key = 0; int value = 0; - ht = hash_create (hash_direct_hash, hash_direct_equal, destroy_key, destroy_value); - CuAssertPtrNotNull (tc, ht); - if (!hash_set (ht, &key, &value)) + map = hash_create (hash_direct_hash, hash_direct_equal, destroy_key, destroy_value); + CuAssertPtrNotNull (tc, map); + if (!hash_set (map, &key, &value)) CuFail (tc, "should not be reached"); - hash_free (ht); + hash_free (map); CuAssertIntEquals (tc, 1, key); CuAssertIntEquals (tc, 2, value); @@ -91,30 +91,30 @@ test_hash_free_destroys (CuTest *tc) static void test_hash_iterate (CuTest *tc) { - hash_t *ht; - hash_iter_t hi; + hashmap *map; + hashiter iter; int key = 1; int value = 2; void *pkey; void *pvalue; int ret; - ht = hash_create (hash_direct_hash, hash_direct_equal, NULL, NULL); - CuAssertPtrNotNull (tc, ht); - if (!hash_set (ht, &key, &value)) + map = hash_create (hash_direct_hash, hash_direct_equal, NULL, NULL); + CuAssertPtrNotNull (tc, map); + if (!hash_set (map, &key, &value)) CuFail (tc, "should not be reached"); - hash_iterate (ht, &hi); + hash_iterate (map, &iter); - ret = hash_next (&hi, &pkey, &pvalue); + ret = hash_next (&iter, &pkey, &pvalue); CuAssertIntEquals (tc, 1, ret); CuAssertPtrEquals (tc, pkey, &key); CuAssertPtrEquals (tc, pvalue, &value); - ret = hash_next (&hi, &pkey, &pvalue); + ret = hash_next (&iter, &pkey, &pvalue); CuAssertIntEquals (tc, 0, ret); - hash_free (ht); + hash_free (map); } static void @@ -123,14 +123,14 @@ test_hash_set_get (CuTest *tc) char *key = "KEY"; char *value = "VALUE"; char *check; - hash_t *ht; + hashmap *map; - ht = hash_create (hash_string_hash, hash_string_equal, NULL, NULL); - hash_set (ht, key, value); - check = hash_get (ht, key); + map = hash_create (hash_string_hash, hash_string_equal, NULL, NULL); + hash_set (map, key, value); + check = hash_get (map, key); CuAssertPtrEquals (tc, check, value); - hash_free (ht); + hash_free (map); } static void @@ -139,26 +139,26 @@ test_hash_set_get_remove (CuTest *tc) char *key = "KEY"; char *value = "VALUE"; char *check; - hash_t *ht; + hashmap *map; int ret; - ht = hash_create (hash_string_hash, hash_string_equal, NULL, NULL); + map = hash_create (hash_string_hash, hash_string_equal, NULL, NULL); - if (!hash_set (ht, key, value)) + if (!hash_set (map, key, value)) CuFail (tc, "should not be reached"); - check = hash_get (ht, key); + check = hash_get (map, key); CuAssertPtrEquals (tc, check, value); - ret = hash_remove (ht, key); + ret = hash_remove (map, key); CuAssertIntEquals (tc, ret, 1); - ret = hash_remove (ht, key); + ret = hash_remove (map, key); CuAssertIntEquals (tc, ret, 0); - check = hash_get (ht, key); + check = hash_get (map, key); CuAssert (tc, "should be null", check == NULL); - hash_free (ht); + hash_free (map); } static void @@ -167,38 +167,38 @@ test_hash_set_get_clear (CuTest *tc) char *key = "KEY"; char *value = "VALUE"; char *check; - hash_t *ht; + hashmap *map; - ht = hash_create (hash_direct_hash, hash_direct_equal, NULL, NULL); + map = hash_create (hash_direct_hash, hash_direct_equal, NULL, NULL); - if (!hash_set (ht, key, value)) + if (!hash_set (map, key, value)) CuFail (tc, "should not be reached"); - check = hash_get (ht, key); + check = hash_get (map, key); CuAssertPtrEquals (tc, check, value); - hash_clear (ht); + hash_clear (map); - check = hash_get (ht, key); + check = hash_get (map, key); CuAssert (tc, "should be null", check == NULL); - hash_free (ht); + hash_free (map); } static void test_hash_remove_destroys (CuTest *tc) { - hash_t *ht; + hashmap *map; int key = 0; int value = 0; int ret; - ht = hash_create (hash_direct_hash, hash_direct_equal, destroy_key, destroy_value); - CuAssertPtrNotNull (tc, ht); - if (!hash_set (ht, &key, &value)) + map = hash_create (hash_direct_hash, hash_direct_equal, destroy_key, destroy_value); + CuAssertPtrNotNull (tc, map); + if (!hash_set (map, &key, &value)) CuFail (tc, "should not be reached"); - ret = hash_remove (ht, &key); + ret = hash_remove (map, &key); CuAssertIntEquals (tc, ret, 1); CuAssertIntEquals (tc, 1, key); CuAssertIntEquals (tc, 2, value); @@ -207,7 +207,7 @@ test_hash_remove_destroys (CuTest *tc) key = 0; value = 0; - ret = hash_remove (ht, &key); + ret = hash_remove (map, &key); CuAssertIntEquals (tc, ret, 0); CuAssertIntEquals (tc, 0, key); CuAssertIntEquals (tc, 0, value); @@ -216,7 +216,7 @@ test_hash_remove_destroys (CuTest *tc) key = 0; value = 0; - hash_free (ht); + hash_free (map); CuAssertIntEquals (tc, 0, key); CuAssertIntEquals (tc, 0, value); @@ -225,18 +225,18 @@ test_hash_remove_destroys (CuTest *tc) static void test_hash_set_destroys (CuTest *tc) { - hash_t *ht; + hashmap *map; int key = 0; int value = 0; int value2 = 0; int ret; - ht = hash_create (hash_direct_hash, hash_direct_equal, destroy_key, destroy_value); - CuAssertPtrNotNull (tc, ht); - if (!hash_set (ht, &key, &value)) + map = hash_create (hash_direct_hash, hash_direct_equal, destroy_key, destroy_value); + CuAssertPtrNotNull (tc, map); + if (!hash_set (map, &key, &value)) CuFail (tc, "should not be reached"); - ret = hash_set (ht, &key, &value2); + ret = hash_set (map, &key, &value2); CuAssertIntEquals (tc, ret, 1); CuAssertIntEquals (tc, 0, key); CuAssertIntEquals (tc, 2, value); @@ -246,7 +246,7 @@ test_hash_set_destroys (CuTest *tc) value = 0; value2 = 0; - hash_free (ht); + hash_free (map); CuAssertIntEquals (tc, 1, key); CuAssertIntEquals (tc, 0, value); @@ -257,16 +257,16 @@ test_hash_set_destroys (CuTest *tc) static void test_hash_clear_destroys (CuTest *tc) { - hash_t *ht; + hashmap *map; int key = 0; int value = 0; - ht = hash_create (hash_direct_hash, hash_direct_equal, destroy_key, destroy_value); - CuAssertPtrNotNull (tc, ht); - if (!hash_set (ht, &key, &value)) + map = hash_create (hash_direct_hash, hash_direct_equal, destroy_key, destroy_value); + CuAssertPtrNotNull (tc, map); + if (!hash_set (map, &key, &value)) CuFail (tc, "should not be reached"); - hash_clear (ht); + hash_clear (map); CuAssertIntEquals (tc, 1, key); CuAssertIntEquals (tc, 2, value); @@ -274,7 +274,7 @@ test_hash_clear_destroys (CuTest *tc) key = 0; value = 0; - hash_clear (ht); + hash_clear (map); CuAssertIntEquals (tc, 0, key); CuAssertIntEquals (tc, 0, value); @@ -282,7 +282,7 @@ test_hash_clear_destroys (CuTest *tc) key = 0; value = 0; - hash_free (ht); + hash_free (map); CuAssertIntEquals (tc, 0, key); CuAssertIntEquals (tc, 0, value); @@ -298,83 +298,83 @@ test_hash_intptr_with_collisions (const void *data) static void test_hash_add_check_lots_and_collisions (CuTest *tc) { - hash_t *ht; + hashmap *map; int *value; int i; - ht = hash_create (test_hash_intptr_with_collisions, + map = hash_create (test_hash_intptr_with_collisions, hash_intptr_equal, NULL, free); for (i = 0; i < 20000; ++i) { value = malloc (sizeof (int)); *value = i; - if (!hash_set (ht, value, value)) + if (!hash_set (map, value, value)) CuFail (tc, "should not be reached"); } for (i = 0; i < 20000; ++i) { - value = hash_get (ht, &i); + value = hash_get (map, &i); CuAssertPtrNotNull (tc, value); CuAssertIntEquals (tc, i, *value); } - hash_free (ht); + hash_free (map); } static void test_hash_count (CuTest *tc) { - hash_t *ht; + hashmap *map; int *value; int i, ret; - ht = hash_create (hash_intptr_hash, hash_intptr_equal, NULL, free); + map = hash_create (hash_intptr_hash, hash_intptr_equal, NULL, free); - CuAssertIntEquals (tc, 0, hash_count (ht)); + CuAssertIntEquals (tc, 0, hash_size (map)); for (i = 0; i < 20000; ++i) { value = malloc (sizeof (int)); *value = i; - if (!hash_set (ht, value, value)) + if (!hash_set (map, value, value)) CuFail (tc, "should not be reached"); - CuAssertIntEquals (tc, i + 1, hash_count (ht)); + CuAssertIntEquals (tc, i + 1, hash_size (map)); } for (i = 0; i < 20000; ++i) { - ret = hash_remove (ht, &i); + ret = hash_remove (map, &i); CuAssertIntEquals (tc, 1, ret); - CuAssertIntEquals (tc, 20000 - (i + 1), hash_count (ht)); + CuAssertIntEquals (tc, 20000 - (i + 1), hash_size (map)); } - hash_clear (ht); - CuAssertIntEquals (tc, 0, hash_count (ht)); + hash_clear (map); + CuAssertIntEquals (tc, 0, hash_size (map)); - hash_free (ht); + hash_free (map); } static void test_hash_ulongptr (CuTest *tc) { - hash_t *ht; + hashmap *map; unsigned long *value; unsigned long i; - ht = hash_create (hash_ulongptr_hash, hash_ulongptr_equal, NULL, free); + map = hash_create (hash_ulongptr_hash, hash_ulongptr_equal, NULL, free); for (i = 0; i < 20000; ++i) { value = malloc (sizeof (unsigned long)); *value = i; - if (!hash_set (ht, value, value)) + if (!hash_set (map, value, value)) CuFail (tc, "should not be reached"); } for (i = 0; i < 20000; ++i) { - value = hash_get (ht, &i); + value = hash_get (map, &i); CuAssertPtrNotNull (tc, value); CuAssertIntEquals (tc, i, *value); } - hash_free (ht); + hash_free (map); } int -- cgit v1.1