Initial commitHEADmaster

1 files changed, 148 insertions, 0 deletions

diff --git a/core/index.hpp b/core/index.hpp
new file mode 100644
index 0000000..d110586
--- /dev/null
+++ b/core/index.hpp
@@ -0,0 +1,148 @@
+#ifndef hVYFXl0fhRtHkuIHnrxmZOhDCeI
+#define hVYFXl0fhRtHkuIHnrxmZOhDCeI
+
+#include <assert.h>
+
+#include <string>
+
+#include "time.hpp"
+#include "checkpoint.hpp"
+#include "simlimits.hpp"
+#include "template_helpers.hpp"
+#include "vector.hpp"
+
+// TODO: update r/w-barriers in vector
+
+using std::string;
+
+template<typename Quant>
+struct Index;
+
+template<typename Ptr>
+struct CommonIndex {
+  CommonIndex() = delete;
+  CommonIndex(const string name, Ptr max);
+
+  // type and const defs
+  typedef Ptr ptr_t;
+  static constexpr ptr_t nil() {
+    BOOST_STATIC_ASSERT(( (ptr_t) -1 > 0 ));
+    return -1;
+  }
+
+  // read operations
+  //   HINT: time refers to creation time, not delievery time; the
+  //         later is handled by Filter<>
+  inline ptr_t last();                // returns the latest known event
+  ptr_t last(Time t);                 // ... before (or at) time t
+  inline ptr_t first(); // ... after (or at) ...
+  ptr_t first(Time t);
+
+  ptr_t binarySearch(Time t);
+
+  virtual void sync() { 
+    time.barrierRead() = time.barrierWrite();
+    time.sync();
+  }
+  
+  // vector storing timing
+  Vector<Time> time;
+
+  // writing
+  inline ptr_t add(Time t);
+};
+
+template<typename Ptr>
+inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::last() {
+  // get ptr from any barrier (all should be the same!)
+  ptr_t id = time.barrierWrite.get();
+  if (id==0)
+    return nil();
+  else
+    return id - 1;
+}
+
+template<typename Ptr>
+inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::first() {
+  // get ptr from any barrier (all should be the same!)
+  ptr_t id = time.barrierWrite.get();
+  if (id==0)
+    return nil();
+  else
+    return 0;
+}
+
+template<typename Ptr>
+CommonIndex<Ptr>::CommonIndex(const string name, ptr_t max) : 
+  time(name, max)
+{}
+
+template<typename Ptr>
+typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::last(Time t) {
+  ptr_t cur = binarySearch(t);
+  if ((cur == nil()) or (time(cur) > t))
+    return nil();
+
+  // there may be several elements with time = t; go to the last one
+  while ((cur < last()) && (time(cur + 1) == t))
+    cur++;
+
+  return cur;
+}
+
+template<typename Ptr>
+typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::first(Time t) {
+  ptr_t cur = binarySearch(t);
+
+  if (cur == nil())
+    return nil();
+  if ((time(cur) < t) && (cur < last()))
+      cur = cur + 1;
+  if (time(cur) < t)
+    return nil();
+    
+
+  // there may be several elements with time = t; go to the first one
+  while ((cur > first()) && (time(cur - 1) == t))
+    cur--;
+  return cur;
+}
+
+template<typename Ptr>
+typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::binarySearch(Time t) {
+  // TODO (optimize): use a constant frequency approximation to
+  // initialize min, max and pivot (w/ proper fallback)
+
+  // get the limits of the heap
+  ptr_t max = last();
+  if (max == nil()) return nil(); // no elements, yet
+  ptr_t min = first();
+
+  // check if t \in [min, max]
+  if (t > time(max)) return max;
+  if (t < time(min)) return min;
+
+  // binary search in the heap
+  // invariant: min <= target <= max
+  while ((time(min) != time(max))) {
+    ptr_t pivot = (min + max + 1) / 2;
+    if (t >= time(pivot)) {
+      min = pivot;
+    }else{
+      max = pivot - 1;
+    }
+  }
+
+  return max; // min would be ok, too
+}
+
+template<typename Ptr>
+inline typename CommonIndex<Ptr>::ptr_t CommonIndex<Ptr>::add(Time aTime) {
+  ptr_t id = last() + 1;         // get position to write
+  time.set(id, aTime);           // add new record
+  time.barrierWrite.set(id + 1); // increase write barrier
+
+  return id;
+  }
+
+#endif // hVYFXl0fhRtHkuIHnrxmZOhDCeI