aboutsummaryrefslogtreecommitdiff
path: root/hashtab.c
diff options
context:
space:
mode:
authorThomas Schmucker <ts@its1.de>2020-08-02 10:38:41 +0200
committerThomas Schmucker <ts@its1.de>2020-08-02 10:38:41 +0200
commite7986e3e11b9ca91079bacae7fc2f79dce515f5d (patch)
tree8445b05e4b1f3f8c0dfeef5f9e6d023f52ad108d /hashtab.c
parent1aecbf40567f0f1943285c774b4d6369e1a90ceb (diff)
downloaddata-structures-e7986e3e11b9ca91079bacae7fc2f79dce515f5d.tar.gz
data-structures-e7986e3e11b9ca91079bacae7fc2f79dce515f5d.tar.bz2
data-structures-e7986e3e11b9ca91079bacae7fc2f79dce515f5d.zip
format code
Diffstat (limited to 'hashtab.c')
-rw-r--r--hashtab.c51
1 files changed, 28 insertions, 23 deletions
diff --git a/hashtab.c b/hashtab.c
index 6b35c89..e53da51 100644
--- a/hashtab.c
+++ b/hashtab.c
@@ -1,8 +1,8 @@
1#include <ctype.h>
2#include <stdbool.h>
1#include <stdio.h> 3#include <stdio.h>
2#include <stdlib.h> 4#include <stdlib.h>
3#include <string.h> 5#include <string.h>
4#include <stdbool.h>
5#include <ctype.h>
6 6
7#include "util.h" 7#include "util.h"
8 8
@@ -10,19 +10,19 @@ typedef int T;
10 10
11struct hash_item { 11struct hash_item {
12 struct hash_item *next; 12 struct hash_item *next;
13 char *key; 13 char * key;
14 T data; 14 T data;
15}; 15};
16 16
17struct hash_tab { 17struct hash_tab {
18 struct hash_item *table[251]; // fit for your needs... 18 struct hash_item *table[251]; // fit for your needs...
19}; 19};
20 20
21static unsigned long 21static unsigned long
22hash_key(const unsigned char *str) 22hash_key(const unsigned char *str)
23{ 23{
24 unsigned long hash = 5381; 24 unsigned long hash = 5381;
25 int c; 25 int c;
26 26
27 while ( (c = *str++) != '\0' ) 27 while ( (c = *str++) != '\0' )
28 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 28 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
@@ -41,9 +41,9 @@ static struct hash_item *
41hash_add(struct hash_item *next, const char *key, T data) 41hash_add(struct hash_item *next, const char *key, T data)
42{ 42{
43 struct hash_item *new_item; 43 struct hash_item *new_item;
44 char *new_key; 44 char * new_key;
45 45
46 new_key = strdup(key); // strdup: not standard but commonly used... 46 new_key = strdup(key); // strdup: not standard but commonly used...
47 new_item = malloc(sizeof(*new_item)); 47 new_item = malloc(sizeof(*new_item));
48 48
49 if ( new_key == NULL || new_item == NULL ) { 49 if ( new_key == NULL || new_item == NULL ) {
@@ -54,7 +54,7 @@ hash_add(struct hash_item *next, const char *key, T data)
54 } 54 }
55 55
56 new_item->next = next; 56 new_item->next = next;
57 new_item->key = new_key; 57 new_item->key = new_key;
58 new_item->data = data; 58 new_item->data = data;
59 59
60 return new_item; 60 return new_item;
@@ -63,9 +63,9 @@ hash_add(struct hash_item *next, const char *key, T data)
63T * 63T *
64hash_lookup(struct hash_tab *ht, const char *key, T data, int create) 64hash_lookup(struct hash_tab *ht, const char *key, T data, int create)
65{ 65{
66 unsigned long h; 66 unsigned long h;
67 struct hash_item *item; 67 struct hash_item *item;
68 68
69 h = hash_key((const unsigned char *) key) % NELEM(ht->table); 69 h = hash_key((const unsigned char *) key) % NELEM(ht->table);
70 for ( item = ht->table[h]; item; item = item->next ) 70 for ( item = ht->table[h]; item; item = item->next )
71 if ( strcmp(key, item->key) == 0 ) 71 if ( strcmp(key, item->key) == 0 )
@@ -86,10 +86,10 @@ hash_lookup(struct hash_tab *ht, const char *key, T data, int create)
86bool 86bool
87hash_delete(struct hash_tab *ht, const char *key) 87hash_delete(struct hash_tab *ht, const char *key)
88{ 88{
89 unsigned long h; 89 unsigned long h;
90 struct hash_item *prev, *p; 90 struct hash_item *prev, *p;
91 91
92 h = hash_key((const unsigned char *) key) % NELEM(ht->table); 92 h = hash_key((const unsigned char *) key) % NELEM(ht->table);
93 prev = NULL; 93 prev = NULL;
94 for ( p = ht->table[h]; p; p = p->next ) { 94 for ( p = ht->table[h]; p; p = p->next ) {
95 if ( strcmp(key, p->key) == 0 ) { 95 if ( strcmp(key, p->key) == 0 ) {
@@ -101,7 +101,7 @@ hash_delete(struct hash_tab *ht, const char *key)
101 free(p->key); 101 free(p->key);
102 free(p); 102 free(p);
103 103
104 return true; // successfully removed! 104 return true; // successfully removed!
105 } 105 }
106 prev = p; 106 prev = p;
107 } 107 }
@@ -134,27 +134,28 @@ hash_free(struct hash_tab *ht)
134 } 134 }
135} 135}
136 136
137int getword(FILE *fp, char *buf, int size, int first(int c), int rest(int c)) 137int
138getword(FILE *fp, char *buf, int size, int first(int), int rest(int))
138{ 139{
139 int i = 0, c; 140 int i = 0, c;
140 141
141 c = getc(fp); 142 c = getc(fp);
142 for ( ; c != EOF; c = getc(fp) ) 143 for ( ; c != EOF; c = getc(fp) )
143 if ( first(c) ) { 144 if ( first(c) ) {
144 if ( i < size-1 ) 145 if ( i < size - 1 )
145 buf[i++] = c; 146 buf[i++] = c;
146 c = getc(fp); 147 c = getc(fp);
147 break; 148 break;
148 } 149 }
149 150
150 for ( ; c != EOF && rest(c); c = getc(fp) ) 151 for ( ; c != EOF && rest(c); c = getc(fp) )
151 if ( i < size-1) 152 if ( i < size - 1 )
152 buf[i++] = c; 153 buf[i++] = c;
153 154
154 if ( i < size ) 155 if ( i < size )
155 buf[i] = 0; 156 buf[i] = 0;
156 else 157 else
157 buf[size-1] = 0; 158 buf[size - 1] = 0;
158 159
159 if ( c != EOF ) 160 if ( c != EOF )
160 ungetc(c, fp); 161 ungetc(c, fp);
@@ -162,15 +163,20 @@ int getword(FILE *fp, char *buf, int size, int first(int c), int rest(int c))
162 return c > 0; 163 return c > 0;
163} 164}
164 165
165int first(int c) { 166int
167first(int c)
168{
166 return isalpha(c); 169 return isalpha(c);
167} 170}
168 171
169int rest(int c) { 172int
173rest(int c)
174{
170 return isalpha(c) || c == '_'; 175 return isalpha(c) || c == '_';
171} 176}
172 177
173void print(const char *key, T data, void *cl) 178void
179print(const char *key, T data, void *cl)
174{ 180{
175 fprintf(cl, "%s: %d\n", key, data); 181 fprintf(cl, "%s: %d\n", key, data);
176} 182}
@@ -179,7 +185,7 @@ int
179main() 185main()
180{ 186{
181 struct hash_tab ht[1]; 187 struct hash_tab ht[1];
182 char word[100]; 188 char word[100];
183 189
184 hash_init(ht); 190 hash_init(ht);
185 191
@@ -195,4 +201,3 @@ main()
195 201
196 hash_free(ht); 202 hash_free(ht);
197} 203}
198