summaryrefslogtreecommitdiff
path: root/pages/develop/guides/c/eina/hash-tables.md.txt
blob: ff0cb886af330ef1ff4c2311793d17c4447d17a6 (plain) (blame)
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
---
~~Title: Eina Hash Tables~~
~~NOCACHE~~
---

# Hash Tables # 

The ``Eina_Hash`` provides a way to store values associated with a key. For example, you can use it to store tuples in a table. 

The ``Eina_Hash`` is implemented using an array of *buckets*. Each bucket is a pointer to a structure that is the head of a red-black tree. This implementation makes it very robust against weak keys as in the worst case scenario, you can still depend on an efficient binary tree implementation.

## Creating a Hash Table ##

To create the hash table, use the ``eina_hash_new()`` function:

* The first parameter is the function called when obtaining the key size.
* The second parameter is the function called when comparing keys.
* The third parameter is the function called when reading values.
* The fourth parameter is the function called on each value when the hash table is freed, or when an item is deleted from it. ``NULL`` can be passed as the callback.
* The last parameter is the size of the buckets.

When you create an ``Eina_Hash`` instance, you have to create four potentially long callback functions. ``Eina_Hash`` has some predefined functions to make these shorter. These are used to create various types of hash tables:

* ``eina_hash_string_djb2_new()`` creates a new hash table using the [djb2](https://en.wikipedia.org/wiki/List_of_hash_functions#Non-cryptographic_hash_functions) algorithm for strings.
* ``eina_hash_string_superfast_new()`` creates a new hash table for use with strings. This is best for long strings.
* ``eina_hash_string_small_new()`` creates a new hash table for use with strings with a small bucket size.
* ``eina_hash_int32_new()`` and ``eina_hash_int64_new()`` create a new hash table for use with 32-bit and 64-bit integers.
* ``eina_hash_pointer_new()`` creates a new hash table for use with pointers.
* ``eina_hash_stringshared_new()`` creates a new hash table for use with shared strings.

All these predefined functions require only one parameter: the function to free the data you've stored in the hash table.

The following example shows how to manage a small phone book using the ``eina_hash_string_superfast_new()`` function to create a hash table.

Create the phone book structure and some static data:

```c
struct _Phone_Entry
{
   const char *name; // Full name
   const char *number; // Phone number
};

typedef struct _Phone_Entry Phone_Entry;

static Phone_Entry _start_entries[] =
{
   { "Wolfgang Amadeus Mozart", "+01 23 456-78910" },
   { "Ludwig van Beethoven", "+12 34 567-89101" },
   { "Richard Georg Strauss", "+23 45 678-91012" },
   { "Heitor Villa-Lobos", "+34 56 789-10123" },
   { NULL, NULL }
};
```

Create the callback to free the data:

```c
static void
_phone_entry_free_cb(void *data)
{
   free(data);
}
```

The free callback can be changed later using the function ``eina_hash_free_cb_set()``. You need to pass the hash and new callback function.

The ``eina_hash_free_buckets()`` function frees all hash table buckets. It empties the hash but does not destroy it. You may still use it for another purpose if you wish. When you call``eina_hash_free()`` the space allocated to the hash is freed.

Create and destroy a hash table as follows:

```c
int free_data()
{
   Eina_Hash *phone_book = NULL;
   phone_book = eina_hash_string_superfast_new(_phone_entry_free_cb);

   // Empty the phone book without destroying it
   eina_hash_free_buckets(phone_book);
   eina_hash_free(phone_book);
}
```

## Modifying Hash Table Content ##

### Add data to a hash ###

Use the ``eina_hash_add()`` function to add data. This function takes the hash, the key to access the data and the data itself as its parameters. The following example shows how to add the initial data declared earlier to the hash:

```c
for (i = 0; _start_entries[i].name != NULL; i++)
  {
     eina_hash_add(phone_book, _start_entries[i].name, strdup(_start_entries[i].number));
  }
```

The ``Eina_Hash`` offers various ways to add elements to a hash such as the function ``eina_hash_direct_add()``. This adds an entry without duplicating the string key. The key is stored in the struct, so this function can be used with ``eina_stringshare`` to avoid key data duplication.

```c
for (i = 0; _start_entries[i].name != NULL; i++)
  {
     // Allocating memory for the phone entry
     Phone_Entry *e = malloc(sizeof(Phone_Entry));

     // Creating an eina_stringshare for the name and the phone number
     e->name = eina_stringshare_add(_start_entries[i].name);
     e->number = eina_stringshare_add(_start_entries[i].number);

     // Adding the entry to the hash
     eina_hash_direct_add(phone_book, e->name, e);
  }
```

### Modify an entry ###

Use the ``eina_hash_modify()`` function to modify an entry, passing the hash, the key of the data to change and the new data. This function returns the old data on completion.

The ``eina_hash_set()`` function does the same work as ``eina_hash_modify()`` but if an entry doesn't exist, the function creates a new one.

```c
char *old_phone = NULL;
// Replace the phone number of Richard Strauss
old_phone = eina_hash_modify(phone_book, "Richard Georg Strauss", strdup("+23 45 111-11111"));
// ...
old_phone = eina_hash_set(phone_book, "Philippe de Magalhães", strdup("+33 6 111-11111"));
// ...
old_phone = eina_hash_set(phone_book, "Richard Georg Strauss", strdup("+23 45 111-117711"));
// ...
```

> **NOTE**:
> Remember to check the return value of ``eina_hash_modify()`` and ``eina_hash_set()`` and free it if required, or you might be leaking the previous entry in the hash!

### Change the key associated with data ###

Use the ``eina_hash_move()`` function to change the key without freeing and creating a new entry . You need only pass the hash, the old key and the new key. If the operation succeeds, the function returns ``EINA_TRUE``, if not it returns ``EINA_FALSE``.

```c
Eina_Bool res;
res = eina_hash_move(phone_book, "Philippe de Magalhães", "Filipe de Magalhães");
```

### Delete entries from a hash table ###

Use the ``eina_hash_del()`` function to remove an entry identified by a key or data from the given hash table:

```c
Eina_Bool r;
const char *entry_name = "Heitor Villa-Lobos";
r = eina_hash_del(phone_book, entry_name, NULL);
```

Use the ``eina_hash_del_by_key()`` function to remove an entry based on the key:

```c
r = eina_hash_del_by_key(phone_book, "Richard Georg Strauss");
```

Use the ``eina_hash_del_by_data()`` function to remove an entry based on data:

```c
r = eina_hash_del_by_data(phone_book, "+12 34 567-89101");
```

### Accessing Hash Table Data ###

To find hash table elements and get data based on the key name:



### To retrieve an entry based on its key ###

Use the ``eina_hash_find()`` function by passing the hash and the key you're searching for:

```c
char *phone = NULL;
const char *entry_name = "Heitor Villa-Lobos";

// Look for a specific entry and get its phone number
phone = eina_hash_find(phone_book, entry_name);
```

### Retrieve the number of entries in a hash ###

Use the ``eina_hash_population()`` function to see the number of entries. Pass the hash as the only argument:

```c
unsigned int nb_elm;
nb_elm = eina_hash_population(phone_book);
```

### Iterate through a hash table ###

There are several ways to iterate through a hash table. One is to use the ``eina_hash_foreach()`` function. The first parameter is the hash. The second parameter is the callback function called on each iteration. The callback function must return ``EINA_TRUE`` if the iteration has to continue and ``EINA_FALSE`` if the iteration must end. The last parameter one is the data passed to the callback function.

The following example prints the key and the data of the hash entry (name and phone number):

```c
static Eina_Bool
pb_foreach_cb(const Eina_Hash *phone_book, const void *key, void *data, void *fdata)
{
   const char *name = key;
   const char *number = data;
   printf("%s: %s\n", name, number);

   // Return EINA_FALSE to stop this callback from being called
   return EINA_TRUE;
}

printf("List of phones:\n");

// Running the callback on the hash called phone_book
eina_hash_foreach(phone_book, pb_foreach_cb, NULL);
printf("\n");
```

### Iterate over keys ###

Use the ''eina_hash_iterator_key_new()'' function to iterate over keys:

```c
// Declaration of the Eina_Iterator
Eina_Iterator *it;

// Variable to handle the current iteration "data"
void *data;

// Iterate over the keys (names)
printf("List of names in the phone book:\n");

it = eina_hash_iterator_key_new(phone_book);

// Use the generic eina_iterator_next()
while (eina_iterator_next(it, &data))
{
   const char *name = data;
   printf("%s\n", name);
}

// Free the iterator
eina_iterator_free(it);
```

### Iterate over hash data ###

Use the ``eina_hash_iterator_data_new()`` function in the same way as ``eina_hash_iterator_key_new()`` to iterate over hash data:

```c
// Declaration of the Eina_Iterator
Eina_Iterator *it;

// Variable to handle the current iteration "data"
void *data;

// Iterate over hash data
printf("List of numbers in the phone book:\n");

it = eina_hash_iterator_data_new(phone_book);
while (eina_iterator_next(it, &data))
  {
     const char *number = data;
     printf("%s\n", number);
  }

// Free the iterator
eina_iterator_free(it);
```

### Iterate over a tuple composed of keys and data ###

Use the ``eina_hash_iterator_tuple_new()`` function  to iterate in this way:

```c
// Declaration of the Eina_Iterator
Eina_Iterator *tit;

// Variable to handle the current iteration "data"
void *tuple;

printf("List of phones:\n");
tit = eina_hash_iterator_tuple_new(phone_book);
while (eina_iterator_next(tit, &tuple))
  {
     Eina_Hash_Tuple *t = tuple;
     const char *name = t->key;
     const char *number = t->data;
     printf("%s: %s\n", name, number);
  }

// Always free the iterator after its use
eina_iterator_free(tit);
```

## Further Reading ##

[Hash Table API](https://www.enlightenment.org/develop/legacy/api/c/start#group__Eina__Hash__Group.html)
:    A reference for the Hash Table API.

[Hash Table Example](https://git.enlightenment.org/tools/examples.git/tree/reference/c/eina/src/eina_hash.c)
:    An example use of the Hash Table API.