erster Commit

1 files changed, 198 insertions, 0 deletions

diff --git a/hashtab.c b/hashtab.c
new file mode 100644
index 0000000..6b35c89
--- /dev/null
+++ b/hashtab.c
@@ -0,0 +1,198 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+#include <ctype.h>
+
+#include "util.h"
+
+typedef int T;
+
+struct hash_item {
+        struct hash_item *next;
+        char *key;
+        T data;
+};
+
+struct hash_tab {
+        struct hash_item *table[251];           // fit for your needs...
+};
+
+static unsigned long
+hash_key(const unsigned char *str)
+{
+        unsigned long hash = 5381;
+        int c;
+
+        while ( (c = *str++) != '\0' )
+                hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
+
+        return hash;
+}
+
+void
+hash_init(struct hash_tab *ht)
+{
+        for ( int i = 0; i != NELEM(ht->table); ++i )
+                ht->table[i] = NULL;
+}
+
+static struct hash_item *
+hash_add(struct hash_item *next, const char *key, T data)
+{
+        struct hash_item *new_item;
+        char *new_key;
+
+        new_key = strdup(key);  // strdup: not standard but commonly used...
+        new_item = malloc(sizeof(*new_item));
+
+        if ( new_key == NULL || new_item == NULL ) {
+                free(new_key);
+                free(new_item);
+                ERROR("out of memory");
+                return NULL;
+        }
+
+        new_item->next = next;
+        new_item->key = new_key;
+        new_item->data = data;
+
+        return new_item;
+}
+
+T *
+hash_lookup(struct hash_tab *ht, const char *key, T data, int create)
+{
+        unsigned long h;
+        struct hash_item *item;
+   
+        h = hash_key((const unsigned char *) key) % NELEM(ht->table);
+        for ( item = ht->table[h]; item; item = item->next )
+                if ( strcmp(key, item->key) == 0 )
+                        return &item->data;
+
+        // not found! create?
+        if ( create ) {
+                item = hash_add(ht->table[h], key, data);
+                if ( item != NULL )
+                        ht->table[h] = item;
+                else
+                        ERROR("can't create item");
+        }
+
+        return item ? &item->data : NULL;
+}
+
+bool
+hash_delete(struct hash_tab *ht, const char *key)
+{
+        unsigned long h;
+        struct hash_item *prev, *p;
+
+        h = hash_key((const unsigned char *) key) % NELEM(ht->table);
+        prev = NULL;
+        for ( p = ht->table[h]; p; p = p->next ) {
+                if ( strcmp(key, p->key) == 0 ) {
+                        if ( prev == NULL )
+                                ht->table[h] = p->next;
+                        else
+                                prev->next = p->next;
+
+                        free(p->key);
+                        free(p);
+
+                        return true;            // successfully removed!
+                }
+                prev = p;
+        }
+
+        return false;
+}
+
+void
+hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl)
+{
+        struct hash_item *item;
+
+        for ( int i = 0; i != NELEM(ht->table); ++i )
+                for ( item = ht->table[i]; item; item = item->next )
+                        visit(item->key, item->data, cl);
+}
+
+void
+hash_free(struct hash_tab *ht)
+{
+        struct hash_item *p, *next;
+
+        for ( int i = 0; i != NELEM(ht->table); ++i ) {
+                for ( p = ht->table[i]; p; p = next ) {
+                        next = p->next;
+                        free(p->key);
+                        free(p);
+                }
+                ht->table[i] = NULL;
+        }
+}
+
+int getword(FILE *fp, char *buf, int size, int first(int c), int rest(int c))
+{
+        int i = 0, c;
+
+        c = getc(fp);
+        for ( ; c != EOF; c = getc(fp) )
+                if ( first(c) ) {
+                        if ( i < size-1 )
+                                buf[i++] = c;
+                        c = getc(fp);
+                        break;
+                }
+
+        for ( ; c != EOF && rest(c); c = getc(fp) )
+                if ( i < size-1)
+                        buf[i++] = c;
+
+        if ( i < size )
+                buf[i] = 0;
+        else
+                buf[size-1] = 0;
+
+        if ( c != EOF )
+                ungetc(c, fp);
+
+        return c > 0;
+}
+
+int first(int c) {
+        return isalpha(c);
+}
+
+int rest(int c) {
+        return isalpha(c) || c == '_';
+}
+
+void print(const char *key, T data, void *cl)
+{
+        fprintf(cl, "%s: %d\n", key, data);
+}
+
+int
+main()
+{
+        struct hash_tab ht[1];
+        char word[100];
+
+        hash_init(ht);
+
+        while ( getword(stdin, word, sizeof word, first, rest) ) {
+                int *p = hash_lookup(ht, word, 0, 1);
+                if ( p != NULL )
+                        ++(*p);
+        }
+
+        hash_delete(ht, "new_item");
+
+        hash_apply(ht, print, stdout);
+
+        hash_free(ht);
+}
+