Associative arrays/Creation/C: Difference between revisions
loop
m (Delete {{collection}}, because it dumps the page into a phantom category. There seems no requirement to put {{collection}} in this type of page.) |
(loop) |
||
(7 intermediate revisions by 3 users not shown) | |||
Line 2:
* Back to [[Associative arrays/Creation]].
==From Scratch==
A hash table can be implemented with the following. Because of this example's simplicity, it comes with some restrictions on use and capabilities: It can't be resized automatically, if you try to insert more values than its capacity it will freeze, the hashing function is very simple, etc. All are fixable with additional logic or using a library:
<syntaxhighlight lang="с">
#include <stdlib.h>
typedef struct {
int size;
void **keys;
void **values;
} hash_t;
hash_t *hash_new (int size) {
hash_t *h = calloc(1, sizeof (hash_t));
h->keys = calloc(size, sizeof (void *));
h->values = calloc(size, sizeof (void *));
h->size = size;
return h;
}
int hash_index (hash_t *h, void *key) {
int i = (int) key % h->size;
while (h->keys[i] && h->keys[i] != key)
i = (i + 1) % h->size;
return i;
}
void hash_insert (hash_t *h, void *key, void *value) {
int i = hash_index(h, key);
h->keys[i] = key;
h->values[i] = value;
}
void *hash_lookup (hash_t *h, void *key) {
int i = hash_index(h, key);
return h->values[i];
}
int main () {
hash_t *h = hash_new(15);
hash_insert(h, "hello", "world");
hash_insert(h, "a", "b");
printf("hello => %s\n", hash_lookup(h, "hello"));
printf("herp => %s\n", hash_lookup(h, "herp"));
printf("a => %s\n", hash_lookup(h, "a"));
return 0;
}
</syntaxhighlight>
==Libraries==
Line 10 ⟶ 59:
{{libheader|Judy}}
<syntaxhighlight lang="с">
▲<lang c>#include <stdio.h>
#include <stdio.h>
#include <Judy.h>
Line 43 ⟶ 93:
return 0;
}
</syntaxhighlight>
{{libheader|Judy}}
Line 49 ⟶ 100:
We can easily iterate over pair of keys (indexes) and values.
<
#include <Judy.h>
Line 80 ⟶ 131:
JudySLFreeArray(&assoc_arr, PJE0);
return 0;
}</
===POSIX hsearch()===
Line 102 ⟶ 153:
{{libheader|POSIX}}
<
#include <search.h> /* hcreate(), hsearch() */
#include <stdio.h> /* perror(), printf() */
Line 193 ⟶ 244:
*/
return 0;
}</
<pre>red has value ff0000
Line 205 ⟶ 256:
====To delete or iterate====
{{libheader|POSIX}}
<
#include <search.h>
#include <stdio.h>
Line 354 ⟶ 405:
return 0;
}</
<pre>5 is not deleted
Line 381 ⟶ 432:
{{works with|OpenBSD|4.8}}
<
#include <err.h> /* err() */
Line 606 ⟶ 657:
number_example();
return 0;
}</
Output:
Line 629 ⟶ 680:
{{works with|OpenBSD|4.8}}
<
#include <err.h> /* err() */
Line 851 ⟶ 902:
number_example();
return 0;
}</
Output:
|