xorriso  1.5.4.pl02
About: GNU xorriso creates, loads, manipulates and writes ISO 9660 filesystem images with Rock Ridge extensions. It is suitable for incremental data backup and for production of bootable ISO 9660 images. GNU xorriso is a statical compilation of the libraries libburn, libisofs, libisoburn, and libjte.
  Fossies Dox: xorriso-1.5.4.pl02.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

util_htable.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2007 Vreixo Formoso
3  * Copyright (c) 2014 Thomas Schmitt
4  *
5  * This file is part of the libisofs project; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License version 2
7  * or later as published by the Free Software Foundation.
8  * See COPYING file for details.
9  */
10 
11 #ifdef HAVE_CONFIG_H
12 #include "../config.h"
13 #endif
14 
15 #include "util.h"
16 #include "libisofs.h"
17 
18 #include <stdlib.h>
19 #include <string.h>
20 
21 /*
22  * Hash table implementation
23  */
24 
25 struct iso_hnode
26 {
27  void *key;
28  void *data;
29 
30  /** next node for chaining */
31  struct iso_hnode *next;
32 };
33 
34 struct iso_htable
35 {
36  struct iso_hnode **table;
37 
38  size_t size; /**< number of items in table */
39  size_t cap; /**< number of slots in table */
40 
43 };
44 
45 static
46 struct iso_hnode *iso_hnode_new(void *key, void *data)
47 {
48  struct iso_hnode *node = malloc(sizeof(struct iso_hnode));
49  if (node == NULL)
50  return NULL;
51 
52  node->data = data;
53  node->key = key;
54  node->next = NULL;
55  return node;
56 }
57 
58 /**
59  * Put an element in a Hash Table. The element will be identified by
60  * the given key, that you should use to retrieve the element again.
61  *
62  * This function allow duplicates, i.e., two items with the same key. In those
63  * cases, the value returned by iso_htable_get() is undefined. If you don't
64  * want to allow duplicates, use iso_htable_put() instead;
65  *
66  * Both the key and data pointers will be stored internally, so you should
67  * free the objects they point to. Use iso_htable_remove() to delete an
68  * element from the table.
69  */
70 int iso_htable_add(IsoHTable *table, void *key, void *data)
71 {
72  struct iso_hnode *node;
73  struct iso_hnode *new;
74  unsigned int hash;
75 
76  if (table == NULL || key == NULL) {
77  return ISO_NULL_POINTER;
78  }
79 
80  new = iso_hnode_new(key, data);
81  if (new == NULL) {
82  return ISO_OUT_OF_MEM;
83  }
84 
85  hash = table->hash(key) % table->cap;
86  node = table->table[hash];
87 
88  table->size++;
89  new->next = node;
90  table->table[hash] = new;
91  return ISO_SUCCESS;
92 }
93 
94 /**
95  * Like iso_htable_add(), but this doesn't allow dulpicates.
96  *
97  * @return
98  * 1 success, 0 if an item with the same key already exists, < 0 error
99  */
100 int iso_htable_put(IsoHTable *table, void *key, void *data)
101 {
102  struct iso_hnode *node;
103  struct iso_hnode *new;
104  unsigned int hash;
105 
106  if (table == NULL || key == NULL) {
107  return ISO_NULL_POINTER;
108  }
109 
110  hash = table->hash(key) % table->cap;
111  node = table->table[hash];
112 
113  while (node) {
114  if (!table->compare(key, node->key)) {
115  return 0;
116  }
117  node = node->next;
118  }
119 
120  new = iso_hnode_new(key, data);
121  if (new == NULL) {
122  return ISO_OUT_OF_MEM;
123  }
124 
125  table->size++;
126  new->next = table->table[hash];
127  table->table[hash] = new;
128  return ISO_SUCCESS;
129 }
130 
131 /**
132  * Retrieve an element from the given table.
133  *
134  * @param table
135  * Hash table
136  * @param key
137  * Key of the element that will be removed
138  * @param data
139  * Will be filled with the element found. Remains untouched if no
140  * element with the given key is found.
141  * @return
142  * 1 if found, 0 if not, < 0 on error
143  */
144 int iso_htable_get(IsoHTable *table, void *key, void **data)
145 {
146  struct iso_hnode *node;
147  unsigned int hash;
148 
149  if (table == NULL || key == NULL) {
150  return ISO_NULL_POINTER;
151  }
152 
153  hash = table->hash(key) % table->cap;
154  node = table->table[hash];
155  while (node) {
156  if (!table->compare(key, node->key)) {
157  if (data) {
158  *data = node->data;
159  }
160  return 1;
161  }
162  node = node->next;
163  }
164  return 0;
165 }
166 
167 /**
168  * Remove an item with the given key from the table. In tables that allow
169  * duplicates, it is undefined the element that will be deleted.
170  *
171  * @param table
172  * Hash table
173  * @param key
174  * Key of the element that will be removed
175  * @param free_data
176  * Function that will be called passing as parameters both the key and
177  * the element that will be deleted. The user can use it to free the
178  * element. You can pass NULL if you don't want to delete the item itself.
179  * @return
180  * 1 success, 0 no element exists with the given key, < 0 error
181  */
182 int iso_htable_remove(IsoHTable *table, void *key, hfree_data_t free_data)
183 {
184  struct iso_hnode *node, *prev;
185  unsigned int hash;
186 
187  if (table == NULL || key == NULL) {
188  return ISO_NULL_POINTER;
189  }
190 
191  hash = table->hash(key) % table->cap;
192  node = table->table[hash];
193  prev = NULL;
194  while (node) {
195  if (!table->compare(key, node->key)) {
196  if (free_data)
197  free_data(node->key, node->data);
198  if (prev) {
199  prev->next = node->next;
200  } else {
201  table->table[hash] = node->next;
202  }
203  free(node);
204  table->size--;
205  return 1;
206  }
207  prev = node;
208  node = node->next;
209  }
210  return 0;
211 }
212 
213 /**
214  * Like remove, but instead of checking for key equality using the compare
215  * function, it just compare the key pointers. If the table allows duplicates,
216  * and you provide different keys (i.e. different pointers) to elements
217  * with same key (i.e. same content), this function ensure the exact element
218  * is removed.
219  *
220  * It has the problem that you must provide the same key pointer, and not just
221  * a key whose contents are equal. Moreover, if you use the same key (same
222  * pointer) to identify several objects, what of those are removed is
223  * undefined.
224  *
225  * @param table
226  * Hash table
227  * @param key
228  * Key of the element that will be removed
229  * @param free_data
230  * Function that will be called passing as parameters both the key and
231  * the element that will be deleted. The user can use it to free the
232  * element. You can pass NULL if you don't want to delete the item itself.
233  * @return
234  * 1 success, 0 no element exists with the given key, < 0 error
235  */
236 int iso_htable_remove_ptr(IsoHTable *table, void *key, hfree_data_t free_data)
237 {
238  struct iso_hnode *node, *prev;
239  unsigned int hash;
240 
241  if (table == NULL || key == NULL) {
242  return ISO_NULL_POINTER;
243  }
244 
245  hash = table->hash(key) % table->cap;
246  node = table->table[hash];
247  prev = NULL;
248  while (node) {
249  if (key == node->key) {
250  if (free_data)
251  free_data(node->key, node->data);
252  if (prev) {
253  prev->next = node->next;
254  } else {
255  table->table[hash] = node->next;
256  }
257  free(node);
258  table->size--;
259  return 1;
260  }
261  prev = node;
262  node = node->next;
263  }
264  return 0;
265 }
266 
267 /**
268  * Hash function suitable for keys that are char strings.
269  */
270 unsigned int iso_str_hash(const void *key)
271 {
272  int i, len;
273  const char *p = key;
274  unsigned int h = 2166136261u;
275 
276  len = strlen(p);
277  for (i = 0; i < len; i++)
278  h = (h * 16777619 ) ^ p[i];
279 
280  return h;
281 }
282 
283 /**
284  * Destroy the given hash table.
285  *
286  * Note that you're responsible to actually destroy the elements by providing
287  * a valid free_data function. You can pass NULL if you only want to delete
288  * the hash structure.
289  */
291 {
292  size_t i;
293  struct iso_hnode *node, *tmp;
294 
295  if (table == NULL) {
296  return;
297  }
298 
299  for (i = 0; i < table->cap; ++i) {
300  node = table->table[i];
301  while (node) {
302  tmp = node->next;
303  if (free_data)
304  free_data(node->key, node->data);
305  free(node);
306  node = tmp;
307  }
308  }
309  free(table->table);
310  free(table);
311 }
312 
313 /**
314  * Create a new hash table.
315  *
316  * @param size
317  * Number of slots in table.
318  * @param hash
319  * Function used to generate
320  */
321 int iso_htable_create(size_t size, hash_funtion_t hash,
322  compare_function_t compare, IsoHTable **table)
323 {
324  IsoHTable *t;
325 
326  if (size <= 0)
327  return ISO_WRONG_ARG_VALUE;
328  if (table == NULL)
329  return ISO_NULL_POINTER;
330 
331  t = malloc(sizeof(IsoHTable));
332  if (t == NULL) {
333  return ISO_OUT_OF_MEM;
334  }
335  t->table = calloc(size, sizeof(void*));
336  if (t->table == NULL) {
337  free(t);
338  return ISO_OUT_OF_MEM;
339  }
340  t->cap = size;
341  t->size = 0;
342  t->hash = hash;
343  t->compare = compare;
344 
345  *table = t;
346  return ISO_SUCCESS;
347 }
int(* compare_function_t)(const void *a, const void *b)
Definition: util.h:343
void(* hfree_data_t)(void *key, void *data)
Definition: util.h:344
unsigned int(* hash_funtion_t)(const void *key)
Definition: util.h:342
#define ISO_SUCCESS
Definition: libisofs.h:8719
#define ISO_OUT_OF_MEM
Definition: libisofs.h:8745
#define ISO_WRONG_ARG_VALUE
Definition: libisofs.h:8751
#define ISO_NULL_POINTER
Definition: libisofs.h:8742
void * data
Definition: util_htable.c:28
void * key
Definition: util_htable.c:27
struct iso_hnode * next
Definition: util_htable.c:31
struct iso_hnode ** table
Definition: util_htable.c:36
size_t cap
Definition: util_htable.c:39
compare_function_t compare
Definition: util_htable.c:42
size_t size
Definition: util_htable.c:38
hash_funtion_t hash
Definition: util_htable.c:41
int iso_htable_remove_ptr(IsoHTable *table, void *key, hfree_data_t free_data)
Definition: util_htable.c:236
int iso_htable_add(IsoHTable *table, void *key, void *data)
Definition: util_htable.c:70
int iso_htable_create(size_t size, hash_funtion_t hash, compare_function_t compare, IsoHTable **table)
Definition: util_htable.c:321
int iso_htable_remove(IsoHTable *table, void *key, hfree_data_t free_data)
Definition: util_htable.c:182
int iso_htable_put(IsoHTable *table, void *key, void *data)
Definition: util_htable.c:100
static struct iso_hnode * iso_hnode_new(void *key, void *data)
Definition: util_htable.c:46
void iso_htable_destroy(IsoHTable *table, hfree_data_t free_data)
Definition: util_htable.c:290
unsigned int iso_str_hash(const void *key)
Definition: util_htable.c:270
int iso_htable_get(IsoHTable *table, void *key, void **data)
Definition: util_htable.c:144