aboutsummaryrefslogtreecommitdiff
path: root/hashtab.c
diff options
context:
space:
mode:
authorThomas Schmucker <ts@its1.de>2022-04-09 09:43:53 +0200
committerThomas Schmucker <ts@its1.de>2022-04-09 09:43:53 +0200
commit154874afda4a8df885e51c01f7681f04fb0b8e61 (patch)
tree274817eb2793584b0e3d856de5504a614f2b4e89 /hashtab.c
parent2863f4f1d2a6a6a8704454824d6c291d2e0d4b5c (diff)
downloaddata-structures-154874afda4a8df885e51c01f7681f04fb0b8e61.tar.gz
data-structures-154874afda4a8df885e51c01f7681f04fb0b8e61.tar.bz2
data-structures-154874afda4a8df885e51c01f7681f04fb0b8e61.zip
neue Verzeichnisstruktur
Diffstat (limited to 'hashtab.c')
-rw-r--r--hashtab.c220
1 files changed, 0 insertions, 220 deletions
diff --git a/hashtab.c b/hashtab.c
deleted file mode 100644
index 256fac9..0000000
--- a/hashtab.c
+++ /dev/null
@@ -1,220 +0,0 @@
1#include <ctype.h>
2#include <stdbool.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6
7#include "util.h"
8
9/* --8<-- hash_type */
10typedef int T;
11
12struct hash_item {
13 struct hash_item *next;
14 char * key;
15 T data;
16};
17
18struct hash_tab {
19 struct hash_item *table[251]; // fit for your needs...
20};
21/* -->8-- */
22
23/* --8<-- hash_key */
24static unsigned long
25hash_key(const unsigned char *str)
26{
27 unsigned long hash = 5381;
28 unsigned int c;
29
30 while ( (c = *str++) != '\0' )
31 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
32
33 return hash;
34}
35/* -->8-- */
36
37/* --8<-- hash_init */
38void
39hash_init(struct hash_tab *ht)
40{
41 for ( size_t i = 0; i != NELEM(ht->table); ++i )
42 ht->table[i] = NULL;
43}
44/* -->8-- */
45
46/* --8<-- hash_add */
47static struct hash_item *
48hash_add(struct hash_item *next, const char *key, T data)
49{
50 struct hash_item *new_item;
51 char * new_key;
52
53 new_key = strdup(key); // strdup: not standard but commonly used...
54 new_item = malloc(sizeof *new_item);
55
56 if ( new_key == NULL || new_item == NULL ) {
57 free(new_key);
58 free(new_item);
59 ERROR("out of memory");
60 return NULL;
61 }
62
63 new_item->next = next;
64 new_item->key = new_key;
65 new_item->data = data;
66
67 return new_item;
68}
69/* -->8-- */
70
71/* --8<-- hash_lookup */
72T *
73hash_lookup(struct hash_tab *ht, const char *key, T data, int create)
74{
75 unsigned long h;
76 struct hash_item *item;
77
78 h = hash_key((const unsigned char *) key) % NELEM(ht->table);
79 for ( item = ht->table[h]; item; item = item->next )
80 if ( strcmp(key, item->key) == 0 )
81 return &item->data;
82
83 // not found! create?
84 if ( create ) {
85 item = hash_add(ht->table[h], key, data);
86 if ( item )
87 ht->table[h] = item;
88 else
89 ERROR("can't create item");
90 }
91
92 return item ? &item->data : NULL;
93}
94/* -->8-- */
95
96/* --8<-- hash_delete */
97bool
98hash_delete(struct hash_tab *ht, const char *key)
99{
100 unsigned long h;
101 struct hash_item *prev, *p;
102
103 h = hash_key((const unsigned char *) key) % NELEM(ht->table);
104 prev = NULL;
105 for ( p = ht->table[h]; p; p = p->next ) {
106 if ( strcmp(key, p->key) == 0 ) {
107 if ( prev == NULL )
108 ht->table[h] = p->next;
109 else
110 prev->next = p->next;
111
112 free(p->key);
113 free(p);
114
115 return true; // successfully removed!
116 }
117 prev = p;
118 }
119
120 return false;
121}
122/* -->8-- */
123
124/* --8<-- hash_apply */
125void
126hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl)
127{
128 struct hash_item *item;
129
130 for ( size_t i = 0; i != NELEM(ht->table); ++i )
131 for ( item = ht->table[i]; item; item = item->next )
132 visit(item->key, item->data, cl);
133}
134/* -->8-- */
135
136/* --8<-- hash_free */
137void
138hash_free(struct hash_tab *ht)
139{
140 struct hash_item *p, *next;
141
142 for ( size_t i = 0; i != NELEM(ht->table); ++i ) {
143 for ( p = ht->table[i]; p; p = next ) {
144 next = p->next;
145 free(p->key);
146 free(p);
147 }
148 ht->table[i] = NULL;
149 }
150}
151/* -->8-- */
152
153static int
154getword(FILE *fp, char *buf, size_t size, int first(int), int rest(int))
155{
156 size_t i = 0;
157 int c;
158
159 c = getc(fp);
160 for ( ; c != EOF; c = getc(fp) )
161 if ( first(c) ) {
162 if ( i < size - 1 )
163 buf[i++] = c;
164 c = getc(fp);
165 break;
166 }
167
168 for ( ; c != EOF && rest(c); c = getc(fp) )
169 if ( i < size - 1 )
170 buf[i++] = c;
171
172 if ( i < size )
173 buf[i] = 0;
174 else
175 buf[size - 1] = 0;
176
177 if ( c != EOF )
178 ungetc(c, fp);
179
180 return c > 0;
181}
182
183static int
184first(int c)
185{
186 return isalpha(c);
187}
188
189static int
190rest(int c)
191{
192 return isalpha(c) || c == '_';
193}
194
195static void
196print(const char *key, T data, void *cl)
197{
198 fprintf(cl, "%s: %d\n", key, data);
199}
200
201int
202main()
203{
204 struct hash_tab ht[1];
205 char word[100];
206
207 hash_init(ht);
208
209 while ( getword(stdin, word, sizeof word, first, rest) ) {
210 T *p = hash_lookup(ht, word, 0, 1);
211 if ( p )
212 ++(*p);
213 }
214
215 hash_delete(ht, "new_item");
216
217 hash_apply(ht, print, stdout);
218
219 hash_free(ht);
220}