Anonymous user
Associative arrays/Creation/C: Difference between revisions
→POSIX hsearch(): Redesign and rewrite the code. The old code was a mess. The new code has fetch(), store() and delete() functions.
(Split from Associative arrays/Creation and Associative arrays/Iteration, to make room for expansion. This text has multiple authors.) |
(→POSIX hsearch(): Redesign and rewrite the code. The old code was a mess. The new code has fetch(), store() and delete() functions.) |
||
Line 82:
}</lang>
===POSIX
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!
* There is no way to delete an entry from the table!
* There is no way to iterate all keys in the table!
The Linux manual page [http://
====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====
To use the hash table as an associative array, this program defines fetch() and store().
{{libheader|POSIX}}
<lang c>#include <
#include <
#include <stdio.h> /* perror(), printf() */
#include <stdlib.h> /* exit() */
void
Line 115 ⟶ 113:
exit(1);
}
/*
* Must hcreate() the hash table before calling fetch() or store().
*
* Because
* void * and intptr_t.
*/
/* Fetch value from the hash table. */
int
fetch(const char *key, intptr_t *value)
{
ENTRY e = {key: (char *)key}, *
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)
{
/*
* hsearch() may insert a new entry or find an existing entry
*
* 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;
/* First, create an empty table that can hold 50 entries. */
if (hcreate(50) == 0)
fail("hcreate");
/*
* Some colors from CSS2,
* http://www.w3.org/TR/CSS2/syndata.html#value-def-color
*/
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. */
if (fetch(keys[i], &value))
printf("%s has value %06" PRIxPTR "\n",
keys[i], value);
else
printf("%s is not in table\n", keys[i]);
}
/*
*
*
* With BSD libc, hdestroy() would call free() with each key in
*
*/
return 0;
}</lang>
<pre>red has value ff0000
orange has value ffa500
yellow is not in table
green has value 008000
blue has value 0000ff
white has value ffffff
black has value 000000</pre>
====To delete or iterate====
{{libheader|POSIX}}
<lang c>#include <inttypes.h>
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void
{
perror(message);
exit(1);
}
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.
* head.next begins a list of all pairs in order of insertion.
*/
struct pair head = {&head, &head};
/* Fetch value from the hash table. */
int
fetch(int32_t key, int32_t *value)
{
ENTRY e, *p;
char buf[16];
snprintf(buf, sizeof buf, "%"PRId32, key);
e.key = buf;
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;
}
void
store(int32_t key, int32_t value)
{
ENTRY e, *p;
char buf[16];
snprintf(buf, sizeof buf, "%"PRId32, key);
e.key = buf;
if (
fail("hsearch");
if (p->key == buf) {
/* Allocate and initialize a new pair. */
struct pair *d = malloc(sizeof *d);
if (d == NULL)
fail("malloc");
d->key = key;
d->value = value;
d->deleted = 0;
p->key = strdup(buf);
/*
* Insert the new pair into the hash table's entry, and
* into the circular queue.
p->data = d;
insque(d, &head);
} else {
/* Replace the value. */
struct pair *d = p->data;
d->value = value;
/* Restore a deleted key. */
d->deleted = 0;
}
}
}
int
delete(int32_t key)
{
ENTRY e, *p;
char buf[16];
snprintf(buf, sizeof buf, "%"PRId32, key);
e.key = buf;
p = hsearch(e, FIND);
if (p) {
if (d->deleted)
return 0;
else {
remque(d);
return d->deleted = 1;
}
} else
return 0;
}
Line 336 ⟶ 326:
main()
{
struct pair *p;
int32_t value;
int i;
if (hcreate(50) == 0)
fail("hcreate");
store(1, mrand48());
store(2, mrand48());
store(3, mrand48());
for (i = 0; i < 3; i++)
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:");
for (p = head.next; p != &head; p = p->next) {
printf(" %"PRId32" => %"PRId32"\n", p->key, p->value);
}
return 0;
}</lang>
<pre>5 is not deleted
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()====
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().
===BSD dbopen()===
| |||