Rewrite LRU cache. Now uses one big hash table and is less buggy.

4 files changed, 147 insertions, 145 deletions

diff --git a/include/urweb/types_cpp.h b/include/urweb/types_cpp.h
index 84423105..4847a3fd 100644
--- a/include/urweb/types_cpp.h
+++ b/include/urweb/types_cpp.h
@@ -123,31 +123,24 @@ typedef struct {
 
 #include "uthash.h"
 
-typedef struct uw_Sqlcache_CacheValue {
+typedef struct uw_Sqlcache_Value {
   char *result;
   char *output;
-} uw_Sqlcache_CacheValue;
+  unsigned long timeValid;
+} uw_Sqlcache_Value;
 
-typedef struct uw_Sqlcache_CacheEntry {
+typedef struct uw_Sqlcache_Entry {
   char *key;
-  void *value;
-  time_t timeValid;
-  struct uw_Sqlcache_CacheEntry *prev;
-  struct uw_Sqlcache_CacheEntry *next;
+  uw_Sqlcache_Value *value;
+  unsigned long timeInvalid;
   UT_hash_handle hh;
-} uw_Sqlcache_CacheEntry;
-
-typedef struct uw_Sqlcache_CacheList {
-  uw_Sqlcache_CacheEntry *first;
-  uw_Sqlcache_CacheEntry *last;
-  int size;
-} uw_Sqlcache_CacheList;
+} uw_Sqlcache_Entry;
 
 typedef struct uw_Sqlcache_Cache {
-  uw_Sqlcache_CacheEntry *table;
-  time_t timeInvalid;
-  uw_Sqlcache_CacheList *lru;
-  int height;
+  struct uw_Sqlcache_Entry *table;
+  unsigned long timeInvalid;
+  unsigned long timeNow;
+  UT_hash_handle hh;
 } uw_Sqlcache_Cache;
 
 #endif
diff --git a/include/urweb/urweb_cpp.h b/include/urweb/urweb_cpp.h
index ab2a91c1..52e54372 100644
--- a/include/urweb/urweb_cpp.h
+++ b/include/urweb/urweb_cpp.h
@@ -405,10 +405,8 @@ void uw_Basis_writec(struct uw_context *, char);
 
 // Sqlcache.
 
-#include "uthash.h"
-
-uw_Sqlcache_CacheValue *uw_Sqlcache_check(uw_Sqlcache_Cache *, char **);
-uw_Sqlcache_CacheValue *uw_Sqlcache_store(uw_Sqlcache_Cache *, char **, uw_Sqlcache_CacheValue *);
-uw_Sqlcache_CacheValue *uw_Sqlcache_flush(uw_Sqlcache_Cache *, char **);
+uw_Sqlcache_Value *uw_Sqlcache_check(uw_Sqlcache_Cache *, char **, int);
+void *uw_Sqlcache_store(uw_Sqlcache_Cache *, char **, int, uw_Sqlcache_Value *);
+void *uw_Sqlcache_flush(uw_Sqlcache_Cache *, char **, int);
 
 #endif
diff --git a/src/c/urweb.c b/src/c/urweb.c
index ef7eb9bb..09d04f1c 100644
--- a/src/c/urweb.c
+++ b/src/c/urweb.c
@@ -4532,144 +4532,154 @@ void uw_set_remoteSock(uw_context ctx, int sock) {
 
 // Sqlcache
 
-void uw_Sqlcache_listDelete(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) {
-  if (list->first == entry) {
-    list->first = entry->next;
-  }
-  if (list->last == entry) {
-    list->last = entry->prev;
-  }
-  if (entry->prev) {
-    entry->prev->next = entry->next;
-  }
-  if (entry->next) {
-    entry->next->prev = entry->prev;
+void uw_Sqlcache_freeValue(uw_Sqlcache_Value *value) {
+  if (value) {
+    free(value->result);
+    free(value->output);
+    free(value);
   }
-  entry->prev = NULL;
-  entry->next = NULL;
-  --(list->size);
 }
 
-void uw_Sqlcache_listAdd(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) {
-  if (list->last) {
-    list->last->next = entry;
-    entry->prev = list->last;
-    list->last = entry;
-  } else {
-    list->first = entry;
-    list->last = entry;
+void uw_Sqlcache_freeEntry(uw_Sqlcache_Entry* entry) {
+  if (entry) {
+    free(entry->key);
+    uw_Sqlcache_freeValue(entry->value);
+    free(entry);
   }
-  ++(list->size);
-}
-
-void uw_Sqlcache_listBump(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) {
-  uw_Sqlcache_listDelete(list, entry);
-  uw_Sqlcache_listAdd(list, entry);
 }
 
-// TODO: deal with time properly.
+// TODO: pick a number.
+unsigned int uw_Sqlcache_maxSize = 1234567890;
 
-time_t uw_Sqlcache_getTimeNow() {
-  return time(NULL);
+void uw_Sqlcache_delete(uw_Sqlcache_Cache *cache, uw_Sqlcache_Entry *entry) {
+  HASH_DEL(cache->table, entry);
+  uw_Sqlcache_freeEntry(entry);
 }
 
-time_t uw_Sqlcache_timeMax(time_t x, time_t y) {
-  return difftime(x, y) > 0 ? x : y;
+uw_Sqlcache_Entry *uw_Sqlcache_find(uw_Sqlcache_Cache *cache, char *key, size_t len, int bump) {
+  uw_Sqlcache_Entry *entry = NULL;
+  HASH_FIND(hh, cache->table, key, len, entry);
+  if (entry && bump) {
+    // Bump for LRU purposes.
+    HASH_DEL(cache->table, entry);
+    // Important that we use [entry->key], because [key] might be ephemeral.
+    HASH_ADD_KEYPTR(hh, cache->table, entry->key, len, entry);
+  }
+  return entry;
 }
 
-void uw_Sqlcache_free(uw_Sqlcache_CacheValue *value) {
-  if (value) {
-    free(value->result);
-    free(value->output);
-    free(value);
+void uw_Sqlcache_add(uw_Sqlcache_Cache *cache, uw_Sqlcache_Entry *entry, size_t len) {
+  HASH_ADD_KEYPTR(hh, cache->table, entry->key, len, entry);
+  if (HASH_COUNT(cache->table) > uw_Sqlcache_maxSize) {
+    // Deletes the first element of the cache.
+    uw_Sqlcache_delete(cache, cache->table);
   }
 }
 
-void uw_Sqlcache_delete(uw_Sqlcache_Cache *cache, uw_Sqlcache_CacheEntry* entry) {
-  //uw_Sqlcache_listUw_Sqlcache_Delete(cache->lru, entry);
-  HASH_DELETE(hh, cache->table, entry);
-  uw_Sqlcache_free(entry->value);
-  free(entry->key);
-  free(entry);
-}
-
-uw_Sqlcache_CacheValue *uw_Sqlcache_checkHelper(uw_Sqlcache_Cache *cache, char **keys, int timeInvalid) {
-  char *key = keys[cache->height];
-  uw_Sqlcache_CacheEntry *entry;
-  HASH_FIND(hh, cache->table, key, strlen(key), entry);
-  timeInvalid = uw_Sqlcache_timeMax(timeInvalid, cache->timeInvalid);
-  if (entry && difftime(entry->timeValid, timeInvalid) > 0) {
-    if (cache->height == 0) {
-      // At height 0, entry->value is the desired value.
-      //uw_Sqlcache_listBump(cache->lru, entry);
-      return entry->value;
-    } else {
-      // At height n+1, entry->value is a pointer to a cache at heignt n.
-      return uw_Sqlcache_checkHelper(entry->value, keys, timeInvalid);
-    }
-  } else {
-    return NULL;
-  }
+unsigned long uw_Sqlcache_getTimeNow(uw_Sqlcache_Cache *cache) {
+  return ++cache->timeNow;
 }
 
-uw_Sqlcache_CacheValue *uw_Sqlcache_check(uw_Sqlcache_Cache *cache, char **keys) {
-  return uw_Sqlcache_checkHelper(cache, keys, 0);
+unsigned long uw_Sqlcache_timeMax(unsigned long x, unsigned long y) {
+  return x > y ? x : y;
 }
 
-void uw_Sqlcache_storeHelper(uw_Sqlcache_Cache *cache, char **keys, uw_Sqlcache_CacheValue *value, int timeNow) {
-  uw_Sqlcache_CacheEntry *entry;
-  char *key = keys[cache->height];
-  HASH_FIND(hh, cache->table, key, strlen(key), entry);
-  if (!entry) {
-    entry = malloc(sizeof(uw_Sqlcache_CacheEntry));
-    entry->key = strdup(key);
-    entry->value = NULL;
-    HASH_ADD_KEYPTR(hh, cache->table, entry->key, strlen(entry->key), entry);
+char uw_Sqlcache_keySep = '_';
+
+char *uw_Sqlcache_allocKeyBuffer(char **keys, int numKeys) {
+  size_t len = 0;
+  while (numKeys-- > 0) {
+    char* k = keys[numKeys];
+    if (!k) {
+      // Can only happen when flushihg, in which case we don't need anything past the null key.
+      break;
+    }
+    // Leave room for separator.
+    len += 1 + strlen(k);
   }
-  entry->timeValid = timeNow;
-  if (cache->height == 0) {
-    //uw_Sqlcache_listAdd(cache->lru, entry);
-    uw_Sqlcache_free(entry->value);
-    entry->value = value;
-    //if (cache->lru->size > MAX_SIZE) {
-      //uw_Sqlcache_delete(cache, cache->lru->first);
-      // TODO: return flushed value.
-    //}
-  } else {
-    if (!entry->value) {
-      uw_Sqlcache_Cache *newuw_Sqlcache_Cache = malloc(sizeof(uw_Sqlcache_Cache));
-      newuw_Sqlcache_Cache->table = NULL;
-      newuw_Sqlcache_Cache->timeInvalid = timeNow;
-      newuw_Sqlcache_Cache->lru = cache->lru;
-      newuw_Sqlcache_Cache->height = cache->height - 1;
-      entry->value = newuw_Sqlcache_Cache;
+  char *buf = malloc(len+1);
+  // If nothing is copied into the buffer, it should look like it has length 0.
+  buf[0] = 0;
+  return buf;
+}
+
+char *uw_Sqlcache_keyCopy(char *buf, char *key) {
+  *buf++ = uw_Sqlcache_keySep;
+  return stpcpy(buf, key);
+}
+
+// The NUL-terminated prefix of [key] below always looks something like "_k1_k2_k3..._kn".
+// TODO: strlen(key) = buf - key?
+
+uw_Sqlcache_Value *uw_Sqlcache_check(uw_Sqlcache_Cache *cache, char **keys, int numKeys) {
+  char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys);
+  char *buf = key;
+  time_t timeInvalid = cache->timeInvalid;
+  uw_Sqlcache_Entry *entry;
+  while (numKeys-- > 0) {
+    buf = uw_Sqlcache_keyCopy(buf, keys[numKeys]);
+    size_t len = buf - key;
+    entry = uw_Sqlcache_find(cache, key, len, 1);
+    if (!entry) {
+      free(key);
+      return NULL;
     }
-    uw_Sqlcache_storeHelper(entry->value, keys, value, timeNow);
+    timeInvalid = uw_Sqlcache_timeMax(timeInvalid, entry->timeInvalid);
   }
-}
-
-void uw_Sqlcache_store(uw_Sqlcache_Cache *cache, char **keys, uw_Sqlcache_CacheValue *value) {
-  uw_Sqlcache_storeHelper(cache, keys, value, uw_Sqlcache_getTimeNow());
-}
-
-void uw_Sqlcache_flushHelper(uw_Sqlcache_Cache *cache, char **keys, int timeNow) {
-  uw_Sqlcache_CacheEntry *entry;
-  char *key = keys[cache->height];
-  if (key) {
-    HASH_FIND(hh, cache->table, key, strlen(key), entry);
-    if (entry) {
-      if (cache->height == 0) {
-        uw_Sqlcache_delete(cache, entry);
+  free(key);
+  uw_Sqlcache_Value *value = entry->value;
+  return value && value->timeValid > timeInvalid ? value : NULL;
+}
+
+void uw_Sqlcache_store(uw_Sqlcache_Cache *cache, char **keys, int numKeys, uw_Sqlcache_Value *value) {
+  char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys);
+  char *buf = key;
+  time_t timeNow = uw_Sqlcache_getTimeNow(cache);
+  uw_Sqlcache_Entry *entry;
+  while (numKeys-- > 0) {
+    buf = uw_Sqlcache_keyCopy(buf, keys[numKeys]);
+    size_t len = buf - key;
+    entry = uw_Sqlcache_find(cache, key, len, 1);
+    if (!entry) {
+      entry = malloc(sizeof(uw_Sqlcache_Entry));
+      entry->key = strdup(key);
+      entry->value = NULL;
+      entry->timeInvalid = 0; // ASK: is this okay?
+      uw_Sqlcache_add(cache, entry, len);
+    }
+  }
+  free(key);
+  uw_Sqlcache_freeValue(entry->value);
+  entry->value = value;
+  entry->value->timeValid = timeNow;
+}
+
+void uw_Sqlcache_flush(uw_Sqlcache_Cache *cache, char **keys, int numKeys) {
+  char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys);
+  char *buf = key;
+  time_t timeNow = uw_Sqlcache_getTimeNow(cache);
+  uw_Sqlcache_Entry *entry;
+  while (numKeys-- > 0) {
+    char *k = keys[numKeys];
+    if (!k) {
+      if (entry) {
+        entry->timeInvalid = timeNow;
       } else {
-        uw_Sqlcache_flushHelper(entry->value, keys, timeNow);
+        // Haven't found an entry yet, so the first key was null.
+        cache->timeInvalid = timeNow;
       }
+      free(key);
+      return;
+    }
+    buf = uw_Sqlcache_keyCopy(buf, k);
+    size_t len = buf - key;
+    entry = uw_Sqlcache_find(cache, key, len, 0);
+    if (!entry) {
+      free(key);
+      return;
     }
-  } else {
-    // Null key means invalidate the entire subtree.
-    cache->timeInvalid = timeNow;
   }
-}
-
-void uw_Sqlcache_flush(uw_Sqlcache_Cache *cache, char **keys) {
-  uw_Sqlcache_flushHelper(cache, keys, uw_Sqlcache_getTimeNow());
+  free(key);
+  // All the keys were non-null and the relevant entry is present, so we delete it.
+  uw_Sqlcache_delete(cache, entry);
 }
diff --git a/src/lru_cache.sml b/src/lru_cache.sml
index e69624d8..6fcfdc55 100644
--- a/src/lru_cache.sml
+++ b/src/lru_cache.sml
@@ -62,6 +62,8 @@ fun setupQuery {index, params} =
 
         val revArgs = paramRepeatRev (fn p => "p" ^ p) ", "
 
+        val numArgs = Int.toString params
+
     in
         Print.box
             [string ("static uw_Sqlcache_Cache cacheStruct" ^ i ^ " = {"),
@@ -70,9 +72,7 @@ fun setupQuery {index, params} =
              newline,
              string "  .timeInvalid = 0,",
              newline,
-             string "  .lru = NULL,",
-             newline,
-             string ("  .height = " ^ Int.toString (params - 1) ^ "};"),
+             string "  .timeNow = 0};",
              newline,
              string ("static uw_Sqlcache_Cache *cache" ^ i ^ " = &cacheStruct" ^ i ^ ";"),
              newline,
@@ -83,7 +83,8 @@ fun setupQuery {index, params} =
              newline,
              string ("  char *ks[] = {" ^ revArgs ^ "};"),
              newline,
-             string ("  uw_Sqlcache_CacheValue *v = uw_Sqlcache_check(cache" ^ i ^ ", ks);"),
+             string "  uw_Sqlcache_Value *v = ",
+             string ("uw_Sqlcache_check(cache" ^ i ^ ", ks, " ^ numArgs ^ ");"),
              newline,
              (* If the output is null, it means we had too much recursion, so it's a miss. *)
              string "  if (v && v->output != NULL) {",
@@ -113,7 +114,7 @@ fun setupQuery {index, params} =
              newline,
              string ("  char *ks[] = {" ^ revArgs ^ "};"),
              newline,
-             string ("  uw_Sqlcache_CacheValue *v = malloc(sizeof(uw_Sqlcache_CacheValue));"),
+             string ("  uw_Sqlcache_Value *v = malloc(sizeof(uw_Sqlcache_Value));"),
              newline,
              string "  v->result = strdup(s);",
              newline,
@@ -121,7 +122,7 @@ fun setupQuery {index, params} =
              newline,
              string ("  puts(\"SQLCACHE: stored " ^ i ^ ".\");"),
              newline,
-             string ("  uw_Sqlcache_store(cache" ^ i ^ ", ks, v);"),
+             string ("  uw_Sqlcache_store(cache" ^ i ^ ", ks, " ^ numArgs ^ ", v);"),
              newline,
              string "  return uw_unit_v;",
              newline,
@@ -134,7 +135,7 @@ fun setupQuery {index, params} =
              newline,
              string ("  char *ks[] = {" ^ revArgs ^ "};"),
              newline,
-             string ("  uw_Sqlcache_flush(cache" ^ i ^ ", ks);"),
+             string ("  uw_Sqlcache_flush(cache" ^ i ^ ", ks, " ^ numArgs ^ ");"),
              newline,
              string "  return uw_unit_v;",
              newline,