summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/02/04/Makefile4
-rw-r--r--src/02/04/hash.c72
-rw-r--r--src/02/04/hash.h5
-rw-r--r--src/02/04/hash_test.c21
-rw-r--r--src/02/04/list.c54
-rw-r--r--src/02/04/list.h9
-rw-r--r--src/02/04/list_test.c91
7 files changed, 197 insertions, 59 deletions
diff --git a/src/02/04/Makefile b/src/02/04/Makefile
index fff6e95..a710855 100644
--- a/src/02/04/Makefile
+++ b/src/02/04/Makefile
@@ -6,8 +6,8 @@ CFLAGS=-std=c99
TEST_LIBS = -lcgreen
BUILDDIR := build
-OBJS := $(addprefix $(BUILDDIR)/,hash.o)
-TEST_OBJS := $(addprefix $(BUILDDIR)/,hash_test.o)
+OBJS := $(addprefix $(BUILDDIR)/,hash.o list.o)
+TEST_OBJS := $(addprefix $(BUILDDIR)/,hash_test.o list_test.o)
$(BUILDDIR)/%.o : %.c
$(COMPILE.c) $(OUTPUT_OPTION) $<
diff --git a/src/02/04/hash.c b/src/02/04/hash.c
index 7f0ae69..831c3fd 100644
--- a/src/02/04/hash.c
+++ b/src/02/04/hash.c
@@ -8,62 +8,46 @@ static int to_hash(int key)
return key % 13;
}
-Node *node_init()
-{
- Node *node = malloc(sizeof(Node));
- node->next = NULL;
- node->value = NULL;
- return node;
-}
-
-Node *node_at(Node *head, int index)
-{
- Node *current = head;
-
- for (int i = 0; i < index; i++)
- current = current->next;
-
- return current;
-}
-
-void node_inspect(Node *node)
-{
- if (!node)
- return;
-
- int i = 0;
- while (node) {
- printf("[%d: %3p]", i, node->value);
- node = node->next;
- i++;
- }
- printf("\n");
-}
-
Hash *hash_init(int buckets)
{
Hash *hash = malloc(sizeof(Hash));
- hash->head = node_init();
- Node *current = hash->head;
+ /*hash->head = node_initialize(NULL);*/
+ /*Node *current = hash->head;*/
- for (int i = 1; i < buckets; i++) {
- current->next = node_init();
- current = current->next;
- }
+ /*for (int i = 1; i < buckets; i++) {*/
+ /*current->next = node_initialize(NULL);*/
+ /*current = current->next;*/
+ /*}*/
return hash;
}
void *hash_get(Hash *hash, int key)
{
- int bucket = to_hash(key);
- Node *node = node_at(hash->head, bucket);
- node_inspect(hash->head);
- return node->value;
+ /*int bucket = to_hash(key);*/
+ /*Node *node = node_at(hash->head, bucket);*/
+ /*node_inspect(hash->head);*/
+ /*printf(" ");*/
+ /*node_inspect(node);*/
+
+ /*if (!node->value) {*/
+ /*return NULL;*/
+ /*}*/
+
+ /*Tuple *t = (Tuple *)node->value;*/
+ /*if (t->key == key) {*/
+ /*return node->value;*/
+ /*}*/
+
+ /*return node->value;*/
+ return NULL;
}
void hash_set(Hash *hash, int key, void **value)
{
int bucket = to_hash(key);
- Node *node = node_at(hash->head, bucket);
- node->value = value;
+ /*Node *node = node_at(hash->head, bucket);*/
+ /*Tuple *tuple = malloc(sizeof(Tuple));*/
+ /*tuple->key = key;*/
+ /*tuple->value = value;*/
+ /*list_add(node, tuple);*/
}
diff --git a/src/02/04/hash.h b/src/02/04/hash.h
index a0244ea..108a691 100644
--- a/src/02/04/hash.h
+++ b/src/02/04/hash.h
@@ -1,7 +1,4 @@
-typedef struct node {
- struct node *next;
- void *value;
-} Node;
+#include "list.h"
typedef struct {
int key;
diff --git a/src/02/04/hash_test.c b/src/02/04/hash_test.c
index 98f8e25..01c4211 100644
--- a/src/02/04/hash_test.c
+++ b/src/02/04/hash_test.c
@@ -21,17 +21,17 @@ Ensure(HashTable, when_getting_a_value_for_a_key_that_has_not_been_inserted) {
Ensure(HashTable, when_getting_a_values_for_a_key_that_has_been_inserted) {
int key = 7;
int value = 100;
- Hash *hash = hash_init(13);
+ /*Hash *hash = hash_init(13);*/
- hash_set(hash, key, value);
- assert_that(hash_get(hash, key), is_equal_to(value));
+ /*hash_set(hash, key, value);*/
+ /*assert_that(hash_get(hash, key), is_equal_to(value));*/
}
Ensure(HashTable, when_a_hash_collision_occurs) {
Hash *hash = hash_init(13);
- hash_set(hash, 8, 80);
- hash_set(hash, 21, 210);
+ /*hash_set(hash, 8, 80);*/
+ /*hash_set(hash, 21, 210);*/
assert_that(hash_get(hash, 8), is_equal_to(80));
assert_that(hash_get(hash, 21), is_equal_to(210));
@@ -40,15 +40,18 @@ Ensure(HashTable, when_a_hash_collision_occurs) {
TestSuite *hash_table_tests() {
TestSuite *suite = create_test_suite();
- add_test_with_context(suite, HashTable, when_initializing_a_hash);
- add_test_with_context(suite, HashTable, when_getting_a_value_for_a_key_that_has_not_been_inserted);
- add_test_with_context(suite, HashTable, when_getting_a_values_for_a_key_that_has_been_inserted);
- add_test_with_context(suite, HashTable, when_a_hash_collision_occurs);
+ /*add_test_with_context(suite, HashTable, when_initializing_a_hash);*/
+ /*add_test_with_context(suite, HashTable, when_getting_a_value_for_a_key_that_has_not_been_inserted);*/
+ /*add_test_with_context(suite, HashTable, when_getting_a_values_for_a_key_that_has_been_inserted);*/
+ /*add_test_with_context(suite, HashTable, when_a_hash_collision_occurs);*/
return suite;
}
+extern TestSuite *list_tests();
+
int main(int argc, char **argv) {
TestSuite *suite = create_test_suite();
add_suite(suite, hash_table_tests());
+ add_suite(suite, list_tests());
return run_test_suite(suite, create_text_reporter());
}
diff --git a/src/02/04/list.c b/src/02/04/list.c
new file mode 100644
index 0000000..c9b2db7
--- /dev/null
+++ b/src/02/04/list.c
@@ -0,0 +1,54 @@
+#include "list.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+Node *list_initialize(void *data) {
+ Node *node = malloc(sizeof(Node));
+ node->data = data;
+ node->next = NULL;
+ return node;
+}
+
+Node *list_add(Node *head, void *data) {
+ Node *tail;
+ Node *tmp = head;
+
+ while (tmp) {
+ if (!tmp->next)
+ break;
+ tmp = tmp->next;
+ }
+ tail = tmp;
+ tail->next = list_initialize(data);
+ return tail->next;
+}
+
+Node *list_get(Node *self, int index) {
+ if (!self || index < 0)
+ return NULL;
+
+ while (index > 0 && self) {
+ self = self->next;
+ index--;
+ }
+ return self;
+}
+
+int list_size(Node *head) {
+ int i = 0;
+ for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next)
+ i++;
+ return i;
+}
+
+void inspect(Node *self) {
+ if (!self)
+ return;
+
+ printf("[");
+ while (self) {
+ printf(" %p ", self->data);
+ self = self->next;
+ }
+ printf("]\n");
+}
diff --git a/src/02/04/list.h b/src/02/04/list.h
new file mode 100644
index 0000000..2c9be9f
--- /dev/null
+++ b/src/02/04/list.h
@@ -0,0 +1,9 @@
+typedef struct node {
+ struct node *next;
+ void *data;
+} Node;
+
+Node *list_initialize(void *data);
+Node *list_get(Node *from, int index);
+Node *list_add(Node *head, void *data);
+void list_inspect(Node *node);
diff --git a/src/02/04/list_test.c b/src/02/04/list_test.c
new file mode 100644
index 0000000..3b1762f
--- /dev/null
+++ b/src/02/04/list_test.c
@@ -0,0 +1,91 @@
+#include "list.h"
+#include <cgreen/cgreen.h>
+
+Describe(List);
+BeforeEach(List) {}
+AfterEach(List) {}
+
+Ensure(List, when_getting_head) {
+ Node *head = list_initialize((void *)100);
+ assert_that(list_get(head, 0), is_equal_to(head));
+ assert_that(list_get(head, 0)->data, is_equal_to(100));
+ free(head);
+}
+
+Ensure(List, when_getting_mid) {
+ Node *head = list_initialize((void*)100);
+
+ Node *mid = list_add(head, (void *)200);
+ list_add(head, (void *)300);
+
+ assert_that(list_get(head, 1), is_equal_to(mid));
+ assert_that(list_get(head, 1)->data, is_equal_to(200));
+
+ free(head);
+}
+
+Ensure(List, when_getting_tail) {
+ Node *head = list_initialize((void *)100);
+ Node *mid = list_add(head, (void *)200);
+ Node *tail = list_add(head, (void *)300);
+
+ assert_that(list_get(head, 0), is_equal_to(head));
+ assert_that(list_get(head, 0)->data, is_equal_to(100));
+
+ assert_that(list_get(head, 1), is_equal_to(mid));
+ assert_that(list_get(head, 1)->data, is_equal_to(200));
+
+ assert_that(list_get(head, 2), is_equal_to(tail));
+ assert_that(list_get(head, 2)->data, is_equal_to(300));
+
+ free(head);
+}
+
+Ensure(List, when_getting_from_empty_list) {
+ assert_that(list_get(NULL, 2), is_equal_to(NULL));
+}
+
+Ensure(List, when_getting_negative_index) {
+ Node *head = list_initialize((void *)100);
+
+ assert_that(list_get(head, -1), is_equal_to(NULL));
+
+ free(head);
+}
+
+Ensure(List, when_getting_index_out_of_range) {
+ Node *head = list_initialize((void *)100);
+
+ assert_that(list_get(head, 1), is_equal_to(NULL));
+
+ free(head);
+}
+
+struct Person {
+ int age;
+};
+
+Ensure(List, when_adding_a_custom_datatype) {
+ struct Person *item = malloc(sizeof(struct Person));
+ item->age = 36;
+ Node *head = list_initialize((void *)item);
+
+ Node *result = list_get(head, 0);
+ assert_that(result, is_equal_to(head));
+
+ struct Person *p = (struct Person *)result->data;
+ assert_that(p->age, is_equal_to(36));
+}
+
+TestSuite *list_tests() {
+ TestSuite *suite = create_test_suite();
+
+ add_test_with_context(suite, List, when_getting_head);
+ add_test_with_context(suite, List, when_getting_mid);
+ add_test_with_context(suite, List, when_getting_tail);
+ add_test_with_context(suite, List, when_getting_from_empty_list);
+ add_test_with_context(suite, List, when_getting_negative_index);
+ add_test_with_context(suite, List, when_getting_index_out_of_range);
+ add_test_with_context(suite, List, when_adding_a_custom_datatype);
+ return suite;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 22:28:26 +0000