From ceb32f60ef7d6210883acf1f17500f87cac8888c Mon Sep 17 00:00:00 2001 From: Uros Majstorovic Date: Sun, 30 Jan 2022 02:01:37 +0100 Subject: hashtable fix --- ecp/src/htable/hashtable.h | 102 ++++++++++++++++++++++++++++++--------------- 1 file changed, 69 insertions(+), 33 deletions(-) (limited to 'ecp/src/htable/hashtable.h') diff --git a/ecp/src/htable/hashtable.h b/ecp/src/htable/hashtable.h index 046f740..a0b1949 100755 --- a/ecp/src/htable/hashtable.h +++ b/ecp/src/htable/hashtable.h @@ -3,8 +3,6 @@ #ifndef __HASHTABLE_CWC22_H__ #define __HASHTABLE_CWC22_H__ -#include - struct hashtable; /* Example of use: @@ -21,12 +19,12 @@ struct hashtable; * v = (struct some_value *) malloc(sizeof(struct some_value)); * * (initialise k and v to suitable values) - * + * * if (! hashtable_insert(h,k,v) ) * { exit(-1); } * * if (NULL == (found = hashtable_search(h,k) )) - * { printf("Not found!"); } + * { printf("not found!"); } * * if (NULL == (found = hashtable_remove(h,k) )) * { printf("Not found\n"); } @@ -35,7 +33,7 @@ struct hashtable; /* Macros may be used to define type-safe(r) hashtable access functions, with * methods specialized to take known key and value types as parameters. - * + * * Example: * * Insert this at the start of your file: @@ -63,30 +61,61 @@ struct hashtable; * */ +/*****************************************************************************/ +struct entry +{ + void *k, *v; + unsigned int h; + struct entry *next; +}; + /***************************************************************************** * create_hashtable - + * @name create_hashtable * @param minsize minimum initial size of hashtable - * @param hash_fn function for hashing keys - * @param eq_fn function for determining key equality - * @param malloc_fn function malloc - * @param realloc_fn function realloc - * @param free_fn function free - * @return hashtable created + * @param hashfunction function for hashing keys + * @param key_eq_fn function for determining key equality + * @return newly created hashtable or NULL on failure */ struct hashtable * -create_hashtable(unsigned int minsize, - unsigned int (*hash_fn) (void*), - int (*eq_fn) (void*,void*), - void *(*malloc_fn) (size_t), - void *(*realloc_fn) (void*,size_t), - void (*free_fn) (void*)); +hashtable_create(unsigned int minsize, + unsigned int (*hashfunction) (void*), + int (*key_eq_fn) (void*,void*)); + +void +hashtable_create_static(struct hashtable *h, struct entry **t, + unsigned int size, + unsigned int (*hashf) (void*), + int (*eqf) (void*,void*)); + +unsigned int +hashtable_prime_size(unsigned int minsize); + +/*****************************************************************************/ +/* hashtable_iterator_key + * - return the key of the (key,value) pair at the current position */ + +extern inline void * +hashtable_entry_key(struct entry *e) +{ + return e->v; +} + +/*****************************************************************************/ +/* hashtable_iterator_value + * - return the value of the (key,value) pair at the current position */ + +extern inline void * +hashtable_entry_value(struct entry *e) +{ + return e->v; +} /***************************************************************************** * hashtable_insert - + * @name hashtable_insert * @param h the hashtable to insert into * @param k the key - hashtable claims ownership and will free on removal @@ -103,9 +132,12 @@ create_hashtable(unsigned int minsize, * If in doubt, remove before insert. */ -int +int hashtable_insert(struct hashtable *h, void *k, void *v); +void +hashtable_insert_static(struct hashtable *h, struct entry *e, void *k, void *v); + #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ int fnname (struct hashtable *h, keytype *k, valuetype *v) \ { \ @@ -114,7 +146,7 @@ int fnname (struct hashtable *h, keytype *k, valuetype *v) \ /***************************************************************************** * hashtable_search - + * @name hashtable_search * @param h the hashtable to search * @param k the key to search for - does not claim ownership @@ -132,7 +164,7 @@ valuetype * fnname (struct hashtable *h, keytype *k) \ /***************************************************************************** * hashtable_remove - + * @name hashtable_remove * @param h the hashtable to remove the item from * @param k the key to search for - does not claim ownership @@ -142,16 +174,19 @@ valuetype * fnname (struct hashtable *h, keytype *k) \ void * /* returns value */ hashtable_remove(struct hashtable *h, void *k); +struct entry * /* returns hash table entry */ +hashtable_remove_static(struct hashtable *h, void *k); + #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ -valuetype * fnname (struct hashtable *h, keytype *k, void (*f) (void *)) \ +valuetype * fnname (struct hashtable *h, keytype *k) \ { \ - return (valuetype *) (hashtable_remove(h,k,f)); \ + return (valuetype *) (hashtable_remove(h,k)); \ } /***************************************************************************** * hashtable_count - + * @name hashtable_count * @param h the hashtable * @return the number of items stored in the hashtable @@ -162,36 +197,37 @@ hashtable_count(struct hashtable *h); /***************************************************************************** * hashtable_destroy - + * @name hashtable_destroy * @param h the hashtable + * @param free_values whether to call 'free' on the remaining values */ void -hashtable_destroy(struct hashtable *h); +hashtable_destroy(struct hashtable *h, int free_values); #endif /* __HASHTABLE_CWC22_H__ */ /* * Copyright (c) 2002, Christopher Clark * All rights reserved. - * + * * 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. - * + * * * Neither the name of the original author; nor the names of any contributors * may 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 -- cgit v1.2.3