]>
git.datanom.net - hashtable.git/blob - hashtable.c
27 static uint32_t hash_table_index(Hashtable
* ht
, const void* key
) {
28 return (ht
->hash(key
) % ht
->size
);
31 Hashtable
* hash_table_create(HashFunc hf
, EqualFunc ef
) {
32 return hash_table_create_full(hf
, ef
, TABLESIZE
, NULL
);
35 Hashtable
* hash_table_create_notify(HashFunc hf
, EqualFunc ef
, FreeFunc ff
) {
36 return hash_table_create_full(hf
, ef
, TABLESIZE
, ff
);
39 Hashtable
* hash_table_create_full(HashFunc hf
, EqualFunc ef
, uint32_t size
, FreeFunc ff
) {
40 Hashtable
* ht
= malloc(sizeof(*ht
));
49 ht
->nodes
= calloc(sizeof(Node
*), ht
->size
);
53 void hash_table_destroy(Hashtable
* ht
) {
54 for (uint32_t i
= 0; i
< ht
->size
; i
++) {
55 while (ht
->nodes
[i
]) {
56 Node
* node
= ht
->nodes
[i
];
57 ht
->nodes
[i
] = ht
->nodes
[i
]->next
;
67 void hash_table_print(Hashtable
* ht
) {
68 printf("Start Table\n");
69 for (uint32_t i
= 0; i
< ht
->size
; i
++) {
70 if (ht
->nodes
[i
] == NULL
) {
71 //printf("\t%i\t---\n", i);
73 printf("\t%i\t\n", i
);
74 Node
* node
= ht
->nodes
[i
];
75 while (node
!= NULL
) {
76 printf("\"%p\" - (%p)", node
->key
, node
->data
);
82 printf("End Table\n");
85 bool hash_table_insert(Hashtable
* ht
, const void* key
, void* obj
) {
86 if (key
== NULL
|| obj
== NULL
|| ht
== NULL
) return false;
89 if (hash_table_lookup(ht
, key
) != NULL
) return false;
91 uint32_t index
= hash_table_index(ht
, key
);
93 Node
* node
= malloc(sizeof(*node
));
95 node
->key
= (void*)key
;
97 node
->next
= ht
->nodes
[index
];
98 ht
->nodes
[index
] = node
;
102 void* hash_table_lookup(Hashtable
* ht
, const void* key
) {
103 if (key
== NULL
|| ht
== NULL
) return false;
104 uint32_t index
= hash_table_index(ht
, key
);
106 Node
* node
= ht
->nodes
[index
];
107 while (node
!= NULL
&& ht
->compare(node
->data
, key
) == false) {
111 if (node
== NULL
) return NULL
;
112 //printf("find: %p -> found: %p\n", key, node->data);
117 void* hash_table_delete(Hashtable
* ht
, const void* key
) {
118 if (key
== NULL
|| ht
== NULL
) return false;
119 uint64_t index
= hash_table_index(ht
, key
);
121 Node
* node
= ht
->nodes
[index
];
123 while (node
!= NULL
&& ht
->compare(node
->data
, key
) == false) {
128 if (node
== NULL
) return NULL
;
130 ht
->nodes
[index
] = node
->next
;
132 prev
->next
= node
->next
;
135 void* result
= node
->data
;
140 List
* hash_table_keys(Hashtable
* ht
) {
145 for (uint32_t i
= 0; i
< ht
->size
; i
++) {
146 if (ht
->nodes
[i
] != NULL
) {
147 Node
* node
= ht
->nodes
[i
];
148 while (node
!= NULL
) {
150 head
= calloc(sizeof(List
*), 1);
154 head
->next
= calloc(sizeof(List
*), 1);
157 head
->data
= ht
->nodes
[i
]->key
;
167 List
* hash_table_values(Hashtable
* ht
) {
169 values
= head
= NULL
;
172 for (uint32_t i
= 0; i
< ht
->size
; i
++) {
173 if (ht
->nodes
[i
] != NULL
) {
174 Node
* node
= ht
->nodes
[i
];
175 while (node
!= NULL
) {
177 head
= calloc(sizeof(List
*), 1);
181 head
->next
= calloc(sizeof(List
*), 1);
184 head
->data
= ht
->nodes
[i
]->data
;
194 void hash_table_list_free(List
* list
) {
195 while (list
!= NULL
) {
202 void hash_table_foreach(Hashtable
* ht
, ForeachFunc ff
, void* userdata
) {
204 for (uint32_t i
= 0; i
< ht
->size
; i
++) {
205 if (ht
->nodes
[i
] != NULL
) {
206 Node
* node
= ht
->nodes
[i
];
207 while (node
!= NULL
) {
208 ff(node
->key
, node
->data
, userdata
);
216 void hash_table_iter_init (HashtableIter
* iter
, Hashtable
* ht
) {
217 RealIter
* ri
= (RealIter
*) iter
;
219 if (ri
!= NULL
&& ht
!= NULL
) {
225 bool hash_table_iter_next(HashtableIter
* iter
, void** key
, void** value
) {
226 RealIter
* ri
= (RealIter
*) iter
;
235 if (pos
>= ri
->table
->size
) {
239 node
= ri
->table
->nodes
[pos
];
240 } while (node
== NULL
);
253 bool hash_table_contains(Hashtable
* ht
, const void* key
) {
254 if (ht
== NULL
|| key
== NULL
) return false;
256 if (hash_table_lookup(ht
, key
) == NULL
)
261 uint64_t hash_table_size(Hashtable
*ht
) {
264 if (ht
== NULL
) return size
;
266 for (uint32_t i
= 0; i
< ht
->size
; i
++) {
267 if (ht
->nodes
[i
] != NULL
) {
268 Node
* node
= ht
->nodes
[i
];
269 while (node
!= NULL
) {
279 bool hash_table_replace(Hashtable
*ht
, void* key
, void* value
) {
280 if (ht
== NULL
|| key
== NULL
|| value
== NULL
) return false;
282 uint32_t index
= hash_table_index(ht
, key
);
284 Node
* node
= ht
->nodes
[index
];
285 while (node
!= NULL
&& ht
->compare(node
->data
, key
) == false) {
290 return hash_table_insert(ht
, key
, value
);
300 uint64_t int_hash(const void* key
) {
301 return *(uint64_t*) key
;
304 uint64_t str_hash(const void* key
) {
305 const signed char* p
;
308 for (p
= key
; *p
!= '\0'; p
++) {
309 h
= (h
<< 5) + h
+ *p
;
315 uint64_t ptr_hash(const void* key
) {
316 return (uint64_t)key
;
319 bool int_equal(const void* a
, const void* b
) {
320 return *((const int*) a
) == *((const int*) b
);
323 bool str_equal(const void* a
, const void* b
) {
324 const char *string1
= (const char*) a
;
325 const char *string2
= (const char*) b
;
327 return strcmp (string1
, string2
) == 0;
330 bool ptr_equal(const void* a
, const void* b
) {
This page took 0.080358 seconds and 6 git commands to generate.