Dev:Source/Data Structures/GHash Tutorial

What is a GHash?

There are times that you need to make an easily searchable list, where the size is unknown, and it needs to be quickly accessed (no linear searching) One great way to get this job done is with a hash table. Setting up your own hash, when you haven't got a clue can be a daunting task. But why reinvent the wheel! There is already a generic hash data structure built into the Blender codebase! ZR wrote ghash which lets you set up and use a hash with very little code. This can give you several options...

• A Keyed Hash Table
• An Item Set

Hash Table

A hash table is basically these key and value pairs that have been stored in such a way that passing the key to the hash will return you the value. ghash uses pointers as the key and value. Since it is set up with void pointers, they can point to just about anything. One application would be the case that you had a data structure that held temporary meta data about an EditEdge. For each edit edge, you could use the EdgeEdge* as your key and then dynamically allocate some memory to your meta data struct and then assign that as the value. Then whenever you needed the metadata for that edge, you pass the key to the hash and it returns the pointer to your struct.

An Item Set

Suppose you just want to make a dynamic list of items. Just feed the keys to the hash with NULL as the value. Then you can check later if the key is in the hash or set up an iterator to step through the keys of your hash.

Using GHash

The Basic GHash

We get there from this .h file

 #include "BLI_ghash.h"

First we need to declare our ghash: Then we need to create our new data structure. We pass this init function pointers to the hash and compare functions that this hash will be using. In this case a pointer hash. The function arguments determine how key values are compared or hashed, and can be used to create more specialized hash tables.

GHash *gh;

gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);

When it comes time to add an entry into our hash we call BLI_ghash_insert and pass it our hash, the key and value. Where key and value are both pointers.

 BLI_ghash_insert(gh, key, value);

Then we can pass the key to BLI_ghash_lookup and retrieve that value back

 value = BLI_ghash_lookup(gh, key);

One way to create a dynamic set of objects is to enter keys into the hash with NULL as the value. Then, you can later use BLI_ghash_haskey to see if that item is in the hash. It returns 1 for yes and 0 for no.

 BLI_ghash_haskey(gh,key)

Of course we can check the size with

 BLI_ghash_size(gh)

When we are done, be sure to clean up after yourself with this little beauty!

 BLI_ghash_free(gh, NULL, NULL);

Using An Iterator

After we create our hash, we need to create an iterator if we want to step though it... Note that it is not safe to insert elements or free the hash while we are itereating through it.

We will need to declare our iterator

 GHashIterator* ghi;

Then later we initialize it with this

 ghi = BLI_ghashIterator_new(gh);

The iterator starts on the first key and we step through the keys using

 BLI_ghashIterator_step(ghi);

On a given key we can get the key or value using these, they return the key or value pointers if the iterator has completly gone through the hash, you will get NULL from either.

BLI_ghashIterator_getKey(ghi);

BLI_ghashIterator_getValue(ghi);

We can also test the doneness of the iterator with this. Returning 1 if done 0 if not.

 BLI_ghashIterator_isDone(ghi);

and eventaully free it with this

 BLI_ghashIterator_free(ghi);

Example

Here is some sample code to print the items in a hash:

void print_hash(GHash *gh) {
    GHashIterator *ghi = BLI_ghashIterator_new(gh);
    for (; !BLI_ghashIterator_isDone(ghi); BLI_ghashIterator_step(ghi)) {
        printf("Key(%p) : Value(%p)\n", BLI_ghashIterator_getKey(ghi),
                                        BLI_ghashIterator_getValue(ghi));
    }
    BLI_ghashIterator_free(ghi);
}