IGT Map

IGT Map — a linear-reprobing hashmap implementation

Functions

Types and Values

struct igt_map_entry
struct igt_map

Includes

#include <igt_map.h>

Description

Implements an open-addressing, linear-reprobing hash table.

For more information, see: http://cgit.freedesktop.org/~anholt/hash_table/tree/README

Example usage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL

static inline uint32_t hash_identifier(const void *val)
{
uint32_t hash = *(uint32_t *) val;

hash = hash * GOLDEN_RATIO_PRIME_32;
return hash;
}

static int equal_identifiers(const void *a, const void *b)
{
uint32_t *key1 = (uint32_t *) a, *key2 = (uint32_t *) b;

return *key1 == *key2;
}

static void free_func(struct igt_map_entry *entry)
{
    free(entry->data);
}

struct igt_map *map;

struct record {
     int foo;
     uint32_t unique_identifier;
};

struct record *r1, r2, *record;
struct igt_map_entry *entry;

r1 = malloc(sizeof(struct record));
map = igt_map_create(hash_identifier, equal_identifiers);
igt_map_insert(map, &r1->unique_identifier, r1);
igt_map_insert(map, &r2.unique_identifier, &r2);

igt_map_foreach(map, entry) {
    record = entry->data;
    printf("key: %u, foo: %d\n", *(uint32_t *) entry->key, record->foo);
}

record = igt_map_search(map, &r1->unique_identifier);
entry = igt_map_search_entry(map, &r2.unique_identifier);

igt_map_remove(map, &r1->unique_identifier, free_func);
igt_map_remove_entry(map, entry);

 igt_map_destroy(map, NULL);

Functions

igt_map_create ()

struct igt_map *
igt_map_create (uint32_t (*hash_function) (const void *key),
                int (*key_equals_function) (const void *a, const void *b));

Function creates a map and initializes it with given hash_function and key_equals_function .

Parameters

hash_function

function that maps key to 32b hash

 

key_equals_function

function that compares given hashes

 

Returns

pointer to just created map


igt_map_destroy ()

void
igt_map_destroy (struct igt_map *map,
                 void (*delete_function) (struct igt_map_entry *entry));

Frees the given hash table. If delete_function is passed, it gets called on each entry present before freeing.

Parameters

map

igt_map pointer

 

delete_function

function that frees data in igt_map_entry

 

igt_map_insert ()

struct igt_map_entry *
igt_map_insert (struct igt_map *map,
                const void *key,
                void *data);

Inserts the data indexed by given key into the map. If the map already contains an entry with the key , it will be replaced. To avoid memory leaks, perform a search before inserting.

Note that insertion may rearrange the table on a resize or rehash, so previously found hash entries are no longer valid after this function.

Parameters

map

igt_map pointer

 

data

data to be store

 

key

pointer to searched key

 

Returns

pointer to just inserted entry


igt_map_search ()

void *
igt_map_search (struct igt_map *map,
                const void *key);

Finds a map entry's data with the given key .

Parameters

map

igt_map pointer

 

key

pointer to searched key

 

Returns

data pointer if the entry was found, NULL otherwise. Note that it may be modified by the user.


igt_map_search_entry ()

struct igt_map_entry *
igt_map_search_entry (struct igt_map *map,
                      const void *key);

Finds a map entry with the given key .

Parameters

map

igt_map pointer

 

key

pointer to searched key

 

Returns

map entry or NULL if no entry is found. Note that the data pointer may be modified by the user.


igt_map_remove ()

void
igt_map_remove (struct igt_map *map,
                const void *key,
                void (*delete_function) (struct igt_map_entry *entry));

Function searches for an entry with a given key , and removes it from the map. If delete_function is passed, it will be called on removed entry.

If the caller has previously found a struct igt_map_entry pointer, (from calling igt_map_search() or remembering it from igt_map_insert()), then igt_map_remove_entry() can be called instead to avoid an extra search.

Parameters

map

igt_map pointer

 

key

pointer to searched key

 

delete_function

function that frees data in igt_map_entry

 

igt_map_remove_entry ()

void
igt_map_remove_entry (struct igt_map *map,
                      struct igt_map_entry *entry);

Function deletes the given hash entry.

Note that deletion doesn't otherwise modify the table, so an iteration over the map deleting entries is safe.

Parameters

map

igt_map pointer

 

entry

pointer to map entry

 

igt_map_next_entry ()

struct igt_map_entry *
igt_map_next_entry (struct igt_map *map,
                    struct igt_map_entry *entry);

This function is an iterator over the hash table. Note that an iteration over the table is O(table_size) not O(entries).

Parameters

map

igt_map pointer

 

entry

pointer to map entry, NULL for the first map entry

 

Returns

pointer to the next entry


igt_map_random_entry ()

struct igt_map_entry *
igt_map_random_entry (struct igt_map *map,
                      int (*predicate) (struct igt_map_entry *entry));

Functions returns random entry from the map. This may be useful in implementing random replacement (as opposed to just removing everything) in caches based on this hash table implementation. predicate may be used to filter entries, or may be set to NULL for no filtering.

Parameters

map

igt_map pointer

 

predicate

filtering entries function

 

Returns

pointer to the randomly chosen map entry


igt_map_foreach()

#define             igt_map_foreach(map, entry)

Macro is a loop, which iterates through each map entry. Inside a loop block current element is accessible by the entry pointer.

This foreach function is safe against deletion (which just replaces an entry's data with the deleted marker), but not against insertion (which may rehash the table, making entry a dangling pointer).

Parameters

map

igt_map pointer

 

entry

igt_map_entry pointer

 

igt_map_search_pre_hashed ()

struct igt_map_entry *
igt_map_search_pre_hashed (struct igt_map *map,
                           uint32_t hash,
                           const void *key);

Finds a map entry with the given key and hash of that key.

Parameters

map

igt_map pointer

 

hash

hash of key

 

key

pointer to searched key

 

Returns

map entry or NULL if no entry is found. Note that the data pointer may be modified by the user.


igt_map_insert_pre_hashed ()

struct igt_map_entry *
igt_map_insert_pre_hashed (struct igt_map *map,
                           uint32_t hash,
                           const void *key,
                           void *data);

Inserts the data indexed by given key and hash of that key into the map. If the map already contains an entry with the key , it will be replaced. To avoid memory leaks, perform a search before inserting.

Note that insertion may rearrange the table on a resize or rehash, so previously found hash entries are no longer valid after this function.

Parameters

map

igt_map pointer

 

hash

hash of key

 

data

data to be store

 

key

pointer to searched key

 

Returns

pointer to just inserted entry

Types and Values

struct igt_map_entry

struct igt_map_entry {
	uint32_t hash;
	const void *key;
	void *data;
};

struct igt_map

struct igt_map {
	struct igt_map_entry *table;
	uint32_t (*hash_function)(const void *key);
	int (*key_equals_function)(const void *a, const void *b);
	uint32_t size;
	uint32_t rehash;
	uint32_t max_entries;
	uint32_t size_index;
	uint32_t entries;
	uint32_t deleted_entries;
};