From 9675cf654d86464344e56705db7a71ea17f76c6f Mon Sep 17 00:00:00 2001
From: Daniel Lange <DLange@git.local>
Date: Mon, 11 Apr 2016 13:00:21 +0200
Subject: Imported Upstream version 0.6.6+svn20070915

---
 Hashtable.c | 91 ++++++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 66 insertions(+), 25 deletions(-)

(limited to 'Hashtable.c')

diff --git a/Hashtable.c b/Hashtable.c
index 30218a5..cfd1470 100644
--- a/Hashtable.c
+++ b/Hashtable.c
@@ -9,6 +9,7 @@ in the source distribution for its full text.
 
 #include <stdlib.h>
 #include <stdbool.h>
+#include <assert.h>
 
 #include "debug.h"
 
@@ -18,7 +19,7 @@ typedef struct Hashtable_ Hashtable;
 typedef void(*Hashtable_PairFunction)(int, void*, void*);
 
 typedef struct HashtableItem {
-   int key;
+   unsigned int key;
    void* value;
    struct HashtableItem* next;
 } HashtableItem;
@@ -31,7 +32,36 @@ struct Hashtable_ {
 };
 }*/
 
-HashtableItem* HashtableItem_new(int key, void* value) {
+#ifdef DEBUG
+
+bool Hashtable_isConsistent(Hashtable* this) {
+   int items = 0;
+   for (int i = 0; i < this->size; i++) {
+      HashtableItem* bucket = this->buckets[i];
+      while (bucket) {
+         items++;
+         bucket = bucket->next;
+      }
+   }
+   return items == this->items;
+}
+
+int Hashtable_count(Hashtable* this) {
+   int items = 0;
+   for (int i = 0; i < this->size; i++) {
+      HashtableItem* bucket = this->buckets[i];
+      while (bucket) {
+         items++;
+         bucket = bucket->next;
+      }
+   }
+   assert(items == this->items);
+   return items;
+}
+
+#endif
+
+HashtableItem* HashtableItem_new(unsigned int key, void* value) {
    HashtableItem* this;
    
    this = (HashtableItem*) malloc(sizeof(HashtableItem));
@@ -45,13 +75,16 @@ Hashtable* Hashtable_new(int size, bool owner) {
    Hashtable* this;
    
    this = (Hashtable*) malloc(sizeof(Hashtable));
+   this->items = 0;
    this->size = size;
    this->buckets = (HashtableItem**) calloc(sizeof(HashtableItem*), size);
    this->owner = owner;
+   assert(Hashtable_isConsistent(this));
    return this;
 }
 
 void Hashtable_delete(Hashtable* this) {
+   assert(Hashtable_isConsistent(this));
    for (int i = 0; i < this->size; i++) {
       HashtableItem* walk = this->buckets[i];
       while (walk != NULL) {
@@ -67,11 +100,12 @@ void Hashtable_delete(Hashtable* this) {
 }
 
 inline int Hashtable_size(Hashtable* this) {
+   assert(Hashtable_isConsistent(this));
    return this->items;
 }
 
-void Hashtable_put(Hashtable* this, int key, void* value) {
-   int index = key % this->size;
+void Hashtable_put(Hashtable* this, unsigned int key, void* value) {
+   unsigned int index = key % this->size;
    HashtableItem** bucketPtr = &(this->buckets[index]);
    while (true)
       if (*bucketPtr == NULL) {
@@ -85,47 +119,53 @@ void Hashtable_put(Hashtable* this, int key, void* value) {
          break;
       } else
          bucketPtr = &((*bucketPtr)->next);
+   assert(Hashtable_isConsistent(this));
 }
 
-void* Hashtable_remove(Hashtable* this, int key) {
-   int index = key % this->size;
-   HashtableItem** bucketPtr = &(this->buckets[index]);
-   while (true)
-      if (*bucketPtr == NULL) {
-         return NULL;
-         break;
-      } else if ((*bucketPtr)->key == key) {
-         void* savedValue = (*bucketPtr)->value;
-         HashtableItem* savedNext = (*bucketPtr)->next;
-         free(*bucketPtr);
-         (*bucketPtr) = savedNext;
+void* Hashtable_remove(Hashtable* this, unsigned int key) {
+   unsigned int index = key % this->size;
+   
+   assert(Hashtable_isConsistent(this));
+
+   HashtableItem** bucket; 
+   for (bucket = &(this->buckets[index]); *bucket; bucket = &((*bucket)->next) ) {
+      if ((*bucket)->key == key) {
+         void* value = (*bucket)->value;
+         HashtableItem* next = (*bucket)->next;
+         free(*bucket);
+         (*bucket) = next;
          this->items--;
          if (this->owner) {
-            free(savedValue);
+            free(value);
+            assert(Hashtable_isConsistent(this));
             return NULL;
          } else {
-            return savedValue;
+            assert(Hashtable_isConsistent(this));
+            return value;
          }
-      } else
-         bucketPtr = &((*bucketPtr)->next);
+      }
+   }
+   assert(Hashtable_isConsistent(this));
+   return NULL;
 }
-//#include <stdio.h>
-inline void* Hashtable_get(Hashtable* this, int key) {
-   int index = key % this->size;
+
+inline void* Hashtable_get(Hashtable* this, unsigned int key) {
+   unsigned int index = key % this->size;
    HashtableItem* bucketPtr = this->buckets[index];
-   // fprintf(stderr, "%d -> %d\n", key, index);
    while (true) {
       if (bucketPtr == NULL) {
+         assert(Hashtable_isConsistent(this));
          return NULL;
       } else if (bucketPtr->key == key) {
+         assert(Hashtable_isConsistent(this));
          return bucketPtr->value;
       } else
          bucketPtr = bucketPtr->next;
-      // fprintf(stderr, "*\n");
    }
 }
 
 void Hashtable_foreach(Hashtable* this, Hashtable_PairFunction f, void* userData) {
+   assert(Hashtable_isConsistent(this));
    for (int i = 0; i < this->size; i++) {
       HashtableItem* walk = this->buckets[i];
       while (walk != NULL) {
@@ -133,4 +173,5 @@ void Hashtable_foreach(Hashtable* this, Hashtable_PairFunction f, void* userData
          walk = walk->next;
       }
    }
+   assert(Hashtable_isConsistent(this));
 }
-- 
cgit v1.2.3