Commits

Daniel LaMotte committed 73a337e

initial

Comments (0)

Files changed (7)

+syntax: glob
+
+*.o
+
+syntax: re
+
+^main$
+CFLAGS = -Wall -g
+CC = gcc
+LD = ld
+
+all: main
+
+clean:
+	rm -f *.o main
+
+main: main.o list.o list.h hash.c hash.h
+	$(CC) $(filter-out %.h,$^) -o main
+
+%.o: %.c
+	$(CC) $(CFLAGS) -c $<
+
+.PHONY: all clean
+#include <stdlib.h>
+#include <string.h>
+
+#include "hash.h"
+
+struct hash* hash_init() {
+    struct hash *h;
+    int i;
+
+    h = malloc(sizeof(struct hash));
+    if (h == NULL)
+        return NULL;
+
+    h->size = 5;
+    h->table = malloc(sizeof(struct hash*) * h->size);
+    if (h->table == NULL) {
+        free(h);
+        return NULL;
+    }
+
+    for (i = 0; i < h->size; i += 1) {
+        h->table[i] = NULL;
+    }
+
+    return h;
+}
+
+unsigned int hash(struct hash *h, const char *str) {
+    unsigned int val = 0;
+
+    for (; *str != '\0'; str += 1) {
+        val = *str + (val << 5) - val;
+    }
+
+    return val % h->size;
+}
+
+static struct hash_list* _hash_find(struct hash *h, const char *key) {
+    unsigned int val = hash(h, key);
+    struct hash_list *l;
+
+    for (l = h->table[val]; l != NULL; l = l->next) {
+        if (strcmp(key, l->key) == 0) {
+            return l;
+        }
+    }
+
+    return NULL;
+}
+
+void* hash_get(struct hash *h, const char *key, void *default_) {
+    struct hash_list *l;
+
+    l = _hash_find(h, key);
+    if (l == NULL) {
+        return default_;
+    }
+    else {
+        return l->value;
+    }
+}
+
+int hash_set(struct hash *h, const char *key, void *value) {
+    unsigned int val;
+    struct hash_list *l, *next;
+
+    l = _hash_find(h, key);
+    if (l == NULL) {
+        next = malloc(sizeof(struct hash_list));
+        if (next == NULL)
+            return 1;
+
+        next->key = strdup(key);
+        next->value = value;
+
+        val = hash(h, key);
+        next->next = h->table[val];
+        h->table[val] = next;
+    }
+    else {
+        l->value = value;
+    }
+
+    return 0;
+}
+
+void hash_free(struct hash *h) {
+    struct hash_list *l, *next;
+    size_t i;
+
+    for (i = 0; i < h->size; i += 1) {
+        next = h->table[i];
+
+        while (next != NULL) {
+            l = next;
+            next = next->next;
+            free(l->key);
+            free(l);
+        }
+    }
+
+    free(h->table);
+    free(h);
+}
+#ifndef SOMEC_HASH_H
+#define SOMEC_HASH_H
+
+struct hash;
+struct hash_list;
+
+struct hash_list {
+    char *key;
+    void *value;
+    struct hash_list *next;
+};
+
+struct hash {
+    size_t size;
+    struct hash_list **table;
+};
+
+unsigned int hash(struct hash *h, const char *str);
+struct hash* hash_init();
+void* hash_get(struct hash *h, const char *key, void *default_);
+int hash_set(struct hash *h, const char *key, void *value);
+void hash_free(struct hash *h);
+
+#endif /* SOMEC_HASH_H */
+#include <stdlib.h>
+
+#include "list.h"
+
+struct list* list_init(void *data) {
+    struct list *l = NULL;
+
+    l = malloc(sizeof(struct list));
+    if (l == NULL)
+        return NULL;
+
+    l->prev = l->next = NULL;
+    l->data = data;
+
+    return l;
+}
+
+struct list* list_append(struct list *l, void *data) {
+    struct list *next = NULL, *last = NULL;
+
+    if (l == NULL)
+        return NULL;
+
+    next = list_init(data);
+    if (next == NULL)
+        return NULL;
+
+    last = list_tail(l);
+    last->next = next;
+    next->prev = last;
+
+    return next;
+}
+
+struct list* list_head(struct list *l) {
+    if (l == NULL)
+        return NULL;
+
+    while (l->prev != NULL) {
+        l = l->prev;
+    }
+
+    return l;
+}
+
+struct list* list_tail(struct list *l) {
+    if (l == NULL)
+        return NULL;
+
+    while (l->next != NULL) {
+        l = l->next;
+    }
+
+    return l;
+}
+
+size_t list_len(struct list *l) {
+    size_t len = 0;
+    for (; l != NULL; l = l->next) {
+        len += 1;
+    }
+    return len;
+}
+
+void list_free(struct list *l) {
+    struct list *next = l;
+
+    while (next != NULL) {
+        l = next;
+        next = next->next;
+        free(l);
+    }
+}
+#ifndef SOMEC_LIST_H
+#define SOMEC_LIST_H
+
+struct list;
+
+struct list {
+    void *data;
+    struct list *next;
+    struct list *prev;
+};
+
+struct list* list_init(void *data);
+struct list* list_append(struct list *l, void *data);
+struct list* list_head(struct list *l);
+struct list* list_tail(struct list *l);
+size_t list_len(struct list *l);
+void list_free(struct list *l);
+
+#endif /* SOMEC_LIST_H */
+#include <stdio.h>
+
+#include "list.h"
+#include "hash.h"
+
+int main(void) {
+    struct list *l = NULL, *iter = NULL;
+    struct hash *h = NULL;
+
+    l = list_init("one");
+    if (l == NULL) {
+        perror("failed to init list");
+        return 1;
+    }
+
+    if (list_append(l, "two") == NULL) {
+        perror("failed to append to list");
+        return 2;
+    }
+
+    list_append(l, "three");
+    list_append(l, "four");
+    list_append(l, "five");
+    list_append(l, "six");
+    list_append(l, "seven");
+    list_append(l, "eight");
+    list_append(l, "nine");
+    list_append(l, "ten");
+    list_append(l, "11");
+    list_append(l, "12");
+    list_append(l, "13");
+    list_append(l, "14");
+    list_append(l, "15");
+    list_append(l, "16");
+    list_append(l, "17");
+    list_append(l, "18");
+    list_append(l, "19");
+    list_append(l, "20");
+    list_append(l, "21");
+    list_append(l, "22");
+    list_append(l, "23");
+    list_append(l, "24");
+    list_append(l, "25");
+
+    for (iter = list_head(l); iter != NULL; iter = iter->next) {
+        printf("item: %s\n", (char *)iter->data);
+    }
+
+    printf("len: %d\n", (int)list_len(l));
+
+    list_free(list_head(l));
+
+    h = hash_init();
+    if (h == NULL) {
+        perror("failed to init hash");
+        return 3;
+    }
+
+    printf("get key: %s\n", (char*)hash_get(h, "key", "default"));
+    hash_set(h, "key", "value");
+    printf("get key: %s\n", (char*)hash_get(h, "key", "default"));
+    hash_set(h, "key", "value2");
+    printf("get key: %s\n", (char*)hash_get(h, "key", "default"));
+
+    hash_free(h);
+
+    return 0;
+}