// 15-210, example code
// Extracted from real code...might be some typos in translation

#include "utils.h"
#include "sequence.h"

struct keyval {
  int k;
  int v;
  bool empty() {return k == -1;}
  bool equal(keyval kv) {return kv.k == k;}
};

class Table {
 public:
   int m;
   int mask;
   keyval* A;
   int hashToRange(intT h) {return h & mask;} // quick way of doing a mod m
   int firstIndex(int v) {return hashToRange(hash(v));}
   int incrementIndex(int h) {return hashToRange(h+1);}

   Table(intT size) {
     m = 1 << utils::log2Up(100+(intT)(2.0*(float)size)); // m is power of 2
     mask = m-1;
     A = new keyval[m];
     cilk_for (int i=0; i < m; i++) A[i].k = -1;
   }

  // linear probing, for equal keys, first one to arrive at location wins
  void insert(keyval kv) {
    int h = firstIndex(kv.k);
    while (1) {
      keyval c = A[h];
      if((c.empty() || c.equal(k)) && utils::CAS(&A[h],c,v)) return;
      h = incrementIndex(h);
    }
  }

  // Returns the value if an equal value is found in the table
  // otherwise returns the "empty" element.
  keyval find(key v) {
    int h = firstIndex(v);
    while (1) {
      keyval c = A[h]; 
      if (c.empty()) return empty; 
      else if (c.equal(k)) return c;
      h = incrementIndex(h);
    }
  }
};