BlenderDev/GHashTutorial

Wikipedia，自由的百科全书

Contents 1 What is a GHash? 1.1 Hash Table 1.2 An Item Set 2 Using GHash 2.1 The Basic GHash 3 #include "BLI_ghash.h" 4 GHash *gh; 5 gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp); 6 BLI_ghash_insert(gh, key, value); 7 value = BLI_ghash_lookup(gh, key); 8 BLI_ghash_haskey(gh,key) 9 BLI_ghash_size(gh) 10 BLI_ghash_free(gh, NULL, NULL); 10.1 Using An Iterator 11 GHashIterator* ghi; 12 ghi = BLI_ghashIterator_new(gh); 13 BLI_ghashIterator_step(ghi); 14 BLI_ghashIterator_getKey(ghi); 15 BLI_ghashIterator_getValue(ghi); 16 BLI_ghashIterator_isDone(ghi); 17 BLI_ghashIterator_free(ghi); 18 中文

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 access (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 this key and value pairs that have been stored in a way so 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 if 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);

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

中文

什么是ghash？ 有时候你需要简单的查找列表，即便查询的数据链的大小未知，但是又要快速的存取（非线形搜索）。一个很好的办法就是使用hash表。在对未知任务没有线索的时候就可以设置自己的hash表。但是为什么要重复造轮子呢？在blender代码中已经有一个完整的一般性hash数据结构存在了。ZR编写的ghash让你可以使用最少的代码来设置一个hash。它可以为你提供一些选项。。。

一个可以索引的hash表 一个元素集

hash 表 一个hash表是一个让key和value配对的存储结构。让你可以通过key来找到value。ghash使用了指针来指定key 和 value。因为是用空指针来设置的，所以他们可以指向任何的类型和对象。一个应用的场合就是，你可能会用一个数据结构来存储一个editedge的临时变更数据。每一个edit edge，你可以使用editedge*来作为你的key，然后动态分配一定的内存给你的更改数据结构再付value给他们，你就可以在需要这些改变数据的时候传一个key给hash，它就会返回指针指向的value。

一个元素集 假设，你只是想创建一个元素的动态链表。只要将key都给成null值。然后你就可以检查key是否在hash中，或者设置一个迭代器来遍列你hash的key。

使用ghash 最简单的ghash 我们从头文件开始。 代码: #include "BLI_ghash.h"

声明我们的ghash，然后创建我们的新数据结构，通过整型函数指针传递hash，和hash需要用到的比较函数。函数的参数可以确定key和value如何匹配或者被hash，也可以用到更特殊的hash表中。 代码: GHash *gh; gh = BLI_ghash_new(BLI_ghashutil_ptrhash,BLI_ghashutil_ptrcmp);

当需要在hash中添加项目的时候，我们调用BLI_ghash_insert传递key和value给hash，这里key和value都是指针。 代码: BLI_ghash_insert(gh, key, value);

当我们给函数 BLI_ghash_lookup一个key值，我们就可以返回一个value值。 代码: value = BLI_ghash_lookup(gh, key);

创建一个动态对象集的办法就是放一个key和一个以null为值的value到hash，然后，使用 BLI_ghash_haskey 来看这个元素是否在hash中，返回的是1代表存在，0代表不存在。 代码: BLI_ghash_haskey(gh,key)

使用下面函数来检查大小 代码: BLI_ghash_size(gh)

如果所有的过程都完了，你也玩累了请记住要用下面的语句来清空。 代码: BLI_ghash_free(gh, NULL, NULL);

Using An Iterator使用迭代器

创建了hash以后，我们还得逐个的遍历它，这样的话就得使用iterator。记住在使用iterator的同时不要向hash中插入元素，也不要将它释放清空。 我们先得声明我们的迭代器 代码: GHashIterator* ghi;

然后再这样将它初始化， 代码: ghi = BLI_ghashIterator_new(gh);

使用下面这个函数，它就会从第一个key开始完全逐个遍历所有key 代码: BLI_ghashIterator_step(ghi);

下面这两个帮我们把key或者value获取，他们会返回key或者value，如果iterator正常的跑完了整个hash，你会从他们两得到相同的null。 代码: BLI_ghashIterator_getKey(ghi); 代码: BLI_ghashIterator_getValue(ghi);

iterator是否完成工作可以用它来测试，1为完成，0为没有。 代码: BLI_ghashIterator_isDone(ghi);

然后释放整个iterator。 代码: BLI_ghashIterator_free(ghi);

这里有一个例子，用来打印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); 

}