/* * netsniff-ng - the packet sniffing beast * Copyright 2009, 2010 Daniel Borkmann. * Subject to the GPL, version 2. */ #include "hash.h" #include "xmalloc.h" /* Hash table implementation from the GIT project. */ /* Copyright 2008 (C) Linus Torvalds, GPL version 2 */ /* * Look up a hash entry in the hash table. Return the pointer to * the existing entry, or the empty slot if none existed. The caller * can then look at the (*ptr) to see whether it existed or not. */ static struct hash_table_entry *lookup_hash_entry(unsigned int hash, const struct hash_table *table) { unsigned int size = table->size, nr = hash % size; struct hash_table_entry *array = table->array; while (array[nr].ptr) { if (array[nr].hash == hash) break; nr++; if (nr >= size) nr = 0; } return array + nr; } /* * Insert a new hash entry pointer into the table. * * If that hash entry already existed, return the pointer to * the existing entry (and the caller can create a list of the * pointers or do anything else). If it didn't exist, return * NULL (and the caller knows the pointer has been inserted). */ static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table) { struct hash_table_entry *entry = lookup_hash_entry(hash, table); if (!entry->ptr) { entry->ptr = ptr; entry->hash = hash; table->nr++; return NULL; } return &entry->ptr; } /* * Removes a hash entry pointer from the table. * * If that hash does not exist, NULL is returned, or, if that hash * exists and is the first entry, ptr_next will be set to that entry * and NULL is returned. Otherwise the caller must maintain the * remaining list. */ static void *remove_hash_entry(unsigned int hash, void *ptr, void *ptr_next, struct hash_table *table) { struct hash_table_entry *entry = lookup_hash_entry(hash, table); if (!entry->ptr) return NULL; else if (entry->ptr == ptr) { entry->ptr = ptr_next; entry->hash = hash; if (!ptr_next) table->nr--; return NULL; } else return entry->ptr; } static void grow_hash_table(struct hash_table *table) { unsigned int i; unsigned int old_size = table->size, new_size; struct hash_table_entry *old_array = table->array, *new_array; new_size = alloc_nr(old_size); new_array = xcalloc(new_size, sizeof(struct hash_table_entry)); table->size = new_size; table->array = new_array; table->nr = 0; for (i = 0; i < old_size; i++) { unsigned int hash = old_array[i].hash; void *ptr = old_array[i].ptr; if (ptr) insert_hash_entry(hash, ptr, table); } free(old_array); } void *lookup_hash(unsigned int hash, const struct hash_table *table) { if (!table->array) return NULL; return lookup_hash_entry(hash, table)->ptr; } void *remove_hash(unsigned int hash, void *ptr, void *ptr_next, struct hash_table *table) { if (!table->array) return NULL; return remove_hash_entry(hash, ptr, ptr_next, table); } void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table) { unsigned int nr = table->nr; if (nr >= table->size/2) grow_hash_table(table); return insert_hash_entry(hash, ptr, table); } int for_each_hash(const struct hash_table *table, int (*fn)(void *)) { int sum = 0; unsigned int i; unsigned int size = table->size; struct hash_table_entry *array = table->array; for (i = 0; i < size; i++) { void *ptr = array->ptr; array++; if (ptr) { int val = fn(ptr); if (val < 0) return val; sum += val; } } return sum; } int for_each_hash_int(const struct hash_table *table, int (*fn)(void *, int), int arg) { int sum = 0; unsigned int i; unsigned int size = table->size; struct hash_table_entry *array = table->array; for (i = 0; i < size; i++) { void *ptr = array->ptr; array++; if (ptr) { int val = fn(ptr, arg); if (val < 0) return val; sum += val; } } return sum; } void free_hash(struct hash_table *table) { free(table->array); table->array = NULL; table->size = 0; table->nr = 0; } ba'>e7aa8c2eb11ba69b1b69099c3c7bd6be3087b0ba (patch) treef63906f41699c8e38af9d12b063e2ceab0286ef2 /lib parente34bac726d27056081d0250c0e173e4b155aa340 (diff)parent868c97a846a73e937d835b09b8c885a69df50ec8 (diff)
Merge tag 'docs-4.10' of git://git.lwn.net/linuxHEADmaster
Pull documentation update from Jonathan Corbet: "These are the documentation changes for 4.10. It's another busy cycle for the docs tree, as the sphinx conversion continues. Highlights include: - Further work on PDF output, which remains a bit of a pain but should be more solid now. - Five more DocBook template files converted to Sphinx. Only 27 to go... Lots of plain-text files have also been converted and integrated. - Images in binary formats have been replaced with more source-friendly versions. - Various bits of organizational work, including the renaming of various files discussed at the kernel summit. - New documentation for the device_link mechanism. ... and, of course, lots of typo fixes and small updates" * tag 'docs-4.10' of git://git.lwn.net/linux: (193 commits) dma-buf: Extract dma-buf.rst Update Documentation/00-INDEX docs: 00-INDEX: document directories/files with no docs docs: 00-INDEX: remove non-existing entries docs: 00-INDEX: add missing entries for documentation files/dirs docs: 00-INDEX: consolidate process/ and admin-guide/ description scripts: add a script to check if Documentation/00-INDEX is sane Docs: change sh -> awk in REPORTING-BUGS Documentation/core-api/device_link: Add initial documentation core-api: remove an unexpected unident ppc/idle: Add documentation for powersave=off Doc: Correct typo, "Introdution" => "Introduction" Documentation/atomic_ops.txt: convert to ReST markup Documentation/local_ops.txt: convert to ReST markup Documentation/assoc_array.txt: convert to ReST markup docs-rst: parse-headers.pl: cleanup the documentation docs-rst: fix media cleandocs target docs-rst: media/Makefile: reorganize the rules docs-rst: media: build SVG from graphviz files docs-rst: replace bayer.png by a SVG image ...
Diffstat (limited to 'lib')