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 .

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.

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.

igt_map_search ()

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

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

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 .

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.

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.

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).

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.

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).

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.

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.

igt_map_hash_32 ()

uint32_t
igt_map_hash_32 (const void *key);

Function is hashing function for 32-bit keys. Key is pointer to 32-bit value so it must be dereferenced.

igt_map_equal_32 ()

int
igt_map_equal_32 (const void *key1,
                  const void *key2);

Function compares 32-bit keys.

igt_map_hash_64 ()

uint32_t
igt_map_hash_64 (const void *key);

Function is hashing function for 64-bit keys. Key is pointer to 64-bit value so it must be dereferenced.

igt_map_equal_64 ()

int
igt_map_equal_64 (const void *key1,
                  const void *key2);

Function compares 64-bit keys.

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;
};