Associative arrays/Creation/C: Difference between revisions
loop
(The page must be in only one collection (so I guess). Remove text about awful libraries; the bigger problem seems to be awful code on this page.) |
(loop) |
||
(8 intermediate revisions by 4 users not shown) | |||
Line 1:
There are no associative arrays in the C language. Some libraries provide hash tables, red-black trees, or other data structures that can become associative arrays.
* 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 12 ⟶ 59:
{{libheader|Judy}}
<syntaxhighlight lang="с">
▲<lang c>#include <stdio.h>
#include <stdio.h>
#include <Judy.h>
Line 45 ⟶ 93:
return 0;
}
</syntaxhighlight>
{{libheader|Judy}}
Line 51 ⟶ 100:
We can easily iterate over pair of keys (indexes) and values.
<
#include <Judy.h>
Line 82 ⟶ 131:
JudySLFreeArray(&assoc_arr, PJE0);
return 0;
}</
===POSIX hsearch()===
Line 104 ⟶ 153:
{{libheader|POSIX}}
<
#include <search.h> /* hcreate(), hsearch() */
#include <stdio.h> /* perror(), printf() */
Line 195 ⟶ 244:
*/
return 0;
}</
<pre>red has value ff0000
Line 207 ⟶ 256:
====To delete or iterate====
{{libheader|POSIX}}
<
#include <search.h>
#include <stdio.h>
Line 356 ⟶ 405:
return 0;
}</
<pre>5 is not deleted
Line 383 ⟶ 432:
{{works with|OpenBSD|4.8}}
<
#include <err.h> /* err() */
Line 608 ⟶ 657:
number_example();
return 0;
}</
Output:
Line 631 ⟶ 680:
{{works with|OpenBSD|4.8}}
<
#include <err.h> /* err() */
Line 853 ⟶ 902:
number_example();
return 0;
}</
Output:
|