Rosetta Code

Associative arrays/Creation/C: Difference between revisions

Page Discussion

Associative arrays/Creation/C (view source)

Revision as of 21:09, 23 April 2023

1,741 bytes added ,  1 year ago
loop
(Split from Associative arrays/Creation and Associative arrays/Iteration, to make room for expansion. This text has multiple authors.)
 
(loop)
 
(11 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.
{{collection|Associative arrays/Creation}}
{{collection|Associative arrays/Iteration}}
 
* Back to [[Associative arrays/Creation]].
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. Some of these libraries are awful. There are too many easy ways to get a compiler error or a segfault.
 
==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 <stdio.h>
#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;
}
}</lang>
</syntaxhighlight>
 
{{libheader|Judy}}
Line 49 ⟶ 100:
We can easily iterate over pair of keys (indexes) and values.
 
<langsyntaxhighlight clang="с">#include <stdio.h>
#include <Judy.h>
 
Line 80 ⟶ 131:
JudySLFreeArray(&assoc_arr, PJE0);
return 0;
}</langsyntaxhighlight>
 
===POSIX hcreatehsearch()===
POSIX defines hcreate(), hdestroy() and hsearch() to manage a hash table. If you have a [[Unix]] system or clone, then your libc probably has these functions, so there is no extra library to install.
 
These functions have some major limitations:
 
* You can only have one hash table, in the entire program!
** With GNU libc, you can call hcreate_r() to have more than one hash table.
* There is no way to delete an entry from the table!
* There is no way to iterate all keys in the table!
* Every key must be a NUL-terminated string.
* Every value is a void *, needs a cast to the correct type.
* The table might become full, and refuse to accept more entries. If you use hcreate(50) then the table might hold at most 50 entries.
* hdestroy() is almost impossible to use. Many programs keep the table and never call hdestroy().
** With BSD libc, hdestroy() will call free() with each key in the table.
** Else the program leaks memory, because there is no way to iterate the keys to free them.
 
The Linux manual page [http://manwww.cxkernel.org/hcreatedoc/man-pages/online/pages/man3/hsearch.3.html hcreatehsearch(3)] hascontains a short example.
 
====To create the hash table====
The hash table has a fixed capacity. <code>hcreate(50)</code> creates a table for 50 entries. The library might increase 50 to a convenient value (perhaps 64 being a power of 2, or 67 being a prime number). The hash table might have only 64 or 67 slots. Each slot might hold one entry, or one list of entries. Access to the hash table is near [[O|O(1)]], but slows to [[O|O(n)]] as the slots become full.
 
The hash table is an associative array of key-value pairs. Each key must be a NUL-terminated string. Each value is a void *.
 
====To fetch or store====
The next example shows how to use hdestroy(), how to use ''intptr_t'' as a value, how to use ''double'' as a key, and how to pretend to delete an entry from the table! POSIX hash table is awful, and the code is too long, but the program does run.
To use the hash table as an associative array, this program defines fetch() and store().
 
{{libheader|POSIX}}
<syntaxhighlight lang="с">#include <inttypes.h> /* intptr_t, PRIxPTR */
 
<lang c>#include <inttypessearch.h> /* PRIxPTRhcreate(), hsearch() */
#include <searchstdio.h> /* hcreateperror(), hsearch(), hdestroyprintf() */
#include <stdintstdlib.h> /* intptr_texit() */
#include <stdio.h> /* perror(), printf(), puts(), snprintf() */
#include <stdlib.h> /* calloc(), exit(), free() */
#include <string.h> /* strdup() */
 
void
Line 115 ⟶ 164:
exit(1);
}
 
 
/*
* Must hcreate() the hash table before calling fetch() or store().
* color_example:
* Maps color strings to integer values, like "red" => 0xff0000.
*
* Because thep->data valuesis (ENTRYa data) are pointerspointer, Ifetch() useand castsstore() to andcast frombetween
* void * and intptr_t.
* intptr_t to store integers instead of pointers.
*/
 
/* Fetch value from the hash table. */
int
fetch(const char *key, intptr_t *value)
{
ENTRY e = {key: (char *)key}, *p;
p = hsearch(e, FIND);
if (p) {
*value = (intptr_t)p->data;
return 1;
} else
return 0;
}
 
/* Store key-value pair into the hash table. */
void
store(const char *key, intptr_t value)
color_example(void)
{
/*
ENTRY e, *ep;
* hsearch() may insert a new entry or find an existing entry
* with the same key. hsearch() ignores e.data if it finds an
* existing entry. We must call hsearch(), then set p->data.
*/
ENTRY e = {key: (char *)key}, *p;
p = hsearch(e, ENTER);
if (p == NULL)
fail("hsearch");
p->data = (void *)value;
}
 
/*
* Use the hash table to map color strings to integer values,
* like "red" => 0xff0000.
*/
int
main()
{
static const char *const keys[] =
{"red", "orange", "yellow", "green", "blue", "white", "black"};
intptr_t value;
int i;
 
/* First, create an empty table that can hold 50 entries. */
puts("color_example:");
 
/* Create an empty table. */
if (hcreate(50) == 0)
fail("hcreate");
 
/*
/* Add keys => values to table. */
* Some colors from CSS2,
{
* http://www.w3.org/TR/CSS2/syndata.html#value-def-color
char *keys[] = { "red", "green", "blue" };
*/
intptr_t values[] = { 0xff0000, 0x00ff00, 0x0000ff };
store("red", 0xff0000);
store("orange", 0x123456); /* Insert wrong value! */
store("green", 0x008000);
store("blue", 0x0000ff);
store("white", 0xffffff);
store("black", 0x000000);
store("orange", 0xffa500); /* Replace with correct value. */
 
for (i = 0; i < 3sizeof(keys) / sizeof(keys[0]); i++) {
if (fetch(keys[i], &value))
/* Need strdup() when using ENTER. */
printf("%s has value %06" PRIxPTR "\n",
if ((e.key = strdup(keys[i])) == NULL)
fail("strdup" keys[i], value);
else
e.data = (void *)values[i];
printf("%s is not in table\n", keys[i]);
 
/* Insert e into table. */
if (hsearch(e, ENTER) == NULL)
fail("hsearch");
}
}
 
/*
/* Check if keys exist. */
* DO NOT CALL hdestroy().
{
*
char *keys[] = { "blue", "green", "orange", "red" };
* With BSD libc, hdestroy() would call free() with each key in
* table. Our keys are static strings, so free() would crash.
*/
return 0;
}</syntaxhighlight>
 
<pre>red has value ff0000
for (i = 0; i < 4; i++) {
orange has value ffa500
/* Not using ENTER, so no strdup(). */
yellow is not in table
e.key = keys[i];
green has value 008000
ep = hsearch(e, FIND);
blue has value 0000ff
if (ep) {
printf("\t'%s'white has value %06" PRIxPTR "\n",ffffff
black has value 000000</pre>
ep->key, (intptr_t)ep->data);
} else
printf("\t'%s' is not in table\n", e.key);
}
}
 
====To delete or iterate====
/*
{{libheader|POSIX}}
* Destroy table. On my machine, hdestroy() will free() all the
<syntaxhighlight lang="с">#include <inttypes.h>
* keys in the table. This is why I had to strdup() my keys.
#include <search.h>
*/
#include <stdio.h>
hdestroy();
#include <stdlib.h>
#include <string.h>
 
void
fail(char *message)
{
perror(message);
exit(1);
}
 
/* A key-value pair */
struct pair {
/* prev is q_forw, so insque(d, &head) sets head.prev = d */
struct pair *prev; /* q_forw */
struct pair *next; /* q_back */
int32_t key;
int32_t value;
int deleted;
};
 
/*
* A circular queue of all pairs in the hash table.
* number_example:
* head.next begins a list of all pairs in order of insertion.
* Maps numbers to strings or numbers, like 2 => 2.71828 or 4 => "four".
*
* First I need a VALUE that can either be a string or a number.
*/
typedef struct valuepair head = {&head, &head};
int v_type;
#define T_NUM 0x1 /* use v_num */
#define T_STR 0x2 /* use v_str */
#define T_DEL 0x4 /* pretend to delete from table */
 
/* Fetch value from the hash table. */
union {
int
double u_num;
fetch(int32_t key, int32_t *value)
char *u_str;
{
} v_union;
ENTRY e, *p;
#define v_num v_union.u_num
char buf[16];
#define v_str v_union.u_str
 
snprintf(buf, sizeof buf, "%"PRId32, key);
struct value *next; /* link all VALUEs in a list */
e.key = buf;
} VALUE;
p = hsearch(e, FIND);
if (p) {
struct pair *d = p->data;
if (d->deleted)
return 0;
else {
*value = d->value;
return 1;
}
} else
return 0;
}
 
/* Store key-value pair into the hash table. */
void
store(int32_t key, int32_t value)
number_example(void)
{
ENTRY e, *epp;
VALUE *all = NULL, *vp;
int i, s;
char buf[16];
 
snprintf(buf, sizeof buf, "%"PRId32, key);
puts("number_example:");
e.key = buf;
 
p = hsearch(e, ENTER);
if (hcreate(50) == 0)
if (p == NULL)
fail("hcreate");
fail("hsearch");
 
/* Add numeric values. */
{
double keys[] = { 2, 3, 4, 5.6 };
double values[] = { 2.71828, 3.14159, 4.47214, 7.8 };
 
for (i = 0; i < 4; i++) {
/* Must convert keys to strings. */
snprintf(buf, sizeof buf, "%.6g", keys[i]);
if ((e.key = strdup(buf)) == NULL)
fail("strdup");
 
if (p->key == buf) {
/* Allocate a new VALUE. */
/* Allocate and initialize a new pair. */
if ((vp = calloc(1, sizeof vp[0])) == NULL)
struct pair *d = malloc(sizeof *d);
fail("calloc");
if (d == NULL)
vp->v_type = T_NUM;
fail("malloc");
vp->v_num = values[i];
e.datad->key = vpkey;
d->value = value;
d->deleted = 0;
 
/* RememberAllocate tospace freefor itkey, apart from buf. */
vpp->nextkey = allstrdup(buf);
allif (p->key == vp;NULL)
fail("strdup");
 
/*
if (hsearch(e, ENTER) == NULL)
* Insert the new pair into the hash table's entry, and
fail("hsearch");
* into the circular queue.
*/
p->data = d;
insque(d, &head);
} else {
/* Replace the value. */
struct pair *d = p->data;
d->value = value;
if (d->deleted) {
/* Restore a deleted key. */
insque(d, &head);
d->deleted = 0;
}
}
}
 
/* Delete key from the hash table. */
/*
int
* Add string values.
delete(int32_t key)
*
{
* For this example, all of my values will be static string
ENTRY e, *p;
* constants. This removes the need to free(vp->v_str)
char buf[16];
* when I replace or delete a value.
*/
{
double keys[] = { 4, 8, 10 };
char *values[] = { "four", "eight", "ten" };
 
snprintf(buf, sizeof buf, "%"PRId32, key);
for (i = 0; i < 3; i++) {
e.key = buf;
/* Must convert keys to strings. */
p = hsearch(e, FIND);
snprintf(buf, sizeof buf, "%.6g", keys[i]);
if (p) {
 
struct pair *d = p->data;
/*
if (d->deleted)
* This shows how to add or replace a value
return 0;
* in the table (so I can change an entry
else {
* from 4 => 4.47214 to 4 => "four").
*/remque(d);
e.keyreturn d->deleted = buf1;
ep = hsearch(e, FIND);
if (ep) {
/* Already have key. Change value. */
vp = (VALUE *)ep->data;
vp->v_type = T_STR;
vp->v_str = values[i];
} else {
/* Need to add key. */
if ((e.key = strdup(buf)) == NULL)
fail("strdup");
 
if ((vp = calloc(1, sizeof vp[0])) == NULL)
fail("calloc");
vp->v_type = T_STR;
vp->v_str = values[i];
e.data = vp;
 
/* Remember to free it. */
vp->next = all;
all = vp;
if (hsearch(e, ENTER) == NULL)
fail("hsearch");
}
}
} else
return 0;
}
 
int
/* Delete key 8. */
main()
snprintf(buf, sizeof buf, "%.6g", (double)8);
{
e.key = buf;
struct pair *p;
ep = hsearch(e, FIND);
int32_t value;
if (ep) {
int i;
vp = (VALUE *)ep->data;
vp->v_type = T_DEL;
}
 
if (hcreate(50) == 0)
/* Check if keys exist. */
fail("hcreate");
{
double keys[] = { 2, 3, 4, 5.6, 7, 8, 10 };
 
store(1, mrand48());
for (i = 0; i < 7; i++) {
store(2, mrand48());
snprintf(buf, sizeof buf, "%.6g", keys[i]);
store(3, mrand48());
e.key = buf;
for (i = 0; i < 3; i++)
ep = hsearch(e, FIND);
store(mrand48(), mrand48());
store(4, mrand48());
delete(1) || puts("1 is not deleted");
delete(2) || puts("2 is not deleted");
delete(5) || puts("5 is not deleted");
store(1, mrand48());
store(3, mrand48());
fetch(2, &value) ? puts("2 is in table") : puts("2 is missing");
fetch(4, &value) ? puts("4 is in table") : puts("4 is missing");
fetch(6, &value) ? puts("6 is in table") : puts("6 is missing");
 
puts("Iterating the hash table:");
if (ep == NULL ||
for (p = head.next; p != &head; p = p->next) {
(vp = (VALUE *)ep->data)->v_type & T_DEL) {
printf("\t%s is not%"PRId32" in=> the table%"PRId32"\n", p->key, p->value);
buf);
} else if (vp->v_type & T_NUM) {
printf("\t%s has value %g\n",
buf, vp->v_num);
} else if (vp->v_type & T_STR) {
printf("\t%s has value '%s'\n",
buf, vp->v_str);
} else {
printf("\t%s has invalid value\n",
buf);
}
}
}
 
/* Destroy table and keys. */
hdestroy();
 
/* Free all values. */
while (all != NULL) {
vp = all->next;
free(all);
all = vp;
}
}
 
int
main()
{
color_example();
number_example();
return 0;
}</langsyntaxhighlight>
 
<pre>5 is not deleted
Output:
2 is missing
4 is in table
6 is missing
Iterating the hash table:
3 => 252797108
1368775034 => 1918061247
66927828 => -487786166
684483038 => -1786318902
4 => 1648047133
1 => -1327126111</pre>
 
====hdestroy()====
<pre>color_example:
hdestroy() is almost impossible to use. With BSD libc, hdestroy() will call free() with each key in the table. With other systems, hdestroy() might leak memory, because the program has no way to iterate the keys to free them. Most programs keep the hash table and never call hdestroy().
'blue' has value 0000ff
'green' has value 00ff00
'orange' is not in table
'red' has value ff0000
number_example:
2 has value 2.71828
3 has value 3.14159
4 has value 'four'
5.6 has value 7.8
7 is not in the table
8 is not in the table
10 has value 'ten'</pre>
 
===BSD dbopen()===
Line 362 ⟶ 427:
* Warning: some GNU/Linux systems have a dbopen(3) manual page without a real dbopen() function. See [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=337581 Debian bug #337581].
 
The next example translates the previous example to dbopen(). Every key and value is a *void, needs a cast to the correct type. Because BSD also has <err.h>, I remove fail() and use err().
 
{{libheader|BSD libc}}
{{works with|OpenBSD|4.8}}
 
<langsyntaxhighlight clang="с">#include <sys/types.h>
 
#include <err.h> /* err() */
Line 592 ⟶ 657:
number_example();
return 0;
}</langsyntaxhighlight>
 
Output:
Line 615 ⟶ 680:
{{works with|OpenBSD|4.8}}
 
<langsyntaxhighlight clang="с">#include <sys/tree.h>
 
#include <err.h> /* err() */
Line 837 ⟶ 902:
number_example();
return 0;
}</langsyntaxhighlight>
 
Output:
Eugrus
45

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/198729...340822"