3 files changed, 117 insertions, 1 deletions

diff --git a/src/user/include/cxx/structs/alist.h b/src/user/include/cxx/structs/alist.h
new file mode 100644
index 0000000..050f775
--- /dev/null
+++ b/src/user/include/cxx/structs/alist.h
@@ -0,0 +1,41 @@
+#ifndef STRUCTS_ALIST_H
+#define STRUCTS_ALIST_H
+
+#include <knob/format.h>
+#include <knob/block.h>
+#include <knob/panic.h>
+#include <knob/heap.h>
+#include <stdint.h>
+
+template<class data>
+class alist {
+public:
+  uint32_t n_entries;
+  uint32_t buf_size;
+  uint32_t expand_by;
+  data *buf;
+
+  alist(uint32_t default_size=10, uint32_t expand_by=10)
+    : n_entries(0), buf_size(default_size), expand_by(expand_by),
+      buf((data *)get_block(default_size * sizeof(data))) {}
+
+  void add_back(data d) {
+    if (n_entries == buf_size) {
+      data *const new_buf = (data *)get_block((buf_size += expand_by) * sizeof(data));
+      blockcpy(new_buf, buf, n_entries * sizeof(data));
+      free_block(buf);
+      buf = new_buf;
+    }
+    buf[n_entries++] = d;
+  }
+
+  //returns -1 if not found
+  uint32_t index_of(data d) {
+    for (uint32_t i = 0; i < n_entries; ++i)
+      if (buf[i] == d)
+        return i;
+    return -1;
+  }
+};
+
+#endif
\ No newline at end of file
diff --git a/src/user/include/cxx/structs/dllist.h b/src/user/include/cxx/structs/dllist.h
index 5783364..91b0369 100644
--- a/src/user/include/cxx/structs/dllist.h
+++ b/src/user/include/cxx/structs/dllist.h
@@ -1,6 +1,8 @@
 #ifndef STRUCTS_DLLIST_H
 #define STRUCTS_DLLIST_H
 
+#include <stdint.h>
+
 template<class data>
 class dllist {
 public:
@@ -13,20 +15,34 @@ public:
       : next(next), prev(prev), d(d) {}
   };
   node *first;
+  node *last;
 
-  dllist() : first(0) {}
+  dllist() : first(0), last(0) {}
 
   void add_front(data d) {
     node *const n = new node(first, 0, d);
     if (first)
       first->prev = n;
     first = n;
+    if (!last)
+      last = n;
+  }
+
+  void add_back(data d) {
+    node *const n = new node(0, last, d);
+    if (last)
+      last->next = n;
+    last = n;
+    if (!first)
+      first = n;
   }
 
   //return previous, or zero if this is the first
   node *remove_in_place(node *n) {
     if (n == first)
       first = n->next;
+    if (n == last)
+      last = n->prev;
     if (n->next)
       n->next->prev = n->prev;
     if (n->prev)
@@ -34,6 +50,26 @@ public:
     delete n;
     return n->prev;
   }
+
+  bool try_remove_by_ref(data d) {
+    for (node *n = first; n; n = n->next)
+      if (&n->d == &d) {
+        remove_in_place(n);
+        return true;
+      }
+    return false;
+  }
+
+  //returns -1 if it isn't found
+  uint32_t index_of(data d) {
+    uint32_t i = 0;
+    for (const node *n = first; n; n = n->next)
+      if (d == n->d)
+        return i;
+      else
+        ++i;
+    return -1;
+  }
 };
 
 #endif
\ No newline at end of file
diff --git a/src/user/include/cxx/structs/map.h b/src/user/include/cxx/structs/map.h
new file mode 100644
index 0000000..f9c477f
--- /dev/null
+++ b/src/user/include/cxx/structs/map.h
@@ -0,0 +1,39 @@
+#ifndef STRUCTS_MAP_H
+#define STRUCTS_MAP_H
+
+#include <structs/alist.h>
+
+template<class type>
+bool default_equals(type a, type b) {
+  return a == b;
+}
+
+template<class key, class value, bool (*equals)(key, key) = &default_equals<key>>
+class map {
+public:
+  alist<key> keys;
+  alist<value> values;
+
+  map(uint32_t default_size=10, uint32_t expand_by=10)
+    : keys(default_size, expand_by), values(default_size, expand_by) {}
+
+  void add_pair(key k, value v) {
+    for (key *i = keys.buf; i < keys.buf + keys.n_entries; ++i)
+      if (equals(k, *i)) {
+        values.buf[i - keys.buf] = v;
+        return;
+      }
+    keys.add_back(k);
+    values.add_back(v);
+  }
+
+  __attribute__ ((pure))
+  value transform(key k, value fallback=value()) {
+    for (key *i = keys.buf; i < keys.buf + keys.n_entries; ++i)
+      if (equals(k, *i))
+        return values.buf[i - keys.buf];
+    return fallback;
+  }
+};
+
+#endif
\ No newline at end of file