/*
* 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 = xzmalloc(sizeof(struct hash_table_entry) * new_size);
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;
}
bel'>mode:
Merge tag 'for-linus-20160523' of git://git.infradead.org/linux-mtd
Pull MTD updates from Brian Norris:
"First cycle with Boris as NAND maintainer! Many (most) bullets stolen
from him.
Generic:
- Migrated NAND LED trigger to be a generic MTD trigger
NAND:
- Introduction of the "ECC algorithm" concept, to avoid overloading
the ECC mode field too much more
- Replaced the nand_ecclayout infrastructure with something a little
more flexible (finally!) and future proof
- Rework of the OMAP GPMC and NAND drivers; the TI folks pulled some
of this into their own tree as well
- Prepare the sunxi NAND driver to receive DMA support
- Handle bitflips in erased pages on GPMI revisions that do not
support this in hardware.
SPI NOR:
- Start using the spi_flash_read() API for SPI drivers that support
it (i.e., SPI drivers with special memory-mapped flash modes)
And other small scattered improvments"
* tag 'for-linus-20160523' of git://git.infradead.org/linux-mtd: (155 commits)
mtd: spi-nor: support GigaDevice gd25lq64c
mtd: nand_bch: fix spelling of "probably"
mtd: brcmnand: respect ECC algorithm set by NAND subsystem
gpmi-nand: Handle ECC Errors in erased pages
Documentation: devicetree: deprecate "soft_bch" nand-ecc-mode value
mtd: nand: add support for "nand-ecc-algo" DT property
mtd: mtd: drop NAND_ECC_SOFT_BCH enum value
mtd: drop support for NAND_ECC_SOFT_BCH as "soft_bch" mapping
mtd: nand: read ECC algorithm from the new field
mtd: nand: fsmc: validate ECC setup by checking algorithm directly
mtd: nand: set ECC algorithm to Hamming on fallback
staging: mt29f_spinand: set ECC algorithm explicitly
CRIS v32: nand: set ECC algorithm explicitly
mtd: nand: atmel: set ECC algorithm explicitly
mtd: nand: davinci: set ECC algorithm explicitly
mtd: nand: bf5xx: set ECC algorithm explicitly
mtd: nand: omap2: Fix high memory dma prefetch transfer
mtd: nand: omap2: Start dma request before enabling prefetch
mtd: nandsim: add __init attribute
mtd: nand: move of_get_nand_xxx() helpers into nand_base.c
...