docs: todo: remove bullet point
[netsniff-ng.git] / src / hash.c
blob81bb297f34a69202c044f8a225fed12155539776
1 /*
2 * netsniff-ng - the packet sniffing beast
3 * By Daniel Borkmann <daniel@netsniff-ng.org>
4 * Copyright 2009, 2010 Daniel Borkmann.
5 * Subject to the GPL, version 2.
6 */
8 #include "hash.h"
9 #include "xmalloc.h"
11 /* Hash table implementation from the GIT project. */
12 /* Copyright 2008 (C) Linus Torvalds, GPL version 2 */
15 * Look up a hash entry in the hash table. Return the pointer to
16 * the existing entry, or the empty slot if none existed. The caller
17 * can then look at the (*ptr) to see whether it existed or not.
19 static struct hash_table_entry *lookup_hash_entry(unsigned int hash,
20 const struct hash_table
21 *table)
23 unsigned int size = table->size, nr = hash % size;
24 struct hash_table_entry *array = table->array;
25 while (array[nr].ptr) {
26 if (array[nr].hash == hash)
27 break;
28 nr++;
29 if (nr >= size)
30 nr = 0;
32 return array + nr;
37 * Insert a new hash entry pointer into the table.
39 * If that hash entry already existed, return the pointer to
40 * the existing entry (and the caller can create a list of the
41 * pointers or do anything else). If it didn't exist, return
42 * NULL (and the caller knows the pointer has been inserted).
44 static void **insert_hash_entry(unsigned int hash, void *ptr,
45 struct hash_table *table)
47 struct hash_table_entry *entry = lookup_hash_entry(hash, table);
48 if (!entry->ptr) {
49 entry->ptr = ptr;
50 entry->hash = hash;
51 table->nr++;
52 return NULL;
54 return &entry->ptr;
58 * Removes a hash entry pointer from the table.
60 * If that hash does not exist, NULL is returned, or, if that hash
61 * exists and is the first entry, ptr_next will be set to that entry
62 * and NULL is returned. Otherwise the caller must maintain the
63 * remaining list.
65 static void *remove_hash_entry(unsigned int hash, void *ptr, void *ptr_next,
66 struct hash_table *table)
68 struct hash_table_entry *entry = lookup_hash_entry(hash, table);
69 if (!entry->ptr)
70 return NULL;
71 else if (entry->ptr == ptr) {
72 entry->ptr = ptr_next;
73 entry->hash = hash;
74 if (!ptr_next)
75 table->nr--;
76 return NULL;
77 } else
78 return entry->ptr;
81 static void grow_hash_table(struct hash_table *table)
83 unsigned int i;
84 unsigned int old_size = table->size, new_size;
85 struct hash_table_entry *old_array = table->array, *new_array;
86 new_size = alloc_nr(old_size);
87 new_array = xzmalloc(sizeof(struct hash_table_entry) * new_size);
88 table->size = new_size;
89 table->array = new_array;
90 table->nr = 0;
91 for (i = 0; i < old_size; i++) {
92 unsigned int hash = old_array[i].hash;
93 void *ptr = old_array[i].ptr;
94 if (ptr)
95 insert_hash_entry(hash, ptr, table);
97 if (old_array)
98 xfree(old_array);
101 void *lookup_hash(unsigned int hash, const struct hash_table *table)
103 if (!table->array)
104 return NULL;
105 return lookup_hash_entry(hash, table)->ptr;
108 void *remove_hash(unsigned int hash, void *ptr, void *ptr_next,
109 struct hash_table *table)
111 if (!table->array)
112 return NULL;
113 return remove_hash_entry(hash, ptr, ptr_next, table);
116 void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)
118 unsigned int nr = table->nr;
119 if (nr >= table->size/2)
120 grow_hash_table(table);
121 return insert_hash_entry(hash, ptr, table);
124 int for_each_hash(const struct hash_table *table, int (*fn)(void *))
126 int sum = 0;
127 unsigned int i;
128 unsigned int size = table->size;
129 struct hash_table_entry *array = table->array;
130 for (i = 0; i < size; i++) {
131 void *ptr = array->ptr;
132 array++;
133 if (ptr) {
134 int val = fn(ptr);
135 if (val < 0)
136 return val;
137 sum += val;
140 return sum;
143 int for_each_hash_int(const struct hash_table *table, int (*fn)(void *, int),
144 int arg)
146 int sum = 0;
147 unsigned int i;
148 unsigned int size = table->size;
149 struct hash_table_entry *array = table->array;
150 for (i = 0; i < size; i++) {
151 void *ptr = array->ptr;
152 array++;
153 if (ptr) {
154 int val = fn(ptr, arg);
155 if (val < 0)
156 return val;
157 sum += val;
160 return sum;
163 void free_hash(struct hash_table *table)
165 if (table->array)
166 xfree(table->array);
167 table->array = NULL;
168 table->size = 0;
169 table->nr = 0;