diff options
Diffstat (limited to 'hashtab.c')
| -rw-r--r-- | hashtab.c | 51 |
1 files changed, 28 insertions, 23 deletions
| @@ -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 | ||
| 11 | struct hash_item { | 11 | struct 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 | ||
| 17 | struct hash_tab { | 17 | struct 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 | ||
| 21 | static unsigned long | 21 | static unsigned long |
| 22 | hash_key(const unsigned char *str) | 22 | hash_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 * | |||
| 41 | hash_add(struct hash_item *next, const char *key, T data) | 41 | hash_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) | |||
| 63 | T * | 63 | T * |
| 64 | hash_lookup(struct hash_tab *ht, const char *key, T data, int create) | 64 | hash_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) | |||
| 86 | bool | 86 | bool |
| 87 | hash_delete(struct hash_tab *ht, const char *key) | 87 | hash_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 | ||
| 137 | int getword(FILE *fp, char *buf, int size, int first(int c), int rest(int c)) | 137 | int |
| 138 | getword(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 | ||
| 165 | int first(int c) { | 166 | int |
| 167 | first(int c) | ||
| 168 | { | ||
| 166 | return isalpha(c); | 169 | return isalpha(c); |
| 167 | } | 170 | } |
| 168 | 171 | ||
| 169 | int rest(int c) { | 172 | int |
| 173 | rest(int c) | ||
| 174 | { | ||
| 170 | return isalpha(c) || c == '_'; | 175 | return isalpha(c) || c == '_'; |
| 171 | } | 176 | } |
| 172 | 177 | ||
| 173 | void print(const char *key, T data, void *cl) | 178 | void |
| 179 | print(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 | |||
| 179 | main() | 185 | main() |
| 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 | |||
