IGT Map: igt-gpu-tools Reference Manual

## IGT Map IGT Map — a linear-reprobing hashmap implementation |

## Functions

struct igt_map * | igt_map_create ()
void | igt_map_destroy ()
struct igt_map_entry * | igt_map_insert ()
void * | igt_map_search ()
struct igt_map_entry * | igt_map_search_entry ()
void | igt_map_remove ()
void | igt_map_remove_entry ()
struct igt_map_entry * | igt_map_next_entry ()
struct igt_map_entry * | igt_map_random_entry ()
#define | igt_map_foreach()
struct igt_map_entry * | igt_map_search_pre_hashed ()
struct igt_map_entry * | igt_map_insert_pre_hashed ()

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