ul_hptree.h ul_htimdefs.h ul_htimer.h ul_itbase.h \
ul_list.h ul_listbase.h ul_utdefs.h ul_utmalloc.h \
ul_uniqid.h ul_dbufflog.h ul_log.h ul_logbase.h \
- ul_logreg.h ul_cbuff.h ul_dqfifo.h
+ ul_logreg.h ul_cbuff.h ul_dqfifo.h ul_hashtab.h \
+ ul_hashtabcust.h
ifneq ($(CONFIG_OC_ULUTMINIMAL),y)
include_HEADERS += ul_evcbase.h
endif
ulut_SOURCES = ul_dbufbase.c ul_dbufmore.c ul_gsa.c ul_gsacust.c \
- ul_gavlprim.c ul_hptree.c \
+ ul_gavlprim.c ul_hashtabprim.c ul_hptree.c \
ul_htimer.c ul_htimbase.c ul_htimroot.c \
ul_htimdefault.c ul_dbufflog.c ul_logbase.c \
ul_cbuff.c
lib_LOADLIBES = ulut
ifeq ($(CONFIG_OC_ULUT_TESTS),y)
-utils_PROGRAMS = ul_gavlchk ul_gsachk ul_htimchk
+utils_PROGRAMS = ul_gavlchk ul_gsachk ul_htimchk ul_hashtabchk
endif
ul_gavlchk_SOURCES = ul_gavlchk.c
ul_gsachk_SOURCES = ul_gsachk.c
ul_htimchk_SOURCES = ul_htimchk.c
+ul_hashtabchk_SOURCES = ul_hashtabchk.c
endif
--- /dev/null
+/*******************************************************************
+ uLan Utilities Library - C library of basic reusable constructions
+
+ ul_hashtab.h - hash table declarations
+
+ (C) Copyright 2009 by Pavel Pisa - Originator
+
+ The uLan utilities library can be used, copied and modified under
+ next licenses
+ - GPL - GNU General Public License
+ - LGPL - GNU Lesser General Public License
+ - MPL - Mozilla Public License
+ - and other licenses added by project originators
+ Code can be modified and re-distributed under any combination
+ of the above listed licenses. If contributor does not agree with
+ some of the licenses, he/she can delete appropriate line.
+ Warning, if you delete all lines, you are not allowed to
+ distribute source code and/or binaries utilizing code.
+
+ See files COPYING and README for details.
+
+ *******************************************************************/
+
+#ifndef _UL_HASHTAB_H
+#define _UL_HASHTAB_H
+
+#include "ul_utdefs.h"
+#include "ul_itbase.h"
+#include "ul_gavl.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef unsigned int ul_hashtab_hashval_t;
+
+/**
+ * struct ul_hastab_node - Structure Representing Node of Generic AVL Tree
+ * @treenode: place to store GAVL node information
+ */
+typedef struct ul_hashtab_node {
+ gavl_node_t treenode;
+} ul_hashtab_node_t;
+
+/**
+ * struct ul_hashtab_node_hashcache - Structure Representing Node of Generic AVL Tree
+ * @treenode: place to store GAVL node information
+ * @hashval: place to store computed hash value
+ */
+typedef struct ul_hashtab_node_hashval {
+ gavl_node_t treenode;
+ ul_hashtab_hashval_t hashval;
+} ul_hashtab_node_hashval_t;
+
+typedef struct ul_hashtab_treeroot {
+ gavl_cust_root_field_t treeroot;
+} ul_hashtab_treeroot_t;
+
+/**
+ * struct ul_hashtab_cust_table_field - Structure Representing Hash Table
+ * @count: number of inserted items
+ * @hashmask: mask of bits used to index into actual allocated size
+ * @treeroots: internal storage for hash resolution
+ */
+
+typedef struct ul_hashtab_cust_table_field {
+ union {
+ ul_hashtab_treeroot_t *treetable;
+ ul_hashtab_treeroot_t treesingle;
+ } treeroots;
+ long count;
+ ul_hashtab_hashval_t hashmask;
+} ul_hashtab_cust_table_field_t;
+
+typedef int (ul_hashtab_resize_insert_fnc_t)(ul_hashtab_cust_table_field_t *table_field, gavl_node_t *treenode) UL_ATTR_REENTRANT;
+
+void ul_hashtab_init_table_field_primitive(ul_hashtab_cust_table_field_t *table_field);
+int ul_hashtab_delete_all_primitive(ul_hashtab_cust_table_field_t *table_field);
+int ul_hashtab_resize_primitive(ul_hashtab_cust_table_field_t *table_field,
+ ul_hashtab_hashval_t newsize, ul_hashtab_resize_insert_fnc_t *ins_fnc);
+gavl_node_t *ul_hashtab_next_it_primitive(const ul_hashtab_cust_table_field_t *table_field,
+ ul_hashtab_treeroot_t **pptreeroot, gavl_node_t *treenode);
+
+/* Declaration of new custom hash table with internal node */
+#define UL_HASTAB_CUST_NODE_INT_DEC_SCOPE(cust_scope, cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
+ cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
+\
+typedef struct {\
+ cust_table_t *container; \
+ ul_hashtab_treeroot_t *ptreeroot; \
+ cust_item_t *item; \
+} cust_prefix##_it_t;\
+\
+cust_scope int cust_prefix##_search_node(const cust_table_t *table, cust_key_t const *key, typeof(((cust_item_t*)0)->cust_item_node) **nodep);\
+cust_scope cust_item_t *cust_prefix##_find(const cust_table_t *table, cust_key_t const *key);\
+cust_scope int cust_prefix##_insert(cust_table_t *table, cust_item_t *item);\
+cust_scope int cust_prefix##_delete_node(cust_table_t *table, gavl_node_t *node);\
+cust_scope cust_item_t *cust_prefix##_delete_key(cust_table_t *table, cust_key_t const *key);\
+cust_scope int cust_prefix##_delete(cust_table_t *table, cust_item_t *item);\
+cust_scope int cust_prefix##_resize_table(cust_table_t *table, ul_hashtab_hashval_t newsize);\
+cust_scope void cust_prefix##_next_it(cust_prefix##_it_t *it);\
+cust_scope int cust_prefix##_find_it(cust_table_t *container, cust_key_t const *key, cust_prefix##_it_t *it);\
+cust_scope void cust_prefix##_delete_it(cust_prefix##_it_t *it);\
+\
+static inline \
+void cust_prefix##_init_table_field(cust_table_t *table)\
+{\
+ return ul_hashtab_init_table_field_primitive(&table->cust_table_field);\
+} \
+\
+static inline \
+int cust_prefix##_delete_all(cust_table_t *table)\
+{\
+ return ul_hashtab_delete_all_primitive(&table->cust_table_field);\
+} \
+\
+static inline \
+cust_item_t *cust_prefix##_it2item(const cust_prefix##_it_t *it)\
+{\
+ return it->item;\
+} \
+\
+static inline int \
+cust_prefix##_is_end_it(cust_prefix##_it_t *it)\
+{\
+ return !it->item;\
+} \
+\
+static inline void \
+cust_prefix##_first_it(cust_table_t *container, cust_prefix##_it_t *it)\
+{\
+ it->container=container;\
+ it->item=NULL;\
+ cust_prefix##_next_it(it);\
+} \
+\
+void cust_prefix##_next_it(cust_prefix##_it_t *it) \
+{ \
+ gavl_node_t *treenode; \
+ treenode=ul_hashtab_next_it_primitive(\
+ &it->container->cust_table_field, &it->ptreeroot, \
+ it->item!=NULL?&it->item->cust_item_node.treenode: NULL); \
+ it->item=treenode!=NULL?UL_CONTAINEROF(treenode, cust_item_t, cust_item_node.treenode):NULL;\
+}
+
+#define UL_HASTAB_CUST_NODE_INT_DEC(cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
+ cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
+ UL_HASTAB_CUST_NODE_INT_DEC_SCOPE(extern, cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
+ cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc)
+
+#ifdef __cplusplus
+} /* extern "C"*/
+#endif
+
+#endif /* _UL_HASHTAB_H */
--- /dev/null
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#ifndef SDCC
+#include <sys/time.h>
+#endif
+
+#include "ul_utmalloc.h"
+#include "ul_hashtab.h"
+#include "ul_hashtabcust.h"
+
+typedef int ul_randser_int_t;
+
+#define UL_HASHTAB_WITH_HASHVAL
+
+typedef struct cust3_item {
+ int my_val;
+ #ifndef UL_HASHTAB_WITH_HASHVAL
+ ul_hashtab_node_t my_node;
+ #else /*UL_HASHTAB_WITH_HASHCACHE*/
+ ul_hashtab_node_hashval_t my_node;
+ #endif /*UL_HASHTAB_WITH_HASHCACHE*/
+ int more_data;
+} cust3_item_t;
+
+typedef struct cust3_table {
+ ul_hashtab_cust_table_field_t my_table;
+ int my_info;
+ int my_first_val;
+ int my_last_val;
+} cust3_table_t;
+
+typedef int cust3_key_t;
+
+UL_HASTAB_CUST_NODE_INT_DEC(cust3, cust3_table_t, cust3_item_t, cust3_key_t,
+ my_table, my_node, my_val, cust3_cmp_fnc)
+
+inline int
+cust3_cmp_fnc(const cust3_key_t *a, const cust3_key_t *b)
+{
+ if (*a>*b) return 1;
+ if (*a<*b) return -1;
+ return 0;
+}
+
+inline ul_hashtab_hashval_t
+cust3_hash_fnc(const cust3_key_t *a)
+{
+ return *a;
+}
+
+inline ul_hashtab_hashval_t
+cust3_hash_get_fnc(const cust3_item_t *item)
+{
+ #ifdef UL_HASHTAB_WITH_HASHVAL
+ return item->my_node.hashval;
+ #else /*UL_HASHTAB_WITH_HASHCACHE*/
+ return cust3_hash_fnc(&item->my_val);
+ #endif /*UL_HASHTAB_WITH_HASHCACHE*/
+}
+
+inline void
+cust_hash_prep_fnc(cust3_item_t *item)
+{
+ #ifdef UL_HASHTAB_WITH_HASHVAL
+ item->my_node.hashval=cust3_hash_fnc(&item->my_val);
+ #endif /*UL_HASHTAB_WITH_HASHCACHE*/
+}
+
+UL_HASTAB_CUST_NODE_INT_IMP(cust3, cust3_table_t, cust3_item_t, cust3_key_t,
+ my_table, my_node, my_val, cust3_cmp_fnc, cust3_hash_fnc,
+ cust3_hash_get_fnc, cust_hash_prep_fnc, 0, 0)
+
+
+cust3_table_t cust3_table;
+
+ul_randser_int_t *ul_randser_generate(ul_randser_int_t len)
+{
+ ul_randser_int_t *ser;
+ ul_randser_int_t i;
+
+ ser=malloc(sizeof(*ser)*len);
+ if(ser==NULL)
+ return NULL;
+
+ for(i=0; i<len; i++) {
+ ser[i]=i;
+ }
+
+ for(i=len; i--; ) {
+ ul_randser_int_t t, k;
+ k=rand();
+ k=(unsigned long long)k*i/RAND_MAX;
+ t=ser[k];
+ ser[k]=ser[i];
+ ser[i]=t;
+ }
+
+ return ser;
+}
+
+void timing_test_print(struct timeval *start, struct timeval *stop, char *s)
+{
+ long sec, usec;
+ sec=stop->tv_sec-start->tv_sec;
+ usec=stop->tv_usec-start->tv_usec;
+ if(usec>=1000000) {
+ usec-=1000000;
+ sec++;
+ }
+ if(usec<0) {
+ usec+=1000000;
+ sec--;
+ }
+ printf("%s :\t%4ld.%06ld\n",s,sec,usec);
+}
+
+int main(int argc, char *argv[])
+{
+ cust3_table_t *table=&cust3_table;
+ cust3_item_t *item;
+ cust3_key_t k;
+ cust3_it_t it;
+ int count=100000;
+ int tablepow=12;
+ cust3_item_t **item_arr;
+ struct timeval time_start, time_stop;
+ int i, j;
+ int res;
+ ul_randser_int_t *ser1, *ser2;
+
+ cust3_init_table_field(table);
+
+ if(argc>=2) {
+ count=atol(argv[1]);
+ }
+ if(argc>=3) {
+ tablepow=atol(argv[2]);
+ }
+
+ cust3_resize_table(table, 1<<tablepow);
+
+ ser1=ul_randser_generate(count);
+ if(ser1==NULL)
+ return 1;
+
+ ser2=ul_randser_generate(count);
+ if(ser2==NULL)
+ return 1;
+
+ item_arr=malloc(sizeof(*item_arr)*count);
+ if(!item_arr)
+ return 1;
+
+ for(i=0; i<count; i++) {
+ item=malloc(sizeof(*item));
+ item->my_val=ser1[i];
+ item_arr[i]=item;
+ }
+
+ gettimeofday(&time_start,NULL);
+ for(i=0; i<count; i++) {
+ res=cust3_insert(table, item_arr[i]);
+ if(res<=0) {
+ printf("cust3_insert %d returned %d\n", i, res);
+ }
+ }
+ gettimeofday(&time_stop,NULL);
+ timing_test_print(&time_start,&time_stop,"HASHTAB random insert");
+
+ gettimeofday(&time_start,NULL);
+ for(j=0; j<10; j++) {
+ for(i=0; i<count; i++) {
+ k=ser2[i];
+ item=cust3_find(table, &k);
+ if(item==NULL) {
+ printf("cust3_find %d failed to found item\n", k);
+ }
+ }
+ }
+ gettimeofday(&time_stop,NULL);
+ timing_test_print(&time_start,&time_stop,"HASHTAB random find 10x");
+
+ #if 0
+ for(k=10; (k<count) && (k<20); k++) {
+ item=cust3_find(table, &k);
+ if(item==NULL) {
+ printf("cust3_find %d failed to found item in loop 2\n", k);
+ continue;
+ }
+ if(cust3_delete(table, item)<0)
+ printf("cust3_delete failed to found item %d\n", item->my_val);
+ else
+ free(item);
+ }
+
+ for(k=20; k<count; k++) {
+ item=cust3_delete_key(table, &k);
+ if(item==NULL)
+ printf("cust3_delete_key failed to found key %d\n", k);
+ else
+ free(item);
+ }
+ #endif
+
+ gettimeofday(&time_start,NULL);
+ for(j=0; j<10; j++) {
+ i=0;
+ ul_for_each_it(cust3, table, it){
+ item=cust3_it2item(&it);
+ if(item) {
+ i++;
+ } else {
+ printf("ul_for_each_it error\n");
+ }
+ }
+ if(i!=table->my_table.count)
+ printf("ul_for_each_it skipped some items\n");
+ }
+ gettimeofday(&time_stop,NULL);
+ timing_test_print(&time_start,&time_stop,"HASHTAB for each by iterator 10x");
+
+ gettimeofday(&time_start,NULL);
+ for(cust3_first_it(table,&it); !cust3_is_end_it(&it); ) {
+ item=cust3_it2item(&it);
+ cust3_delete_it(&it);
+ free(item);
+ }
+ gettimeofday(&time_stop,NULL);
+ timing_test_print(&time_start,&time_stop,"HASHTAB delete rest by iterator");
+
+ cust3_delete_all(table);
+
+ free(ser1);
+ free(ser2);
+ free(item_arr);
+
+ return 0;
+}
\ No newline at end of file
--- /dev/null
+/*******************************************************************
+ uLan Utilities Library - C library of basic reusable constructions
+
+ ul_hastabcust.h - custom hash table implementation
+
+ (C) Copyright 2009 by Pavel Pisa - Originator
+
+ The uLan utilities library can be used, copied and modified under
+ next licenses
+ - GPL - GNU General Public License
+ - LGPL - GNU Lesser General Public License
+ - MPL - Mozilla Public License
+ - and other licenses added by project originators
+ Code can be modified and re-distributed under any combination
+ of the above listed licenses. If contributor does not agree with
+ some of the licenses, he/she can delete appropriate line.
+ Warning, if you delete all lines, you are not allowed to
+ distribute source code and/or binaries utilizing code.
+
+ See files COPYING and README for details.
+
+ *******************************************************************/
+
+#ifndef _UL_HASHTABCUST_H
+#define _UL_HASHTABCUST_H
+
+#include "ul_utdefs.h"
+#include "ul_hashtab.h"
+#include "ul_gavlcust.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define UL_HASTAB_CUST_NODE_INT_IMP(cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
+ cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc, cust_hash_fnc, \
+ cust_hash_get_fnc, cust_hash_prep_fnc, cust_expand_ratio, cust_shrink_ratio) \
+GAVL_CUST_NODE_INT_DEC_SCOPE(static, cust_prefix##_privtree, ul_hashtab_treeroot_t, cust_item_t, cust_key_t,\
+ treeroot, cust_item_node.treenode, cust_item_key, cust_cmp_fnc) \
+GAVL_CUST_NODE_INT_IMP(cust_prefix##_privtree, ul_hashtab_treeroot_t, cust_item_t, cust_key_t,\
+ treeroot, cust_item_node.treenode, cust_item_key, cust_cmp_fnc) \
+\
+static inline \
+ul_hashtab_treeroot_t *cust_prefix##_privtree_tree4item(cust_table_t *table, const cust_item_t *item)\
+{\
+ return !table->cust_table_field.hashmask? &(table->cust_table_field.treeroots.treesingle):\
+ &(table->cust_table_field.treeroots.treetable[cust_hash_get_fnc(item)&table->cust_table_field.hashmask]);\
+} \
+\
+static inline \
+const ul_hashtab_treeroot_t *cust_prefix##_privtree_tree4key(const cust_table_t *table, cust_key_t const *key)\
+{\
+ return !table->cust_table_field.hashmask? &(table->cust_table_field.treeroots.treesingle):\
+ &(table->cust_table_field.treeroots.treetable[cust_hash_fnc(key)&table->cust_table_field.hashmask]);\
+} \
+\
+static \
+int cust_prefix##_privinternal_insert(cust_table_t *table, cust_item_t *item)\
+{\
+ return cust_prefix##_privtree_insert(cust_prefix##_privtree_tree4item(table, item), item);\
+} \
+\
+static \
+int cust_prefix##_privresize_insert(ul_hashtab_cust_table_field_t *table_field, gavl_node_t *treenode) UL_ATTR_REENTRANT\
+{\
+ return cust_prefix##_privinternal_insert(UL_CONTAINEROF(table_field, cust_table_t, cust_table_field),\
+ cust_prefix##_privtree_node2item(NULL,treenode));\
+} \
+\
+int cust_prefix##_resize_table(cust_table_t *table, ul_hashtab_hashval_t newsize)\
+{\
+ return ul_hashtab_resize_primitive(&table->cust_table_field, newsize, cust_prefix##_privresize_insert);\
+} \
+\
+int cust_prefix##_insert(cust_table_t *table, cust_item_t *item)\
+{\
+ int res;\
+ if(cust_expand_ratio<=0?0:(table->cust_table_field.count/cust_expand_ratio>table->cust_table_field.hashmask)) \
+ cust_prefix##_resize_table(table, (table->cust_table_field.hashmask+1)<<1);\
+ cust_hash_prep_fnc(item);\
+ res=cust_prefix##_privinternal_insert(table, item);\
+ if(res>0) \
+ table->cust_table_field.count++; \
+ return res; \
+} \
+\
+int cust_prefix##_delete(cust_table_t *table, cust_item_t *item)\
+{\
+ int res;\
+ res=cust_prefix##_privtree_delete(cust_prefix##_privtree_tree4item(table, item), item);\
+ if(res>0) { \
+ table->cust_table_field.count--; \
+ if(cust_shrink_ratio<=0?0:(table->cust_table_field.count/cust_shrink_ratio<table->cust_table_field.hashmask)) \
+ cust_prefix##_resize_table(table, (table->cust_table_field.hashmask>>1)+1);\
+ }\
+ return res; \
+} \
+\
+cust_item_t *cust_prefix##_delete_key(cust_table_t *table, cust_key_t const *key) \
+{\
+ gavl_node_t *node; \
+ const ul_hashtab_treeroot_t *treeroot; \
+ treeroot=cust_prefix##_privtree_tree4key(table, key); \
+ if(cust_prefix##_privtree_search_node(treeroot, key, &node)) \
+ return NULL; \
+ cust_prefix##_privtree_delete_node((ul_hashtab_treeroot_t *)treeroot, node); \
+ return cust_prefix##_privtree_node2item(NULL,node); \
+} \
+\
+int cust_prefix##_search_node(const cust_table_t *table, cust_key_t const *key, typeof(((cust_item_t*)0)->cust_item_node) **nodep) \
+{\
+ gavl_node_t *node;\
+ if(cust_prefix##_privtree_search_node(cust_prefix##_privtree_tree4key(table, key), key, &node)) { \
+ *nodep=NULL; \
+ return -1; \
+ } \
+ *nodep=&(UL_CONTAINEROF(node, cust_item_t, cust_item_node.treenode)->cust_item_node); \
+ return 0; \
+} \
+\
+cust_item_t *cust_prefix##_find(const cust_table_t *table, cust_key_t const *key) \
+{\
+ return cust_prefix##_privtree_find(cust_prefix##_privtree_tree4key(table, key), key); \
+} \
+\
+int cust_prefix##_find_it(cust_table_t *container, cust_key_t const *key, cust_prefix##_it_t *it) \
+{\
+ it->container=container; \
+ it->ptreeroot=(ul_hashtab_treeroot_t*)cust_prefix##_privtree_tree4key(it->container, key); \
+ it->item=cust_prefix##_privtree_find(it->ptreeroot, key); \
+ return it->item!=NULL?1:0; \
+}\
+\
+void cust_prefix##_delete_it(cust_prefix##_it_t *it)\
+{\
+ cust_item_t *item;\
+ ul_hashtab_treeroot_t *treeroot; \
+ if(!(item=it->item)) return;\
+ treeroot=it->ptreeroot; \
+ cust_prefix##_next_it(it);\
+ if(cust_prefix##_privtree_delete(treeroot,item)>=0)\
+ it->container->cust_table_field.count--; \
+}
+
+#ifdef __cplusplus
+} /* extern "C"*/
+#endif
+
+#endif /* _UL_HASHTABCUST_H */
--- /dev/null
+/*******************************************************************
+ uLan Utilities Library - C library of basic reusable constructions
+
+ ul_hashtabprim.c - primitives to support hash tables
+
+ (C) Copyright 2009 by Pavel Pisa - Originator
+
+ The uLan utilities library can be used, copied and modified under
+ next licenses
+ - GPL - GNU General Public License
+ - LGPL - GNU Lesser General Public License
+ - MPL - Mozilla Public License
+ - and other licenses added by project originators
+ Code can be modified and re-distributed under any combination
+ of the above listed licenses. If contributor does not agree with
+ some of the licenses, he/she can delete appropriate line.
+ Warning, if you delete all lines, you are not allowed to
+ distribute source code and/or binaries utilizing code.
+
+ See files COPYING and README for details.
+
+ *******************************************************************/
+
+#include <string.h>
+#include "ul_utmalloc.h"
+#include "ul_hashtab.h"
+
+void ul_hashtab_init_table_field_primitive(ul_hashtab_cust_table_field_t *table_field)
+{
+ table_field->hashmask=0;
+ table_field->count=0;
+ table_field->treeroots.treesingle.treeroot=NULL;
+}
+
+int ul_hashtab_delete_all_primitive(ul_hashtab_cust_table_field_t *table_field)
+{
+ if(table_field->hashmask)
+ free(table_field->treeroots.treetable);
+ table_field->hashmask=0;
+ table_field->count=0;
+ table_field->treeroots.treesingle.treeroot=NULL;
+ return 0;
+}
+
+int ul_hashtab_resize_primitive(ul_hashtab_cust_table_field_t *table_field,
+ ul_hashtab_hashval_t newsize, ul_hashtab_resize_insert_fnc_t *ins_fnc)
+{
+ ul_hashtab_hashval_t oldsize=table_field->hashmask+1;
+ ul_hashtab_treeroot_t oldsingle;
+ ul_hashtab_treeroot_t *pt;
+ ul_hashtab_treeroot_t *oldtable;
+ gavl_node_t *treenode;
+ int res;
+
+ if(newsize<=0)
+ newsize=1;
+
+ if(oldsize>1) {
+ oldtable=table_field->treeroots.treetable;
+ } else {
+ oldsingle.treeroot=table_field->treeroots.treesingle.treeroot;
+ oldtable=NULL;
+ }
+
+ if(newsize>1) {
+ pt=malloc(sizeof(*pt)*newsize);
+ if(pt==NULL)
+ return -1;
+ memset(pt,0,sizeof(*pt)*newsize);
+ table_field->treeroots.treetable=pt;
+ } else {
+ table_field->treeroots.treesingle.treeroot=NULL;
+ }
+ table_field->hashmask=newsize-1;
+
+ pt = oldtable!=NULL? oldtable: &oldsingle;
+
+ while(oldsize--) {
+ while(pt->treeroot!=NULL) {
+ treenode=gavl_cut_first_primitive(&pt->treeroot);
+ res=ins_fnc(table_field, treenode);
+ }
+ pt++;
+ }
+
+ if(oldtable)
+ free(oldtable);
+
+ return 0;
+}
+
+gavl_node_t *ul_hashtab_next_it_primitive(const ul_hashtab_cust_table_field_t *table_field,
+ ul_hashtab_treeroot_t **pptreeroot, gavl_node_t *treenode)
+{
+ if(treenode!=NULL) {
+ treenode=gavl_next_node(treenode);
+ if((treenode!=NULL) || !table_field->hashmask)
+ return treenode;
+ if(table_field->treeroots.treetable+table_field->hashmask==*pptreeroot)
+ return treenode;
+ (*pptreeroot)++;
+ } else {
+ if(!table_field->hashmask) {
+ const ul_hashtab_treeroot_t *treeroot=&table_field->treeroots.treesingle;
+ *pptreeroot=(ul_hashtab_treeroot_t *)treeroot;
+ } else {
+ *pptreeroot=table_field->treeroots.treetable;
+ }
+ }
+ do {
+ if(*pptreeroot) {
+ treenode=(*pptreeroot)->treeroot;
+ if(treenode)
+ while(treenode->left!=NULL)
+ treenode=treenode->left;
+ if(treenode!=NULL)
+ return treenode;
+ }
+ if(!table_field->hashmask)
+ return treenode;
+ if(table_field->treeroots.treetable+table_field->hashmask==*pptreeroot)
+ return treenode;
+ (*pptreeroot)++;
+ } while (1);
+}
projects / ulut.git / commitdiff