/*
* 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;
}
>2016-09-28 10:23:50 +1000
| committer | Dave Airlie <airlied@redhat.com> | 2016-09-28 10:23:50 +1000 |
|---|
| commit | aaee1d1e2d97e3cb99cf0e096d2172237d762e4e (patch) |
|---|
| tree | b157e95fcba896ec4c6b4e73322bb9e8ab32fb94 |
|---|
| parent | b86f9faa34b4f08f4fbca333648d999bfcf42192 (diff) |
|---|
| parent | bad3d80fd001d3b74ab8bb3d561bc4d1b08797d3 (diff) |
|---|
Merge branch 'linux-4.8' of git://github.com/skeggsb/linux into drm-fixes
nouveau: couple of fixes.
* 'linux-4.8' of git://github.com/skeggsb/linux:
drm/nouveau: Revert "bus: remove cpu_coherent flag"
drm/nouveau/fifo/nv04: avoid ramht race against cookie insertion