Updated libcache

3 files changed, 185 insertions, 93 deletions

diff --git a/src/lib/third_party/include/libcache.h b/src/lib/third_party/include/libcache.h
index f959b3a9c..1f240854f 100644
--- a/src/lib/third_party/include/libcache.h
+++ b/src/lib/third_party/include/libcache.h
@@ -1,65 +1,45 @@
-#ifndef __LIBCACHE_H__
-#define __LIBCACHE_H__
-
-#include <stdint.h>
-
-
-/* Codes representing the result of some functions */
-typedef enum {
-  CACHE_NO_ERROR = 0,
-  CACHE_CONTAINS_FALSE = 0,
-  CACHE_CONTAINS_TRUE,
-  CACHE_INVALID_INPUT,
-  CACHE_REMOVE_NOT_FOUND,
-  CACHE_MALLOC_ERROR
-} cache_result;
-
-/* CACHE_T */
-typedef struct cache_t cache_t;
+/**
+ * @file libcache.h
+ * @author William Guglielmo <william@deselmo.com>
+ * @brief File containing header of cache_t type.
+ *
+ */
 
-/* CACHE_ENTRY */
-typedef struct cache_entry cache_entry;
 
-/* CACHE_ENTRY_MAP */
-typedef struct cache_entry_map cache_entry_map;
+#ifndef __DESELMO_LIBCACHE_H__
+#define __DESELMO_LIBCACHE_H__
 
+#include <stdint.h>
 
-/* STRUCT CACHE_T */
-struct cache_t {
-  uint32_t size;
-  uint32_t max_size;
-  cache_entry *head;
-  cache_entry *tail;
-  cache_entry_map **map;
-};
+/**
+ * @brief Codes representing the result of some functions
+ *
+ */
+typedef enum cache_result {
+  CACHE_NO_ERROR = 0,         /**< Returned by a function if no error occurs. */
+  CACHE_CONTAINS_FALSE = 0,   /**< Returned by function cache_contains if item is not present. */
+  CACHE_CONTAINS_TRUE,        /**< Returned by function cache_contains if item is present. */
+  CACHE_INVALID_INPUT,        /**< Returned by a function if it is called with invalid input parameters. */
+  CACHE_REMOVE_NOT_FOUND,     /**< Returned by function cache_remove if item is not present. */
+  CACHE_MALLOC_ERROR          /**< Returned by a function if a malloc fail. */
+} cache_result;
 
-/* STRUCT CACHE_ENTRY */
-struct cache_entry_map {
-  cache_entry *entry;
-  cache_entry_map *next;
-};
 
-/* STRUCT CACHE_ENTRY_MAP */
-struct cache_entry {
-  void *item;
-  uint32_t item_size;
-  cache_entry *prev;
-  cache_entry *next;
-};
+typedef struct cache_t *cache_t;
 
 
 /**
- * Returns a new cache_t
+ * @brief Returns a new cache_t
  * 
  * @par    cache_max_size  = max number of item that the new cache_t can contain
  * @return a new cache_t, or NULL if an error occurred
  *
  */
-cache_t *cache_new(uint32_t cache_max_size);
+cache_t cache_new(uint32_t cache_max_size);
 
 
 /**
- * Add an item in the specified cache_t
+ * @brief Add an item in the specified cache_t
  * 
  * @par    cache      = the cache_t
  * @par    item       = pointer to the item to add
@@ -67,11 +47,11 @@ cache_t *cache_new(uint32_t cache_max_size);
  * @return a code representing the result of the function
  *
  */
-cache_result cache_add(cache_t *cache, void *item, uint32_t item_size);
+cache_result cache_add(cache_t cache, void *item, uint32_t item_size);
 
 
 /**
- * Check if an item is in the specified cache_t
+ * @brief Check if an item is in the specified cache_t
  * 
  * @par    cache      = the cache_t
  * @par    item       = pointer to the item to check
@@ -79,11 +59,11 @@ cache_result cache_add(cache_t *cache, void *item, uint32_t item_size);
  * @return a code representing the result of the function
  *
  */
-cache_result cache_contains(cache_t *cache, void *item, uint32_t item_size);
+cache_result cache_contains(cache_t cache, void *item, uint32_t item_size);
 
 
 /**
- * Remove an item in the specified cache_t
+ * @brief Remove an item in the specified cache_t
  * 
  * @par    cache      = the cache_t
  * @par    item       = pointer to the item to remove
@@ -91,15 +71,15 @@ cache_result cache_contains(cache_t *cache, void *item, uint32_t item_size);
  * @return a code representing the result of the function
  *
  */
-cache_result cache_remove(cache_t *cache, void *item, uint32_t item_size);
+cache_result cache_remove(cache_t cache, void *item, uint32_t item_size);
 
 /**
- * Free the specified cache_t
+ * @brief Free the specified cache_t
  * 
  * @par alist  = the cache
  *
  */
-void cache_free(cache_t *cache);
+void cache_free(cache_t cache);
 
 
 #endif
diff --git a/src/lib/third_party/src/libcache.c b/src/lib/third_party/src/libcache.c
index dc4bf9460..d5545beae 100644
--- a/src/lib/third_party/src/libcache.c
+++ b/src/lib/third_party/src/libcache.c
@@ -1,3 +1,11 @@
+/**
+ * @file libcache.c
+ * @author William Guglielmo
+ * @brief File containing implementation of cache_t type.
+ *
+ */
+
+
 #include <stdio.h>
 #include <stdlib.h>
 #include <stdint.h>
@@ -7,6 +15,7 @@
 
 
 // https://en.wikipedia.org/wiki/Jenkins_hash_function
+#define HASH_FUNCTION jenkins_one_at_a_time_hash
 uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
   size_t i = 0;
   uint32_t hash = 0;
@@ -21,19 +30,62 @@ uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
   return hash;
 }
 
-cache_entry_map *cache_entry_map_new() {
-  return (cache_entry_map *) calloc(sizeof(cache_entry_map), 1);
+
+typedef struct cache_entry *cache_entry;
+
+typedef struct cache_entry_map *cache_entry_map;
+
+struct cache_t {
+  uint32_t size;
+  uint32_t max_size;
+  cache_entry head;
+  cache_entry tail;
+  cache_entry_map *map;
+};
+
+struct cache_entry_map {
+  cache_entry entry;
+  cache_entry_map next;
+};
+
+struct cache_entry {
+  void *item;
+  uint32_t item_size;
+  cache_entry prev;
+  cache_entry next;
+};
+
+
+void cache_touch_entry(cache_t cache, cache_entry entry) {
+  if(entry->prev) {
+    if(entry->next) {
+      entry->prev->next = entry->next;
+      entry->next->prev = entry->prev;
+    } else {
+      entry->prev->next = NULL;
+      cache->tail = entry->prev;
+    }
+    entry->prev = NULL;
+    entry->next = cache->head;
+    cache->head->prev = entry;
+    cache->head = entry;
+  }
+}
+
+
+cache_entry cache_entry_new() {
+  return (cache_entry) calloc(sizeof(struct cache_entry), 1);
 }
-cache_entry *cache_entry_new() {
-  return (cache_entry *) calloc(sizeof(cache_entry), 1);
+cache_entry_map cache_entry_map_new() {
+  return (cache_entry_map) calloc(sizeof(struct cache_entry_map), 1);
 }
 
-cache_t *cache_new(uint32_t cache_max_size) {
+cache_t cache_new(uint32_t cache_max_size) {
   if(!cache_max_size) {
     return NULL;
   }
 
-  cache_t *cache = (cache_t *) calloc(sizeof(cache_t), 1);
+  cache_t cache = (cache_t) calloc(sizeof(struct cache_t), 1);
   if(!cache) {
     return NULL;
   }
@@ -41,7 +93,7 @@ cache_t *cache_new(uint32_t cache_max_size) {
   cache->size = 0;
   cache->max_size = cache_max_size;
 
-  cache->map = (cache_entry_map **) calloc(sizeof(cache_entry_map *), cache->max_size);
+  cache->map = (cache_entry_map *) calloc(sizeof(cache_entry_map ), cache->max_size);
 
   if(!cache->map) {
     free(cache);
@@ -51,15 +103,15 @@ cache_t *cache_new(uint32_t cache_max_size) {
   return cache;
 }
 
-cache_result cache_add(cache_t *cache, void *item, uint32_t item_size) {
+cache_result cache_add(cache_t cache, void *item, uint32_t item_size) {
   if(!cache || !item || !item_size) {
     return CACHE_INVALID_INPUT;
   }
 
-  uint32_t hash = jenkins_one_at_a_time_hash(item, item_size) % cache->max_size;
+  uint32_t hash = HASH_FUNCTION(item, item_size) % cache->max_size;
 
   if((cache->map)[hash]) {
-    cache_entry_map *hash_entry_map = cache->map[hash];
+    cache_entry_map hash_entry_map = cache->map[hash];
     while(hash_entry_map) {
       if(item_size == hash_entry_map->entry->item_size &&
           !memcmp(hash_entry_map->entry->item, item, item_size)) {
@@ -70,32 +122,19 @@ cache_result cache_add(cache_t *cache, void *item, uint32_t item_size) {
     }
 
     if(hash_entry_map) {
-      cache_entry *entry = hash_entry_map->entry;
-      if(entry->prev) {
-        if(entry->next) {
-          entry->prev->next = entry->next;
-          entry->next->prev = entry->prev;
-        } else {
-          entry->prev->next = NULL;
-          cache->tail = entry->prev;
-        }
-        entry->prev = NULL;
-        entry->next = cache->head;
-        cache->head->prev = entry;
-        cache->head = entry;
-      }
+      cache_touch_entry(cache, hash_entry_map->entry);
 
       return CACHE_NO_ERROR;
     }
   }
 
   
-  cache_entry *entry = cache_entry_new();
+  cache_entry entry = cache_entry_new();
   if(!entry) {
     return CACHE_MALLOC_ERROR;
   }
 
-  cache_entry_map *map_entry = cache_entry_map_new();
+  cache_entry_map map_entry = cache_entry_map_new();
   if(!map_entry) {
     free(entry);
     return CACHE_MALLOC_ERROR;
@@ -121,12 +160,12 @@ cache_result cache_add(cache_t *cache, void *item, uint32_t item_size) {
       cache->tail = entry;
     }
   } else {
-    cache_entry *tail = cache->tail;
+    cache_entry tail = cache->tail;
 
-    uint32_t hash = jenkins_one_at_a_time_hash(tail->item, tail->item_size) % cache->max_size;
+    uint32_t hash = HASH_FUNCTION(tail->item, tail->item_size) % cache->max_size;
     if(cache->map[hash]) {
-      cache_entry_map *hash_entry_map_prev = NULL;
-      cache_entry_map *hash_entry_map = cache->map[hash];
+      cache_entry_map hash_entry_map_prev = NULL;
+      cache_entry_map hash_entry_map = cache->map[hash];
       while(hash_entry_map) {
         if(tail->item_size == hash_entry_map->entry->item_size &&
             !memcmp(tail->item, hash_entry_map->entry->item, item_size)) {
@@ -155,18 +194,20 @@ cache_result cache_add(cache_t *cache, void *item, uint32_t item_size) {
   return CACHE_NO_ERROR;
 }
 
-cache_result cache_contains(cache_t *cache, void *item, uint32_t item_size) {
+cache_result cache_contains(cache_t cache, void *item, uint32_t item_size) {
   if(!cache || !item || !item_size) {
     return CACHE_INVALID_INPUT;
   }
 
-  uint32_t hash = jenkins_one_at_a_time_hash(item, item_size) % cache->max_size;
+  uint32_t hash = HASH_FUNCTION(item, item_size) % cache->max_size;
 
   if(cache->map[hash]) {
-    cache_entry_map *hash_entry_map = cache->map[hash];
+    cache_entry_map hash_entry_map = cache->map[hash];
     while(hash_entry_map) {
       if(item_size == hash_entry_map->entry->item_size &&
           !memcmp(hash_entry_map->entry->item, item, item_size)) {
+        cache_touch_entry(cache, hash_entry_map->entry);
+
         return CACHE_CONTAINS_TRUE;
       }
       
@@ -177,16 +218,16 @@ cache_result cache_contains(cache_t *cache, void *item, uint32_t item_size) {
   return CACHE_CONTAINS_FALSE;
 }
 
-cache_result cache_remove(cache_t *cache, void *item, uint32_t item_size) {
+cache_result cache_remove(cache_t cache, void *item, uint32_t item_size) {
   if(!cache || !item || !item_size) {
     return CACHE_INVALID_INPUT;
   }
 
-  uint32_t hash = jenkins_one_at_a_time_hash(item, item_size) % cache->max_size;
+  uint32_t hash = HASH_FUNCTION(item, item_size) % cache->max_size;
 
   if(cache->map[hash]) {
-    cache_entry_map *hash_entry_map_prev = NULL;
-    cache_entry_map *hash_entry_map = cache->map[hash];
+    cache_entry_map hash_entry_map_prev = NULL;
+    cache_entry_map hash_entry_map = cache->map[hash];
     while(hash_entry_map) {
       if(item_size == hash_entry_map->entry->item_size &&
           !memcmp(hash_entry_map->entry->item, item, item_size)) {
@@ -205,7 +246,7 @@ cache_result cache_remove(cache_t *cache, void *item, uint32_t item_size) {
         cache->map[hash] = hash_entry_map->next;
       }
 
-      cache_entry *entry = hash_entry_map->entry;
+      cache_entry entry = hash_entry_map->entry;
 
       if(entry->prev) {
         entry->prev->next = entry->next;
@@ -230,15 +271,15 @@ cache_result cache_remove(cache_t *cache, void *item, uint32_t item_size) {
   return CACHE_REMOVE_NOT_FOUND;
 }
 
-void cache_free(cache_t *cache) {
+void cache_free(cache_t cache) {
   if(!cache) {
     return;
   }
 
   int i;
   for(i = 0; i < cache->max_size; i++) {
-    cache_entry_map *prev = NULL;
-    cache_entry_map *curr = cache->map[i];
+    cache_entry_map prev = NULL;
+    cache_entry_map curr = cache->map[i];
     while(curr) {
       prev = curr;
       curr = curr->next;
diff --git a/src/lib/third_party/src/test.c b/src/lib/third_party/src/test.c
new file mode 100644
index 000000000..63097fcc3
--- /dev/null
+++ b/src/lib/third_party/src/test.c
@@ -0,0 +1,71 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include "libcache.h"
+
+
+int main() {
+  cache_t cache = cache_new(3);
+  long e;
+
+  e = 0;
+  assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  assert(cache_remove(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  assert(cache_remove(cache, &e, sizeof(e)) == CACHE_REMOVE_NOT_FOUND);
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_FALSE);
+  assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 1;
+  assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 2;
+  assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 3;
+  assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 0;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_FALSE);
+  e = 1;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 2;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 3;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 1;
+  assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  e = 4;
+  assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  e = 0;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_FALSE);
+  e = 1;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 2;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_FALSE);
+  e = 3;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  e = 4;
+  assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  // e = 5;
+  // assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+  // e = 1;
+  // assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_FALSE);
+
+  for(e = 0; e < 1000; e++) {
+    assert(cache_add(cache, &e, sizeof(e)) == CACHE_NO_ERROR);
+    assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  }
+  for(e = 0; e < 997; e++) {
+    assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_FALSE);
+  }  
+  for(e = 997; e < 1000; e++) {
+    assert(cache_contains(cache, &e, sizeof(e)) == CACHE_CONTAINS_TRUE);
+  }
+
+  cache_free(cache);
+
+  puts("OK");
+  return 0;
+}