Merge branch 'correct-file-names'

1 files changed, 220 insertions, 0 deletions

diff --git a/src/hash-table.c b/src/hash-table.c
new file mode 100644
index 0000000..256fac9
--- /dev/null
+++ b/src/hash-table.c
@@ -0,0 +1,220 @@
+#include <ctype.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "util.h"
+
+/* --8<-- hash_type */
+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...
+};
+/* -->8-- */
+
+/* --8<-- hash_key */
+static unsigned long
+hash_key(const unsigned char *str)
+{
+        unsigned long hash = 5381;
+        unsigned int  c;
+
+        while ( (c = *str++) != '\0' )
+                hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
+
+        return hash;
+}
+/* -->8-- */
+
+/* --8<-- hash_init */
+void
+hash_init(struct hash_tab *ht)
+{
+        for ( size_t i = 0; i != NELEM(ht->table); ++i )
+                ht->table[i] = NULL;
+}
+/* -->8-- */
+
+/* --8<-- hash_add */
+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;
+}
+/* -->8-- */
+
+/* --8<-- hash_lookup */
+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 )
+                        ht->table[h] = item;
+                else
+                        ERROR("can't create item");
+        }
+
+        return item ? &item->data : NULL;
+}
+/* -->8-- */
+
+/* --8<-- hash_delete */
+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;
+}
+/* -->8-- */
+
+/* --8<-- hash_apply */
+void
+hash_apply(struct hash_tab *ht, void (*visit)(const char *key, T data, void *cl), void *cl)
+{
+        struct hash_item *item;
+
+        for ( size_t i = 0; i != NELEM(ht->table); ++i )
+                for ( item = ht->table[i]; item; item = item->next )
+                        visit(item->key, item->data, cl);
+}
+/* -->8-- */
+
+/* --8<-- hash_free */
+void
+hash_free(struct hash_tab *ht)
+{
+        struct hash_item *p, *next;
+
+        for ( size_t 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;
+        }
+}
+/* -->8-- */
+
+static int
+getword(FILE *fp, char *buf, size_t size, int first(int), int rest(int))
+{
+        size_t i = 0;
+        int    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;
+}
+
+static int
+first(int c)
+{
+        return isalpha(c);
+}
+
+static int
+rest(int c)
+{
+        return isalpha(c) || c == '_';
+}
+
+static 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) ) {
+                T *p = hash_lookup(ht, word, 0, 1);
+                if ( p )
+                        ++(*p);
+        }
+
+        hash_delete(ht, "new_item");
+
+        hash_apply(ht, print, stdout);
+
+        hash_free(ht);
+}