Yamyam: 1版をインポートしました

2018-06-28T17:45:48Z

1版をインポートしました

wiki>Jby601: /* What is a GHash? */ minor grammatical edit

2012-01-15T14:36:00Z

‎What is a GHash?: minor grammatical edit

新規ページ

= 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

<source lang="c">
#include "BLI_ghash.h"
</source>

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.

<source lang="c">
GHash *gh;

gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
</source>

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.

<source lang="c">
BLI_ghash_insert(gh, key, value);
</source>

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

<source lang="c">
value = BLI_ghash_lookup(gh, key);
</source>

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.

<source lang="c">
BLI_ghash_haskey(gh,key)
</source>

Of course we can check the size with

<source lang="c">
BLI_ghash_size(gh)
</source>

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

<source lang="c">
BLI_ghash_free(gh, NULL, NULL);
</source>

== 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

<source lang="c">
GHashIterator* ghi;
</source>

Then later we initialize it with this

<source lang="c">
ghi = BLI_ghashIterator_new(gh);
</source>

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

<source lang="c">
BLI_ghashIterator_step(ghi);
</source>

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.

<source lang="c">
BLI_ghashIterator_getKey(ghi);

BLI_ghashIterator_getValue(ghi);
</source>

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

<source lang="c">
BLI_ghashIterator_isDone(ghi);
</source>

and eventaully free it with this

<source lang="c">
BLI_ghashIterator_free(ghi);
</source>

== Example ==

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

<source lang="c">
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);
}
</source>

[[Category:Script]]

← 古い版	2018年6月28日 (木) 17:45時点における版
(相違点なし)

Dev:Source/Data Structures/GHash Tutorial - 版の履歴

Yamyam: 1版 をインポートしました

wiki>Jby601: /* What is a GHash? */ minor grammatical edit

Yamyam: 1版をインポートしました