From c3120f2e649f4ce86ad15f3da151a8f7812dde70 Mon Sep 17 00:00:00 2001
From: Jorge Gorbe <jgorbe@stcsl.es>
Date: Mon, 3 Mar 2014 15:00:48 +0100
Subject: [PATCH 1/1] persistent_vector wip

---
 persistent_vector.h | 90 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)
 create mode 100644 persistent_vector.h

diff --git a/persistent_vector.h b/persistent_vector.h
new file mode 100644
index 0000000..0ac3f45
--- /dev/null
+++ b/persistent_vector.h
@@ -0,0 +1,90 @@
+#ifndef PERSISTENT_VECTOR_H
+#define PERSISTENT_VECTOR_H
+
+#include <memory>
+#include <cstdint>
+#include <stdexcept>
+
+namespace persistent {
+
+    class index_out_of_bounds_exception : public std::runtime_error {
+        index_out_of_bounds_exception(): std::runtime_error("Index out of bounds")
+        {
+        }
+    };
+
+    template<typename T>
+    class persistent_vector {
+        private:
+        typedef std::shared_ptr<void> NodePtr;
+        typedef std::vector<T>        ElementVector;
+        typedef std::vector<NodePtr>  NodeVector;
+
+        // U can be either T (for leaf nodes) or NodePtr (for inner nodes)
+        template<typename U> struct node {
+            std::vector<U> array;
+
+            node() : array() {
+                array.reserve(32);
+            }
+        };
+
+
+        uint64_t size;
+        uint32_t shift;
+        NodePtr root;
+        ElementVector tail;
+
+        static std::shared_ptr<void> EMPTY_NODE;
+
+        public:
+        persistent_vector(uint64_t size, uint32_t shift, std::shared_ptr<void> root, std::vector<std::shared_ptr<T>> &&tail) 
+            : size(size)
+            , shift(shift)
+            , root(root)
+            , tail(tail)
+        {
+        }
+
+        persistent_vector() : persistent_vector(0, 5, EMPTY_NODE, std::vector<std::shared_ptr<T>>())
+        {
+        }
+
+        uint64_t tailoff() {
+            if (size < 32)
+                return 0;
+            return ((cnt-1) >> 5) << 5;
+        }
+
+        ElementVector &array_for(uint64_t i) {
+            if (i < size) {
+                if (i >= tailoff()) return tail;
+
+                NodePtr node = root;
+                for (uint32_t level = shift; level > 0; level -= 5) {
+                    node = (node) node->array[(i >> level) & 0x1f];
+                }
+                return node->array;
+            }
+            throw index_out_of_bounds_exception();
+        }
+
+        const T& nth(uint64_t i) {
+            ElementVector &v = array_for(i);
+            return v[i & 0x1f];
+        }
+
+        const T& nth(uint64_t i, const T& notFound) {
+            if (i < size) {
+                return nth(i);
+            }
+            return notFound;
+        }
+
+    };
+
+    template<typename T> std::shared_ptr<void> persistent_vector<T>::EMPTY_NODE = std::make_shared<node<void>>();
+}
+
+
+#endif
-- 
2.34.1