/*
* 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;
}
it.cgi/linux/net-next.git/tree/include/drm/bridge?h=nds-private-remove&id=0ca2b46dbb645c1aa23eda6f5ac49a7be31ac87d'>bridge| 111 | logplain |
| -rw-r--r-- | drmP.h | 25776 | logplain |
| -rw-r--r-- | drm_agpsupport.h | 3867 | logplain |
| -rw-r--r-- | drm_atomic.h | 14443 | logplain |
| -rw-r--r-- | drm_atomic_helper.h | 10607 | logplain |
| -rw-r--r-- | drm_auth.h | 2260 | logplain |
| -rw-r--r-- | drm_blend.h | 2700 | logplain |
| -rw-r--r-- | drm_bridge.h | 7977 | logplain |
| -rw-r--r-- | drm_cache.h | 1763 | logplain |
| -rw-r--r-- | drm_color_mgmt.h | 2166 | logplain |
| -rw-r--r-- | drm_connector.h | 28975 | logplain |
| -rw-r--r-- | drm_crtc.h | 28999 | logplain |
| -rw-r--r-- | drm_crtc_helper.h | 3301 | logplain |
| -rw-r--r-- | drm_debugfs_crc.h | 2670 | logplain |
| -rw-r--r-- | drm_displayid.h | 2850 | logplain |
| -rw-r--r-- | drm_dp_dual_mode_helper.h | 4532 | logplain |
| -rw-r--r-- | drm_dp_helper.h | 30638 | logplain |
| -rw-r--r-- | drm_dp_mst_helper.h | 16260 | logplain |
| -rw-r--r-- | drm_drv.h | 14861 | logplain |
| -rw-r--r-- | drm_edid.h | 14335 | logplain |
| -rw-r--r-- | drm_encoder.h | 8160 | logplain |
| -rw-r--r-- | drm_encoder_slave.h | 6583 | logplain |
| -rw-r--r-- | drm_fb_cma_helper.h | 1929 | logplain |
| -rw-r--r-- | drm_fb_helper.h | 15125 | logplain |
| -rw-r--r-- | drm_fixed.h | 4825 | logplain |
| -rw-r--r-- | drm_flip_work.h | 3071 | logplain |
| -rw-r--r-- | drm_fourcc.h | 2748 | logplain |
| -rw-r--r-- | drm_framebuffer.h | 9623 | logplain |
| -rw-r--r-- | drm_gem.h | 8052 | logplain |
| -rw-r--r-- | drm_gem_cma_helper.h | 2286 | logplain |
| -rw-r--r-- | drm_global.h | 2011 | logplain |
| -rw-r--r-- | drm_hashtab.h | 3139 | logplain |
| -rw-r--r-- | drm_irq.h | 6323 | logplain |
| -rw-r--r-- | drm_legacy.h | 6933 | logplain |
| -rw-r--r-- | drm_mem_util.h | 2468 | logplain |
| -rw-r--r-- | drm_mipi_dsi.h | 10327 | logplain |
| -rw-r--r-- | drm_mm.h | 11462 | logplain |
| -rw-r--r-- | drm_mode_config.h | 23728 | logplain |
| -rw-r--r-- | drm_mode_object.h | 4911 | logplain |
| -rw-r--r-- | drm_modes.h | 17078 | logplain |
| -rw-r--r-- | drm_modeset_helper.h | 1576 | logplain |
| -rw-r--r-- | drm_modeset_helper_vtables.h | 41180 | logplain |
| -rw-r--r-- | drm_modeset_lock.h | 4241 | logplain |
| -rw-r--r-- | drm_of.h | 2034 | logplain |
| -rw-r--r-- | drm_os_linux.h | 2230 | logplain |
| -rw-r--r-- | drm_panel.h | 7079 | logplain |
| -rw-r--r-- | drm_pciids.h | 68035 | logplain |
| -rw-r--r-- | drm_plane.h | 19435 | logplain |
| -rw-r--r-- | drm_plane_helper.h | 3186 | logplain |
| -rw-r--r-- | drm_print.h | 3232 | logplain |
| -rw-r--r-- | drm_property.h | 11460 | logplain |
| -rw-r--r-- | drm_rect.h | 5103 | logplain |
| -rw-r--r-- | drm_simple_kms_helper.h | 4090 | logplain |
| -rw-r--r-- | drm_sysfs.h | 300 | logplain |
| -rw-r--r-- | drm_vma_manager.h | 7840 | logplain |
| -rw-r--r-- | gma_drm.h | 1033 | logplain |
| d--------- | i2c | 109 | logplain |