<|start_filename|>PriorityQueue1.hh<|end_filename|>
#pragma once

#include "TVector.hh"
#include <algorithm>

template <typename T, int INIT_CAPACITY = 10000>
class PriorityQueue1 {
public:
    PriorityQueue1() {
        elems.nontrans_reserve(INIT_CAPACITY);
    }

    void push(T v) {
        elems.push_back(v);
        std::push_heap(elems.begin(), elems.end());
    }

    void pop() {
        // XXX(nate): this doesn't compile on OS X clang with a complaint that std::swap is getting an lvalue.
        // this broke in 9bdea5a (we stopped returning a reference in operator*) but idrk how to fix it.
        std::pop_heap(elems.begin(), elems.end());
        elems.pop_back();
    }

    T top() {
        return elems.front();
    }

    uint32_t size() {
        return elems.size();
    }

    void print() {
        elems.print();
    }

private:
    TVector<T> elems;
};


<|start_filename|>unit-tgeneric.cc<|end_filename|>
#undef NDEBUG
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include "Transaction.hh"
#include "TGeneric.hh"

void testSimpleInt() {
	TGeneric f;
    int f1 = 0;

    {
        TransactionGuard t;
        f.write(&f1, 100);
    }

	{
        TransactionGuard t2;
        int f_read = f.read(&f1);
        assert(f_read == 100);
    }

    assert(f1 == 100);

	printf("PASS: %s\n", __FUNCTION__);
}

void testOpacity1() {
    int f[10];
    for (int i = 0; i < 10; i++)
        f[i] = i;
    TGeneric g;

    try {
        TestTransaction t1(1);
        int x = g.read(&f[3]);
        assert(x == 3);

        TestTransaction t(2);
        g.write(&f[3], 2);
        g.write(&f[4], 6);
        assert(t.try_commit());

        t1.use();
        x = g.read(&f[4]);
        assert(false && "shouldn't get here");
        assert(x == 6);
        assert(!t1.try_commit());
    } catch (Transaction::Abort e) {
    }

    {
        TransactionGuard t2;
        int v = g.read(&f[4]);
        assert(v == 6);
        assert(f[4] == 6);
    }

    printf("PASS: %s\n", __FUNCTION__);
}

void testNoOpacity1() {
    int f[10];
    for (int i = 0; i < 10; i++)
        f[i] = i;
    TNonopaqueGeneric g;

    {
        TestTransaction t1(1);
        int x = g.read(&f[3]);
        assert(x == 3);

        TestTransaction t(2);
        g.write(&f[3], 2);
        g.write(&f[4], 6);
        assert(t.try_commit());

        t1.use();
        x = g.read(&f[4]);
        assert(x == 6);
        assert(!t1.try_commit());
    }

    {
        TransactionGuard t2;
        int v = g.read(&f[4]);
        assert(v == 6);
        assert(f[4] == 6);
    }

    printf("PASS: %s\n", __FUNCTION__);
}

void testVariableSizes() {
    struct {
        int a;
        short b;
        char c;
        char d;
    } foo = { 100, 1, 2, 3 };
    TGeneric g;

    {
        TestTransaction t1(1);
        int x = g.read(&foo.a);
        assert(x == 100);
        x = g.read(&foo.b);
        assert(x == 1);
        g.write(&foo.b, 10);
        g.write(&foo.a, 10000);
        g.write(&foo.d, 99);
        assert(foo.a == 100);
        assert(foo.b == 1);
        assert(foo.d == 3);
        x = g.read(&foo.a);
        assert(x == 10000);
        x = g.read(&foo.b);
        assert(x == 10);
        x = g.read(&foo.c);
        assert(x == 2);
        x = g.read(&foo.d);
        assert(x == 99);
        assert(t1.try_commit());

        assert(foo.a == 10000);
        assert(foo.b == 10);
        assert(foo.c == 2);
        assert(foo.d == 99);
    }

    printf("PASS: %s\n", __FUNCTION__);
}

int main() {
    testSimpleInt();
    testOpacity1();
    testNoOpacity1();
    testVariableSizes();
    return 0;
}


<|start_filename|>randgen.hh<|end_filename|>
#pragma once

struct Rand {
    typedef uint32_t result_type;
    result_type x;
    Rand(result_type a, result_type = 0)
        : x(a) {
    }
    result_type operator()() {
        x = 1103515245 * x + 12345;
        return x & 0x7fffffff;
    }
    static constexpr result_type min() {
        return 0;
    }
    static constexpr result_type max() {
        return 0x7fffffff;
    }
};


<|start_filename|>hashtable_nostm.cc<|end_filename|>
#define STO_NO_STM
#import "Hashtable.hh"

// tests of the hashtable without STM


template <typename MapType>
void basicTests(MapType& m) {
  assert(m.insert(1, "foo"));
  assert(!m.put(2, "bar"));

  std::string val;
  assert(m.read(1, val));
  assert(val == "foo");
  assert(m.read(2, val));
  assert(val == "bar");

  assert(m.put(1, "baz"));
  assert(m.remove(2));
  assert(!m.remove(2));

  assert(m.read(1, val));
  assert(val == "baz");
  assert(!m.read(2, val));

  // already present so should be a no op
  assert(!m.insert(1, "fuzz"));
  assert(m.read(1, val));
  assert(val == "baz");
}

int main() {
  Hashtable<int, std::string> h;
  basicTests(h);
}


<|start_filename|>Boosting_list.hh<|end_filename|>
#pragma once

#include "Boosting_tl2.hh"
#include "Boosting_sto.hh"
#include "Boosting_lockkey.hh"

#include "List.hh"

template <typename T, bool Duplicates = false, typename Compare = DefaultCompare<T>, bool Sorted = true>
class TransList 
#if defined(BOOSTING) && defined(STO)
  : public TransUndoable
#endif
{
public:
  typedef List<T, Duplicates, Compare, Sorted> inner_list_t;

  TransList(Compare comp = Compare()) : list_(comp), listlock_() {}

  static void _undoInsert(void *self, void *c1, void *c2) {
    
    ((TransList*)self)->list_.template remove<false>((T){ c1, c2 });
    //delete elem;
  }

  static void _undoDelete(void *self, void *c1, void *c2) {
    T* elem = (T*)c1;
    ((TransList*)self)->list_.insert(*elem);
    delete elem;
  }

  bool transInsert(const T& elem) {
    // TODO: assuming T is a pair_t (always is in STAMP)
    static_assert(sizeof(T) == 16, "we assume T is pair_t");
    TRANS_WRITE_LOCK(&listlock_);
    bool inserted = list_.insert(elem);
    if (inserted) {
      void *words[2];
      new (words) T(elem);
      ADD_UNDO(TransList::_undoInsert, this, words[0], words[1]);
    }
    return inserted;
  }

  T* transFind(const T& elem) {
    printf("never happens\n");
    TRANS_READ_LOCK(&listlock_);
    T* ret = list_.find(elem);
    return ret;
  }

  bool transDelete(const T& elem) {
    printf("never happens either\n");
    TRANS_WRITE_LOCK(&listlock_);
    bool removed = list_.template remove<false>(elem);
    if (removed) {
      ADD_UNDO(TransList::_undoDelete, this, new T(elem), NULL);
    }
    return removed;
  }

  typename inner_list_t::ListIter transIter() {
    TRANS_READ_LOCK(&listlock_);
    return list_.iter();
  }

  typename inner_list_t::ListIter iter() {
    return list_.iter();
  }

  size_t transSize() {
    TRANS_READ_LOCK(&listlock_);
    return list_.size();
  }
  
private:
  inner_list_t list_;
  RWLock listlock_;
};


<|start_filename|>Boosting_fastset.hh<|end_filename|>
#pragma once

#include "local_vector.hh"
#include <string.h>

// should be a multiple of 64
#define BOOSTING_BLOOMFILTER_SIZE 0

// size 0 means no hashtable
#define BOOSTING_HASHTABLE_SIZE 1024

template <typename T, unsigned Size = 512>
class FastSet {
public:
#if BOOSTING_HASHTABLE_SIZE
  static constexpr uint16_t max_base = 1<<15;
#endif
  FastSet() : lockVec_()
#if BOOSTING_HASHTABLE_SIZE
            , hash_base_(0), hashtable_()
#endif
#if BOOSTING_BLOOMFILTER_SIZE
            , bloom_()
#endif
  {}
  void push(T& obj) {
    lockVec_.push_back(obj);
#if BOOSTING_BLOOMFILTER_SIZE
    uint64_t hash = bloom_hash(obj);
    uint64_t idx = hash / 64;
    hash = hash % 64;
    bloom_[idx] |= 1 << hash;
#endif
#if BOOSTING_HASHTABLE_SIZE
    auto& h = hashtable_[hash(obj)];
    if (h <= hash_base_)
      h = hash_base_ + lockVec_.size();
#endif
  }
  typename local_vector<T, Size>::iterator find (T& obj) {
    auto it = lockVec_.begin();
    for (auto end = lockVec_.end(); it != end; ++it) {
      if (*it == obj) {
        return it;
      }
    }
    return it;
  }
  typename local_vector<T, Size>::iterator begin () {
    return lockVec_.begin();
  }
  typename local_vector<T, Size>::iterator end () {
    return lockVec_.end();
  }
  bool exists(T& obj) {
#if BOOSTING_BLOOMFILTER_SIZE
    if (definitely_absent(obj))
      return false;
#endif
#if BOOSTING_HASHTABLE_SIZE
    auto idx = hashtable_[hash(obj)];
    if (idx <= hash_base_)
      return false;
    else if (lockVec_[idx - hash_base_ - 1] == obj)
        return true;
#endif
    return find(obj) != lockVec_.end();
  }
  void clear() {
#if BOOSTING_HASHTABLE_SIZE
    hash_base_ += lockVec_.size();
    if (hash_base_ >= max_base) {
      memset(hashtable_, 0, sizeof(hashtable_));
      hash_base_ = 0;
    }
#endif
    lockVec_.clear();
#if BOOSTING_BLOOMFILTER_SIZE
    memset(bloom_, 0, sizeof(bloom_));
#endif
  }
  void unsafe_clear() {
#if BOOSTING_HASHTABLE_SIZE
    hash_base_ += lockVec_.size();
    if (hash_base_ >= max_base) {
      memset(hashtable_, 0, sizeof(hashtable_));
      hash_base_ = 0;
    }
#endif
    lockVec_.unsafe_clear();
#if BOOSTING_BLOOMFILTER_SIZE
    memset(bloom_, 0, sizeof(bloom_));
#endif
  }
  bool insert(T& obj) {
    if (exists(obj))
      return false;
    lockVec_.push_back(obj);
    return true;
  }
  bool erase(T& obj) {
    auto it = find(obj);
    if (it != lockVec_.end()) {
      lockVec_.erase(it);
      return true;
    }
    return false;
  }
private:
  local_vector<T, Size> lockVec_;
#if BOOSTING_HASHTABLE_SIZE
  uint16_t hash_base_;
  uint16_t hashtable_[BOOSTING_HASHTABLE_SIZE];
  static inline int hash(T& obj) {
    uintptr_t n = (uintptr_t)obj;
    //    return (n >> 4) % BOOSTING_HASHTABLE_SIZE;
    return (n + (n>>16)*9) % BOOSTING_HASHTABLE_SIZE;
    return ((n >> 4) ^ (n >> 20)) % BOOSTING_HASHTABLE_SIZE;
  }
#endif
#if BOOSTING_BLOOMFILTER_SIZE
  uint64_t bloom_[BOOSTING_BLOOMFILTER_SIZE / 64];
  static inline uint64_t bloom_hash(T& obj) {
    // assuming T is a pointer
    return (((intptr_t)obj >> 2) ^ ((intptr_t)obj >> 5)) % BOOSTING_BLOOMFILTER_SIZE;
  }
public:
  inline bool definitely_absent(T& obj) {
    uint64_t hash = bloom_hash(obj);
    int idx = hash / 64;
    hash = hash % 64;
    return !((1<<hash) & bloom_[idx]);
  }
#endif
};


<|start_filename|>Box.hh<|end_filename|>
#pragma once
#include "Interface.hh"
#include "versioned_value.hh"

template <typename T,  bool GenericSTM = false, typename Structure = versioned_value_struct<T>>
// if we're inheriting from TObject then a SingleElem adds both a version word and a vtable word
// (not much else we can do though)
class Box {
public:
    static constexpr TransItem::flags_type valid_only_bit = TransItem::user0_bit;
    
    Box() : s_() , local_lock(false) {}
    
    T unsafe_read() const {
        return s_.read_value();
    }
    
    void write(T v) {
        bool locked = try_lock();
        // Can be locked by a thread that is about to abort or locked by a thread that is about to release the locks.
        if (!locked) lock_local();
        s_.set_value(v);
        TransactionTid::type newv = (s_.version() + TransactionTid::increment_value) | TransactionTid::nonopaque_bit;
        release_fence();
        s_.version() = newv;
        if (!locked) unlock_local();
        else unlock();
    }

private:
    typedef TransactionTid::type version_type;

    inline void atomicRead(version_type& v, T& val) {
        version_type v2;
        do {
            v2 = s_.version();
            if (TransactionTid::is_locked(v2))
              Sto::abort();
            fence();
            val = s_.read_value();
            fence();
            v = s_.version();
        } while (v != v2);
    }

public:
    T transRead(TransProxy item) {
        if (item.has_write())
            return item.template write_value<T>();
        else {
            version_type v;
            T val;
            atomicRead(v, val);
            if (GenericSTM)
              Sto::check_opacity(v);
            if (item.flags() & valid_only_bit) {
                item.clear_read();
                item.clear_flags(valid_only_bit);
            }
            item.add_read(v);
            return val;
        }
    }
    
    void transWrite(TransProxy item, const T& v) {
        item.add_write(v);
        if (!item.has_read()) {
            item.add_read(v).add_flags(valid_only_bit);
        }
    }
  
    void lock() {
        TransactionTid::lock(s_.version());
    }
    
    bool try_lock() {
        return TransactionTid::try_lock(s_.version());
    }

    void unlock() {
        lock_local();
        TransactionTid::unlock(s_.version());
        unlock_local();
    }

    bool is_locked_elsewhere() const {
        return TransactionTid::is_locked_elsewhere(s_.version());
    }
    bool check_version(version_type v) const {
        return TransactionTid::check_version(s_.version(), v);
    }
    void install(TransItem& item, const Transaction& t) {
        s_.set_value(item.template write_value<T>());
        if (GenericSTM) {
            TransactionTid::set_version(s_.version(), t.commit_tid());
        } else {
            TransactionTid::inc_nonopaque_version(s_.version());
        }
    }

    void lock_local() {
        while (1) {
            bool vv = local_lock;
            if (!vv && bool_cmpxchg(&local_lock, vv, true))
                break;
            relax_fence();
        }
        acquire_fence();
    }
    void unlock_local() {
        assert(local_lock == true);
        local_lock = false;
    }


  protected:
    // we Store the versioned_value inlined (no added boxing)
    Structure s_;
    bool local_lock;
};


<|start_filename|>vector.cc<|end_filename|>
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include "Transaction.hh"
#include "Vector.hh"

void testSimpleInt() {
    Vector<int> f;

    {
        TransactionGuard t;
        f.push_back(100);
        f.push_back(200);
        *(f.begin()) = *(f.begin() + 1);
    }

    {
        TransactionGuard t2;
        int f_read = f[0];
        assert(f_read == 200);
    }

    printf("PASS: testSimpleInt\n");
}

void testWriteNPushBack() {
    Vector<int> f;

    {
        TransactionGuard t;
        f.push_back(10);
    }

    TestTransaction t2(1);
    f[0] = 4;

    TestTransaction t3(2);
    f.push_back(20); // This will resize the array
    assert(t3.try_commit());
    assert(t2.try_commit()); // This should not conflict with the write

    {
        TransactionGuard t4;
        assert(f[0] == 4); // Make sure that the value is actually updated
    }

    printf("PASS: testWriteNPushBack\n");
}

void testPushBack() {
    Vector<int> f;

    {
        TransactionGuard t;
        f.push_back(10);
    }

    TestTransaction t2(1);
    f.push_back(4);
    
    TestTransaction t3(2);
    f.push_back(20);
    assert(t3.try_commit());
    assert(t2.try_commit()); // This should not conflict with the push_back

    {
        TransactionGuard t4;
        assert(f[0] == 10);
        assert(f[1] == 20);
        assert(f[2] == 4);
    }

    printf("PASS: testPushBack\n");
}


void testPushBackNRead() {
    Vector<int> f;

    {
        TransactionGuard t;
        f.push_back(10);
    }

    {
        TransactionGuard t2;
        f.push_back(4);
        assert(f[1] == 4);
    }

    printf("PASS: testPushBackNRead\n");
}

void testPushBackNRead1() {
    Vector<int> f;

    {
        TransactionGuard t;
        f.push_back(10);
    }

    TestTransaction t2(1);
    f.push_back(4);
    assert(f[1] == 4);
    
    TestTransaction t3(2);
    f.push_back(20);
    assert(t3.try_commit());
    assert(!t2.try_commit());

    printf("PASS: testPushBackNRead1\n");
}

void testPushBackNRead2() {
    Vector<int> f;

    {
        TransactionGuard t;
        f.push_back(10);
    }

    TestTransaction t2(1);
    f.push_back(4);
    assert(f[f.size() - 1] == 4);
    
    TestTransaction t3(2);
    f.push_back(20);

    assert(t3.try_commit());
    assert(!t2.try_commit()); // TODO: this can actually commit

    printf("PASS: testPushBackNRead2\n");
}


void testPushBackNWrite() {
    Vector<int> f;

    {
        TransactionGuard t;
        f.push_back(10);
    }

    {
        TransactionGuard t2;
        f.push_back(4);
        f[1] = 10;
    }

    {
        TransactionGuard t3;
        assert(f[1] == 10);
    }

    printf("PASS: testPushBackNRead\n");
}



void testSimpleString() {
    Vector<std::string> f;

    {
        TransactionGuard t;
        f.push_back("100");
    }

    {
	TransactionGuard t2;
	std::string f_read = f[0];
	assert(f_read.compare("100") == 0);
    }

    printf("PASS: testSimpleString\n");
}

void testIter() {
    std::vector<int> arr;
    Vector<int> f;
    TRANSACTION {
    for (int i = 0; i < 10; i++) {
        int x = rand();
        f.push_back(x);
        arr.push_back(x);
    }
    } RETRY(false);

    int max;
    TRANSACTION {
        max = *(std::max_element(f.begin(), f.end()));
    } RETRY(false);
    
    assert(max == *(std::max_element(arr.begin(), arr.end())));
    printf("Max is %i\n", max);
    printf("PASS: vector max_element test\n");
    
}


void testConflictingIter() {
    Vector<int> f;
    TRANSACTION {
    for (int i = 0; i < 10; i++) {
        f.push_back(i);
    }
    } RETRY(false);

    TestTransaction t(1);
    std::max_element(f.begin(), f.end());
    
    TestTransaction t1(2);
    f[4] = 10;
    assert(t1.try_commit());
    assert(!t.try_commit());

    printf("PASS: conflicting vector max_element test\n");
    
}

void testModifyingIter() {
    Vector<int> f;
    {
        TransactionGuard tt;
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    }

    {
        TransactionGuard t;
        std::replace(f.begin(), f.end(), 4, 6);
    }

    {
        TransactionGuard t1;
        int v = f[4];
        assert(v == 6);
    }

    printf("PASS: vector replace test\n");
}

void testConflictingModifyIter1() {
    Vector<int> f;
    TRANSACTION {
    for (int i = 0; i < 10; i++) {
        f.push_back(i);
    }
    } RETRY(false);
    
    TestTransaction t(1);
    std::replace(f.begin(), f.end(), 4, 6);
    
    TestTransaction t1(2);
    f[4] = 10;
    assert(t1.try_commit());
    assert(!t.try_commit());

    {
        TransactionGuard t2;
        int v = f[4];
        assert(v == 10);
    }

    printf("PASS: vector conflicting replace test1\n");
}

void testConflictingModifyIter2() {
    Vector<int> f;
    TRANSACTION {
    for (int i = 0; i < 10; i++) {
        f.push_back(i);
    }
    } RETRY(false);

    {
        TransactionGuard t;
        std::replace(f.begin(), f.end(), 4, 6);
    }

    {
        TransactionGuard t1;
        f[4] = 10;
    }

    {
        TransactionGuard t2;
        int v = f[4];
        assert(v == 10);
    }

    printf("PASS: vector conflicting replace test2\n");
}

void testConflictingModifyIter3() {
    Vector<int> f;
    TRANSACTION {
    for (int i = 0; i < 10; i++) {
        f.push_back(i);
    }
    } RETRY(false);
    
    TestTransaction t1(1);
    (int) f[4];
    
    TestTransaction t(2);
    std::replace(f.begin(), f.end(), 4, 6);
    assert(t.try_commit());
    assert(!t1.try_commit());

    {
        TransactionGuard t2;
        int v = f[4];
        assert(v == 6);
    }

    printf("PASS: vector conflicting replace test3\n");
}

void testIterNPushBack() {
    Vector<int> f;
    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);
    
    int max;
    TRANSACTION {
        f.push_back(20);
        max = *(std::max_element(f.begin(), f.end()));
    } RETRY(false);

    assert(max == 20);
    printf("PASS: IterNPushBack\n");
}

void testIterNPushBack1() {
    Vector<int> f;
    {
        TransactionGuard tt;
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    }

    int max;
    TestTransaction t1(1);
    f.push_back(20);
    max = *(std::max_element(f.begin(), f.end()));
    assert(max == 20);
    
    TestTransaction t2(2);
    f.push_back(12);
    assert(t2.try_commit());
    assert(!t1.try_commit());
    
    printf("PASS: IterNPushBack1\n");    
}

void testIterNPushBack2() {
    Vector<int> f;

    {
        TransactionGuard tt;
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    }

    TestTransaction t1(1);
    std::max_element(f.begin(), f.end());
    
    TestTransaction t2(2);
    f.push_back(2);
    assert(t2.try_commit());
    assert(!t1.try_commit());
    
    printf("PASS: IterNPushBack2\n");
    
}


void testErase() {
    Vector<int> f;

    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);

    {
        TransactionGuard t1;
        f.erase(f.begin() + 5);
    }

    TRANSACTION {
        Vector<int>::iterator it = f.begin();
        Vector<int>::iterator eit = f.end();
        for (; it != eit; ++it) {
            printf("%i\n", (int)*it);
        }
    } RETRY(false);
    
    printf("PASS: testErase\n");
}

void testInsert() {
    Vector<int> f;
    
    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);

    {
        TransactionGuard t1;
        f.insert(f.begin() + 5, 25);
    }

    TRANSACTION {
        Vector<int>::iterator it = f.begin();
        Vector<int>::iterator eit = f.end();
        for (; it != eit; ++it) {
            printf("%i\n", (int)*it);
        }
    } RETRY(false);
    
    printf("PASS: testInsert\n");
}


void testPushNPop() {
    Vector<int> f;
    
    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);

    {
        TransactionGuard t;
        f.push_back(20);
        f.push_back(21);
        assert(f[0] == 0);
        assert(f.size() == 12);
        f.pop_back();
        f.pop_back();
    }
    
    TestTransaction t1(1);
    f.pop_back();
    f.push_back(15);
    
    TestTransaction t2(2);
    f.push_back(20);
    assert(t2.try_commit());
    assert(!t1.try_commit());
    
    TRANSACTION {
        assert(f.size() == 11);
        assert(f[10] == 20);
    } RETRY(false);
    
    
    printf("PASS: testPushNPop\n");
    
    TestTransaction t3(1);
    f.pop_back();
    f.push_back(15);
    
    TestTransaction t4(2);
    f.pop_back();
    assert(t4.try_commit());
    assert(!t3.try_commit());
    
    TRANSACTION {
        assert(f.size() == 10);
    } RETRY(false);

    printf("PASS: testPushNPop1\n");

    TestTransaction t5(1);
    f.pop_back();
    f.pop_back();
    f.push_back(15);

    TestTransaction t6(2);
    f[8] = 16;
    assert(t6.try_commit());

    TestTransaction t7(3);
    (int) f[8];
    
    assert(t5.try_commit());
    assert(!t7.try_commit());

    TRANSACTION {
        assert(f.size() == 9);
        assert(f[8] == 15);
    } RETRY(false);

    printf("PASS: testPushNPop2\n");
}

void testPopAndUdpate() {
    Vector<int> f;
    
    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);
    
    TestTransaction t1(1);
    f[9] = 20;

    TestTransaction t2(2);
    f.pop_back();
    f.pop_back();
    assert(t2.try_commit());
    assert(!t1.try_commit());
}

void testMulPushPops() {
    Vector<int> f;
    
    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);

    {
        TransactionGuard t1;
        f.push_back(100);
        f.push_back(200);
        f.pop_back();
        f.pop_back();
        f.pop_back();
    }
}

void testMulPushPops1() {
    Vector<int> f;
    
    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);

    {
        TransactionGuard t1;
        f.push_back(100);
        f.push_back(200);
        f.pop_back();
        f.pop_back();
        f.push_back(300);
    }
}

void testUpdatePop() {
    Vector<int> f;
    
    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);

    {
        TransactionGuard t1;
        f[9] = 20;
        f.pop_back();
    }
}

void testIteratorBetterSemantics() {
    Vector<int> f;
    
    TRANSACTION {
        for (int i = 0; i < 10; i++) {
            f.push_back(i);
        }
    } RETRY(false);

    TestTransaction t1(1);
    // XXX std::find uses a special case for random-access iterators
    // that calls size()
    Vector<int>::iterator it;
    for (it = f.begin(); it != f.end(); ++it)
        if (*it == 5)
            break;

    TestTransaction t2(2);
    f.push_back(12);
    assert(t2.try_commit());
    t1.use();
    int x = *it;
    assert(t1.try_commit());
    assert(x == 5);

    printf("PASS: IteratorBetterSemantics\n");

}





int main() {
    testSimpleInt();
    testWriteNPushBack();
    testPushBack();
    testPushBackNRead();
    testPushBackNRead1();
    testPushBackNRead2();
    testPushBackNWrite();
    testSimpleString();
    testIter();
    testConflictingIter();
    testModifyingIter();
    testConflictingModifyIter1();
    testConflictingModifyIter2();
    testConflictingModifyIter3();
    testIterNPushBack();
    testIterNPushBack1();
    testIterNPushBack2();
    testErase();
    testInsert();
    testPushNPop();
    testPopAndUdpate();
    testMulPushPops();
    testMulPushPops1();
    testUpdatePop();
    testIteratorBetterSemantics();
    return 0;
}


<|start_filename|>Debug_rcu.hh<|end_filename|>
#pragma once

// a no-op RCU class for MassTrans (aka, completely unimportant code)

#if !RCU
class debug_threadinfo {
public:
#if 0
  debug_threadinfo()
    : ts_(0) { // XXX?
  }
#endif

  class rcu_callback {
  public:
    virtual void operator()(debug_threadinfo& ti) = 0;
  };

private:
  static inline void rcu_callback_function(void* p) {
    debug_threadinfo ti;
    static_cast<rcu_callback*>(p)->operator()(ti);
  }


public:
  // XXX Correct node timstamps are needed for recovery, but for no other
  // reason.
  kvtimestamp_t operation_timestamp() const {
    return 0;
  }
  kvtimestamp_t update_timestamp() const {
    return ts_;
  }
  kvtimestamp_t update_timestamp(kvtimestamp_t x) const {
    if (circular_int<kvtimestamp_t>::less_equal(ts_, x))
      // x might be a marker timestamp; ensure result is not
      ts_ = (x | 1) + 1;
    return ts_;
  }
  kvtimestamp_t update_timestamp(kvtimestamp_t x, kvtimestamp_t y) const {
    if (circular_int<kvtimestamp_t>::less(x, y))
      x = y;
    if (circular_int<kvtimestamp_t>::less_equal(ts_, x))
      // x might be a marker timestamp; ensure result is not
      ts_ = (x | 1) + 1;
    return ts_;
  }
  void increment_timestamp() {
    ts_ += 2;
  }
  void advance_timestamp(kvtimestamp_t x) {
    if (circular_int<kvtimestamp_t>::less(ts_, x))
      ts_ = x;
  }

  // event counters
  void mark(threadcounter) {
  }
  void mark(threadcounter, int64_t) {
  }
  bool has_counter(threadcounter) const {
    return false;
  }
  uint64_t counter(threadcounter) const {
    return 0;
  }

  /** @brief Return a function object that calls mark(ci); relax_fence().
   *
   * This function object can be used to count the number of relax_fence()s
   * executed. */
  relax_fence_function accounting_relax_fence(threadcounter) {
    return relax_fence_function();
  }

  class accounting_relax_fence_function {
  public:
    template <typename V>
    void operator()(V) {
      relax_fence();
    }
  };
  /** @brief Return a function object that calls mark(ci); relax_fence().
   *
   * This function object can be used to count the number of relax_fence()s
   * executed. */
  accounting_relax_fence_function stable_fence() {
    return accounting_relax_fence_function();
  }

  relax_fence_function lock_fence(threadcounter) {
    return relax_fence_function();
  }

  void* allocate(size_t sz, memtag) {
    return malloc(sz);
  }
  void deallocate(void* , size_t , memtag) {
    // in C++ allocators, 'p' must be nonnull
    //free(p);
  }
  void deallocate_rcu(void *, size_t , memtag) {
  }

  void* pool_allocate(size_t sz, memtag) {
    int nl = (sz + CACHE_LINE_SIZE - 1) / CACHE_LINE_SIZE;
    return malloc(nl * CACHE_LINE_SIZE);
  }
  void pool_deallocate(void* , size_t , memtag) {
  }
  void pool_deallocate_rcu(void* , size_t , memtag) {
  }

  // RCU
  void rcu_register(rcu_callback *) {
    //    scoped_rcu_base<false> guard;
    //rcu::s_instance.free_with_fn(cb, rcu_callback_function);
  }

private:
  mutable kvtimestamp_t ts_;
};

#endif


<|start_filename|>trans_test.cc<|end_filename|>
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include <random>
#include <map>
#include "Transaction.hh"
#include "Testers.hh"

#define GLOBAL_SEED 10
#define NTRANS 200 // Number of transactions each thread should run.
#define N_THREADS 3 // Number of concurrent threads
#define MAX_OPS 3 // Maximum number of operations in a transaction.

#define PRIORITY_QUEUE 0
#define HASHTABLE 1
#define RBTREE 2
#define VECTOR 3
#define DS RBTREE 

#if DS == PRIORITY_QUEUE
PqueueTester<PriorityQueue<int>> tester = PqueueTester<PriorityQueue<int>>();
#elif DS == HASHTABLE
HashtableTester<Hashtable<int, int, false, 1000000>> tester = HashtableTester<Hashtable<int, int, false, 1000000>>();
#elif DS == RBTREE
RBTreeTester<RBTree<int, int, true>, std::map<int, int>> tester = RBTreeTester<RBTree<int, int, true>, std::map<int, int>>();
#elif DS == VECTOR
VectorTester<Vector<int>> tester = VectorTester<Vector<int>>();
#endif

template <typename T>
void run(T* q, int me) {
    TThread::set_id(me);
    
    std::uniform_int_distribution<long> slotdist(0, MAX_VALUE);
    for (int i = 0; i < NTRANS; ++i) {
        // so that retries of this transaction do the same thing
        auto transseed = i;
        txn_record *tr = new txn_record;
        while (1) {
        Sto::start_transaction();
        try {
            tr->ops.clear();
            
            uint32_t seed = transseed*3 + (uint32_t)me*NTRANS*7 + (uint32_t)GLOBAL_SEED*MAX_THREADS*NTRANS*11;
            auto seedlow = seed & 0xffff;
            auto seedhigh = seed >> 16;
            Rand transgen(seed, seedlow << 16 | seedhigh);
            
            int numOps = slotdist(transgen) % MAX_OPS + 1;
            
            for (int j = 0; j < numOps; j++) {
                int op = slotdist(transgen) % tester.num_ops_;
                tr->ops.push_back(tester.doOp(q, op, me, slotdist, transgen));
            }

            if (Sto::try_commit()) {
#if PRINT_DEBUG
                TransactionTid::lock(lock);
                std::cout << "[" << me << "] committed " << Sto::commit_tid() << std::endl;
                TransactionTid::unlock(lock);
#endif
                txn_list[me][Sto::commit_tid()] = tr;
                break;
            } else {
#if PRINT_DEBUG
                TransactionTid::lock(lock); std::cout << "[" << me << "] aborted "<< std::endl; TransactionTid::unlock(lock);
#endif
            }

        } catch (Transaction::Abort e) {
#if PRINT_DEBUG
            TransactionTid::lock(lock); std::cout << "[" << me << "] aborted "<< std::endl; TransactionTid::unlock(lock);
#endif
        }
        }
    }
}

template <typename T>
void* runFunc(void* x) {
    TesterPair<T>* tp = (TesterPair<T>*) x;
    run(tp->t, tp->me);
#if PRINT_DEBUG 
    TransactionTid::lock(lock); tester.print_stats(tp->t); TransactionTid::unlock(lock);
#endif
    return nullptr;
}


template <typename T>
void startAndWait(T* ds) {
    pthread_t tids[N_THREADS];
    TesterPair<T> testers[N_THREADS];
    for (int i = 0; i < N_THREADS; ++i) {
        testers[i].t = ds;
        testers[i].me = i;
        pthread_create(&tids[i], NULL, runFunc<T>, &testers[i]);
    }
    pthread_t advancer;
    pthread_create(&advancer, NULL, Transaction::epoch_advancer, NULL);
    pthread_detach(advancer);
    
    for (int i = 0; i < N_THREADS; ++i) {
        pthread_join(tids[i], NULL);
    }
}

void print_time(struct timeval tv1, struct timeval tv2) {
    printf("%f\n", (tv2.tv_sec-tv1.tv_sec) + (tv2.tv_usec-tv1.tv_usec)/1000000.0);
}

int main() {
    std::ios_base::sync_with_stdio(true);
    assert(CONSISTENCY_CHECK); // set CONSISTENCY_CHECK in Transaction.hh
    lock = 0;

#if DS == PRIORITY_QUEUE 
    PriorityQueue<int> q;
    PriorityQueue<int> q1;
#elif DS == HASHTABLE
    Hashtable<int, int, false, 1000000> q;
    Hashtable<int, int, false, 1000000> q1;
#elif DS == RBTREE
    RBTree<int, int, true> q;
    std::map<int, int> q1;
#elif DS == VECTOR
    Vector<int> q;
    Vector<int> q1;
#endif  

    tester.init(&q);
    tester.init(&q1);

    struct timeval tv1,tv2;
    gettimeofday(&tv1, NULL);
    
    for (int i = 0; i < N_THREADS; i++) {
        txn_list.emplace_back();
    }
    
    startAndWait(&q);
    
    gettimeofday(&tv2, NULL);
    printf("Parallel time: ");
    print_time(tv1, tv2);
    
#if STO_PROFILE_COUNTERS
    Transaction::print_stats();
    {
        txp_counters tc = Transaction::txp_counters_combined();
        printf("total_n: %llu, total_r: %llu, total_w: %llu, total_searched: %llu, total_aborts: %llu (%llu aborts at commit time)\n", tc.p(txp_total_n), tc.p(txp_total_r), tc.p(txp_total_w), tc.p(txp_total_searched), tc.p(txp_total_aborts), tc.p(txp_commit_time_aborts));
    }
#endif
    
    
    std::map<uint64_t, txn_record *> combined_txn_list;
    
    for (int i = 0; i < N_THREADS; i++) {
        combined_txn_list.insert(txn_list[i].begin(), txn_list[i].end());
    }
    
    std::cout << "Single thread replay" << std::endl;
    gettimeofday(&tv1, NULL);
    
    std::map<uint64_t, txn_record *>::iterator it = combined_txn_list.begin();
    for(; it != combined_txn_list.end(); it++) {
#if PRINT_DEBUG
        std::cout << "BEGIN txn " << it->first << std::endl;
#endif
        Sto::start_transaction();
        for (unsigned i = 0; i < it->second->ops.size(); i++) {
            tester.redoOp(&q1, it->second->ops[i]);
        }
        assert(Sto::try_commit());
#if PRINT_DEBUG
        std::cout << "COMMITTED" << std::endl;
#endif
    }
    
    gettimeofday(&tv2, NULL);
    printf("Serial time: ");
    print_time(tv1, tv2);
    
   
    tester.check(&q, &q1);
	return 0;
}


<|start_filename|>pqueue.cc<|end_filename|>
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include <random>
#include <map>
#include "Transaction.hh"
#include "Vector.hh"
#include "PriorityQueue.hh"
#include "PriorityQueue1.hh"
#include "randgen.hh"

#define GLOBAL_SEED 0
#define MAX_VALUE  100000
#define NTRANS 1000
#define N_THREADS 4

typedef PriorityQueue<int> data_structure;
unsigned initial_seeds[128];


struct txn_record {
    // keeps track of pushes and pops for a single transaction
    std::vector<int> pushes;
    std::vector<int> tops;
    int pops;
};



template <typename T>
struct TesterPair {
    T* t;
    int me;
};

std::vector<std::map<uint64_t, txn_record *> > txn_list;
typedef TransactionTid::type Version;
Version lock;

void run_conc(data_structure* q, int me) {
    std::uniform_int_distribution<long> slotdist(0, MAX_VALUE);
    Rand transgen(initial_seeds[2*me], initial_seeds[2*me + 1]);

    for (int i = 0; i < NTRANS; ++i) {
        // so that retries of this transaction do the same thing
        int val1 = slotdist(transgen);
        int val2 = slotdist(transgen);
        int val3 = slotdist(transgen);
        q->push_nontrans(val1);
        q->push_nontrans(val2);
        q->push_nontrans(val3);
        //q->pop();
        //q->pop();
    }
}

template <typename T>
void run(T* q, int me) {
    TThread::set_id(me);

    std::uniform_int_distribution<long> slotdist(0, MAX_VALUE);
    Rand transgen(initial_seeds[2*me], initial_seeds[2*me + 1]);

    for (int i = 0; i < NTRANS; ++i) {
        // so that retries of this transaction do the same thing
        Rand transgen_snap = transgen;
        txn_record *tr = new txn_record;
        while (1) {
        Sto::start_transaction();
        try {
            tr->pushes.clear();
            tr->pops = 0;
            tr->tops.clear();

            int val1 = slotdist(transgen);
            int val2 = slotdist(transgen);
            int val3 = slotdist(transgen);
            q->pop();
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] try to push " << val1 << std::endl;
            //TransactionTid::unlock(lock);
            q->push(val1);
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] pushed " << val1 << std::endl;
            //TransactionTid::unlock(lock);
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] try to push " << val2 << std::endl;
            //TransactionTid::unlock(lock);
            q->push(val2);
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] pushed " << val2 << std::endl;
            //TransactionTid::unlock(lock);
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] try to push " << val3 << std::endl;
            //TransactionTid::unlock(lock);
            //q->push(val3);
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] pushed " << val3 << std::endl;
            //TransactionTid::unlock(lock);
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] try to read "  << std::endl;
            //TransactionTid::unlock(lock);
            int rval = q->top();
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] read " << rval << std::endl;
            //TransactionTid::unlock(lock);
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] try to pop "  << std::endl;
            //TransactionTid::unlock(lock);
            //int pval = q->pop();
            q->push(val3);
            //TransactionTid::lock(lock);
            //std::cout << "[" << me << "] popped " << pval << std::endl;
            //TransactionTid::unlock(lock);
            //q->pop();

            tr->pushes.push_back(val1);
            tr->pushes.push_back(val2);
            tr->pushes.push_back(val3);
            tr->pops = 1;
            tr->tops.push_back(rval);

            if (Sto::try_commit()) {
                //TransactionTid::lock(lock);
                //std::cout << "[" << me << "] committed "  << std::endl;
                //TransactionTid::unlock(lock);
                txn_list[me][Sto::commit_tid()] = tr;
                break;
            }

        } catch (Transaction::Abort e) {
            //TransactionTid::lock(lock); std::cout << "[" << me << "] aborted "<< std::endl; TransactionTid::unlock(lock);
        }
        transgen = transgen_snap;
        }
    }
}

template <typename T>
void* runFunc(void* x) {
    TesterPair<T>* tp = (TesterPair<T>*) x;
    run(tp->t, tp->me);
    return nullptr;
}

void* runConcFunc(void* x) {
    TesterPair<data_structure>* tp = (TesterPair<data_structure>*) x;
    run_conc(tp->t, tp->me);
    return nullptr;
}

template <typename T>
void startAndWait(T* queue, bool parallel = true) {
    pthread_t tids[N_THREADS];
    TesterPair<T> testers[N_THREADS];
    for (int i = 0; i < N_THREADS; ++i) {
        testers[i].t = queue;
        testers[i].me = i;
        if (parallel)
            pthread_create(&tids[i], NULL, runFunc<T>, &testers[i]);
        else
            pthread_create(&tids[i], NULL, runConcFunc, &testers[i]);
    }

    for (int i = 0; i < N_THREADS; ++i) {
        pthread_join(tids[i], NULL);
    }
}

// These tests are adapted from the queue tests in single.cc
void queueTests() {
    data_structure q;
    
    // NONEMPTY TESTS
    {
        // ensure pops read pushes in FIFO order
        TransactionGuard t;
        // q is empty
        q.push(1);
        q.push(2);
        assert(q.top()  == 2);
        q.pop();
        assert(q.top() == 1);
        q.pop();
    }
    
    {
        TransactionGuard t;
        // q is empty
        q.push(1);
        q.push(2);
    }
    
    {
        // front with no pops
        TransactionGuard t;
        assert(q.top() == 2);
        assert(q.top() == 2);
    }
    
    {
        // pop until empty
        TransactionGuard t;
        q.pop();
        q.pop(); // After this, queue is empty
        
        // prepare pushes for next test
        q.push(1);
        q.push(2);
        q.push(3);
    }
    
    {
        // fronts intermixed with pops
        TransactionGuard t;
        assert(q.top() == 3);
        q.pop();
        assert(q.top() == 2);
        q.pop();
        assert(q.top() == 1);
        q.pop();
        //q.pop();
        
        // set up for next test
        q.push(1);
        q.push(2);
        q.push(3);
    }
    
    {
        // front intermixed with pushes on nonempty
        TransactionGuard t;
        assert(q.top() == 3);
        assert(q.top() == 3);
        q.push(4);
        assert(q.top() == 4);
    }
    
    {
        // pops intermixed with pushes and front on nonempty
        // q = [4 3 2 1]
        TransactionGuard t;
        q.pop();
        assert(q.top() == 3);
        q.push(5);
        // q = [5 3 2 1]
        q.pop();
        assert(q.top() == 3);
        q.push(6);
        // q = [6 3 2 1]
    }
    
    // EMPTY TESTS
    {
        // front with empty queue
        TransactionGuard t;
        // empty the queue
        q.pop();
        q.pop();
        q.pop();
        q.pop();
        //q.pop();
        
        //q.top();
        
        q.push(1);
        assert(q.top() == 1);
        assert(q.top() == 1);
    }
    
    {
        // pop with empty queue
        TransactionGuard t;
        // empty the queue
        q.pop();
        //q.pop();
        
        //q.top();
        
        q.push(1);
        q.pop();
        //q.pop();
    }
    
    {
        // pop and front with empty queue
        TransactionGuard t;
        //q.top();
        
        q.push(1);
        assert(q.top() == 1);
        q.pop();
        
        q.push(1);
        q.pop();
        //q.top();
        //q.pop();
        
        // add items for next test
        q.push(1);
        q.push(2);
    }
    
    // CONFLICTING TRANSACTIONS TEST
    {
        // test abortion due to pops
        TestTransaction t1(1);
        TestTransaction t2(2);
        // q has >1 element
        t1.use();
        q.pop();
        t2.use();
        bool aborted = false;
        try {
            q.pop();
        } catch (Transaction::Abort e) {
            aborted = true;
        }
        assert(t1.try_commit());
        assert(aborted);
    }
    
    {
        // test nonabortion T1 pops, T2 pushes on nonempty q
        TestTransaction t1(1);
        TestTransaction t2(2);
        // q has 1 element
        t1.use();
        
        q.pop();
        t2.use();
        bool aborted = false;
        try {
            q.push(3);
        } catch (Transaction::Abort e) {
            aborted = true;
        }
        assert(t1.try_commit());
        assert(aborted); // TODO: this also depends on queue implementation
    }
    {
        TransactionGuard t3;
        q.push(3);
    }

    {
        TransactionGuard t1;
        assert(q.top() == 3);
        q.pop(); // q is empty after this
    }
    
    {
        // test abortion due to empty q pops
        TestTransaction t1(1);
        TestTransaction t2(2);
        // q has 0 elements
        t1.use();
        q.pop();
        q.push(1);
        q.push(2);

        t2.use();
        q.push(3);
        q.push(4);
        q.push(5);
        q.pop();

        assert(!t1.try_commit()); // TODO: this can actually commit
        assert(t2.try_commit());
    }
    
    {
        TransactionGuard t;
        q.pop();
        q.pop();
        q.push(1);
        q.push(2);
    }
    
    {
        // test nonabortion T1 pops/fronts and pushes, T2 pushes on nonempty q
        TestTransaction t1(1);
        TestTransaction t2(2);
        
        // q has 2 elements [2, 1]
        t1.use();
        assert(q.top() == 2);
        q.push(4);
        
        // pop from non-empty q
        q.pop();
        assert(q.top() == 2);
        assert(t1.try_commit());

        t2.use();
        q.push(3);
        // order of pushes doesn't matter, commits succeed
        assert(t2.try_commit());
    }

    {
        // check if q is in order
        TransactionGuard t;
        assert(q.top() == 3);
        q.pop();
        assert(q.top() == 2);
        q.pop();
        assert(q.top() == 1);
        q.pop();
    }
    
    {
        TransactionGuard t;
        q.push(10);
        q.push(4);
        q.push(5);
    }

    {
        TestTransaction t1(1);
        q.pop();
        q.push(20);
        
        TestTransaction t2(2);
        bool aborted = false;
        try {
            q.push(12);
        } catch (Transaction::Abort e) {
            aborted = true;
        }
        
        assert(t1.try_commit());
        assert(aborted);
    }
    
    {
        TestTransaction t(1);
        q.top();
        
        TestTransaction t1(2);
        q.push(100);
        
        assert(t1.try_commit());
        assert(!t.try_commit());
    }
    
    {
        // prepare queue for next test
        TransactionGuard t;
        q.pop();
        q.pop();
        q.pop();
        q.pop();
        q.push(5);
    }
    
    {
        TestTransaction t(1);
        q.top(); // gets 5
        q.push(10);

        TestTransaction t1(2);
        q.push(7);
        assert(t1.try_commit());
        assert(!t.try_commit());
    }
    
    {
        // prepare queue for next test
        TransactionGuard t;
        q.pop();
        q.pop();
    }
    
    {
        TestTransaction t(1);
        q.pop(); // poping froming an empty queue

        TestTransaction t1(2);
        q.push(4);
        assert(t1.try_commit());
        assert(!t.try_commit());
    }
    
    {
        TestTransaction t(1);
        assert(q.top() == 4);

        TestTransaction t1(2);
        q.push(6);
        assert(t1.try_commit());

        TestTransaction t2(3);
        q.pop();

        assert(!t.try_commit());
        assert(t2.try_commit());
    }

    
    {
        TestTransaction t(1);
        assert(q.top() == 4);

        TestTransaction t1(2);
        q.push(6);
        assert(t1.try_commit());
        
        t.use();
        bool aborted = false;
        try {
            q.pop();
        } catch (Transaction::Abort e) {
            aborted = true;
        }
        assert(aborted);
    }
}

void print_time(struct timeval tv1, struct timeval tv2) {
    printf("%f\n", (tv2.tv_sec-tv1.tv_sec) + (tv2.tv_usec-tv1.tv_usec)/1000000.0);
}

int main() {
    queueTests();
    std::cout << "Done queue tests" << std::endl;
    lock = 0;
    // Run a parallel test with lots of transactions doing pushes and pops
    data_structure q;
    /*for (int i = 0; i < 10000; i++) {
        TRANSACTION {
            q.push(i);
        } RETRY(false);
    }
    for (int i = 0; i < 2000; i++) {
        TRANSACTION {
            q.pop();
        } RETRY(false);
    }*/

#if GLOBAL_SEED
    srandom(GLOBAL_SEED);
#else
    srandomdev();
#endif
    for (unsigned i = 0; i < arraysize(initial_seeds); ++i)
        initial_seeds[i] = random();

    struct timeval tv1,tv2;
    gettimeofday(&tv1, NULL);
    
    for (int i = 0; i < N_THREADS; i++) {
        txn_list.emplace_back();
    }

    pthread_t advancer;
    pthread_create(&advancer, NULL, Transaction::epoch_advancer, NULL);
    pthread_detach(advancer);

    startAndWait(&q);
    
    gettimeofday(&tv2, NULL);
    printf("Parallel time: ");
    print_time(tv1, tv2);
    
#if STO_PROFILE_COUNTERS
    Transaction::print_stats();
    {
        txp_counters tc = Transaction::txp_counters_combined();
        printf("total_n: %llu, total_r: %llu, total_w: %llu, total_searched: %llu, total_aborts: %llu (%llu aborts at commit time)\n", tc.p(txp_total_n), tc.p(txp_total_r), tc.p(txp_total_w), tc.p(txp_total_searched), tc.p(txp_total_aborts), tc.p(txp_commit_time_aborts));
    }
#endif
    
    
    std::map<uint64_t, txn_record *> combined_txn_list;
    
    for (int i = 0; i < N_THREADS; i++) {
        combined_txn_list.insert(txn_list[i].begin(), txn_list[i].end());
    }
    
    std::cout << "Single thread replay" << std::endl;
    data_structure q1;
    gettimeofday(&tv1, NULL);
    
    std::map<uint64_t, txn_record *>::iterator it = combined_txn_list.begin();
    
    for(; it != combined_txn_list.end(); it++) {
        Sto::start_transaction();
        q1.pop();
        q1.push(it->second->pushes[0]);
        //std::cout << "Pushed " << it->second->pushes[0] << std::endl;
        q1.push(it->second->pushes[1]);
        //std::cout << "Pushed " << it->second->pushes[1] << std::endl;
        //std::cout << "Pushed " << it->second->pushes[2] << std::endl;
        assert(q1.top() == it->second->tops[0]);
        //assert(q1.pop() == it->second->tops[0]);
        q1.push(it->second->pushes[2]);
        //std::cout << "Popped " << it->second->tops[0] << std::endl;
        assert(Sto::try_commit());
    }
    
    //for (int i = 0; i < N_THREADS; i++) {
    //    run(&q1, i);
    //}
    
    gettimeofday(&tv2, NULL);
    printf("Serial time: ");
    print_time(tv1, tv2);
    
    
    //data_structure q2;
    //gettimeofday(&tv1, NULL);
    
    //startAndWait(&q2, false);
    
    //gettimeofday(&tv2, NULL);
    //printf("Concurrent time: ");
    //print_time(tv1, tv2);
    
    //PriorityQueue1<int> q3;
    //gettimeofday(&tv1, NULL);
    
    //startAndWait(&q3);
    
    //gettimeofday(&tv2, NULL);
    //printf("Vector rep time: ");
    //print_time(tv1, tv2);
    
/*#if STO_PROFILE_COUNTERS
    Transaction::print_stats();
    {
        txp_counters tc = Transaction::txp_counters_combined();
        printf("total_n: %llu, total_r: %llu, total_w: %llu, total_searched: %llu, total_aborts: %llu (%llu aborts at commit time)\n", tc.p(txp_total_n), tc.p(txp_total_r), tc.p(txp_total_w), tc.p(txp_total_searched), tc.p(txp_total_aborts), tc.p(txp_commit_time_aborts));
    }
#endif*/
    
    if (true) {
    TRANSACTION {
        //q.print();
        //q1.print();
    } RETRY(false);
    //std::cout << q.size() << " " << q1.size() << std::endl;
    //assert(q.size() == q1.size());
    assert(q1.unsafe_size() == N_THREADS* NTRANS*2 + 1);
    int size = q1.unsafe_size();
    for (int i = 0; i < size; i++) {
        TRANSACTION {
            int v1 = q.top();
            int v2 = q1.top();
            //std::cout << v1 << " " << v2 << std::endl;
            if (v1 != v2)
                q1.print();
            assert(v1 == v2);
            assert(q.pop() == v1);
            assert(q1.pop() == v2);
        } RETRY(false);
    }
        TRANSACTION {
            q.print();
            assert(q.top() == -1);
            //q1.print();
        } RETRY(false);
    }

	return 0;
}


<|start_filename|>Boosting_common.hh<|end_filename|>
#pragma once

// this is common glue used by both TL2 bindings and "standalone" bindings 
// (but not by the STO bindings)

#include <assert.h>

#include "config.h"
#include "compiler.hh"

#include "Boosting_fastset.hh"
#include "Boosting_locks.hh"

#if !defined(BOOSTING) || defined(STO)
#error "Should not be used with BoostingSTO"
#endif

#define STO_NO_STM

// these 3 functions are what data structures use
#define ADD_UNDO ON_ABORT
#define TRANS_WRITE_LOCK transWriteLock
#define TRANS_READ_LOCK transReadLock

struct boosting_threadinfo {
  FastSet<SpinLock*> lockset;
  FastSet<RWLock*> rwlockset;
};

#define BOOSTING_MAX_THREADS 16
extern boosting_threadinfo boosting_threads[BOOSTING_MAX_THREADS];
extern __thread int boosting_threadid;

static inline boosting_threadinfo& _thread() {
  return boosting_threads[boosting_threadid];
}


void boosting_txStartHook();

void boosting_setThreadID(int threadid);

void boosting_releaseLocksCallback(void*, void*, void*);

void transReadLock(RWLock *lock);
void transWriteLock(RWLock *lock);


<|start_filename|>Boosting_sto.hh<|end_filename|>
#pragma once

#if defined(BOOSTING) && defined(STO)

#include "Transaction.hh"
#include "TransUndoable.hh"
#include "TransPessimisticLocking.hh"

extern TransPessimisticLocking __pessimistLocking;

#define ADD_UNDO(callback, self, context1, context2) ({ assert(self == this); this->add_undo(callback, context1, context2); })
#define TRANS_READ_LOCK(lock) __pessimistLocking.transReadLock(lock)
#define TRANS_WRITE_LOCK(lock) __pessimistLocking.transWriteLock(lock)

#endif


<|start_filename|>TIntRange.hh<|end_filename|>
#pragma once
#include <limits>
#include "compiler.hh"
#include "Transaction.hh"

template <typename T>
struct TIntRange {
    T first;
    T second;

    static TIntRange<T> unconstrained() {
        return TIntRange<T>{std::numeric_limits<T>::min(), std::numeric_limits<T>::max()};
    }
    void observe(T value) {
        if (first <= value && value <= second)
            first = second = value;
        else
            Sto::abort();
    }
    void observe_test_eq(T value, T comparison) {
        if (value == comparison) {
            first = std::max(first, value);
            second = std::min(second, value);
        } else if (value < comparison)
            second = std::min(second, comparison - 1);
        else
            first = std::max(first, comparison + 1);
        if (first > second)
            Sto::abort();
    }
    void observe_lt(T value, bool was_lt = true) {
        if (was_lt)
            second = std::min(second, value - 1);
        else
            first = std::max(first, value);
        if (first > second)
            Sto::abort();
    }
    void observe_le(T value, bool was_le = true) {
        if (was_le)
            second = std::min(second, value);
        else
            first = std::max(first, value + 1);
        if (first > second)
            Sto::abort();
    }
    void observe_gt(T value, bool was_gt = true) {
        observe_le(value, !was_gt);
    }
    void observe_ge(T value, bool was_ge = true) {
        observe_lt(value, !was_ge);
    }
    bool verify(T value) const {
        return first <= value && value <= second;
    }

    friend std::ostream& operator<<(std::ostream& w, const TIntRange<T>& r) {
        return w << '[' << r.first << ',' << r.second << ']';
    }
};

template <typename T, bool Signed = std::is_signed<T>::value>
class TIntRangeProxy;

template <typename T>
class TIntRangeProxy<T, false> {
public:
    typedef T value_type;
    typedef typename mass::make_signed<T>::type difference_type;

    TIntRangeProxy(TIntRange<T>* r, value_type original, difference_type delta)
        : r_(r), original_(original), delta_(delta) {
    }

    operator value_type() const {
        // XXX this assumes that TransItem doesn't change location
        if (r_)
            r_->observe(original_);
        return original_ + delta_;
    }

    bool operator==(value_type x) const {
        x -= delta_;
        if (r_)
            r_->observe_test_eq(original_, x);
        return original_ == x;
    }
    bool operator!=(value_type x) const {
        return !(*this == x);
    }
    bool operator<(value_type x) const {
        x -= delta_;
        if (r_)
            r_->observe_lt(x, original_ < x);
        return original_ < x;
    }
    bool operator<=(value_type x) const {
        x -= delta_;
        if (r_)
            r_->observe_le(x, original_ <= x);
        return original_ <= x;
    }
    bool operator>=(value_type x) const {
        return !(*this < x);
    }
    bool operator>(value_type x) const {
        return !(*this <= x);
    }

    // difference_type versions just for friendliness
    bool operator==(difference_type x) const {
        return *this == value_type(x);
    }
    bool operator!=(difference_type x) const {
        return *this != value_type(x);
    }
    bool operator<(difference_type x) const {
        return *this < value_type(x);
    }
    bool operator<=(difference_type x) const {
        return *this <= value_type(x);
    }
    bool operator>=(difference_type x) const {
        return *this >= value_type(x);
    }
    bool operator>(difference_type x) const {
        return *this > value_type(x);
    }

private:
    TIntRange<T>* r_;
    value_type original_;
    difference_type delta_;
};

template <typename T>
class TIntRangeProxy<T, true> {
public:
    typedef T value_type;

    TIntRangeProxy(TIntRange<T>* r, value_type original, value_type delta)
        : r_(r), original_(original), delta_(delta) {
    }

    operator value_type() const {
        // XXX this assumes that TransItem doesn't change location
        if (r_)
            r_->observe(original_);
        return original_ + delta_;
    }

    bool operator==(value_type x) const {
        x -= delta_;
        if (r_)
            r_->observe_test_eq(original_, x);
        return original_ == x;
    }
    bool operator!=(value_type x) const {
        return !(*this == x);
    }
    bool operator<(value_type x) const {
        x -= delta_;
        if (r_)
            r_->observe_lt(x, original_ < x);
        return original_ < x;
    }
    bool operator<=(value_type x) const {
        x -= delta_;
        if (r_)
            r_->observe_le(x, original_ <= x);
        return original_ <= x;
    }
    bool operator>=(value_type x) const {
        return !(*this < x);
    }
    bool operator>(value_type x) const {
        return !(*this <= x);
    }

private:
    TIntRange<T>* r_;
    value_type original_;
    value_type delta_;
};

template <typename T>
class TIntRangeDifferenceProxy {
public:
    typedef T size_type;
    typedef typename mass::make_signed<T>::type difference_type;

    TIntRangeDifferenceProxy(TIntRange<T>* r, size_type original, difference_type delta)
        : r_(r), original_(original), delta_(delta) {
    }

    operator difference_type() const {
        // XXX this assumes that TransItem doesn't change location
        if (r_)
            r_->observe(original_);
        return original_ + delta_;
    }

    bool operator==(difference_type x) const {
        x -= delta_;
        if (r_ && x >= 0)
            r_->observe_test_eq(original_, x);
        return x >= 0 && original_ == size_type(x);
    }
    bool operator!=(difference_type x) const {
        return !(*this == x);
    }
    bool operator<(difference_type x) const {
        x -= delta_;
        if (r_ && x >= 0)
            r_->observe_lt(x, original_ < size_type(x));
        return x >= 0 && original_ < size_type(x);
    }
    bool operator<=(difference_type x) const {
        x -= delta_;
        if (r_ && x >= 0)
            r_->observe_le(x, original_ <= size_type(x));
        return x >= 0 && original_ <= size_type(x);
    }
    bool operator>=(difference_type x) const {
        return !(*this < x);
    }
    bool operator>(difference_type x) const {
        return !(*this <= x);
    }

private:
    TIntRange<T>* r_;
    size_type original_;
    difference_type delta_;
};

template <typename T, bool Signed>
bool operator==(T a, const TIntRangeProxy<T, Signed>& b) {
    return b == a;
}
template <typename T, bool Signed>
bool operator!=(T a, const TIntRangeProxy<T, Signed>& b) {
    return b != a;
}
template <typename T, bool Signed>
bool operator<(T a, const TIntRangeProxy<T, Signed>& b) {
    return b > a;
}
template <typename T, bool Signed>
bool operator<=(T a, const TIntRangeProxy<T, Signed>& b) {
    return b >= a;
}
template <typename T, bool Signed>
bool operator>=(T a, const TIntRangeProxy<T, Signed>& b) {
    return b <= a;
}
template <typename T, bool Signed>
bool operator>(T a, const TIntRangeProxy<T, Signed>& b) {
    return b < a;
}

template <typename T>
bool operator==(typename TIntRangeDifferenceProxy<T>::difference_type a,
                const TIntRangeDifferenceProxy<T>& b) {
    return b == a;
}
template <typename T>
bool operator!=(typename TIntRangeDifferenceProxy<T>::difference_type a,
                const TIntRangeDifferenceProxy<T>& b) {
    return b != a;
}
template <typename T>
bool operator<(typename TIntRangeDifferenceProxy<T>::difference_type a,
               const TIntRangeDifferenceProxy<T>& b) {
    return b > a;
}
template <typename T>
bool operator<=(typename TIntRangeDifferenceProxy<T>::difference_type a,
                const TIntRangeDifferenceProxy<T>& b) {
    return b >= a;
}
template <typename T>
bool operator>=(typename TIntRangeDifferenceProxy<T>::difference_type a,
                const TIntRangeDifferenceProxy<T>& b) {
    return b <= a;
}
template <typename T>
bool operator>(typename TIntRangeDifferenceProxy<T>::difference_type a,
               const TIntRangeDifferenceProxy<T>& b) {
    return b < a;
}


<|start_filename|>List.hh<|end_filename|>
#pragma once

#include "TaggedLow.hh"
#include "Interface.hh"

#ifndef STO_NO_STM
#include "Transaction.hh"
#endif

template<typename T>
class DefaultCompare {
public:
  int operator()(const T& t1, const T& t2) {
    if (t1 < t2)
      return -1;
    return t2 < t1 ? 1 : 0;
  }
};

template <typename T, bool Duplicates = false, typename Compare = DefaultCompare<T>, bool Sorted = true, bool Opacity = true> class ListIterator;

template <typename T, bool Duplicates = false, typename Compare = DefaultCompare<T>, bool Sorted = true, bool Opacity = true>
class List 
#ifndef STO_NO_STM
: public TObject
#endif
{
  friend class ListIterator<T, Duplicates, Compare, Sorted, Opacity>;
  typedef ListIterator<T, Duplicates, Compare, Sorted, Opacity> iterator;
public:
  List(Compare comp = Compare()) : head_(NULL), listsize_(0), listlock_(0), listversion_(0), comp_(comp) {
  }

private:
  // not an actual tid but we use that type for the spinlock implementations
  typedef TransactionTid::type list_lock_type;
  typedef TVersion node_version_type;
  typedef TVersion list_version_type;

public:
    static constexpr TransactionTid::type invalid_bit = TransactionTid::user_bit;

    static constexpr TransItem::flags_type insert_bit = TransItem::user0_bit;
    static constexpr TransItem::flags_type delete_bit = TransItem::user0_bit<<1;
    static constexpr TransItem::flags_type doupdate_bit = TransItem::user0_bit<<2;

  struct list_node {
    list_node(const T& val, list_node *next, bool invalid)
      : val(val), next(next), vers(Sto::initialized_tid() | (invalid ? (invalid_bit | TransactionTid::lock_bit | TThread::id()) : 0)) {
    }

    // used for delete commit
    void mark_invalid(bool Txnal) {
      assert(!Txnal || vers.is_locked_here());
      auto new_version = vers | invalid_bit;
      fence();
      vers = new_version;
    }

    node_version_type version() {
      return vers;
    }

    void set_version(node_version_type new_v) {
      vers.set_version(new_v);
    }

    void set_version_unlock(node_version_type new_v) {
      vers.set_version_unlock(new_v);
    }

    bool try_lock() {
      return vers.try_lock();
    }
    void unlock() {
      vers.unlock();
    }

    bool is_valid() {
      return !(vers.value() & invalid_bit);
    }

    T val;
    list_node *next;
    node_version_type vers;
  };

  static constexpr list_node* list_key = nullptr;
  // Can't have non-NULL constexpr pointer
  static inline list_node* size_key() { return (list_node*)1; }

  bool find(const T& elem, T& val) {
    auto *ret = _find(elem);
    if (ret) {
      val = ret->val;
    }
    return !!ret;
  }

  T* find(const T& elem) {
    auto *ret = _find(elem);
    if (ret) {
      return &ret->val;
    }
    return NULL;
  }

  list_node* _find(const T& elem) {
    list_node *cur = head_;
    while (cur != NULL) {
      int c = comp_(cur->val, elem);
      if (c == 0) {
        return cur;
      }
      if (Sorted && c > 0) {
        return NULL;
      }
      cur = cur->next;
    }
    return NULL;
  }

  template <bool Txnal = false>
  list_node* _insert(const T& elem, bool *inserted = NULL) {
    if (inserted)
      *inserted = true;
    lock(listlock_);
    if (!Sorted && !Duplicates) {
      list_node *new_head = new list_node(elem, head_, Txnal);
      head_ = new_head;
      unlock(listlock_);
      return new_head;
    }

    list_node *prev = NULL;
    list_node *cur = head_;
    while (cur != NULL) {
      int c = comp_(cur->val, elem);
      if (!Duplicates && c == 0) {
        unlock(listlock_);
        if (inserted)
          *inserted = false;
        return cur;
      } else if (Sorted && c >= 0) {
        break;
      }
      prev = cur;
      cur = cur->next;
    }
    auto ret = new list_node(elem, cur, Txnal);
    if (prev) {
        prev->next = ret;
    } else {
        head_ = ret;
    }
    if (!Txnal)
      listsize_++;
    unlock(listlock_);
    return ret;
  }

  bool insert(const T& elem) {
    bool inserted;
    _insert<false>(elem, &inserted);
    return inserted;
  }

  template <bool Txnal>
  bool remove(const T& elem, bool locked = false) {
    return _remove<Txnal>([&] (list_node *n2) { return comp_(n2->val, elem) == 0; }, locked);
  }

  template <bool Txnal>
  bool remove(list_node *n, bool locked = false) {
    // TODO: doing this remove means we don't have to value compare, but we also
    // have to go through the whole list (possibly). Unclear which is better.
    return _remove<Txnal>([n] (list_node *n2) { return n == n2; }, locked);
  }

  template <bool Txnal, typename FoundFunc>
  bool _remove(FoundFunc found_f, bool locked = false) {
    if (!locked)
      lock(listlock_);
    list_node *prev = NULL;
    list_node *cur = head_;
    while (cur != NULL) {
      if (found_f(cur)) {
        cur->mark_invalid(Txnal);
        if (prev) {
            prev->next = cur->next;
        } else {
            head_ = cur->next;
        }
        if (Txnal) {
          Transaction::rcu_delete(cur);
        } else {
          delete cur;
        }
        if (!Txnal)
          listsize_--;
        if (!locked)
          unlock(listlock_);
        return true;
      }
      prev = cur;
      cur = cur->next;
    }
    if (!locked)
      unlock(listlock_);
    return false;
  }

#ifndef STO_NO_STM
  T* transFind(const T& elem) {
    auto listv = listversion_;
    fence();
    auto *n = _find(elem);
    if (n) {
      auto version = n->version();
      fence();
      auto item = t_item(n);
      if (!validityCheck(n, item)) {
        Sto::abort();
        return NULL;
      }
      if (has_delete(item)) {
        return NULL;
      }
      item.observe(version);
    } else {
      // log list v#
      verify_list(listv);
      return NULL;
    }
    return &n->val;
  }

  bool transInsert(const T& elem) {
    bool inserted;
    auto *node = _insert<true>(elem, &inserted);
    auto item = t_item(node);
    if (!inserted) {
      auto version = node->version();
      fence();
      if (!validityCheck(node, item)) {
        Sto::abort();
        return false;
      }
      // intertransactional insert-then-insert = failed insert
      if (has_insert(item)) {
        return false;
      }
      // delete-then-insert, then insert -- failed insert
      if (has_doupdate(item)) {
        return false;
      }
      // delete-then-insert... (should really become an update...)
      if (has_delete(item)) {
	// delete already should have observed a version
        item.clear_write().add_write(elem);
        item.assign_flags(doupdate_bit);
        add_trans_size_offs(1);
        return true;
      }
      // "normal" failed insert
      // need to make sure it's still there at commit time
      item.observe(version);
      return false;
    }
    add_trans_size_offs(1);
    // we lock the list for inserts
    add_lock_list_item();
    item.add_write(0);
    item.add_flags(insert_bit);
    return true;
  }

  bool transDelete(const T& elem) {
    auto listv = listversion_;
    fence();
    auto *n = _find(elem);
    if (n) {
      auto version = n->version();
      fence();
      auto item = t_item(n);
      if (!validityCheck(n, item)) {
        Sto::abort();
        return false;
      }
      if (has_delete(item)) {
        // we're deleting our delete
        return false;
      }
      // delete-then-insert, then delete
      if (has_doupdate(item)) {
        // back to deleting
        item.assign_flags(delete_bit);
        add_trans_size_offs(-1);
        return true;
      }
      // insert-then-delete becomes absent-get
      if (has_insert(item)) {
        remove<true>(n);
        item.remove_read().remove_write().clear_flags(insert_bit);
        add_trans_size_offs(-1);
        // TODO: should have a count on add_lock_list_item so we can cancel that here
        // still need to make sure no one else inserts something
        verify_list(listv);
        return true;
      }
      item.assign_flags(delete_bit);
      // mark as a write
      item.add_write(0);
      // we also need to check that it's still valid at commit time (not
      // bothering with valid_check_only_bit optimization right now)
      item.observe(version);
      add_lock_list_item();
      add_trans_size_offs(-1);
      return true;
    } else {
      verify_list(listv);
      return false;
    }
  }

  inline list_version_type opacity_check() {
    // When we check for opacity, we need to compare the latest listversion and not
    // the one at the beginning of the operation.
    assert(Opacity);
    auto listv = listversion_;
    fence();
    if (listv.is_locked_elsewhere()) {
      Sto::abort();
    }
    Sto::check_opacity(listv.value());
    return listv;
  }

  struct ListIter;

  ListIter transIter() {
    auto listv = listversion_;
    fence();
    auto head = head_;
    fence();
    if (listv != listversion_)
      Sto::abort();
    verify_list(listv);
    return ListIter(this, head, true);
  }

  size_t size() {
    auto listv = listversion_;
    fence();
    auto size = listsize_;
    fence();
    // doesn't seem worth putting much effort in here--if we got different versions just abort.
    if (listv != listversion_)
      Sto::abort();
    verify_list(listv);
    return size + trans_size_offs();
  }

  size_t nontrans_size() const {
    return listsize_;
  }

#endif /* !STO_NO_STM */
    
  iterator begin() { return iterator(this, head_); }
  iterator end() { return iterator(this, NULL); }

  struct ListIter {
    ListIter() : us(NULL), cur(NULL) {}

    bool valid() const {
      return us != NULL;
    }

    bool hasNext() const {
      return !!cur;
    }

    void reset() {
      cur = us->head_;
    }

    T* next() {
      auto ret = cur ? &cur->val : NULL;
      if (cur)
        cur = cur->next;
      return ret;
    }

    bool transHasNext() const {
      return !!cur;
    }

    void transReset() {
      cur = us->head_;
      ensureValid();
    }

    T* transNext() {
      auto ret = cur ? &cur->val : NULL;
      if (cur)
        cur = cur->next;
      ensureValid();
      return ret;
    }

    T* transNthNext(int n) {
      T* ret = NULL;
      while (n > 0 && transHasNext()) {
        ret = transNext();
        n--;
      }
      if (n == 0)
        return ret;
      return NULL;
    }

private:
    ListIter(List *us, list_node *cur, bool trans) : us(us), cur(cur) {
      if (trans)
        ensureValid();
    }

    void ensureValid() {
#ifndef STO_NO_STM
      while (cur) {
        // need to check if this item already exists
	// XXX: we could probably use threadids in inserted items so this
        // doesn't have to search the write set. But I'm not sure there's
        // a way to avoid checking for if we deleted the item?
        auto item = Sto::check_item(us, cur);
        if (!cur->is_valid()) {
          if (!item || !us->has_insert(*item)) {
            Sto::abort();
            // TODO: do we continue in this situation or abort?
            cur = cur->next;
            continue;
          }
        }
        if (item && us->has_delete(*item)) {
          cur = cur->next;
          continue;
        }
        break;
      }
      fence();
      if (Opacity)
        us->opacity_check();
#endif
    }

    friend class List;
    List *us;
    list_node *cur;
  };

  ListIter iter() {
    return ListIter(this, head_, false);
  }

  size_t unsafe_size() const {
      return listsize_;
  }

  void clear() {
      while (auto item = head_)
        remove<false>(head_, true);
  }

  void verify_list(list_version_type readv) {
    t_item(list_key).observe(readv);
    acquire_fence();
  }


  void lock(list_lock_type& v) {
    TransactionTid::lock(v);
  }

  void unlock(list_lock_type& v) {
    TransactionTid::unlock(v);
  }

  bool is_locked(list_lock_type& v) {
    return TransactionTid::is_locked(v);
  }

#ifndef STO_NO_STM
    bool lock(TransItem& item, Transaction&) override {
      list_node *n = item.key<list_node*>();
      if (n == list_key) {
        return listversion_.try_lock();
      } else if (!has_insert(item)) {
        // we only lock non-inserts (removes, updates) so as to make our 
	// life harder (also it's not necessary for inserts).
        return n->try_lock();
      }
      return true;
    }

  bool check(TransItem& item, Transaction&) override {
    if (item.key<list_node*>() == list_key) {
      auto lv = listversion_;
      return lv.check_version(item.template read_value<list_version_type>());
    }
    auto n = item.key<list_node*>();
    if (!n->is_valid()) {
      return has_insert(item);
    }
    return n->version().check_version(item.template read_value<node_version_type>());
  }

  void install(TransItem& item, Transaction& t) override {
    // TODO: this item tracks the total size differential so we could just do 
    // a single fetch and add of the size delta here.
    if (item.key<list_node*>() == list_key)
      return;
    list_node *n = item.key<list_node*>();
    if (has_delete(item)) {
      remove<true>(n, true);
      listsize_--;
      // not super ideal that we have to change version
      // but we need to invalidate transSize() calls
      if (Opacity) {
        listversion_.set_version(t.commit_tid());
      } else {
        listversion_.inc_nonopaque_version();
      }
    } else if (has_doupdate(item)) {
      n->set_version(t.commit_tid());
      n->val = item.template write_value<T>();
    } else {
      // insert
      // clears the invalid bit too
      n->set_version_unlock(t.commit_tid());
      listsize_++;
      if (Opacity) {
        listversion_.set_version(t.commit_tid());
      } else {
        listversion_.inc_nonopaque_version();
      }
    }
  }

  void unlock(TransItem& item) override {
    auto n = item.key<list_node*>();
    if (n == list_key) {
      listversion_.unlock();
    } else if (!has_insert(item)) {
      n->unlock();
    }
  }

  void cleanup(TransItem& item, bool committed) override {
      if (!committed && (item.flags() & insert_bit)) {
          list_node *n = item.key<list_node*>();
          remove<true>(n);
      }
  }

  TransProxy t_item(list_node* node) {
    // can switch this to fresh_item to not read our writes
    return Sto::item(this, node);
  }

  bool has_insert(const TransItem& item) {
      return item.has_write() && !has_delete(item) && !has_doupdate(item);
  }

  bool has_delete(const TransItem& item) {
      return item.flags() & delete_bit;
  }

  bool has_doupdate(const TransItem& item) {
      return item.flags() & doupdate_bit;
  }

  void add_lock_list_item() {
    t_item(list_key).add_write(0);
  }

  void add_trans_size_offs(int size_offs) {
    // TODO: it'd be simpler and maybe even faster if this was just the 
    // write_value of our list_key item (and we renamed list_key to size_key)
    auto item = t_item(size_key());
    item.template set_stash<int>(item.template stash_value<int>(0) + size_offs);
  }

  int trans_size_offs() {
    return t_item(size_key()).template stash_value<int>(0);
  }
#endif /* !STO_NO_STM */

  bool validityCheck(list_node *n, TransItem& item) {
      return n->is_valid() || (item.flags() & insert_bit);
  }

  list_node *head_;
  long listsize_;
  list_lock_type listlock_;
  list_version_type listversion_;
  Compare comp_;
};

    
template <typename T, bool Duplicates, typename Compare, bool Sorted, bool Opacity>
class ListIterator : public std::iterator<std::forward_iterator_tag, T> {
    typedef ListIterator<T, Duplicates, Compare, Sorted, Opacity> iterator;
    typedef List<T, Duplicates, Compare, Sorted, Opacity> list_type;
    typedef typename list_type::list_node list_node;
public:
    ListIterator(list_type * list, list_node* ptr) : myList(list), myPtr(ptr) {
        myList->list_verify(myList->listversion_);
    }
    ListIterator(const ListIterator& itr) : myList(itr.myList), myPtr(itr.myPtr) {}
    
    ListIterator& operator= (const ListIterator& v) {
        myList = v.myList;
        myPtr = v.myPtr;
        return *this;
    }
    
    bool operator==(iterator other) const {
        return (myList == other.myList) && (myPtr == other.myPtr);
    }
    
    bool operator!=(iterator other) const {
        return !(operator==(other));
    }
    
    T& operator*() {
        return myPtr->val; // Just returing the pointer to the value because this
                           // list does not transactionally track updates to list values.
    }
    
    void increment_ptr() {
        if (myPtr)
            myPtr = myPtr->next;
        while (myPtr) {
            // need to check if this item already exists
            auto item = Sto::check_item(myList, myPtr);
            if (!myPtr->is_valid()) {
                if (!item || !myList->has_insert(*item)) {
                    Sto::abort();
                    // TODO: do we continue in this situation or abort?
                    myPtr = myPtr->next;
                    continue;
                }
            }
            if (item && myList->has_delete(*item)) {
                myPtr = myPtr->next;
                continue;
            }
            break;
        }
    }
    
    /* This is the prefix case */
    iterator& operator++() {
        increment_ptr();
        return *this;
    }
    
    /* This is the postfix case */
    iterator operator++(int) {
        iterator clone(*this);
        increment_ptr();
        return clone;
    }
    
private:
    list_type * myList;
    list_node * myPtr;
};




<|start_filename|>Boosting_map.hh<|end_filename|>
#pragma once

#include "Boosting_tl2.hh"
#include "Boosting_sto.hh"
#include "Boosting_lockkey.hh"

#include "Hashtable.hh"
#include "RBTree.hh"

#define VOIDP(x) ((void*)(uintptr_t)(x))

template <typename K, typename V, unsigned Init_size = 129, typename Hash = std::hash<K>, typename Pred = std::equal_to<K>, 
          typename MapType = Hashtable<K, V, true, Init_size, V, Hash, Pred>>
class TransMap 
#if defined(BOOSTING) && defined(STO)
  : public TransUndoable
#endif
{
public:
  typedef MapType map_type;
private:
  MapType map_;
  LockKey<K, Init_size, Hash, Pred> lockKey_;

public:
  typedef K Key;
  typedef V Value;

  TransMap() : map_(), lockKey_(Init_size, Hash(), Pred()) {}

  TransMap(MapType&& map, unsigned size = Init_size, Hash h = Hash(), Pred p = Pred()) : map_(std::move(map)), lockKey_(size, h, p) {}

  bool transGet(const Key& k, Value& retval) {
    lockKey_.readLock(k);
    return map_.nontrans_find(k, retval);
  }

  bool remove(const Key& k) {
    return map_.nontrans_remove(k);
  }
  bool insert(const Key& k, const Value& val) {
    return map_.nontrans_insert(k, val);
  }
  bool read(const Key& k, Value& val) {
    return map_.nontrans_find(k, val);
  }

  static void _undoDelete(void *self, void *c1, void *c2) {
    static_assert(sizeof(Key) <= 8, "must be trivial and word sized");
    static_assert(sizeof(Value) <= 8, "must be trivial and word sized");
    Key key = (Key)(uintptr_t)c1;
    Value val = (Value)(uintptr_t)c2;
    bool inserted = ((TransMap*)self)->map_.nontrans_insert(key, val);
    assert(inserted);
    // XXX: Assume we're always running in STAMP and thus key and value are always POD
    //    delete key;
    //    delete val;
  }
  
  static void _undoInsert(void *self, void *c1, void *c2) {
    Key key = (Key)(uintptr_t)c1;
    bool success = ((TransMap*)self)->map_.nontrans_remove(key);
    assert(success);
    //    delete key;
  }

  bool transDelete(const Key& k) {
    lockKey_.writeLock(k);
    Value oldval;
    bool success = map_.nontrans_remove(k, oldval);
    if (success) {
      ADD_UNDO(TransMap::_undoDelete, this, VOIDP(k), VOIDP(oldval));
    }

    return success;
  }

  bool transInsert(const Key& k, const Value& val) {
    lockKey_.writeLock(k);
    bool success = map_.nontrans_insert(k, val);
    
    if (success) {
      ADD_UNDO(TransMap::_undoInsert, this, VOIDP(k), NULL);
    }

    return success;
  }

// for concurrent.cc
// probably won't compile with RBTree :(

// barf
#ifdef USE_HASHTABLE

  static void _undoSet(void *self, void *c1, void *c2) {
    Key key = (Key)(uintptr_t)c1;
    Value value = (Value)(uintptr_t)c2;
    bool exists = ((TransMap*)self)->map_.put(key, value);
    assert(exists);
    //    delete key;
  }

  void transPut(const Key& k, const Value& val) {
    lockKey_.writeLock(k);
    Value oldval;
    bool exists = map_.put_getold(k, val, oldval);
    if (exists) {
      ADD_UNDO(TransMap::_undoSet, this, VOIDP(k), VOIDP(oldval));
    } else {
      ADD_UNDO(TransMap::_undoInsert, this, VOIDP(k), NULL);
    }
  }
  bool transUpdate(const Key& k, const Value& val) {
    lockKey_.writeLock(k);
    Value oldval;
    bool there = map_.nontrans_find(k, oldval);
    bool exists = map_.template put<false/*Insert*/, true/*Set*/>(k, val);
    assert(there == exists);
    if (there) {
      ADD_UNDO(TransMap::_undoSet, this, VOIDP(k), VOIDP(oldval));
    }
    return there;
  }
  Value unsafe_get(const Key& k) {
    return map_.unsafe_get(k);
  }
#endif
};


<|start_filename|>IntStr.hh<|end_filename|>
#pragma once
#include "str.hh"

struct IntStr {
    char s_[16];
    lcdf::Str str_;
    IntStr(int i) {
        int n = snprintf(s_, sizeof(s_), "%d", i);
        str_.assign(s_, n);
    }
    lcdf::Str& str() {
        return str_;
    }
    operator lcdf::Str&() {
        return str_;
    }
};


<|start_filename|>RBTreeInternal.hh<|end_filename|>
#pragma once

#include <utility>
#include <tuple>
#include <vector>
#include <iomanip>
#include <iostream>
#include "Interface.hh"

#ifndef rbaccount
# define rbaccount(x)
#endif

template <typename T>
class rbnodeptr {
  public:
    // what is unspecified_bool_type doing? 
    typedef bool (rbnodeptr<T>::*unspecified_bool_type)() const;

    rbnodeptr() = default;
    inline rbnodeptr(T* x, bool color);
    explicit inline rbnodeptr(uintptr_t ivalue);

    inline operator unspecified_bool_type() const;
    inline bool operator!() const;
    inline uintptr_t ivalue() const;

    inline T* node() const;
    inline rbnodeptr<T>& child(bool isright) const;
    inline bool children_same_color() const;
    inline bool find_child(T* node) const;
    inline rbnodeptr<T>& load_color();
    inline rbnodeptr<T> set_child(bool isright, rbnodeptr<T> x, T*& root) const;
    inline T*& parent() const;
    inline rbnodeptr<T> black_parent() const;

    inline bool red() const;
    inline rbnodeptr<T> change_color(bool color) const;
    inline rbnodeptr<T> reverse_color() const;

    inline rbnodeptr<T> rotate(bool isright) const;
    inline rbnodeptr<T> flip() const;

    size_t size() const;
    template <typename C>
    void check(T* parent, int this_black_height, int& black_height,
               T* root, T* begin, T* end, C& compare) const;
    void output(std::ostream& s, int indent, T* highlight) const;

  private:
    uintptr_t x_;
};

template <typename T>
class rblinks {
  public:
    T* p_;
    rbnodeptr<T> c_[2];
}; 

namespace rbpriv {
template <typename Compare>
struct rbcompare : private Compare {
    inline rbcompare(const Compare &compare);
    template <typename T>
    inline int node_compare(const T& a, const T& b) const;
    template <typename A, typename B>
    inline int compare(const A &a, const B &b) const;
    inline Compare& get_compare() const;
};

template <typename T>
struct default_comparator {
    inline int operator()(const T &a, const T &b) const {
    return a < b ? -1 : (b < a ? 1 : 0);
    }
};

template <typename T>
inline int default_compare(const T &a, const T &b) {
    return default_comparator<T>()(a, b);
}

template <typename T, typename Compare>
struct rbrep : public rbcompare<Compare> {
    T* root_;
    T* limit_[2];
    typedef rbcompare<Compare> rbcompare_type;
    inline rbrep(const Compare &compare);
};

template <typename C, typename Ret> class rbcomparator;

template <typename C>
class rbcomparator<C, bool> {
  public:
    inline rbcomparator(C comp)
        : comp_(comp) {
    }
    template <typename A, typename B>
    inline bool less(const A& a, const B& b) {
        return comp_(a, b);
    }
    template <typename A, typename B>
    inline bool greater(const A& a, const B& b) {
        return comp_(b, a);
    }
    template <typename A, typename B>
    inline int compare(const A& a, const B& b) {
        return comp_(a, b) ? -1 : comp_(b, a);
    }
  private:
    C comp_;
};

template <typename C>
class rbcomparator<C, int> {
  public:
    inline rbcomparator(C comp)
        : comp_(comp) {
    }
    template <typename A, typename B>
    inline bool less(const A& a, const B& b) {
        return comp_(a, b) < 0;
    }
    template <typename A, typename B>
    inline bool greater(const A& a, const B& b) {
        return comp_(a, b) > 0;
    }
    template <typename A, typename B>
    inline int compare(const A& a, const B& b) {
        return comp_(a, b);
    }
  private:
    C comp_;
};

template <typename K, typename T, typename C>
inline auto make_compare(C comp) -> rbcomparator<C, decltype(comp(*(K*)nullptr, *(T*)nullptr))> {
    return rbcomparator<C, decltype(comp(*(K*)nullptr, *(T*)nullptr))>(comp);
}

} // namespace rbpriv

template <typename T>
class rbalgorithms {
  public:
    static inline T* next_node(T* n);
    static inline T* prev_node(T* n);
    static inline T* prev_node(T* n, T* last);
    static inline T* step_node(T* n, bool forward);
    static inline T* edge_node(T* n, bool forward);
};


template <typename T, typename Compare = rbpriv::default_comparator<T>>
class rbtree {
  public:
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef Compare value_compare;
    typedef T node_type;

    typedef TVersion Version;
    typedef std::tuple<T*, Version> node_info_type;
    typedef std::pair<node_info_type, node_info_type> boundaries_type;

    inline rbtree(const value_compare &compare = value_compare());
    ~rbtree();

    inline node_type *root();

    // lookup
    inline bool empty() const;
    inline size_t size() const;

    // modifiers
    inline rbnodeptr<T> insert(reference n);
    inline T* erase(reference x);
  
    template <typename TT, typename CC>
    friend std::ostream &operator<<(std::ostream &s, const rbtree<TT, CC> &tree);
    int check() const;

  private:
    rbpriv::rbrep<T, Compare> r_;
    // moved from RBTree.hh
    Version treeversion_;

    template <typename K, typename Comp>
    inline std::tuple<T*, Version, bool, boundaries_type> find_any(const K& key, Comp comp) const;

    template <typename K, typename Comp>
    inline std::tuple<T*, Version, bool, boundaries_type, node_info_type> find_insert(K& key, Comp comp);

    template <typename K, typename Comp>
    inline std::tuple<rbnodeptr<T>, bool> find_or_parent(const K& key, Comp comp) const;

    void insert_commit(T* x, rbnodeptr<T> p, bool side);
    T* delete_node(T* victim, T* successor_hint);
    void delete_node_fixup(rbnodeptr<T> p, bool side);

    template<typename K, typename V, bool GlobalSize> friend class RBTree;
};

template <typename T>
inline rbnodeptr<T>::rbnodeptr(T* x, bool color)
    : x_(reinterpret_cast<uintptr_t>(x) | color) {
}

template <typename T>
inline rbnodeptr<T>::rbnodeptr(uintptr_t x)
    : x_(x) {
}

template <typename T>
inline rbnodeptr<T>::operator unspecified_bool_type() const {
    return x_ != 0 ? &rbnodeptr<T>::operator! : 0;
}

template <typename T>
inline bool rbnodeptr<T>::operator!() const {
    return !x_;
}

template <typename T>
inline uintptr_t rbnodeptr<T>::ivalue() const {
    return x_;
}

template <typename T>
inline T* rbnodeptr<T>::node() const {
    return reinterpret_cast<T*>(x_ & ~uintptr_t(1));
}

template <typename T>
inline rbnodeptr<T>& rbnodeptr<T>::child(bool isright) const {
    return node()->rblinks_.c_[isright];
}

template <typename T>
inline bool rbnodeptr<T>::children_same_color() const {
    return ((node()->rblinks_.c_[0].x_ ^ node()->rblinks_.c_[1].x_) & 1) == 0;
}

template <typename T>
inline bool rbnodeptr<T>::find_child(T* n) const {
    return x_ && node()->rblinks_.c_[1].node() == n;
}

template <typename T>
inline rbnodeptr<T>& rbnodeptr<T>::load_color() {
    assert(!red());
    rbnodeptr<T> p;
    if (x_ && (p = black_parent()) && p.child(p.find_child(node())).red())
        x_ |= 1;
    return *this;
}

template <typename T>
inline rbnodeptr<T> rbnodeptr<T>::set_child(bool isright, rbnodeptr<T> x, T*& root) const {
    if (x_)
    child(isright) = x;
    else
    root = x.node();
    return x;
}

template <typename T>
inline T*& rbnodeptr<T>::parent() const {
    return node()->rblinks_.p_;
}

template <typename T>
inline rbnodeptr<T> rbnodeptr<T>::black_parent() const {
    return rbnodeptr<T>(node()->rblinks_.p_, false);
}

template <typename T>
inline bool rbnodeptr<T>::red() const {
    return x_ & 1;
}

template <typename T>
inline rbnodeptr<T> rbnodeptr<T>::change_color(bool color) const {
    return rbnodeptr<T>(color ? x_ | 1 : x_ & ~uintptr_t(1));
}

template <typename T>
inline rbnodeptr<T> rbnodeptr<T>::reverse_color() const {
    return rbnodeptr<T>(x_ ^ 1);
}

template <typename T>
inline rbnodeptr<T> rbnodeptr<T>::rotate(bool side) const {
    rbaccount(rotation);
    rbnodeptr<T> x = child(!side);
    // XXX no need to track rotations if using boundary nodes
    // increment the nodeversions of these nodes
    // node()->inc_nodeversion();
    // x.node()->inc_nodeversion();
    // if (x.child(side)) x.child(side).node()->inc_nodeversion();
    // perform the rotation
    if ((child(!side) = x.child(side)))
        x.child(side).parent() = node();
    bool old_color = red();
    x.child(side) = change_color(true);
    x.parent() = parent();
    parent() = x.node();
    return x.change_color(old_color);
}

template <typename T>
inline rbnodeptr<T> rbnodeptr<T>::flip() const {
    rbaccount(flip);
    child(false) = child(false).reverse_color();
    child(true) = child(true).reverse_color();
    return reverse_color();
}

namespace rbpriv {
template <typename Compare>
inline rbcompare<Compare>::rbcompare(const Compare& compare)
    : Compare(compare) {
}

template <typename Compare> template <typename T>
inline int rbcompare<Compare>::node_compare(const T& a, const T& b) const {
    int cmp = this->operator()(a, b);
    return cmp ? cmp : rbpriv::default_compare(&a, &b);
}

template <typename Compare> template <typename A, typename B>
inline int rbcompare<Compare>::compare(const A& a, const B& b) const {
    return this->operator()(a, b);
}

template <typename T, typename C>
inline rbrep<T, C>::rbrep(const C &compare) : rbcompare_type(compare) {
    this->root_ = this->limit_[0] = this->limit_[1] = 0;
}

template <typename Compare>
inline Compare& rbcompare<Compare>::get_compare() const {
    return *const_cast<Compare*>(static_cast<const Compare*>(this));
}

} // namespace rbpriv

// RBTREE FUNCTION DEFINITIONS
template <typename T, typename C>
inline rbtree<T, C>::rbtree(const value_compare &compare)
    : r_(compare), treeversion_(Sto::initialized_tid()) {
}

template <typename T, typename C>
rbtree<T, C>::~rbtree() {
}

template <typename T, typename C>
void rbtree<T, C>::insert_commit(T* x, rbnodeptr<T> p, bool side) {
    // link in new node; it's red
    x->rblinks_.p_ = p.node();
    x->rblinks_.c_[0] = x->rblinks_.c_[1] = rbnodeptr<T>(0, false);

    // maybe set limits
    if (p) {
        p.child(side) = rbnodeptr<T>(x, true);
        if (p.node() == r_.limit_[side])
            r_.limit_[side] = x;
    } else
        r_.root_ = r_.limit_[0] = r_.limit_[1] = x;

    // flip up the tree
    // invariant: we are looking at the `side` of `p`
    while (p.red()) {
        rbnodeptr<T> gp = p.black_parent(), z;
        if (gp.child(0).red() && gp.child(1).red()) {
            z = gp.flip();
            p = gp.black_parent().load_color();
        } else {
            bool gpside = gp.find_child(p.node());
            if (gpside != side) {
                gp.child(gpside) = p.rotate(gpside);
            } 
            z = gp.rotate(!gpside); 
            p = z.black_parent();
        }
        side = p.find_child(gp.node());
        p.set_child(side, z, r_.root_);
    }
}

template <typename T, typename C>
rbnodeptr<T> rbtree<T, C>::insert(reference x) {
    rbaccount(insert);

    // find insertion point
    rbnodeptr<T> p(r_.root_, false);
    bool side = false;
    while (p && (side = r_.node_compare(x, *p.node()) > 0,
                 p.child(side)))
        p = p.child(side);

    insert_commit(&x, p, side);
    return p;
}

template <typename T, typename C>
T* rbtree<T, C>::delete_node(T* victim_node, T* succ) {
    using std::swap;
    // find the node's color
    rbnodeptr<T> victim(victim_node, false);
    rbnodeptr<T> p = victim.black_parent();
    bool side = p.find_child(victim_node);

    // swap with successor if necessary
    if (victim.child(0) && victim.child(1)) {
        if (!succ)
            for (succ = victim.child(true).node();
                 succ->rblinks_.c_[0];
                 succ = succ->rblinks_.c_[0].node())
                /* nada */;
        rbnodeptr<T> succ_p = rbnodeptr<T>(succ->rblinks_.p_, false);
        bool sside = succ == succ_p.child(true).node();
        if (p)
            p.child(side) = rbnodeptr<T>(succ, p.child(side).red());
        else
            r_.root_ = succ;
        swap(succ->rblinks_, victim.node()->rblinks_);
        if (sside)
            succ->rblinks_.c_[sside] = victim.change_color(succ->rblinks_.c_[sside].red());
        succ->rblinks_.c_[0].parent() = succ->rblinks_.c_[1].parent() = succ;
        p = victim.black_parent();
        side = sside;
    } else
        succ = nullptr;

    // splice out victim
    bool active = !victim.child(false);
    rbnodeptr<T> x = victim.child(active);
    bool color = p && p.child(side).red();
    p.set_child(side, x, r_.root_);
    if (x)
        x.parent() = p.node();

    // maybe set limits
    for (int i = 0; i != 2; ++i)
        if (victim.node() == this->r_.limit_[i]) {
            rbnodeptr<T> b = (x ? x : p);
            while (b && b.child(i))
                b = b.child(i);
            this->r_.limit_[i] = b.node();
        }

    if (!color)
        delete_node_fixup(p, side);
   
    // return parent node to increment nodeversion
    return p.node();
}

template <typename T, typename C>
void rbtree<T, C>::delete_node_fixup(rbnodeptr<T> p, bool side) {
    while (p && !p.child(0).red() && !p.child(1).red()
           && !p.child(!side).child(0).red()
           && !p.child(!side).child(1).red()) {
        p.child(!side) = p.child(!side).change_color(true);
        T* node = p.node();
        p = p.black_parent();
        side = p.find_child(node);
    }

    if (p && !p.child(side).red()) {
        rbnodeptr<T> gp = p.black_parent();
        bool gpside = gp.find_child(p.node());

        if (p.child(!side).red()) {
            // invariant: p is black (b/c one of its children is red)
            gp.set_child(gpside, p.rotate(side), r_.root_);
            gp = p.black_parent(); // p is now further down the tree
            gpside = side;         // (since we rotated in that direction)
        }

        rbnodeptr<T> w = p.child(!side);
        if (!w.child(0).red() && !w.child(1).red()) {
            p.child(!side) = w.change_color(true);
            p = p.change_color(false);
        } else {
            if (!w.child(!side).red()) {
                p.child(!side) = w.rotate(!side);
            }
            bool gpside = gp.find_child(p.node());
            if (gp)
                p = gp.child(gpside); // fetch correct color for `p`
            p = p.rotate(side);
            p.child(0) = p.child(0).change_color(false);
            p.child(1) = p.child(1).change_color(false);
        }
        gp.set_child(gpside, p, r_.root_);
    } else if (p)
        p.child(side) = p.child(side).change_color(false);
}

template <typename T, typename C>
inline T* rbtree<T, C>::root() {
    return r_.root_;
}

// Return a pair of node, bool: if bool is true, then the node is the found node, 
// else if bool is false the node is the parent of the absent read. If (null, false), we have
// an empty tree
template <typename T, typename C> template <typename K, typename Comp>
inline std::tuple<T*, typename rbtree<T, C>::Version, bool,
       typename rbtree<T, C>::boundaries_type>
rbtree<T, C>::find_any(const K& key, Comp comp) const {

    rbnodeptr<T> n(r_.root_, false);
    rbnodeptr<T> p(nullptr, false);

    T* lhs = r_.limit_[0];
    T* rhs = r_.limit_[1];
    boundaries_type boundary = std::make_pair(std::make_tuple(lhs, lhs ? lhs->nodeversion() : 0),
                    std::make_tuple(rhs, rhs ? rhs->nodeversion() : 0));

    while (n.node()) {
        int cmp = comp.compare(key, *n.node());
        if (cmp == 0)
            break;

        // narrow down to find the boundary nodes
        // update the LEFT boundary when going RIGHT, and vice versa
        if (cmp > 0) {
            T* nb = n.node();
            boundary.first = std::make_tuple(nb, nb->nodeversion());
        } else {
            T* nb = n.node();
            boundary.second = std::make_tuple(nb, nb->nodeversion());
        }
        p = n;
        n = n.node()->rblinks_.c_[cmp > 0];
    }

    bool found = (n.node() != nullptr);
    T* retnode = found ? n.node() : p.node();
    Version retver = retnode ? retnode->version() : treeversion_;

    return std::make_tuple(retnode, retver, found, boundary);
}

template <typename T, typename C> template <typename K, typename Comp>
inline std::tuple<rbnodeptr<T>, bool> rbtree<T, C>::find_or_parent(const K& key, Comp comp) const {
    rbnodeptr<T> n(r_.root_, false);
    rbnodeptr<T> p(nullptr, false);

    while (n.node()) {
        int cmp = comp.compare(key, *n.node());
        if (cmp == 0)
            break;

        p = n;
        n = n.node()->rblinks_.c_[cmp > 0];
    }

    bool found = (n.node() != nullptr);

    return std::make_tuple(found ? n : p, found);
}

template <typename K, typename T>
class rbpair;

template <typename T, typename C> template <typename K, typename Comp>
inline std::tuple<T*, typename rbtree<T, C>::Version, bool,
       typename rbtree<T, C>::boundaries_type, typename rbtree<T, C>::node_info_type>
rbtree<T, C>::find_insert(K& key, Comp comp) {
    // lookup part, almost identical to find_any()
    rbnodeptr<T> n(r_.root_, false);
    rbnodeptr<T> p(nullptr, false);

    T* lhs = r_.limit_[0];
    T* rhs = r_.limit_[1];
    boundaries_type boundary = std::make_pair(std::make_tuple(lhs, lhs ? lhs->nodeversion() : 0),
                    std::make_tuple(rhs, rhs ? rhs->nodeversion() : 0));

    int cmp = 0;
    while (n.node()) {
        cmp = comp.compare(key, *n.node());
        if (cmp == 0)
            break;
        if (cmp > 0) {
            T* nb = n.node();
            boundary.first = std::make_tuple(nb, nb->nodeversion());
        } else {
            T* nb = n.node();
            boundary.second = std::make_tuple(nb, nb->nodeversion());
        }
        p = n;
        n = n.node()->rblinks_.c_[cmp > 0];
    }

    bool found = (n.node() != nullptr);
    T* retnode = n.node();
    Version retver = retnode ? (found ? retnode->version() : 0) : 0;
    node_info_type parent = std::make_tuple(p.node(), p.node() ? p.node()->nodeversion() : 0);

    // perform the insertion if not found
    if (!found) {
        retnode = (T*)malloc(sizeof(T));
        new (retnode) T((rbpair<typename K::key_type, typename K::value_type>)key);
        retver = retnode->nodeversion();
        insert_commit(retnode, p, (cmp > 0));

        // no more inc_nodeversion; nodeversion updates now occur at commit time
    }

    return std::make_tuple(retnode, retver, found, boundary, parent);
}

template <typename T, typename C>
inline T* rbtree<T, C>::erase(T& node) {
    rbaccount(erase);
    T* ret = delete_node(&node, nullptr);
    return ret;
}

// RBNODEPTR FUNCTION DEFINITIONS
template <typename T>
void rbnodeptr<T>::output(std::ostream &s, int indent, T* highlight) const {
    if (!*this)
    s << "<empty>\n";
    else {
    if (child(0))
        child(0).output(s, indent + 2, highlight);
    s << std::setw(indent) << "" << (const T&) *node() << " @" << (void*) node() << (red() ? " red" : "");
    if (highlight && highlight == node())
        s << " ******  p@" << (void*) node()->rblinks_.p_ << "\n";
    else
        s << "\n";
    if (child(1))
        child(1).output(s, indent + 2, highlight);
    }
}

template <typename T, typename C>
std::ostream &operator<<(std::ostream &s, const rbtree<T, C> &tree) {
    rbnodeptr<T>(tree.r_.root_, false).output(s, 0, 0);
    return s;
}

template <typename T>
size_t rbnodeptr<T>::size() const {
    return 1 + (child(false) ? child(false).size() : 0)
    + (child(true) ? child(true).size() : 0);
}

template <typename T, typename C>
inline bool rbtree<T, C>::empty() const {
    return !r_.root_;
}

template <typename T, typename C>
inline size_t rbtree<T, C>::size() const {
    return r_.root_ ? rbnodeptr<T>(r_.root_, false).size() : 0;
}

#define rbcheck_assert(x) do { if (!(x)) { rbnodeptr<T>(root, false).output(std::cerr, 0, node()); assert(x); } } while (0)

template <typename T> template <typename C>
void rbnodeptr<T>::check(T* parent, int this_black_height, int& black_height,
                         T* root, T* begin, T* end, C& compare) const {
    rbcheck_assert(node()->rblinks_.p_ == parent);
    if (parent) {
        int cmp = compare(*node(), *parent);
        if (parent->rblinks_.c_[0].node() == node())
            rbcheck_assert(cmp < 0 || (cmp == 0 && node() < parent));
        else
            rbcheck_assert(cmp > 0 || (cmp == 0 && node() > parent));
    }
    if (red())
        rbcheck_assert(!child(false).red() && !child(true).red());
    else {
        //rbcheck_assert(child(false).red() || !child(true).red()); /* LLRB */
        ++this_black_height;
    }
    if (begin && !child(false))
        assert(begin == node());
    if (end && !child(true))
        assert(end == node());
    for (int i = 0; i < 2; ++i)
        if (child(i))
            child(i).check(node(), this_black_height, black_height,
                           root, i ? 0 : begin, i ? end : 0, compare);
        else if (black_height == -1)
            black_height = this_black_height;
        else
            assert(black_height == this_black_height);
}

#undef rbcheck_assert

template <typename T, typename C>
int rbtree<T, C>::check() const {
    int black_height = -1;
    if (r_.root_)
        rbnodeptr<T>(r_.root_, false).check(0, 0, black_height, r_.root_,
                                            r_.limit_[0], r_.limit_[1], r_.get_compare());
    else
        assert(!r_.limit_[0] && !r_.limit_[1]);
    return black_height;
}

// RBALGORITHMS FUNCTION DEFINITIONS
template <typename T>
inline T* rbalgorithms<T>::edge_node(T* n, bool forward) {
    while (n->rblinks_.c_[forward])
        n = n->rblinks_.c_[forward].node();
    return n;
}

template <typename T>
inline T* rbalgorithms<T>::step_node(T* n, bool forward) {
    if (n->rblinks_.c_[forward])
        n = edge_node(n->rblinks_.c_[forward].node(), !forward);
    else {
        T* prev;
        do {
            prev = n;
            n = n->rblinks_.p_;
        } while (n && n->rblinks_.c_[!forward].node() != prev);
    }
    return n;
}

template <typename T>
inline T* rbalgorithms<T>::next_node(T* n) {
    return step_node(n, true);
}

template <typename T>
inline T* rbalgorithms<T>::prev_node(T* n) {
    return step_node(n, false);
}

template <typename T>
inline T* rbalgorithms<T>::prev_node(T* n, T* last) {
    return n ? step_node(n, false) : last;
}


<|start_filename|>ex-counter.cc<|end_filename|>
#include <string>
#include <iostream>
#include <sys/time.h>
#include <assert.h>
#include <sys/resource.h>
#include <vector>
#include "Transaction.hh"
#include "TIntRange.hh"
#include "TWrapped.hh"
#include "randgen.hh"
#include "clp.h"
#define GUARDED if (TransactionGuard tguard{})
unsigned initial_seeds[64];
unsigned ops_per_trans = 1;
double usleep_fraction = 0.1;

struct results_t {
    uint64_t trans, a, b, c, rbuf_find;
    struct timeval finished;
} results[32];

void print_time(struct timeval tv1, struct timeval tv2) {
  printf("%f", (tv2.tv_sec-tv1.tv_sec) + (tv2.tv_usec-tv1.tv_usec)/1000000.0);
}

class TCounter0 : public TObject {
    TWrapped<int> n_;
    TVersion v_;
public:
    TCounter0(int n = 0)
        : n_(n) {
    }
    int nontrans_access() {
        return n_.access();
    }
    void increment() {
        TransProxy it = Sto::item(this, 0);
        int n = it.has_write() ? it.write_value<int>() : n_.read(it, v_);
        it.add_write(n + 1);
    }
  void decrement() {
        TransProxy it = Sto::item(this, 0);
        int n = it.has_write() ? it.write_value<int>() : n_.read(it, v_);
        it.add_write(n - 1);
  }
  bool test() const {
     TransProxy it = Sto::item(this, 0);
     return (it.has_write() ? it.write_value<int>() : n_.read(it, v_)) > 0;
  }

    bool lock(TransItem& item, Transaction& txn) override {
        return txn.try_lock(item, v_);
    }
    bool check(TransItem& it, Transaction&) override {
        return it.check_version(v_);
    }
    void install(TransItem& it, Transaction& txn) override {
        n_.access() = it.write_value<int>();
        txn.set_version_unlock(v_, it);
    }
    void unlock(TransItem&) override {
        v_.unlock();
    }

    void print(std::ostream& w) const {
        w << "{TCounter0 " << n_.access() << " V" << v_ << "}";
    }
    friend std::ostream& operator<<(std::ostream& w, const TCounter0& tc) {
        tc.print(w);
        return w;
    }
};

class TCounter1 : public TObject {
    TWrapped<int> n_;
    TVersion v_;
    static int wval(TransProxy it) {
       return it.write_value<int>(0);
    }
    static int wval(const TransItem& it) {
       return it.write_value<int>(0);
    }
public:
    TCounter1(int n = 0)
        : n_(n) {
    }
    int nontrans_access() {
        return n_.access();
    }
  void increment() {
     auto it = Sto::item(this, 0);
     it.add_write(wval(it) + 1);
  }
  void decrement() {
     auto it = Sto::item(this, 0);
     it.add_write(wval(it) - 1);
  }
  bool test() const {
     auto it = Sto::item(this, 0);
     int n = n_.read(it, v_);
     return n + wval(it) > 0;
  }

    bool lock(TransItem& item, Transaction& txn) override {
        return txn.try_lock(item, v_);
    }
    bool check(TransItem& it, Transaction&) override {
        return it.check_version(v_);
    }
    void install(TransItem& it, Transaction& txn) override {
        n_.access() += wval(it);
        txn.set_version_unlock(v_, it);
    }
    void unlock(TransItem&) override {
        v_.unlock();
    }

    void print(std::ostream& w) const {
        w << "{TCounter1 " << n_.access() << " V" << v_ << "}";
    }
    friend std::ostream& operator<<(std::ostream& w, const TCounter1& tc) {
        tc.print(w);
        return w;
    }
};

class TCounter2 : public TObject {
    TWrapped<int> n_;
    TVersion v_;
    //unsigned next_cache_line_[17];
    TWrapped<int> zc_n_;
    TVersion zc_v_;
    static int wval(TransProxy it) {
        return it.write_value<int>(0);
    }
    static int wval(const TransItem& it) {
        return it.write_value<int>(0);
    }
    static constexpr TransItem::flags_type zc_bit = TransItem::user0_bit;
    static constexpr TransItem::flags_type zc_set_bit = zc_bit << 1;
public:
    TCounter2(int n = 0)
        : n_(n), zc_n_(n) {
    }
    int nontrans_access() {
        return n_.access();
    }
    void increment() {
        auto it = Sto::item(this, 0);
        it.add_write(wval(it) + 1);
    }
    void decrement() {
        auto it = Sto::item(this, 0);
        it.add_write(wval(it) - 1);
    }
    bool test() const {
        auto it = Sto::item(this, 0);
        if (!it.has_write()) {
            it.add_flags(zc_bit);
            return zc_n_.read(it, zc_v_) > 0;
        } else { /* assume opacity */
            if (it.has_flag(zc_bit))
                it.clear_flags(zc_bit).clear_read();
            return n_.read(it, v_) + wval(it) > 0;
        }
    }

    bool lock(TransItem& it, Transaction& txn) override {
        bool ok = txn.try_lock(it, v_);
        if (ok) {
            int n = n_.access();
            if ((n > 0) != (n + wval(it) > 0)) {
                zc_v_.value() |= (v_.value() & (TransactionTid::nonopaque_bit - 1));
                it.add_flags(zc_set_bit);
            }
        }
        return ok;
    }
    bool check(TransItem& it, Transaction&) override {
        return it.check_version(it.has_flag(zc_bit) ? zc_v_ : v_);
    }
    void install(TransItem& it, Transaction& txn) override {
        n_.access() += wval(it);
        if (it.has_flag(zc_set_bit)) {
            zc_n_.access() = n_.access();
            txn.set_version_unlock(zc_v_, it);
        }
        txn.set_version_unlock(v_, it);
    }
    void unlock(TransItem& it) override {
        if (it.has_flag(zc_set_bit))
            zc_v_.unlock();
        v_.unlock();
    }
    void print(std::ostream& w, const TransItem& item) const override {
        w << "{TCounter2";
        if (item.has_flag(zc_bit))
            w << ".ZC";
        if (item.has_read())
            w << " R" << item.read_value<TVersion>();
        if (item.has_write())
            w << " Δ" << item.write_value<int>();
        if (item.has_flag(zc_set_bit))
            w << "ZC";
        w << "}";
    }
    void print(std::ostream& w) const {
        w << "{TCounter2 " << n_.access() << " V" << v_ << " ZCV" << zc_v_ << "}";
    }
    friend std::ostream& operator<<(std::ostream& w, const TCounter2& tc) {
        tc.print(w);
        return w;
    }
};

class TCounter3 : public TObject {
    TWrapped<int> n_;
    TVersion v_;
    typedef TIntRange<int> pred_type;
    static int wval(TransProxy it) {
        return it.write_value<int>(0);
    }
    static int wval(const TransItem& it) {
        return it.write_value<int>(0);
    }
public:
    TCounter3(int n = 0)
        : n_(n) {
    }
    int nontrans_access() {
        return n_.access();
    }
    void increment() {
        auto it = Sto::item(this, 0);
        it.add_write(wval(it) + 1);
    }
    void decrement() {
        auto it = Sto::item(this, 0);
        it.add_write(wval(it) - 1);
    }
    bool test() const {
        TransProxy it = Sto::item(this, 0);
        if (!it.has_predicate())
            it.set_predicate(pred_type::unconstrained());
        int n = n_.snapshot(it, v_);
        bool gt = n + wval(it) > 0;
        it.predicate_value<pred_type>().observe_gt(-wval(it), gt);
        return gt;
    }

    bool lock(TransItem& item, Transaction& txn) override {
        return txn.try_lock(item, v_);
    }
    bool check_predicate(TransItem& item, Transaction& txn, bool committing) override {
        TransProxy p(txn, item);
        pred_type pred = item.template predicate_value<pred_type>();
        int n = n_.wait_snapshot(p, v_, committing);
        return pred.verify(n);
    }
    bool check(TransItem& it, Transaction&) override {
        return it.check_version(v_);
    }
    void install(TransItem& it, Transaction& txn) override {
        n_.access() += wval(it);
        txn.set_version_unlock(v_, it);
    }
    void unlock(TransItem&) override {
        v_.unlock();
    }

    void print(std::ostream& w) const {
        w << "{TCounter3 " << n_.access() << " V" << v_ << "}";
    }
    friend std::ostream& operator<<(std::ostream& w, const TCounter3& tc) {
        tc.print(w);
        return w;
    }
};


static int initial_value = -100;
static double test_fraction = 0.5;
static int nthreads = 4;
static double exptime = 10;

enum { opt_nthreads = 1, opt_test_fraction, opt_initial_value, opt_seed,
       opt_ops_per, opt_time, opt_usleep_fraction };

static const Clp_Option options[] = {
  { "nthreads", 'j', opt_nthreads, Clp_ValInt, 0 },
  { "test-fraction", 'f', opt_test_fraction, Clp_ValDouble, 0 },
  { "initial-value", 'i', opt_initial_value, Clp_ValInt, 0 },
  { "opspertrans", 'o', opt_ops_per, Clp_ValUnsigned, 0 },
  { "time", 't', opt_time, Clp_ValDouble, 0 },
  { "usleep-fraction", 'u', opt_usleep_fraction, Clp_ValDouble, 0 },
  { "seed", 0, opt_seed, Clp_ValUnsigned, 0 }
};


struct result {
    uint64_t ngt;
    int final_value;
};

class Tester {
public:
    virtual result run() = 0;
};

template <typename T>
class TTester : public Tester {
public:
    static T* counter;
    static volatile unsigned go;
    static void* runfunc(void*);
    result run();
};

template <typename T> T* TTester<T>::counter;
template <typename T> volatile unsigned TTester<T>::go;

template <typename T>
void* TTester<T>::runfunc(void* arg) {
    int me = (int) (uintptr_t) arg;
    T* counter = TTester<T>::counter;
    TThread::set_id(me);
    Rand transgen(initial_seeds[2*me], initial_seeds[2*me + 1]);
    unsigned test_threshold = test_fraction * transgen.max();
    unsigned increment_threshold = (0.499 * test_fraction + 0.501) * transgen.max();
    unsigned usleep_threshold = usleep_fraction * transgen.max();

    while (!go)
        relax_fence();
    uint64_t trans = 0, a = 0, b = 0, c = 0, count_test = 0, rbuf_find = 0, retry = 0;

    while (go) {
        Rand snap_transgen = transgen;
        unsigned na, nb, nc, ngt, nfind;
        while (1) {
            na = nb = nc = ngt = nfind = 0;
            ++retry;
            try {
                Sto::start_transaction();
                for (unsigned k = 0; k < ops_per_trans; ++k) {
                    unsigned op = transgen();
                    if (op < test_threshold) {
                        ngt += counter->test();
                        ++na;
                    } else if (op < increment_threshold) {
                        counter->increment();
                        ++nb;
                    } else {
                        counter->decrement();
                        ++nc;
                    }
                }
                if (transgen() < usleep_threshold)
                    usleep(1);
                if (Sto::try_commit())
                    break;
            } catch (Transaction::Abort e) {
            }
            transgen = snap_transgen;
        }
        a += na;
        b += nb;
        c += nc;
        count_test += ngt;
        rbuf_find += nfind;
        ++trans;
    }

    results[me].trans = trans;
    results[me].a = a;
    results[me].b = b;
    results[me].c = c;
    results[me].rbuf_find = rbuf_find;
    gettimeofday(&results[me].finished, NULL);
    return reinterpret_cast<void*>(count_test);
}

static bool has_epoch_advancer = false;

template <typename T>
result TTester<T>::run() {
    counter = new T(initial_value);
    pthread_t tids[nthreads];
    go = 0;

    for (uintptr_t i = 0; i < uintptr_t(nthreads); ++i)
        pthread_create(&tids[i], NULL, runfunc, reinterpret_cast<void*>(i));

    if (!has_epoch_advancer) {
        pthread_t advancer;
        pthread_create(&advancer, NULL, Transaction::epoch_advancer, NULL);
        pthread_detach(advancer);
        has_epoch_advancer = true;
    }

    go = 1;
    usleep(exptime * 1000000);
    go = 0;
    uint64_t total = 0;
    for (int i = 0; i < nthreads; ++i) {
        void* mine;
        pthread_join(tids[i], &mine);
        total += reinterpret_cast<uintptr_t>(mine);
    }
    std::cout << *counter << '\n';
    return result{total, counter->nontrans_access()};
}

static Tester* ttesters[] = { new TTester<TCounter0>, new TTester<TCounter1>,
    new TTester<TCounter2>, new TTester<TCounter3> };

int main(int argc, char *argv[]) {
  Clp_Parser *clp = Clp_NewParser(argc, argv, arraysize(options), options);
  srandomdev();
  std::vector<int> tests;
  unsigned seed = 0;

  int opt;
  while ((opt = Clp_Next(clp)) != Clp_Done) {
    switch (opt) {
    case opt_nthreads:
      nthreads = clp->val.i;
      break;
    case opt_ops_per:
      ops_per_trans = clp->val.u;
      break;
    case opt_test_fraction:
      test_fraction = clp->val.d;
      break;
    case opt_initial_value:
      initial_value = clp->val.i;
      break;
    case opt_seed:
        seed = clp->val.u;
        break;
    case opt_time:
        exptime = clp->val.d;
        break;
    case opt_usleep_fraction:
        usleep_fraction = clp->val.d;
        break;
    case Clp_NotOption: {
        int testnum = atoi(clp->vstr);
        assert(testnum >= 0 && testnum <= 3);
        tests.push_back(testnum);
        break;
    }
    default:
      assert(0);
    }
  }
  Clp_DeleteParser(clp);

  if (seed)
      srandom(seed);
  else
      srandomdev();
  for (unsigned i = 0; i < arraysize(initial_seeds); ++i)
      initial_seeds[i] = random();

    if (tests.empty())
        tests.push_back(1);
    for (auto testnum : tests) {
        struct timeval tv1,tv2;
        struct rusage ru1,ru2;
        gettimeofday(&tv1, NULL);
        getrusage(RUSAGE_SELF, &ru1);
        result r = ttesters[testnum]->run();
        gettimeofday(&tv2, NULL);
        getrusage(RUSAGE_SELF, &ru2);

        uint64_t total_trans = 0;
        for (int i = 0; i != nthreads; ++i)
            total_trans += results[i].trans;
        printf("THROUGHPUT: %f TRANS/SEC\n", total_trans / exptime);

        printf("  real time: ");
        print_time(tv1,tv2);
        printf(", utime: ");
        print_time(ru1.ru_utime, ru2.ru_utime);
        printf(", stime: ");
        print_time(ru1.ru_stime, ru2.ru_stime);

        printf("\n  ./ex-counter -j%d -t%g -f%g -u%g -i%d -o%u %d\n",
               nthreads, exptime, test_fraction, usleep_fraction,
               initial_value, ops_per_trans, testnum);
        printf("  test() true %llu, value %d\n", (unsigned long long) r.ngt, r.final_value);
        printf("  duration: ");
        for (int i = 0; i != nthreads; ++i) {
            printf(i ? ", %llu/" : "%llu/", (unsigned long long) results[i].trans);
            print_time(tv1, results[i].finished);
        }
        printf("\n");
#if STO_PROFILE_COUNTERS
        Transaction::print_stats();
        if (txp_count >= txp_total_aborts) {
            txp_counters tc = Transaction::txp_counters_combined();
            const char* sep = "";
            if (txp_count > txp_total_w) {
                printf("%stotal_n: %llu, total_r: %llu, total_w: %llu", sep, tc.p(txp_total_n), tc.p(txp_total_r), tc.p(txp_total_w));
                sep = ", ";
            }
            if (txp_count > txp_total_searched) {
                printf("%stotal_searched: %llu", sep, tc.p(txp_total_searched));
                sep = ", ";
            }
            if (txp_count > txp_total_aborts) {
                printf("%stotal_aborts: %llu (%llu aborts at commit time)\n", sep, tc.p(txp_total_aborts), tc.p(txp_commit_time_aborts));
                sep = ", ";
            }
            if (*sep)
                printf("\n");
        }
        Transaction::clear_stats();
#endif
    }
}


<|start_filename|>Boosting_locks.hh<|end_filename|>
#pragma once

#include "config.h"
#include "compiler.hh"

// XXX: these should really be standalone classes rather than a boosting specific header.

#define READ_SPIN 100000
//(long(1)<<60)
#define WRITE_SPIN 100000
//(long(1)<<60)

class SpinLock {
public:
  typedef uint64_t lock_type;
private:
  lock_type lock;
  
  static constexpr lock_type lock_bit = lock_type(1) << (sizeof(lock_type) * 8 - 1);

public:
  SpinLock() : lock(0) {}

  bool tryLock(long spin = 0) {
    while (spin >= 0) {
      lock_type cur = lock;
      if (!(cur & lock_bit) && bool_cmpxchg(&lock, cur, lock_bit)) {
        return true;
      }
      spin--;
      relax_fence();
    }
    return false;
  }

  void unlock() {
    fence();
    lock = 0;
  }
};

// nate: realized after writing this we have an rwlock.hh. But this one has 
// support for not starving writers (which I guess could be useful), and for 
// upgrading read -> write locks (which we probably need for boosting).
// It's also as of yet untested :)
class RWLock {
public:
  typedef uint64_t lock_type;
private:
  lock_type lock;

  static constexpr lock_type write_lock_bit = lock_type(1) << (sizeof(lock_type) * 8 - 1);
  static constexpr lock_type waiting_write_bit = lock_type(1) << (sizeof(lock_type) * 8 - 2);
  static constexpr lock_type readerMask = ~(write_lock_bit | waiting_write_bit);


public:
  RWLock() : lock(0) {}

  bool tryReadLock(long spin = 0) {
    while (spin >= 0) {
      lock_type cur = lock;
      fence();
      if (!(cur & write_lock_bit) && !(cur & waiting_write_bit)) {
        // apparently this is faster than cmpxchg
        lock_type prev = __sync_fetch_and_add(&lock, 1);
        // woops, it was already locked or about to be.
        if ((prev & write_lock_bit) || (prev & waiting_write_bit)) {
          __sync_fetch_and_add(&lock, -1);
        } else {
          acquire_fence();
          return true;
        }
      }
      spin--;
      relax_fence();
    }
    return false;
  }

  void readUnlock() {
    assert(lock & readerMask);
    __sync_fetch_and_add(&lock, -1);
  }

  bool tryWriteLock(long spin = 0) {
    bool registered = false;
    while (spin >= 0) {
      lock_type cur = lock;
      fence();
      if (!(cur & write_lock_bit) && !(cur & readerMask)) {
	// we try to set the lock to just write_lock_bit, which will clear any
	// other flags
        if (bool_cmpxchg(&lock, cur, write_lock_bit)) {
          acquire_fence();
          return true;
        }
      }
      // cur could be out of date but then we'll just set this next iteration
      if (!(cur & waiting_write_bit) && spin > 0) {
        lock_type prev = __sync_fetch_and_or(&lock, waiting_write_bit);
        registered = !(prev & waiting_write_bit);
      }
      spin--;
      relax_fence();
    }
    if (registered) {
      __sync_fetch_and_and(&lock, ~waiting_write_bit);
    }
    return false;
  }

  void writeUnlock() {
    __sync_fetch_and_and(&lock, ~write_lock_bit);
  }
  
  // if successful, we now hold a write lock. doesn't release the read lock in
  // either case.
  bool tryUpgrade(long spin = 0) {
    lock_type cur = lock;
    assert(cur & readerMask);
    // XXX: it could be more clear to have a separate bit for this rather than overloading waiting_write_bit
    if ((cur & waiting_write_bit) || (__sync_fetch_and_or(&lock, waiting_write_bit) & waiting_write_bit)) {
      // either someone else is trying to upgrade this lock, or some other
      // writer is waiting for the lock. In the former case we're in a bit
      // of a deadlock with the other upgrader, so we may as well as let
      // them have it. In the latter case, it still seems okay to just
      // let the other writer win this one.
      return false;
    }
    fence();
    while (spin >= 0) {
      // now just have to wait for readers
      lock_type cur = lock;
      // no new readers should be adding themselves, so once this is 1 it won't go
      // back up (except temporarily)
      if ((cur & readerMask) == 1) {
	// simultaneously write lock and discard our read lock.
	// I think we should always be able to get this since
	// we have a read lock, and only one upgrader should
	// run at a time.
	if (bool_cmpxchg(&lock, cur, write_lock_bit)) {
	  acquire_fence();
	  return true;
	}
      }
      spin--;
      relax_fence();
    }
    // we got tired of waiting for other readers, didn't upgrade after all
    __sync_fetch_and_and(&lock, ~waiting_write_bit);
    return false;
  }

  // precondition is that you have at least a read lock
  bool isWriteLocked() {
    lock_type cur = lock;
    fence();
    return (cur & write_lock_bit);
  }
};


<|start_filename|>pqVsIt.cc<|end_filename|>
#define TVECTOR_DEFAULT_CAPACITY 16384
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include <random>
#include <map>
#include <queue>
#include "Transaction.hh"
#include "TVector.hh"
#include "TVector_nopred.hh"
#include "PriorityQueue.hh"
#include "PriorityQueue1.hh"
#include "clp.h"
#include "randgen.hh"
int waiting = 5000;
int max_value = 100000;
int global_seed = 0;
int nthreads = 4;
int opspertrans = 1;
int prepopulate = 1000;
double push_percent = 0.75;
int blocks = 1000;
int runtime = 10;
unsigned initial_seeds[128];

volatile bool running = true;

#define SMALLER_WRITES 0
#define SINGLE_POP 0
#define FIX_RUNTIME 1
#if FIX_RUNTIME
int ntrans = 1000000;
#else
int ntrans = 300000;
#endif

TransactionTid::type lock;

template <typename T>
struct TesterPair {
    T* t;
    int me;
    uint64_t num_trans;
};

template <typename T>
uint64_t run(T* q, int me) {
    TThread::set_id(me);
#if SMALLER_WRITES
    std::uniform_int_distribution<long> slotdist(0, max_value/blocks);
#else
    std::uniform_int_distribution<long> slotdist(0, max_value);
#endif
    Rand transgen(initial_seeds[2*me], initial_seeds[2*me + 1]);
    uint64_t num_trans = 0;
#if !FIX_RUNTIME
    int N = ntrans/nthreads;
#endif
    int OPS = opspertrans;
    int ratio = ( push_percent / (1 - push_percent));
    if (ratio < 1) ratio = 1;
    bool only_pop = false;
    bool only_push = false;
#if SINGLE_POP
    if (me == 0) only_pop = true;
    else only_push = true;
#endif

#if FIX_RUNTIME
    int i = -1;
    while(running) {
    i++;
#else
    for (int i = 0; i < N; ++i) {
#endif
        // so that retries of this transaction do the same thing
        Rand transgen_snap = transgen;
        while (1) {
            Sto::start_transaction();
            try {
                for (int j = 0; j < OPS; ++j) {
                    int op = slotdist(transgen) % 100;
                    if (only_push || (!only_pop && op < push_percent * 100)) {
                            int val = slotdist(transgen);
#if SMALLER_READS
                            val = val + (1 - (i/N))*max_value;
#endif
                            q->push(val);
                    } else {
                        for (int r = 0; r < ratio; r++) {
                            try {
                                q->pop();
                            } catch (std::out_of_range e) {
                                // gross but whatever
                            }
                        }
                    }
                }
 
                if (Sto::try_commit()) {
#if FIX_RUNTIME
                    num_trans++;
#endif
                    break;
                }
        
            } catch (Transaction::Abort e) { }
            transgen = transgen_snap;
        }
        /* Waiting time */
        for (int k = 0; k < waiting; k++) {__asm__ __volatile__("");}
    }
    return num_trans;
}

template <typename T>
void* runFunc(void* x) {
    TesterPair<T>* tp = (TesterPair<T>*) x;
    uint64_t num_trans = run(tp->t, tp->me);
    tp->num_trans = num_trans;
    return nullptr;
}

template <typename T>
uint64_t startAndWait(int n, T* queue) {
    running = true;
    pthread_t tids[nthreads];
    TesterPair<T> *testers = new TesterPair<T>[n];
    for (int i = 0; i < nthreads; ++i) {
        testers[i].t = queue;
        testers[i].me = i;
        pthread_create(&tids[i], NULL, runFunc<T>, &testers[i]);
    }
#if FIX_RUNTIME
    sleep(runtime);
    printf("stopping...\n");
    running = false;
#endif 
    __sync_synchronize();
    for (int i = 0; i < nthreads; ++i) {
        pthread_join(tids[i], NULL);
    }

    uint64_t tot_trans = 0;
    for (int i = 0; i < nthreads; ++i) {
       tot_trans += testers[i].num_trans; 
    }
    return tot_trans;
}

void print_time(struct timeval tv1, struct timeval tv2) {
    printf("%f\n", (tv2.tv_sec-tv1.tv_sec) + (tv2.tv_usec-tv1.tv_usec)/1000000.0);
}

enum {
    opt_nthreads = 1, opt_ntrans, opt_opspertrans, opt_pushpercent, opt_toppercent, opt_prepopulate, opt_seed
};

static const Clp_Option options[] = {
    { "nthreads", 0, opt_nthreads, Clp_ValInt, Clp_Optional },
    { "ntrans", 0, opt_ntrans, Clp_ValInt, Clp_Optional },
    { "opspertrans", 0, opt_opspertrans, Clp_ValInt, Clp_Optional },
    { "pushpercent", 0, opt_pushpercent, Clp_ValDouble, Clp_Optional },
    { "toppercent", 0, opt_toppercent, Clp_ValDouble, Clp_Optional },
    { "prepopulate", 0, opt_prepopulate, Clp_ValInt, Clp_Optional },
    { "seed", 0, opt_seed, Clp_ValInt, Clp_Optional }
};

static void help() {
    printf("Usage: [OPTIONS]\n\
           Options:\n\
           --nthreads=NTHREADS (default %d)\n\
           --ntrans=NTRANS, how many total transactions to run (they'll be split between threads) (default %d)\n\
           --opspertrans=OPSPERTRANS, how many operations to run per transaction (default %d)\n\
           --pushpercent=PUSHPERCENT, probability with which to do pushes (default %f)\n\
           --prepopulate=PREPOPULATE, prepopulate table with given number of items (default %d)\n\
           --seed=SEED, global seed to run the experiment \n",
            nthreads, ntrans, opspertrans, push_percent, prepopulate);
    exit(1);
}

template <typename T>
void init(T* q) {
    std::uniform_int_distribution<long> slotdist(0, max_value);
    Rand transgen(random(), random());
    for (int i = 0; i < prepopulate; i++) {
        TRANSACTION {
            int val = slotdist(transgen);
#if SMALLER_WRITES
            val = val + max_value*(1+blocks)/blocks;
#endif
            q->push(val);
        } RETRY(false);
    }
}

template <typename T>
void run_and_report(const char* name) {
    T* q;
    TRANSACTION {
        q = new T;
    } RETRY(true);
    init(q);

    struct timeval tv1, tv2;
    gettimeofday(&tv1, NULL);
    unsigned long long num_trans = startAndWait(nthreads, q);
    gettimeofday(&tv2, NULL);

#if FIX_RUNTIME
    double time = tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec-tv1.tv_usec)/1000000.0;
    unsigned long long throughput = num_trans/time;
    printf("%s: %llu\n", name, throughput);
#else
    printf("%s time: ", name);
    print_time(tv1, tv2);
#endif
#if STO_PROFILE_COUNTERS
    Transaction::print_stats();
    {
        txp_counters tc = Transaction::txp_counters_combined();
        printf("total_n: %llu, total_r: %llu, total_w: %llu, total_searched: %llu, total_aborts: %llu (%llu aborts at commit time)\n", tc.p(txp_total_n), tc.p(txp_total_r), tc.p(txp_total_w), tc.p(txp_total_searched), tc.p(txp_total_aborts), tc.p(txp_commit_time_aborts));
    }
    Transaction::clear_stats();
#endif
}

int main(int argc, char *argv[]) {
    lock = 0;
    Clp_Parser *clp = Clp_NewParser(argc, argv, arraysize(options), options);
    std::vector<const char*> tests;
        
    int opt;
    while ((opt = Clp_Next(clp)) != Clp_Done) {
        switch (opt) {
            case opt_nthreads:
                nthreads = clp->val.i;
                break;
            case opt_ntrans:
                ntrans = clp->val.i;
                break;
            case opt_opspertrans:
                opspertrans = clp->val.i;
                break;
            case opt_pushpercent:
                push_percent = clp->val.d;
                break;
            case opt_prepopulate:
                prepopulate = clp->val.i;
                break;
            case opt_seed:
                global_seed = clp->val.i;
                break;
            case Clp_NotOption:
                tests.push_back(clp->vstr);
                break;
            default:
                help();
        }
    }
    Clp_DeleteParser(clp);

    if (tests.empty()) {
        tests.push_back("PQ");
        tests.push_back("it");
    }

    if (global_seed)
        srandom(global_seed);
    else
        srandomdev();
    for (unsigned i = 0; i < arraysize(initial_seeds); ++i)
        initial_seeds[i] = random();

    pthread_t advancer;
    pthread_create(&advancer, NULL, Transaction::epoch_advancer, NULL);
    pthread_detach(advancer);

    // Run a parallel test with lots of transactions doing pushes and pops
    for (auto test : tests) {
        if (strcmp(test, "PQ") == 0 || strcmp(test, "pq") == 0)
            run_and_report<PriorityQueue<int>>("PQ");
        else if (strcmp(test, "PQ1") == 0 || strcmp(test, "pq1") == 0 || strcmp(test, "it") == 0)
            run_and_report<PriorityQueue1<int>>("PQ1");
        else if (strcmp(test, "std") == 0)
            run_and_report<std::priority_queue<int, TVector<int>>>("std");
        else if (strcmp(test, "std-nopred") == 0)
            run_and_report<std::priority_queue<int, TVector_nopred<int>>>("std-nopred");
        else
            assert(false);
    }

    return 0;
}


<|start_filename|>singleelems.cc<|end_filename|>
#include "Transaction.hh"
#include "SingleElem.hh"
#include "TGeneric.hh"
#include <string>
#include <assert.h>

void bigObjTests() {
  struct foo {
    int a;
    int b;
    double c;
  };
  SingleElem<foo> f;
  printf("big obj size: %lu\n", sizeof(f));
  
  {
      TransactionGuard t;
      f = foo{1, 2, 3.4};
  }

  {
      TransactionGuard t2;
      foo f_read = f;
      assert(f_read.a == 1);
      assert(f_read.b == 2);
      assert(f_read.c - 3.4 < .001);
  }
}

void nontrivialObjTests() {
  SingleElem<std::string> f;
  printf("std string size: %lu\n", sizeof(f));

  {
      TransactionGuard t;
      f = "foobarbaz";
  }

  {
      TransactionGuard t2;
      std::string s = f;
      assert(s == std::string("foobarbaz"));
  }
}

float y = 1.1;
void genericSTMTests() {
  TGeneric stm;
  int x = 4;
  uint64_t *z = (uint64_t*)malloc(sizeof(*z));
  *z = 0xffffffffffULL;
  {TransactionGuard t;
    assert(stm.read(&x) == 4);
    stm.write(&x, 5);
    assert(stm.read(&x) == 5);
    
    assert(stm.read(&y) - 1.1 < 0.01);
    
    assert(stm.read(z) == (uint64_t)0xffffffffffULL);
    stm.write(z, (uint64_t)0x7777777777ULL);
    assert(stm.read(z) == (uint64_t)0x7777777777ULL);
  }

  assert(x == 5);

  {TransactionGuard t;
    assert(stm.read(&x) == 5);
    assert(stm.read(&y) - 1.1 < 0.01);
    assert(stm.read(z) == (uint64_t)0x7777777777ULL);
  }
}

void incrementTest() {
    SingleElem<int> f;
    
    TRANSACTION {
        f = 1;
    } RETRY(false);
    
    TRANSACTION {
        f = f + 1;
    } RETRY(false);
    
    int v;
    TRANSACTION {
        v = f;
    } RETRY(false);

    assert(v == 2);
}

int main() {
  SingleElem<int> f;
  printf("size: %lu\n", sizeof(f));

  {
      TransactionGuard t;
      f = 1;
      assert(f == 1);
  }

  {
      TransactionGuard t2;
      assert(f == 1);
  }

  bigObjTests();
  nontrivialObjTests();

  genericSTMTests();

  incrementTest();

  return 0;
}


<|start_filename|>simple_str.hh<|end_filename|>
#pragma once
// Adopted from stuffed_str
class simple_str {
public:
  static unsigned pad(unsigned v)
  {
    if (likely(v <= 512)) {
      return (v + 15) & ~15;
    }
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
#if UINT_MAX == UINT64_MAX
    v |= v >> 32;
#endif
    v++;
    return v;
  }

  static inline int size_for(int len) {
    int res = pad(len + sizeof(simple_str));
    return res;

  }

  bool needs_resize(int len) {
    return len > (int)capacity_;
  }

  const char *data() {
    return buf_;
  }
  
  int length() {
    return size_;
  }
  
  int capacity() {
    return capacity_;
  }

  inline simple_str& operator= (const std::string& v) {
    int len = v.length();
    size_ = len;
    if (unlikely(needs_resize(len))) {
      capacity_ = size_for(len) - sizeof(simple_str);
      buf_ = (char *) malloc(capacity_);
    }
    memcpy(buf_, v.data(), len);
    return *this;    
  }
  
  operator std::string() {
    return std::string(this->data(), this->length());  
  }

  simple_str(const std::string& v) {
    int len = v.length();
    size_ = len;
    capacity_ = size_for(len) - sizeof(simple_str);
    buf_ = (char *) malloc(capacity_);
    memcpy(buf_, v.data(), len);
  }
private:
  uint32_t size_;
  uint32_t capacity_;
  char *buf_;
};



<|start_filename|>Boosting_standalone.cc<|end_filename|>
#include "Boosting_standalone.hh"

Boosting __boostingtransactions[BOOSTING_MAX_THREADS];


<|start_filename|>Boosting_standalone.hh<|end_filename|>
#pragma once

#if defined(BOOSTING) && defined(BOOSTING_STANDALONE)
#include "local_vector.hh"
#include "Boosting_common.hh"

class Boosting {
public:
  class Abort {};
  typedef void (*Callback)(void*, void*, void*);

  Boosting() : commitCallbacks(), abortCallbacks() {}

  void did_commit() {
    for (auto it = commitCallbacks.begin(); it != commitCallbacks.end(); ++it) {
      auto& cb = *it;
      cb.callback(cb.context1, cb.context2, cb.context3);
    }
    abortCallbacks.unsafe_clear();
    commitCallbacks.unsafe_clear();
  }
  void did_abort() {
    // iterate in reverse
    for (auto it = abortCallbacks.rbegin(); it != abortCallbacks.rend(); ++it) {
      auto& cb = *it;
      cb.callback(cb.context1, cb.context2, cb.context3);
    }
    // callbacks have trivial destructors
    abortCallbacks.unsafe_clear();
    commitCallbacks.unsafe_clear();
  }

  void add_commit_callback(Callback func, void *c1, void *c2, void *c3) {
    commitCallbacks.emplace_back(func, c1, c2, c3);
    assert(commitCallbacks.size() == 1);
  }
  void add_abort_callback(Callback func, void *c1, void *c2, void *c3) {
    abortCallbacks.emplace_back(func, c1, c2, c3);
  }

private:
  struct _Callback {
    _Callback(Callback callback, void *context1, void *context2, void *context3) : callback(callback), context1(context1), context2(context2), context3(context3) {}
    Callback callback;
    void *context1;
    void *context2;
    void *context3;
  };

  // we only have 1 commit callback currently
  local_vector<_Callback, 1> commitCallbacks;
  local_vector<_Callback, 16> abortCallbacks;
};

extern Boosting __boostingtransactions[BOOSTING_MAX_THREADS];
#define BOOSTING_T() (__boostingtransactions[boosting_threadid])

#define TRANSACTION \
  do {              \
    while (1) {     \
      boosting_txStartHook(); \
      try {
#define RETRY(retry)                        \
        BOOSTING_T().did_commit();          \
        break;                              \
      } catch(Boosting::Abort e) {}         \
      BOOSTING_T().did_abort();             \
      if (!(retry))                         \
        throw Boosting::Abort();            \
    }                                       \
  } while(0)

#define DO_ABORT() (throw Boosting::Abort())
#define POST_COMMIT(callback, context1, context2, context3) BOOSTING_T().add_commit_callback((callback), (context1), (context2), (context3))
#define ON_ABORT(callback, context1, context2, context3) BOOSTING_T().add_abort_callback((callback), (context1), (context2), (context3))
#endif


<|start_filename|>Vector.hh<|end_filename|>
#pragma once

#include "config.h"
#include "compiler.hh"
#include <iostream>
#include <vector>
#include <map>
#include <string.h>
#include "Transaction.hh"
#include "TArrayProxy.hh"
#include "Box.hh"
#include "rwlock.hh"
#include <stdexcept>

#define IT_SIZE 10000
#define log2(x) ceil(log((double) size) / log(2.0))

template<typename T, bool Opacity = false, typename Elem = Box<T>, bool SmartIterator = true> class Vector;
template<typename T, bool Opacity = false, typename Elem = Box<T>, bool SmartIterator = true> class VecIterator;

template <typename T, bool Opacity, typename Elem, bool SmartIterator>
class Vector : public TObject {
public:
  typedef unsigned index_type;
  
private:
  friend class VecIterator<T, Opacity, Elem, SmartIterator>;
  typedef const Vector<T, Opacity, Elem, SmartIterator> const_vector_type;
  typedef Vector<T, Opacity, Elem, SmartIterator> vector_type;
  
  typedef TransactionTid::type Version;
  
  static constexpr int vector_key = -1;
  static constexpr int push_back_key = -2;
  static constexpr int size_key = -3;
  static constexpr int size_pred_key = -4;
  static constexpr TransItem::flags_type list_bit = TransItem::user0_bit;
  static constexpr TransItem::flags_type delete_bit = TransItem::user0_bit<<1;
  static constexpr int32_t value_shift = 1;
  static constexpr int32_t geq_mask = 1;
public:
  typedef int key_type;
  typedef T value_type;
  typedef value_type get_type;
  
  typedef VecIterator<T, Opacity, Elem, SmartIterator> iterator;
  typedef const VecIterator<T, Opacity, Elem, SmartIterator> const_iterator;
  typedef TArrayProxy<Vector<T, Opacity, Elem, SmartIterator>> proxy_type;
  typedef TConstArrayProxy<Vector<T, Opacity, Elem, SmartIterator>> const_proxy_type;
  typedef int32_t size_type;
  
  
  Vector(): resize_lock_() {
    capacity_ = 0;
    size_ = 0;
    vecversion_ = 0;
    data_ = NULL;
  }
  
  Vector(size_type size): resize_lock_() {
    size_ = 0;
    capacity_ = 1 << ((int) log2(size));
    vecversion_ = 0;
    
    data_ = new Elem[capacity_];
  }
  
  void reserve(size_type new_capacity) {
    if (new_capacity <= capacity_)
      return;
    Elem * new_data = new Elem[new_capacity];
    
    resize_lock_.write_lock();
    for (size_type i = 0; i < capacity_; i++) {
      new_data[i] = data_[i];
    }
    capacity_ = new_capacity;
    if (data_ != NULL)
      Transaction::rcu_delete_array(data_);
    data_ = new_data;
    resize_lock_.write_unlock();
  }
  
  void push_back(const value_type& v) {
    if (trans_size_offs() < 0) {
      // There are some deleted items in the array, we need to overwrite them
      auto item = Sto::item(this, size_ + trans_size_offs());
      if (!item.has_write() || ! has_delete(item)) {
        // some other transaction has pushed items in the mean time, so abort
        Sto::abort();
      } else {
        item.clear_write();
        item.clear_flags(delete_bit);
        item.add_write(v);
        add_trans_size_offs(1);
      }
      return;
    }
    auto item = Sto::item(this, push_back_key);
    if (item.has_write()) {
      if (!is_list(item)) {
        auto& val = item.template write_value<T>();
        std::vector<T> write_list;
        write_list.push_back(val);
        write_list.push_back(v);
        item.clear_write();
        item.add_write(write_list);
        item.add_flags(list_bit);
      }
      else {
        auto& write_list = item.template write_value<std::vector<T>>();
        write_list.push_back(v);
      }
    }
    else {
      item.add_write(v);
      item.clear_flags(list_bit);
    }
    add_lock_vector_item();
    add_trans_size_offs(1);
  }
  void nontrans_push_back(T x) {
    assert(size_ < capacity_);
    data_[size_].write(std::move(x));
    ++size_;
  }
  
  void pop_back() {
    auto item = Sto::item(this, push_back_key);
    if (item.has_write()) {
      if (!is_list(item)) {
        item.clear_write();
        add_trans_size_offs(-1);
        return;
      }
      else {
        /* list */
        auto& write_list= item.template write_value<std::vector<T>>();
        write_list.pop_back();
        if (write_list.size() == 0) item.clear_write();
        add_trans_size_offs(-1);
        return;
      }
    }
    // add vecversion_ to the read set
    auto vecitem = add_vector_version(TransactionTid::unlocked(vecversion_));
    acquire_fence();
    size_type size = size_;
    acquire_fence();
    if (size + trans_size_offs() == 0) {
      // Empty vector, behavior is undefined - so do nothing
    } else {
      // add vecversion_ to the write set as well
      vecitem.add_write(0);
      auto item = Sto::item(this, size_ + trans_size_offs() - 1).add_write(0).add_flags(delete_bit);
      if (item.flags() & Elem::valid_only_bit) {
        item.clear_read();
        item.clear_flags(Elem::valid_only_bit);
      }
      add_trans_size_offs(-1);
    }
  }
  
  iterator erase(iterator pos) {
    iterator end_it = end();
    for (iterator it = pos; it != (end_it - 1); ++it) {
      *(it) = (T) *(it + 1);
    }
    pop_back();
    return pos;
    
  }
  
  iterator insert(iterator pos, const T& value) {
    iterator end_it = end();
    push_back(*(end_it - 1));
    for (iterator it = (end_it - 1); it != pos; --it) {
      *(it) = (T) *(it - 1);
    }
    
    *pos = value;
    return pos;
  }
  
  size_type size() {
    add_vector_version(TransactionTid::unlocked(vecversion_));
    acquire_fence();
    return size_ + trans_size_offs();
  }
  
  bool checkSize(size_type sz) {
    if (!SmartIterator) {
      return size() == sz;
    }
    size_type size = size_;
    int32_t offset = trans_size_offs();
    
    int32_t pred = (sz - offset) << value_shift;
    if (size + offset == sz) {
    } else if (size + offset > sz) {
      pred |= geq_mask;
    } else {
      Sto::abort();
    }
    auto item = Sto::item(this, size_pred_key);
    if (item.has_predicate()) {
      int32_t old_pred = item.template predicate_value<int32_t>();
      // Add the covering predicate of the old predicate and the new one.
      if (pred == old_pred || (old_pred & pred & geq_mask))
        pred = pred >= old_pred ? pred : old_pred;
      else if ((old_pred & geq_mask) && old_pred <= (pred | geq_mask))
      /* OK */;
      else if ((pred & geq_mask) && pred <= (old_pred | geq_mask))
        pred = old_pred;
      else
        Sto::abort();
    }
    item.set_predicate(pred);
    return size + offset == sz;
  }
  
  size_type nontrans_size() const {
    return size_;
  }
  T nontrans_get(key_type i) const {
    assert(i < size_);
    return data_[i].unsafe_read();
  }
  
  proxy_type front() {
    if (size_ + trans_size_offs() == 0)
      Sto::abort();
    return proxy_type(this, 0);
  }
  
  proxy_type back() {
    size_t sz = size();
    if (sz == 0)
      Sto::abort();
    return proxy_type(this, sz - 1);
  }
  
  const_proxy_type operator[](key_type i) const {
    size_type sz = size_ + trans_size_offs();
    if (i >= sz)
      Sto::abort();
    return const_proxy_type(this, i);
  }
  proxy_type operator[](key_type i) {
    size_type sz = size_ + trans_size_offs();
    if (i >= sz)
      Sto::abort();
    return proxy_type(this, i);
  }
  
  value_type transGet(const key_type& i) const {
    Version ver = vecversion_;
    acquire_fence();
    size_type size = size_;
    acquire_fence();
    if (i >= size + trans_size_offs()) {
      Sto::check_opacity(); // TODO: this should also check predicates
      throw std::out_of_range("Vector::transGet");
    }
    if (i < size)
      return data_[i].transRead(Sto::item(this, i));
    else {
      int diff = i - size;
      
      auto extra_items = Sto::item(this, push_back_key);
      // We need to register the vecversion_ to invalidate other concurrent push_backs.
      add_vector_version(TransactionTid::unlocked(ver));
      if (extra_items.has_write()) {
        if (is_list(extra_items)) {
          auto& write_list= extra_items.template write_value<std::vector<T>>();
          if (!write_list.empty()) {
            return write_list[diff];
          }
          else assert(false);
        }
        // not a list, has exactly one element
        else {
          assert(diff == 0);
          return extra_items.template write_value<T>();
        }
      }
      assert(false);
    }
  }
  
  void transUpdate(const key_type& i, value_type v) {
    //std::cout << "Writing to " << i << " with value " << v << std::endl;
    Version ver = vecversion_;
    acquire_fence();
    size_type size = size_;
    acquire_fence();
    if (i >= size + trans_size_offs()) {
      Sto::check_opacity();
      throw std::out_of_range("Vector::transUpdate");
    }
    if (i < size)
      data_[i].transWrite(Sto::item(this, i), std::move(v));
    else {
      int diff = i - size;
      
      auto extra_items = Sto::item(this, push_back_key);
      // We need to register the vecversion_ to invalidate other concurrent push_backs.
      add_vector_version(TransactionTid::unlocked(ver));
      if (extra_items.has_write()) {
        if (is_list(extra_items)) {
          auto& write_list= extra_items.template write_value<std::vector<T>>();
          if (!write_list.empty()) {
            write_list[diff] = v;
          }
          else assert(false);
        }
        // not a list, has exactly one element
        else {
          assert(diff == 0);
          extra_items.clear_write();
          extra_items.add_write(v);
        }
      } else {
        assert(false);
      }
    }
  }
  void transPut(const key_type& i, value_type v) {
    transUpdate(i, v);
  }
  
  static bool is_list(const TransItem& item) {
    return item.flags() & list_bit;
  }
  
  static bool has_delete(const TransItem& item) {
    return item.flags() & delete_bit;
  }
  
  void lock_version(Version& v) {
    TransactionTid::lock(v);
  }
  
  void unlock_version(Version& v) {
    TransactionTid::unlock(v);
  }
  
  bool is_locked(Version& v) const {
    return TransactionTid::is_locked(v);
  }
  
  void lock(key_type i) {
    while(1) {
      resize_lock_.read_lock();
      bool locked = data_[i].try_lock();
      resize_lock_.read_unlock();
      if (locked) break;
    }
  }
  
  void unlock(key_type i) {
    resize_lock_.read_lock();
    data_[i].unlock();
    resize_lock_.read_unlock();
  }
  
  void add_trans_size_offs(int size_offs) {
    // TODO: it would be more efficient to store this directly in Transaction,
    // since the "key" is fixed (rather than having to search the transset each time)
    auto item = Sto::item(this, size_key);
    item.set_stash(item.template stash_value<int>(0) + size_offs);
  }
  
  int trans_size_offs() const {
    return Sto::item(const_cast<Vector<T, Opacity, Elem, SmartIterator>*>(this), size_key).template stash_value<int>(0);
  }
  
  TransProxy vector_item() const {
    // can switch this to fresh_item to not read our writes
    return Sto::item(this, vector_key);
  }
  
  void add_lock_vector_item() {
    vector_item().add_write(0);
  }
  
  TransProxy add_vector_version(Version ver) const {
    return vector_item().add_read(ver);
  }
  
  bool lock(TransItem& item, Transaction&) override {
    if (item.key<int>() == vector_key) {
      lock_version(vecversion_); // TODO: no need to lock vecversion_ if trans_size_offs() is 0
    } else if (item.key<int>() != push_back_key) {
      lock(item.key<key_type>());
    }
    return true;
  }
  
  bool check_predicate(TransItem& item, Transaction&, bool) override {
    assert(item.key<int>() == size_pred_key);
    auto lv = vecversion_;
    if (is_locked(lv))
      return false;
    vector_item().add_read(lv);
    acquire_fence();
    auto size = size_;
    int32_t pred = item.template predicate_value<int32_t>();
    int32_t pred_value = pred >> value_shift;
    if (pred & geq_mask)
      return size >= pred_value;
    else
      return size == pred_value;
  }
  
  bool check(TransItem& item, Transaction&) override {
    if (item.key<int>() == vector_key || item.key<int>() == push_back_key)
      return TransactionTid::check_version(vecversion_, item.template read_value<Version>());
    key_type i = item.key<key_type>();
    assert(i >= 0);
    if (item.flags() & Elem::valid_only_bit) {
      return i < size_ + trans_size_offs()
      && !data_[i].is_locked_elsewhere();
    } else
      return data_[i].check_version(item.template read_value<Version>());
  }
  
  void install(TransItem& item, Transaction& t) override {
    //install value
    if (item.key<int>() == vector_key)
      return;
    if (item.key<int>() == push_back_key) {
      // write all the elements
      if (is_list(item)) {
        auto& write_list = item.template write_value<std::vector<T>>();
        for (size_t i = 0; i < write_list.size(); i++) {
          if (size_ >= capacity_) {
            // Need to resize
            int new_capacity = (capacity_  == 0) ? 1 : capacity_ << 1;
            reserve(new_capacity);
          }
          resize_lock_.read_lock();
          data_[size_].write(write_list[i]);
          acquire_fence();
          size_++;
          resize_lock_.read_unlock();
        }
      }
      else {
        auto& val = item.template write_value<T>();
        if (size_ >= capacity_) {
          // Need to resize
          int new_capacity = (capacity_  == 0) ? 1 : capacity_ << 1;
          reserve(new_capacity);
        }
        resize_lock_.read_lock();
        data_[size_].write(val);
        acquire_fence();
        size_++;
        resize_lock_.read_unlock();
      }
      
      if (Opacity) {
        TransactionTid::set_version(vecversion_, t.commit_tid());
      } else {
        TransactionTid::inc_nonopaque_version(vecversion_);
      }
    } else {
      auto index = item.key<key_type>();
      if (has_delete(item)) {
        if (index < size_) {
          size_ = index;
          
          if (Opacity) {
            TransactionTid::set_version(vecversion_, t.commit_tid());
          } else {
            TransactionTid::inc_nonopaque_version(vecversion_);
          }
        }
      } else if (index >= size_) {
        assert(false);
      }
      
      resize_lock_.read_lock();
      data_[index].install(item, t);
      resize_lock_.read_unlock();
    }
  }
  
  void unlock(TransItem& item) override {
    if (item.key<int>() == vector_key)
      unlock_version(vecversion_);
    else if (item.key<int>() != push_back_key)
      unlock(item.key<key_type>());
  }
  
  void print(std::ostream& w, const TransItem& item) const override {
    w << "{Vector<";
    const char* pf = strstr(__PRETTY_FUNCTION__, "with T = ");
    if (pf) {
      pf += 9;
      const char* semi = strchr(pf, ';');
      w.write(pf, semi - pf);
    }
    w << "> " << (void*) this;
    if (item.key<int>() == size_pred_key) {
      w << ".size" << (item.predicate_value<int32_t>() & geq_mask ? ">=" : "==") << (item.predicate_value<int32_t>() >> value_shift);
    } else {
      if (item.key<int>() == size_key)
        w << ".size";
      else if (item.key<int>() == push_back_key)
        w << ".push_back";
      else if (item.key<int>() == vector_key)
        w << ".vector";
      else {
        w << "[" << item.key<int>() << "]";
        if (has_delete(item))
          w << "XX";
      }
      if (item.has_read())
        w << " ?" << item.read_value<Version>();
      if (item.has_write())
        w << " =" << item.write_value<void*>();
    }
    w << "}";
  }
  
  iterator begin() {
    return iterator(this, 0, false);
  }
  iterator end() {
    //vector_item().add_read(vecversion_);// to invalidate size changes after this call.
    //acquire_fence();
    return iterator(this, 0, true);
  }
  
  // This is not-transactional and only used for debugging purposes
  void print() {
    for (int i = 0; i < nontrans_size(); i++) {
      std::cout << nontrans_get(i) << " ";
    }
    std::cout << std::endl;
  }
  
private:
  size_type size_;
  size_type capacity_;
  Version vecversion_; // for vector size
  rwlock resize_lock_; // to do concurrent resize
  Elem* data_;
  };
  
  
  template<typename T, bool Opacity, typename Elem, bool SmartIterator>
  class VecIterator : public std::iterator<std::random_access_iterator_tag, T> {
  public:
    typedef T value_type;
    typedef Vector<T, Opacity, Elem, SmartIterator> vector_type;
    typedef typename vector_type::proxy_type proxy_type;
    typedef VecIterator<T, Opacity, Elem, SmartIterator> iterator;
    VecIterator() = default;
    VecIterator(Vector<T, Opacity, Elem, SmartIterator> * arr, int ptr, bool endy) : myArr(arr), myPtr(ptr), endy(endy) { }
    VecIterator(const VecIterator& itr) : myArr(itr.myArr), myPtr(itr.myPtr), endy(itr.endy) {}
    
    VecIterator& operator= (const VecIterator& v) {
      myArr = v.myArr;
      myPtr = v.myPtr;
      endy = v.endy;
      return *this;
    }
    
    bool operator==(iterator other) const {
      if (myArr != other.myArr)
        return false;
      else if (endy == other.endy)
        return myPtr == other.myPtr;
      else {
        size_t sz = endy ? other.myPtr - myPtr : myPtr - other.myPtr;
        return myArr->checkSize(sz);
      }
    }
    
    bool operator!=(iterator other) const {
      return !(operator==(other));
    }
    
    proxy_type operator*() {
      return proxy_type(myArr, endy ? myArr->size() + myPtr : myPtr);
    }
    
    proxy_type operator[](int delta) {
      return proxy_type(myArr, (endy ? myArr->size() + myPtr : myPtr) + delta);
    }
    
    /* This is the prefix case */
    iterator& operator++() { ++myPtr; return *this; }
    
    /* This is the postfix case */
    iterator operator++(int) {
      VecIterator<T, Opacity, Elem, SmartIterator> clone(*this);
      ++myPtr;
      return clone;
    }
    
    iterator& operator--() { --myPtr; return *this; }
    
    iterator operator--(int) {
      VecIterator<T, Opacity, Elem, SmartIterator> clone(*this);
      --myPtr;
      return clone;
    }
    
    iterator operator+(int i) {
      VecIterator<T, Opacity, Elem, SmartIterator> clone(*this);
      clone.myPtr += i;
      return clone;
    }
    
    iterator operator-(int i) {
      VecIterator<T, Opacity, Elem, SmartIterator> clone(*this);
      clone.myPtr -= i;
      return clone;
    }
    
    int operator-(const iterator& rhs) {
      assert(rhs.myArr == myArr);
      if (endy == rhs.endy)
        return (myPtr - rhs.myPtr);
      else {
        size_t size = myArr->size();
        if (endy)
          return size + myPtr - rhs.myPtr;
        else
          return myPtr - rhs.myPtr - size;
      }
    }
    
  private:
    Vector<T, Opacity, Elem, SmartIterator> * myArr;
    size_t myPtr;
    bool endy;
  };


<|start_filename|>ht_mt.cc<|end_filename|>
#include <iostream>
#include <assert.h>
#include <stdio.h>

#include "Hashtable.hh"
#include "MassTrans.hh"
#include "Transaction.hh"
#include "simple_str.hh"
#include "randgen.hh"

#define DS 0
#define USE_STRINGS 1

#if DS == 0
#if USE_STRINGS == 1
typedef Hashtable<std::string, std::string, false, 1000000, simple_str> ds;
#else
typedef Hashtable<int, std::string, false, 1000000, simple_str> ds;
#endif
#else
typedef MassTrans<std::string> ds;
#endif

#define NTRANS 5000000
#define NINIT 100000
#define MAX_VALUE NINIT
using namespace std;

std::string value;


void run(ds& h) {
    std::uniform_int_distribution<long> slotdist(0, MAX_VALUE);
    for (int i = 0; i < NTRANS; ++i) {
        auto transseed = i;
        uint32_t seed = transseed*3;// + (uint32_t)me*NTRANS*7 + (uint32_t)GLOBAL_SEED*MAX_THREADS*NTRANS*11;
        auto seedlow = seed & 0xffff;
        auto seedhigh = seed >> 16;
        Rand transgen(seed, seedlow << 16 | seedhigh);
            
        int key = slotdist(transgen);
        std::string value;
#if DS == 0
        TRANSACTION{
#if USE_STRINGS == 1
            std::string s = std::to_string(key);
            h.transGet(s, value);
#else
	    h.transGet(key, value);
#endif
        } RETRY(false);
#else
        TRANSACTION{
#if USE_STRINGS == 1
            std::string s = std::to_string(key);
            h.transGet(s, value);
#else
            h.transGet(key, value);
#endif 
	} RETRY(false);
#endif
    }
    
}


void init(ds& h) {
    for (int i = 0; i < NINIT; ++i) {
        TRANSACTION{
#if USE_STRINGS == 1
            std::string s = std::to_string(i);
            h.transPut(s, value);
#else
	    h.transPut(i, value);
#endif
        } RETRY(false);
    }
    
}


void print_time(struct timeval tv1, struct timeval tv2) {
    printf("%f\n", (tv2.tv_sec-tv1.tv_sec) + (tv2.tv_usec-tv1.tv_usec)/1000000.0);
}

int main() {
    value = std::string('a', 100);
    ds h;
#if DS != 0
    h.thread_init();
#endif
    
    init(h);
    struct timeval tv1,tv2;
    gettimeofday(&tv1, NULL);
    
    run(h);
    
    gettimeofday(&tv2, NULL);
    printf("Time taken: ");
    print_time(tv1, tv2);
}


<|start_filename|>SingleElem.hh<|end_filename|>
#pragma once
#include "Interface.hh"
#include "versioned_value.hh"

template <typename T, bool GenericSTM = false, typename Structure = versioned_value_struct<T>>
// if we're inheriting from TObject then a SingleElem adds both a version word and a vtable word
// (not much else we can do though)
class SingleElem : public TObject {
public:
    T unsafe_read() const {
        return s_.read_value();
    }
    void unsafe_write(T v) {
        s_.set_value(v);
    }
    
    void write(T v) {
        TransactionTid::lock(s_.version());
        s_.set_value(v);
        TransactionTid::set_version_unlock(s_.version(), TransactionTid::next_nonopaque_version(s_.version()));
    }

private:
    typedef TransactionTid::type version_type;

    inline void atomicRead(version_type& v, T& val) const {
        version_type v2;
        do {
            v2 = s_.version();
            if (TransactionTid::is_locked(v2))
              Sto::abort();
            fence();
            val = s_.read_value();
            fence();
            v = s_.version();
        } while (v != v2);
    }

public:
    T transRead() const {
        auto item = Sto::item(this, this);
        if (item.has_write())
            return item.template write_value<T>();
        else {
            version_type v;
            T val;
            atomicRead(v, val);
            if (GenericSTM)
              Sto::check_opacity(v);
            item.add_read(v);
            return val;
        }
    }
    
    /* Overloading cast operation so that we can now directly read values from SingleElem objects */
    operator T() {
        if (Sto::in_progress())
            return transRead();
        else
            return unsafe_read();
    }

    void transWrite(const T& v) {
        Sto::item(this, this).add_write(v);
    }
  
    /* Overloads = operator with transWrite */
    SingleElem& operator= (const T& v) {
        if (Sto::in_progress())
            transWrite(v);
        else
            unsafe_write(v);
        return *this;
    }

    void lock() {
        TransactionTid::lock(s_.version());
    }

    void unlock() {
        TransactionTid::unlock(s_.version());
    }

    bool lock(TransItem& item, Transaction& txn) override {
        return txn.try_lock(item, s_.version());
    }

    bool check(TransItem& item, Transaction&) override {
        return TransactionTid::check_version(s_.version(), item.template read_value<version_type>());
    }

    void install(TransItem& item, Transaction& t) override {
        s_.set_value(item.template write_value<T>());
        if (GenericSTM) {
            TransactionTid::set_version(s_.version(), t.commit_tid());
        } else {
            TransactionTid::inc_nonopaque_version(s_.version());
        }
    }

    void unlock(TransItem&) override {
        unlock();
    }

  protected:
    // we Store the versioned_value inlined (no added boxing)
    Structure s_;
};


<|start_filename|>StringWrapper.hh<|end_filename|>
#pragma once
#include <string>
#include "Packer.hh"

class StringWrapper {
public:
    StringWrapper(std::string& s)
        : sptr_(&s) {
    }
    StringWrapper(const std::string& s)
        : sptr_(const_cast<std::string*>(&s)) {
    }
    std::string* value() const {
        return sptr_;
    }
    operator std::string&() {
        return *sptr_;
    }
    operator const std::string&() const {
        return *sptr_;
    }
private:
    std::string* sptr_;
};

template <>
struct Packer<std::string, false> {
    template <typename... Args>
    static void* pack(TransactionBuffer& buf, Args&&... args) {
        return buf.template allocate<std::string>(std::forward<Args>(args)...);
    }
    static void* pack(TransactionBuffer&, const StringWrapper& wrapper) {
        return wrapper.value();
    }
    static void* pack(TransactionBuffer&, StringWrapper&& wrapper) {
        return wrapper.value();
    }
    static void* pack_unique(TransactionBuffer& buf, const std::string& x) {
        if (const void* ptr = buf.find<UniqueKey<std::string> >(x))
            return const_cast<void*>(ptr);
        else
            return buf.allocate<UniqueKey<std::string> >(x);
    }
    template <typename... Args>
    static void* repack(TransactionBuffer& buf, void*, Args&&... args) {
        return pack(buf, std::forward<Args>(args)...);
    }
    static std::string& unpack(void* x) {
        return *(std::string*) x;
    }
};


<|start_filename|>TaggedLow.hh<|end_filename|>
#pragma once
#include "compiler.hh"

// Tagged pointer which uses lower 3 bits of pointer for tag bits
// (so, requires pointer is one returned by malloc, i.e. 8-byte aligned)
// does not require extra space on 32-bit architectures
template <typename T>
class TaggedLow {
    typedef T* packed_type;
    typedef uintptr_t flags_type;

    static packed_type pack(T* ptr, uint8_t flags) {
        assert(!(reinterpret_cast<flags_type>(ptr) & 7) && !(flags & ~7));
        return reinterpret_cast<packed_type>(reinterpret_cast<flags_type>(ptr) | flags);
    }

  public:
    TaggedLow(T* ptr, uint8_t flags)
        : p_(pack(ptr, flags)) {
    }

    operator T*() {
        return (T*) ptr();
    }

    operator const T*() const {
        return ptr();
    }

    const T* ptr() const {
        return reinterpret_cast<T*>(reinterpret_cast<flags_type>(p_) & ~flags_type(7));
    }

    uint8_t flags() const {
        return reinterpret_cast<flags_type>(p_) & 7;
    }

    void assign_ptr(T* ptr) {
        fence();
        p_ = reinterpret_cast<packed_type>(reinterpret_cast<flags_type>(ptr) | flags());
    }

    void assign_flags(uint8_t flags) {
        assert((flags & ~7) == 0);
        fence();
        p_ = reinterpret_cast<packed_type>((reinterpret_cast<flags_type>(p_) & ~flags_type(7)) | flags);
    }

    void or_flags(uint8_t flags) {
        assert((flags & ~7) == 0);
        fence();
        p_ = reinterpret_cast<packed_type>(reinterpret_cast<flags_type>(p_) | flags);
    }

    void atomic_add_flags(uint8_t flags) {
        assert((flags & ~7) == 0);
        while (1) {
            auto cur = reinterpret_cast<flags_type>(p_);
            fence();
            if ((cur & flags) == 0 && bool_cmpxchg(&p_, reinterpret_cast<packed_type>(cur),
                                                   reinterpret_cast<packed_type>(cur | flags))) {
                break;
            }
            relax_fence();
        }
    }

  private:
    T* p_;
};


<|start_filename|>stuffed_str.hh<|end_filename|>
#pragma once
#include "string_base.hh"

template <typename Stuff>
class stuffed_str {
public:
  typedef Stuff stuff_type;

  struct StandardMalloc {
    void *operator()(size_t s) {
      return malloc(s);
    }
  };

  template <typename Malloc = StandardMalloc>
  static stuffed_str* make(const char *str, int len, int capacity, const Stuff& val, Malloc m = Malloc()) {
    // TODO: it might be better if we just take the max of size_for() and capacity
    assert(size_for(len) <= capacity);
    //    printf("%d from %lu\n", alloc_size, len + sizeof(stuffed_str));
    auto vs = (stuffed_str*)m(capacity);
    new (vs) stuffed_str(val, len, capacity - sizeof(stuffed_str), str);
    return vs;
  }

  template <typename Malloc = StandardMalloc>
  static stuffed_str* make(const std::string& s, const Stuff& val, Malloc m = Malloc()) {
    return make(s.data(), s.length(), size_for(s.length()), val, m);
  }

  template <typename Str, typename Malloc = StandardMalloc>
  static stuffed_str* make(const lcdf::String_base<Str>& s, const Stuff& val, Malloc m = Malloc()) {
    return make(s.data(), s.length(), size_for(s.length()), val, m);
  }

  static unsigned pad(unsigned v)
  {
    if (likely(v <= 512)) {
      return (v + 15) & ~15;
    }
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
#if UINT_MAX == UINT64_MAX
    v |= v >> 32;
#endif
    v++;
    return v;
  }

  static inline int size_for(int len) {
    return pad(len + sizeof(stuffed_str));
  }

  bool needs_resize(int len) {
    return len > (int)capacity_;
  }

  template <typename Malloc = StandardMalloc>
  stuffed_str* reserve(int len, Malloc m = Malloc()) {
    if (likely(!needs_resize(len))) {
      return this;
    }
    return stuffed_str::make(buf_, size_, len, stuff_, m);
  }

  // returns NULL if replacement could happen without a new malloc, otherwise returns new stuffed_str*
  // malloc should be a functor that takes a size and returns a buffer of that size
  template <typename Malloc = StandardMalloc>
  stuffed_str* replace(const char *str, int len, Malloc m = Malloc()) {
    if (likely(!needs_resize(len))) {
      size_ = len;
      memcpy(buf_, str, len);
      return this;
    }
    return stuffed_str::make(str, len, size_for(len), stuff_, m);
  }

  const char *data() {
    return buf_;
  }
  
  int length() {
    return size_;
  }
  
  int capacity() {
    return capacity_;
  }

  Stuff& stuff() {
    return stuff_;
  }

  Stuff stuff() const {
    return stuff_;
  }

private:
  stuffed_str(const Stuff& stuff, uint32_t size, uint32_t capacity, const char *buf) :
    stuff_(stuff), size_(size), capacity_(capacity) {
    memcpy(buf_, buf, size);
  }

  Stuff stuff_;
  uint32_t size_;
  uint32_t capacity_;
  char buf_[0];
};


<|start_filename|>Boosting.cc<|end_filename|>
#include "Boosting_tl2.hh"
#include "Boosting_standalone.hh"

boosting_threadinfo boosting_threads[BOOSTING_MAX_THREADS];
__thread int boosting_threadid;

void boosting_txStartHook() {
  POST_COMMIT(boosting_releaseLocksCallback, NULL, NULL, NULL);
  // XXX: this needs to exec last. We do this by having boosting execute callbacks in revers order
  ON_ABORT(boosting_releaseLocksCallback, NULL, NULL, NULL);
}

void boosting_setThreadID(int threadid) {
  boosting_threadid = threadid;
}

void boosting_releaseLocksCallback(void*, void*, void*) {
  for (auto *lock : _thread().lockset) {
    lock->unlock();
  }
  for (auto *rwlockp : _thread().rwlockset) {
    auto& rwlock = *rwlockp;
    if (rwlock.isWriteLocked()) {
      rwlock.writeUnlock();
    } else {
      rwlock.readUnlock();
    }
  }

  _thread().lockset.unsafe_clear();
  _thread().rwlockset.unsafe_clear();
}

void transReadLock(RWLock *lock) {
  if (!_thread().rwlockset.exists(lock)) {
    if (!lock->tryReadLock(READ_SPIN)) {
      DO_ABORT();
      return;
    }
    _thread().rwlockset.push(lock);
  }
}

void transWriteLock(RWLock *lock) {
  if (!_thread().rwlockset.exists(lock)) {
    // don't have the lock in any form yet
    if (!lock->tryWriteLock(WRITE_SPIN)) {
      DO_ABORT();
      return;
    }
    _thread().rwlockset.push(lock);
  } else {
    // only have a read lock so far
    if (!lock->isWriteLocked()) {
      if (!lock->tryUpgrade(WRITE_SPIN)) {
        DO_ABORT();
      }
    }
  }
}


<|start_filename|>srandomdev.c<|end_filename|>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/time.h>

#if __cplusplus__
extern "C" {
#endif
void srandomdev(void) {
    unsigned seed;
    size_t n = 0;
    FILE* f = fopen("/dev/urandom", "r");
    if (f) {
        n = fread(&seed, sizeof(seed), 1, f);
        fclose(f);
    }
    if (!n) {
        struct timeval tv;
        gettimeofday(&tv, NULL);
        seed = (getpid() ^ tv.tv_sec) + tv.tv_usec;
    }
    srandom(seed);
}
#if __cplusplus__
}
#endif


<|start_filename|>TransAlloc.hh<|end_filename|>
#pragma once
#include "config.h"
#include "compiler.hh"
#include "Interface.hh"
#include "Transaction.hh"

class TransAlloc : public TObject {
public:
    static constexpr TransItem::flags_type alloc_flag = TransItem::user0_bit;
    typedef void (*free_type)(void*);

    // used to free things only if successful commit
    void transFree(void *ptr) {
        Sto::new_item(this, ptr).template add_write<free_type, free_type>(::free);
    }

    // malloc() which will be freed on abort
    void* transMalloc(size_t sz) {
        void *ptr = malloc(sz);
        Sto::new_item(this, ptr).template add_write<free_type, free_type>(::free).add_flags(alloc_flag);
        return ptr;
    }

    // delete which only applies if transaction commits
    template <typename T>
    void transDelete(T *x) {
        Sto::new_item(this, x).template add_write<free_type, free_type>(&ObjectDestroyer<T>::destroy_and_free);
    }

    // new which will be delete'd on abort.
    // arguments go to T's constructor
    template <typename T, typename... Args>
    T* transNew(Args&&... args) {
        T* x = new T(std::forward<Args>(args)...);
        Sto::new_item(this, x).template add_write<free_type, free_type>(&ObjectDestroyer<T>::destroy_and_free).add_flags(alloc_flag);
        return x;
    }

    bool lock(TransItem&, Transaction&) override { return true; }
    bool check(TransItem&, Transaction&) override { return false; }
    void install(TransItem&, Transaction&) override {}
    void unlock(TransItem&) override {}
    void cleanup(TransItem& item, bool committed) override {
        if (committed == !item.has_flag(alloc_flag))
	  Transaction::rcu_call(item.write_value<free_type>(), item.key<void*>());
    }
    void print(std::ostream& w, const TransItem& item) const override {
        w << "{TransAlloc @" << item.key<void*>();
        if (item.write_value<int>())
            w << ".alloc}";
        else
            w << ".free}";
    }
};


<|start_filename|>TransUndoable.hh<|end_filename|>
#pragma once

#include "Transaction.hh"

class TransUndoable : public TObject {
public:
  typedef void (*UndoFunction)(void*, void*, void*);
  void add_undo(UndoFunction undo_func, void *context1, void *context2) {
    // abusing semantics a bit here: technically there *could* be duplicates, but we're only
    // using this item for cleanup; duplicates shouldn't affect anything.
    // best solution is probably to have only one item for this and stuff everything in there.
    auto item = Sto::new_item(this, undo_func);
    item.set_stash(context1);
    item.add_write(context2);
  }

  // TODO: would be nice to have an add_undo that takes a std::function or something too.


  bool lock(TransItem&, Transaction&) override { return true; }
  void unlock(TransItem&) override {}
  bool check(const TransItem&, const Transaction&) override { return false; }
  void install(TransItem&, const Transaction&) override {}
  void cleanup(TransItem& item, bool committed) override {
    if (!committed) {
      auto undo_func = item.key<UndoFunction>();
      undo_func(this, item.stash_value<void*>(), item.write_value<void*>());
    }
  }
};


<|start_filename|>unit-tintpredicate.cc<|end_filename|>
#undef NDEBUG
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include "Transaction.hh"
#include "TIntPredicate.hh"
#include "StringWrapper.hh"
#include "TBox.hh"

void testTrivial() {
	TIntPredicate<int> ip;

    {
        TransactionGuard t;
        ip = 1;
    }

	{
        TransactionGuard t;
        int i_read = ip;
        assert(i_read == 1);
    }

	printf("PASS: %s\n", __FUNCTION__);
}

void testSimpleRangesOk() {
    TIntPredicate<int> ip;
    TBox<int> box;
    bool match;

    {
        TestTransaction t1(1);
        match = ip < 3;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 1;
        assert(t2.try_commit());
        assert(t1.try_commit());
    }

    {
        TestTransaction t1(1);
        match = ip < 0;
        assert(!match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 0;
        assert(t2.try_commit());
        assert(t1.try_commit());
    }

    {
        TestTransaction t1(1);
        match = ip > -1;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = -1;
        assert(t2.try_commit());
        assert(!t1.try_commit());
    }

    {
        TestTransaction t1(1);
        match = ip > 0;
        assert(!match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 0;
        assert(t2.try_commit());
        assert(t1.try_commit());
    }

    {
        TestTransaction t1(1);
        match = ip >= 0;
        assert(match);
        match = ip < 4;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 3;
        assert(t2.try_commit());
        assert(t1.try_commit());
    }

    {
        TestTransaction t1(1);
        match = ip >= 0;
        assert(match);
        match = ip < 4;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = -1;
        assert(t2.try_commit());
        assert(!t1.try_commit());
    }

    ip.nontrans_write(3);

    {
        TestTransaction t1(1);
        match = ip >= 0;
        assert(match);
        match = ip < 4;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 4;
        assert(t2.try_commit());
        assert(!t1.try_commit());
    }

    {
        TestTransaction t1(1);
        match = ip > -4;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = -1;
        assert(t2.try_commit());
        assert(t1.try_commit());
    }

    ip.nontrans_write(1);

    {
        TestTransaction t1(1);
        match = ip == 1;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 2;
        assert(t2.try_commit());

        TestTransaction t3(2);
        ip = 1;
        assert(t3.try_commit());

        assert(t1.try_commit());
    }

    printf("PASS: %s\n", __FUNCTION__);
}

void testSimpleRangesFail() {
    TIntPredicate<int> ip;
    TBox<int> box;
    bool match;

    {
        TestTransaction t1(1);
        match = ip < 3;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 5;
        assert(t2.try_commit());

        assert(!t1.try_commit());
    }

    ip.nontrans_write(0);

    {
        TestTransaction t1(1);
        match = ip < 3;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 5;
        assert(t2.try_commit());

        t1.use();
        match = ip > 1;
        // XXX we are actually able to abort here, but don't, because there
        // *does* exist an eventual value that satisfies all constraints (2)
        assert(!t1.try_commit());
    }

    ip.nontrans_write(0);

    {
        TestTransaction t1(1);
        match = ip < 3;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 5;
        assert(t2.try_commit());

        t1.use();
        match = ip > 1;
        // XXX we are actually able to abort here, but don't, because there
        // *does* exist an eventual value that satisfies all constraints (2).
        // It would probably be better to abort.
        assert(match);

        TestTransaction t3(2);
        ip = 2;
        assert(t3.try_commit());
        assert(t1.try_commit());
    }

    ip.nontrans_write(4);

    try {
        TestTransaction t1(1);
        match = ip > 1;
        assert(match);
        box = 9; /* avoid read-only txn */

        TestTransaction t2(2);
        ip = 0;
        assert(t2.try_commit());

        t1.use();
        match = ip < 1;
        assert(false && "should not get here");
        assert(!t1.try_commit());
    } catch (Transaction::Abort e) {
    }

    printf("PASS: %s\n", __FUNCTION__);
}

int main() {
    assert((mass::is_trivially_copyable<TIntPredicate<int>::pred_type>::value));
    assert((mass::is_trivially_copyable<TVersion>::value));
    assert((mass::is_trivially_copyable<TNonopaqueVersion>::value));

    // some assertions about TransactionBuffer
    {
        TransactionBuffer buf;
        void* v1 = Packer<uintptr_t>::pack(buf, 12938);
        void* v2 = Packer<uintptr_t>::pack_unique(buf, 12938);
        void* v3 = Packer<uintptr_t>::pack(buf, 12938);
        void* v4 = Packer<uintptr_t>::pack_unique(buf, 12938);
        assert(v1 == v2 && v2 == v3 && v3 == v4 && v4 == (void*) (uintptr_t) 12938);
        assert(Packer<uintptr_t>::unpack(v1) == 12938);
        assert(Packer<uintptr_t>::unpack(v2) == 12938);
        assert(Packer<uintptr_t>::unpack(v3) == 12938);
        assert(Packer<uintptr_t>::unpack(v4) == 12938);

        v1 = Packer<std::string>::pack(buf, "Hello");
        v2 = Packer<std::string>::pack_unique(buf, "Hello");
        v3 = Packer<std::string>::pack(buf, "Hello2");
        v4 = Packer<std::string>::pack_unique(buf, "Hello2");
        void* v5 = Packer<std::string>::pack(buf, "Hello");
        void* v6 = Packer<std::string>::pack_unique(buf, "Hello");
        assert(v1 != v2 && v1 != v5 && v2 != v5 && v1 != v6 && v5 != v6);
        assert(v2 == v6);
        assert(Packer<std::string>::unpack(v1) == "Hello");
        assert(Packer<std::string>::unpack(v2) == "Hello");
        assert(Packer<std::string>::unpack(v3) == "Hello2");
        assert(Packer<std::string>::unpack(v4) == "Hello2");
        assert(Packer<std::string>::unpack(v5) == "Hello");
        assert(Packer<std::string>::unpack(v6) == "Hello");

        std::string hello("Hello");
        void* v7 = Packer<std::string>::pack(buf, StringWrapper(hello));
        assert(v7 == &hello);
    }


    testTrivial();
    testSimpleRangesOk();
    testSimpleRangesFail();
    return 0;
}


<|start_filename|>Testers.hh<|end_filename|>
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include <random>
#include <map>
#include "Transaction.hh"
#include "PriorityQueue.hh"
#include "Hashtable.hh"
#include "RBTree.hh"
#include "Vector.hh"

#define MAX_VALUE 10 // Max value of integers used in data structures
#define PRINT_DEBUG 1 // Set this to 1 to print some debugging statements

struct Rand {
    typedef uint32_t result_type;
    
    result_type u, v;
    Rand(result_type u, result_type v) : u(u|1), v(v|1) {}
    
    inline result_type operator()() {
        v = 36969*(v & 65535) + (v >> 16);
        u = 18000*(u & 65535) + (u >> 16);
        return (v << 16) + u;
    }
    
    static constexpr result_type max() {
        return (uint32_t)-1;
    }
    
    static constexpr result_type min() {
        return 0;
    }
};

struct op_record {
    // Keeps track of a transactional operation, arguments used, and any read data.
    int op;
    std::vector<int> args;
    std::vector<int> rdata;
};

struct txn_record {
    // keeps track of operations in a single transaction
    std::vector<op_record*> ops;
};

template <typename T>
struct TesterPair {
    T* t;
    int me;
};

std::vector<std::map<uint64_t, txn_record *> > txn_list;

typedef TransactionTid::type Version;
Version lock;

template <typename DT, typename RT>
class Tester {
public: 
    virtual ~Tester() {}
    // initialize the data structures
    // structure under test
    virtual void init_sut(DT* q) = 0;
    // reference structure
    virtual void init_ref(RT* q) = 0;
    // Perform a particular operation on the data structure.    
    virtual op_record* doOp(DT* q, int op, int me, std::uniform_int_distribution<long> slotdist, Rand transgen) = 0 ;
    // Redo a operation. This is called during serial execution.
    virtual void redoOp(RT* q, op_record *op) = 0;
    // Checks that final state of the two data structures are the same.
    virtual void check(DT* q, RT* q1) = 0;
#if PRINT_DEBUG
    // Print stats for each data structure
    //void print_stats(T* q) {};
#endif
};

template <typename DT, typename RT>
class RBTreeTester: Tester<DT, RT> {
public:
    template <typename T>
    void init(T* q) {
        for (int i = 0; i < MAX_VALUE; i++) {
            TRANSACTION {
                (*q)[i] = i;
            } RETRY(false);
        }
    }

    void init_sut(DT* q) {init<DT>(q);}
    void init_ref(RT* q) {init<RT>(q);}

    op_record* doOp(DT* q, int op, int me, std::uniform_int_distribution<long> slotdist, Rand transgen) {
#if !PRINT_DEBUG
        (void)me;
#endif
        int key = slotdist(transgen);
        if (op == 0) {
            int val = slotdist(transgen);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to operator[] key " << key << " and val " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            (*q)[key] = val;
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] insert key " << key << " and val " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(key);
            rec->args.push_back(val);
            return rec;
        } else if (op == 1) {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to erase " << key<< std::endl;
            TransactionTid::unlock(lock);
#endif
            int num = q->erase(key);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] erased " << num << " items with key " << key << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(key);
            rec->rdata.push_back(num);
            return rec;
        } else if (op == 2) {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to count " << key << std::endl;
            TransactionTid::unlock(lock);
#endif
            int num = q->count(key);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] counted " << num << " items with key " << key << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(key);
            rec->rdata.push_back(num);
            return rec;
        } else if (op == 3) {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to size" << std::endl;
            TransactionTid::unlock(lock);
#endif
            size_t size = q->size();
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] size " << size << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->rdata.push_back(size);
            return rec;
        } /*else if (op == 4) {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to iterator* start" << std::endl;
            TransactionTid::unlock(lock);
#endif
            if (q->size() == 0) {
#if PRINT_DEBUG
                TransactionTid::lock(lock);
                std::cout << "[" << me << "] tried to *start empty tree" << std::endl;
                TransactionTid::unlock(lock);
#endif
                op_record* rec = new op_record;
                rec->op = op;
                rec->rdata.push_back(-1);
                return rec;
            }
            auto it = q->begin();
            int val = it->second;
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] found value " << val << " at start" << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->rdata.push_back(val);
            return rec;
        } else if (op == 5) {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to iterator* --end" << std::endl;
            TransactionTid::unlock(lock);
#endif
            if (q->size() == 0) {
#if PRINT_DEBUG
                TransactionTid::lock(lock);
                std::cout << "[" << me << "] tried to -- empty tree" << std::endl;
                TransactionTid::unlock(lock);
#endif
                op_record* rec = new op_record;
                rec->op = op;
                rec->rdata.push_back(-1);
                return rec;
            }
            auto it = --(q->end());
            int val = it->second;
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] found value " << val << " at end" << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->rdata.push_back(val);
            return rec;
        } else if (op == 6) {
            int forward = slotdist(transgen);
            int backward = slotdist(transgen);
            backward = (forward < backward) ? forward : backward;
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to * " << forward << " forward and " << backward << " backward" << std::endl;
            TransactionTid::unlock(lock);
#endif
            auto it = q->begin();
            if (q->size() == 0) {
#if PRINT_DEBUG
                TransactionTid::lock(lock);
                std::cout << "[" << me << "] tried to iterate empty tree" << std::endl;
                TransactionTid::unlock(lock);
#endif
                op_record* rec = new op_record;
                rec->op = op;
                rec->rdata.push_back(-1);
                return rec;
            }
            for (int i = 0; i <= forward && it != q->end(); i++, it++) {}
            for (int i = backward; i > 0 && it != q->begin(); i--, it--) {}
            if (it == q->end()) {
                it = q->begin();
                assert(it != q->end());
#if PRINT_DEBUG
                TransactionTid::lock(lock);
                std::cout << "[" << me << "] \t iterator was at end" << std::endl;
                TransactionTid::unlock(lock);
#endif
            }
            int val = it->second;
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] found value " << val << " @ " << forward << " - " << backward<< std::endl;
            TransactionTid::unlock(lock);
#endif
            // comment block start
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] redoing "<<  forward << " forward and " << backward << " backward with prefix"<< std::endl;
            TransactionTid::unlock(lock);
#endif
            auto it2 = q->begin();
            tmp = it2;
            for (int i = 0; i <= forward && it2 != q->end(); i++, ++it2) {
                tmp = it2;
            }

            for (int i = backward; i > 0 && it2 != q->begin(); i--, --it2) {
                tmp = it2;
            }
            int val2 = *tmp;
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] found value2 " << val2 << " @ " << forward << " - " << backward << std::endl;
            TransactionTid::unlock(lock);
#endif
            assert(val == val2);
            // comment block end
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(forward);
            rec->args.push_back(backward);
            rec->rdata.push_back(val);
            return rec;
        }*/
        return nullptr;
    }

    void redoOp(RT* q, op_record *op) {
        if (op->op == 0) {
            int key = op->args[0];
            int val = op->args[1];
            (*q)[key] = val;
#if PRINT_DEBUG
            std::cout << "inserting: " << key << ", " << val << std::endl;
#endif
        } else if (op->op == 1) {
            int key = op->args[0];
            int erased = q->erase(key);
#if PRINT_DEBUG
            std::cout << "erasing: " << key << std::endl;
            std::cout << "erase replay: " << erased << std::endl;
            std::cout << "erase expected: " << op->rdata[0] << std::endl;
#endif
            assert (erased == op->rdata[0]);
        } else if (op->op == 2) {
            int key = op->args[0];
            int counted = q->count(key);
#if PRINT_DEBUG
            std::cout << "counting: " << key << std::endl;
            std::cout << "count replay: " << counted << std::endl;
            std::cout << "count expected: " << op->rdata[0] << std::endl;
#endif
            assert(counted == op->rdata[0]);
        } else if (op->op == 3) {
            size_t size = q->size();
#if PRINT_DEBUG
            std::cout << "size replay: " << size << std::endl;
            std::cout << "size expected: " << op->rdata[0] << std::endl;
#endif
            assert(size == (size_t) op->rdata[0]);
        } /*else if (op->op == 4) {
            if (q->size() == 0) {
                assert(op->rdata[0] == -1);
                return;
            }
            auto it = q->begin();
            int val = it->second;
#if PRINT_DEBUG
            std::cout << "*it start replay: " << val << std::endl;
            std::cout << "*it start expected: " << op->rdata[0]  << std::endl;
#endif
            assert(val == op->rdata[0]);
        } else if (op->op == 5) {
            auto it = q->end();
            // deal with empty tree end()
            if (q->size() == 0) {
                assert(op->rdata[0] == -1);
                return;
            }
            auto val1 = (--it)->second;
            assert(++it == q->end());
            it--;
            auto val2 = it->second;
#if PRINT_DEBUG
            std::cout << "*it end-1 replay: " << val1 << std::endl;
            std::cout << "*it end-1 expected: " << op->rdata[0]  << std::endl;
#endif
            assert(val1 == val2);
            assert(val1 == op->rdata[0]);
        } else if (op->op == 6) {
            auto it = q->begin();
            // deal with empty tree begin()
            if (q->size() == 0) {
                assert(op->rdata[0] == -1);
                return;
            }
            int forward = op->args[0];
            int backward = op->args[1];
            for (int i = 0; i <= forward && it != q->end(); i++, it++) {}
            for (int i = backward; i > 0 && it != q->begin(); i--, it--) {}
            if (it == q->end()) it = q->begin();
            int val = it->second;
#if PRINT_DEBUG
            std::cout << "*it replay at place " << forward << " - " << backward << ": " << val << std::endl;
            std::cout << "*it expected at place " << forward << " - " << backward << ": " << op->rdata[0]  << std::endl;
#endif
            assert(val == op->rdata[0]);
        }*/
    }

    void check(DT* q, RT*q1) {
        for (int i = 0; i < MAX_VALUE; i++) {
#if PRINT_DEBUG
            std::cout << "i is: " << i << std::endl;
#endif
            TRANSACTION {
/*
                if (q->size() != 0) {
                    auto it = q->begin();
                    auto it1 = q1->begin();
                    for (; (it != q->end() || it1 != q1->end()); it++, it1++) {
                        assert(it->second == it1->second);
                    }
                }
*/
                size_t s = q->size();
                size_t s1 = q1->size();
#if PRINT_DEBUG
                std::cout << "q size: " << std::endl;
                std::cout << "q1 size: " << s1 << std::endl;
#endif
                assert(s == s1);
                size_t c = q->count(i);
                size_t c1 = q1->count(i);
#if PRINT_DEBUG
                std::cout << "q count: " << c << std::endl;
                std::cout << "q1 count: " << c1 << std::endl;
#endif
                assert(c == c1);
                int v1 = (*q)[i];
                int v2 = (*q1)[i];
#if PRINT_DEBUG
                std::cout << "v1: " << v1 << std::endl;
                std::cout << "v2: " << v2 << std::endl;
#endif
                assert(v1 == v2);

                s = q->size();
                s1 = q1->size();
#if PRINT_DEBUG
                std::cout << "q size: " << s << std::endl;
                std::cout << "q1 size: " << s1 << std::endl;
#endif
                assert(s == s1);

                // this should always return 1 because we inserted an empty element if it
                // did not exist before
                size_t e = q->erase(i);
                size_t e1 = q1->erase(i);
#if PRINT_DEBUG
                std::cout << "q erased: " << e << std::endl;
                std::cout << "q1 erased: " << e1 << std::endl;
#endif
                assert(e == e1);
            } RETRY(false);
        }
        TRANSACTION {
            for (int i = 0; i < MAX_VALUE; i++) {
                assert(q->count(i) == 0);
            }
        } RETRY(false);
    }

#if PRINT_DEBUG
    void print_stats(DT* q) {
        (void)q;
        //q->print_absent_reads();
    }
#endif

    static const int num_ops_ = 4;
};

/*
template <typename T>
class PqueueTester : Tester<T> {
public:
    void init(T* q) {
        for (int i = 0; i < 10000; i++) {
            TRANSACTION {
                q->push(i);
            } RETRY(false);
        }
    }

    op_record* doOp(T* q, int op, int me, std::uniform_int_distribution<long> slotdist, Rand transgen) {
#if !PRINT_DEBUG
        (void)me;
#endif
        if (op == 0) {
            int val = slotdist(transgen);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to push " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            q->push(val);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] pushed " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(val);
            return rec;
        } else if (op == 1) {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to pop " << std::endl;
            TransactionTid::unlock(lock);
#endif
            int val = q->pop();
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] popped " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->rdata.push_back(val);
            return rec;
        } else {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to read " << std::endl;
            TransactionTid::unlock(lock);
#endif
            int val = q->top();
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] read " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->rdata.push_back(val);
            return rec;
        }
    }

    void redoOp(T* q, op_record *op) {
        if (op->op == 0) {
            int val = op->args[0];
            q->push(val);
        } else if (op->op == 1) {
            int val = q->pop();
            assert(val == op->rdata[0]);
        } else {
            int val = q->top();
            assert(val == op->rdata[0]);
        }
    }

    void check(T* q, T*q1) {
        int size = q1->size();
        for (int i = 0; i < size; i++) {
            TRANSACTION {
                int v1 = q->top();
                int v2 = q1->top();
                //std::cout << v1 << " " << v2 << std::endl;
                if (v1 != v2)
                    q1->print();
                assert(v1 == v2);
                assert(q->pop() == v1);
                assert(q1->pop() == v2);
            } RETRY(false);
        }
        TRANSACTION {
            q->print();
            assert(q->top() == -1);
            //q1.print();
        } RETRY(false);
    }

    static const int num_ops_ = 3;
};

template <typename T>
class HashtableTester : Tester<T> {
public:
    void init(T* q) {
        for (int i = 0; i < 10000; i++) {
            TRANSACTION {
                q->transPut(i, i);
            } RETRY(false);
        }
    }

    op_record* doOp(T* q, int op, int me, std::uniform_int_distribution<long> slotdist, Rand transgen) {
#if !PRINT_DEBUG
        (void)me;
#endif
        if (op == 0) {
            int key = slotdist(transgen);
            int val = slotdist(transgen);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to put " << key << ", " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            bool present = q->transPut(key, val);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] put " << key << "," << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(key);
            rec->args.push_back(val);
            rec->rdata.push_back(present);
            return rec;
        } else if (op == 1) {
            int key = slotdist(transgen);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to get " << key << std::endl;
            TransactionTid::unlock(lock);
#endif
            int val;
            bool present = q->transGet(key, val);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] read " << key << ", " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(key);
            rec->rdata.push_back(val);
            rec->rdata.push_back(present);
            return rec;
        } else {
            int key = slotdist(transgen);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to delete " << key << std::endl;
            TransactionTid::unlock(lock);
#endif
            bool success = q->transDelete(key);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] deleted " << key << ", " << success << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(key);
            rec->rdata.push_back(success);
            return rec;
        }
    }

    void redoOp(T* q, op_record* op) {
        if (op->op == 0) {
            int key = op->args[0];
            int val = op->args[1];
            bool present = q->transPut(key, val);
            assert(present == op->rdata[0]);
        } else if (op->op == 1) {
            int key = op->args[0];
            int val;
            bool present = q->transGet(key, val);
            assert(present == op->rdata[1]);
            if (present)
                assert(val == op->rdata[0]);
        } else {
            int key = op->args[0];
            bool success = q->transDelete(key);
            assert(success == op->rdata[0]);
        }
    }

    void check(T* q, T*q1) {
        for (int i = 0; i < MAX_VALUE; i++) {
            TRANSACTION {
                int v1;
                bool p1 = q->transGet(i, v1);
                int v2;
                bool p2 = q1->transGet(i, v2);
                assert(p1 == p2);
                if (p1) {
                    assert(v1 == v2);
                }
            } RETRY(false);
        }
    }
    
#if PRINT_DEBUG
    void print_stats(T* q) {
       
    }
#endif

    static const int num_ops_ = 3;
};

template <typename T>
class VectorTester : Tester<T> {
public:
    void init(T* q) {
        for (int i = 0; i < 1000; i++) {
            TRANSACTION {
                q->push_back(i);
            } RETRY(false);
        }
    }
    
    op_record* doOp(T* q, int op, int me, std::uniform_int_distribution<long> slotdist, Rand transgen) {
#if !PRINT_DEBUG
        (void)me;
#endif
        if (op == 0) {
            int key = slotdist(transgen);
            int val = slotdist(transgen);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to update " << key << ", " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            bool outOfBounds = false;
            try {
            q->transUpdate(key, val);
            } catch (const std::out_of_range& e) {
                outOfBounds = true;
            }
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] update " << !outOfBounds << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(key);
            rec->args.push_back(val);
            rec->rdata.push_back(outOfBounds);
            return rec;
        } else if (op == 1) {
            int key = slotdist(transgen);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to read " << key << std::endl;
            TransactionTid::unlock(lock);
#endif
            int val;
            bool outOfBounds = false;
            try {
            val = q->transGet(key);
            } catch (std::out_of_range& e) {
                outOfBounds = true;
            }
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] read (" << !outOfBounds << ") " << key << ", " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(key);
            rec->rdata.push_back(val);
            rec->rdata.push_back(outOfBounds);
            return rec;
        } else if (op == 2) {
            int val = slotdist(transgen);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to push " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            q->push_back(val);
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] pushed " << val  << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->args.push_back(val);
            return rec;
        } else if (op == 3) {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try to pop " << std::endl;
            TransactionTid::unlock(lock);
#endif
            int val;
            int sz = q->size();
            if (sz > 0) {
              val = q->transGet(sz - 1);
              q->pop_back();
            }
            
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] popped "  << sz-1 << " " << val << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->rdata.push_back(val);
            rec->rdata.push_back(sz > 0);
            return rec;

        } else {
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] try size " << std::endl;
            TransactionTid::unlock(lock);
#endif
            int sz = q->size();
#if PRINT_DEBUG
            TransactionTid::lock(lock);
            std::cout << "[" << me << "] size "  << sz << std::endl;
            TransactionTid::unlock(lock);
#endif
            op_record* rec = new op_record;
            rec->op = op;
            rec->rdata.push_back(sz);
            return rec;

        }
    }
    
    void redoOp(T* q, op_record* op) {
        if (op->op == 0) {
            int key = op->args[0];
            int val = op->args[1];
            int size = q->size();
            if (op->rdata[0]) { assert(key >= size); return; }
            assert(key < size);
            q->transUpdate(key, val);
        } else if (op->op == 1) {
            int key = op->args[0];
            int size = q->size();
            if (op->rdata[1]) { assert(key >= size); return; }
            assert(key < size);
            int val = q->transGet(key);
            assert(val == op->rdata[0]);
        } else if (op->op == 2){
            int val = op->args[0];
            q->push_back(val);
        } else if (op->op == 3) {
            int size = q->size();
            if (!op->rdata[1]) { assert(size == 0); return;}
            assert(size > 0);
            assert(q->transGet(size - 1) == op->rdata[0]);
            q->pop_back();
        } else {
            assert(q->size() == op->rdata[0]);
        }
    }
    
    void check(T* q, T*q1) {
        int size;
        TRANSACTION {
            size = q->size();
            assert(size == q1->size());
        } RETRY(false);
        for (int i = 0; i < size; i++) {
            TRANSACTION {
                assert(q->transGet(i) == q1->transGet(i));
            } RETRY(false);
        }
    }
    
#if PRINT_DEBUG
    void print_stats(T* q) {
        
    }
#endif
    
    static const int num_ops_ = 5;
};
*/


<|start_filename|>Boosting_lockkey.hh<|end_filename|>
#pragma once

#include "Boosting_tl2.hh"
#include "Boosting_sto.hh"
#include "Boosting_locks.hh"

#include "Hashtable.hh"

template <typename K, unsigned Init_size = 129, typename Hash = std::hash<K>, typename Pred = std::equal_to<K>>
class LockKey {
public:
  LockKey(unsigned size = Init_size, Hash h = Hash(), Pred p = Pred()) : lockMap(size, h, p) {}

  void readLock(const K& key) {
    RWLock *lock = getLock(key);
    TRANS_READ_LOCK(lock);
  }

  void writeLock(const K& key) {
    RWLock *lock = getLock(key);
    TRANS_WRITE_LOCK(lock);
  }

public:
  Hashtable<K, RWLock, true, Init_size, RWLock, Hash, Pred> lockMap;

  RWLock *getLock(const K& key) {
    RWLock *lock = lockMap.readPtr(key);
    if (!lock) {
      // TODO(nate): might want to acquire the lock before we insert it
      // lock will either stay the same or be set to the current lock if one exists.
      lock = lockMap.putIfAbsentPtr(key, RWLock());
    }
    return lock;
  }
};


<|start_filename|>List1.hh<|end_filename|>
#pragma once

#include "TaggedLow.hh"
#include "Transaction.hh"
#include "List.hh"
#include "SingleElem.hh"

template <typename T, bool Duplicates = false, typename Compare = DefaultCompare<T>, bool Sorted = true, bool Opacity = false, typename Elem = SingleElem<T>> class List1Iterator;

template <typename T, bool Duplicates = false, typename Compare = DefaultCompare<T>, bool Sorted = true, bool Opacity = false, typename Elem = SingleElem<T>>
class List1 : public TObject {
    friend class List1Iterator<T, Duplicates, Compare, Sorted, Opacity, Elem>;
    typedef List1Iterator<T, Duplicates, Compare, Sorted, Opacity, Elem> iterator;
public:
    List1(Compare comp = Compare()) : head_(NULL), listsize_(0), listversion_(0), comp_(comp) {
    }

private:
    typedef TransactionTid::type version_type;

public:
    static constexpr uint8_t invalid_bit = 1<<0;

    static constexpr TransItem::flags_type insert_bit = TransItem::user0_bit;
    static constexpr TransItem::flags_type delete_bit = TransItem::user0_bit<<1;
    static constexpr TransItem::flags_type doupdate_bit = TransItem::user0_bit<<2;

    static constexpr void* size_key = (void*)0;
    
    struct list_node {
        list_node(const T& val_, list_node *next, bool invalid)
        : val(), next(next, invalid ? invalid_bit : 0) {
            val.write(val_);
        }
        
        void mark_invalid() {
            next.or_flags(invalid_bit);
        }
        
        void mark_valid() {
            next.assign_flags(next.flags() & ~invalid_bit);
        }
        
        bool is_valid() {
            return !(next.flags() & invalid_bit);
        }
        
        Elem val;
        TaggedLow<list_node> next;
    };
    
    bool find(const T& elem, T& val) {
        auto *ret = _find(elem);
        if (ret) {
            val = ret->val;
        }
        return !!ret;
    }
    
    bool find(const T& elem) {
        auto *ret = _find(elem);
        if (ret) {
            return true;
        }
        return false;
    }
    
    bool transFind(const T& elem) {
        auto listv = listversion_;
        fence();
        auto *n = _find(elem);
        if (n) {
            auto item = t_item(n);
            if (!validityCheck(n, item)) {
                Sto::abort();
                return false;
            }
            if (has_delete(item)) {
                return false;
            }
            item.add_read(0);
        } else {
            // log list v#
            verify_list(listv);
            return false;
        }
        return true;
    }
    
    list_node* _find(const T& elem) {
        list_node *cur = head_;
        while (cur != NULL) {
            int c = comp_(cur->val, elem);
            if (c == 0) {
                return cur;
            }
            if (Sorted && c > 0) {
                return NULL;
            }
            cur = cur->next;
        }
        return NULL;
    }
    
    template <bool Txnal = false>
    list_node* _insert(const T& elem, bool *inserted = NULL) {
        if (inserted)
            *inserted = true;
        lock(listversion_);
        if (!Sorted && !Duplicates) {
            list_node *new_head = new list_node(elem, head_, Txnal);
            head_ = new_head;
            unlock(listversion_);
            return new_head;
        }
        
        list_node *prev = NULL;
        list_node *cur = head_;
        while (cur != NULL) {
            int c = comp_(cur->val, elem);
            if (!Duplicates && c == 0) {
                unlock(listversion_);
                if (inserted)
                    *inserted = false;
                return cur;
            } else if (Sorted && c >= 0) {
                break;
            }
            prev = cur;
            cur = cur->next;
        }
        auto ret = new list_node(elem, cur, Txnal);
        if (prev) {
            prev->next.assign_ptr(ret);
        } else {
            head_ = ret;
        }
        if (!Txnal)
            listsize_++;
        unlock(listversion_);
        return ret;
    }
    
    bool insert(const T& elem) {
        bool inserted;
        _insert<false>(elem, &inserted);
        return inserted;
    }
    
    bool transInsert(const T& elem) {
        bool inserted;
        auto *node = _insert<true>(elem, &inserted);
        auto item = t_item(node);
        if (!inserted) {
            if (!validityCheck(node, item)) {
                Sto::abort();
                return false;
            }
            // intertransactional insert-then-insert = failed insert
            if (has_insert(item)) {
                return false;
            }
            // delete-then-insert, then insert -- failed insert
            if (has_doupdate(item)) {
                return false;
            }
            // delete-then-insert... (should really become an update...)
            if (has_delete(item)) {
                item.clear_write().add_write(elem);
                item.assign_flags(doupdate_bit);
                add_trans_size_offs(1);
                return true;
            }
            // "normal" insert-then-insert = failed insert
            // need to make sure it's still there at commit time
            item.add_read(0);
            return false;
        }
        add_trans_size_offs(1);
        // we lock the list for inserts
        add_lock_list_item();
        item.add_write(0);
        item.add_flags(insert_bit);
        return true;
    }
    
    bool transDelete(const T& elem) {
        auto listv = listversion_;
        fence();
        auto *n = _find(elem);
        if (n) {
            auto item = t_item(n);
            if (!validityCheck(n, item)) {
                Sto::abort();
                return false;
            }
            if (has_delete(item)) {
                // we're deleting our delete
                return false;
            }
            // delete-then-insert, then delete
            if (has_doupdate(item)) {
                // back to deleting
                item.assign_flags(delete_bit);
                add_trans_size_offs(-1);
                return true;
            }
            // insert-then-delete becomes nothing
            if (has_insert(item)) {
                remove<true>(n);
                item.remove_read().remove_write().clear_flags(insert_bit);
                add_trans_size_offs(-1);
                // TODO: should have a count on add_lock_list_item so we can cancel that here
                // still need to make sure no one else inserts something
                verify_list(listv);
                return true;
            }
            item.assign_flags(delete_bit);
            // mark as a write
            item.add_write(0);
            // we also need to check that it's still valid at commit time (not
            // bothering with valid_check_only_bit optimization right now)
            item.add_read(0);
            add_lock_list_item();
            add_trans_size_offs(-1);
            return true;
        } else {
            verify_list(listv);
            return false;
        }
    }
    
    template <bool Txnal>
    bool remove(const T& elem, bool locked = false) {
        return _remove<Txnal>([&] (list_node *n2) { return comp_(n2->val, elem) == 0; }, locked);
    }
    
    template <bool Txnal>
    bool remove(list_node *n, bool locked = false) {
        // TODO: doing this remove means we don't have to value compare, but we also
        // have to go through the whole list (possibly). Unclear which is better.
        return _remove<Txnal>([n] (list_node *n2) { return n == n2; }, locked);
    }
    
    template <bool Txnal, typename FoundFunc>
    bool _remove(FoundFunc found_f, bool locked = false) {
        if (!locked)
            lock(listversion_);
        list_node *prev = NULL;
        list_node *cur = head_;
        while (cur != NULL) {
            if (found_f(cur)) {
                cur->mark_invalid();
                if (prev) {
                    prev->next.assign_ptr(cur->next);
                } else {
                    head_ = cur->next;
                }
                if (Txnal) {
                    Transaction::rcu_free(cur);
                } else {
                    free(cur);
                }
                if (!Txnal)
                    listsize_--;
                if (!locked)
                    unlock(listversion_);
                return true;
            }
            prev = cur;
            cur = cur->next;
        }
        if (!locked)
            unlock(listversion_);
        return false;
    }
    
    inline void opacity_check() {
        // When we check for opacity, we need to compare the latest listversion and not
        // the one at the beginning of the operation.
        assert(Opacity);
        auto listv = listversion_;
        fence();
        Sto::check_opacity(listv);
    }
    
    iterator begin() { return iterator(this, head_); }
    iterator end() { return iterator(this, NULL); }
    
    struct ListIter {
        ListIter() : us(NULL), cur(NULL) {}
        
        bool valid() const {
            return us != NULL;
        }
        
        bool hasNext() const {
            return !!cur;
        }
        
        void reset() {
            cur = us->head_;
        }
        
        T* next() {
            auto ret = cur ? &cur->val : NULL;
            if (cur)
                cur = cur->next;
            return ret;
        }
        
        bool transHasNext() const {
            return !!cur;
        }
        
        void transReset() {
            cur = us->head_;
            ensureValid();
        }
        
        T* transNext() {
            auto ret = cur ? &cur->val : NULL;
            if (cur)
                cur = cur->next;
            ensureValid();
            return ret;
        }
        
        T* transNthNext(int n) {
            T* ret = NULL;
            while (n > 0 && transHasNext()) {
                ret = transNext();
                n--;
            }
            if (n == 0)
                return ret;
            return NULL;
        }
        
    private:
        ListIter(List1 *us, list_node *cur, bool trans) : us(us), cur(cur) {
            if (trans)
                ensureValid();
        }
        
        void ensureValid() {
            while (cur) {
                // need to check if this item already exists
                auto item = Sto::check_item(us, cur);
                if (!cur->is_valid()) {
                    if (!item || !us->has_insert(*item)) {
                        Sto::abort();
                        // TODO: do we continue in this situation or abort?
                        cur = cur->next;
                        continue;
                    }
                }
                if (item && us->has_delete(*item)) {
                    cur = cur->next;
                    continue;
                }
                break;
            }
        }
        
        friend class List1;
        List1 *us;
        list_node *cur;
    };
    
    ListIter iter() {
        return ListIter(this, head_, false);
    }
    
    ListIter transIter() {
        verify_list(listversion_);//TODO: rename
        return ListIter(this, head_, true);
    }
    
    size_t size() {
        verify_list(listversion_);
        return listsize_ + trans_size_offs();
    }
    
    size_t unsafe_size() const {
        return listsize_;
    }
    
    void clear() {
        while (auto item = head_)
            remove<false>(head_, true);
    }
    
    void verify_list(version_type readv) {
        t_item(this).add_read(readv);
        acquire_fence();
    }
    
    
    void lock(version_type& v) {
        TransactionTid::lock(v);
    }
    
    void unlock(version_type& v) {
        TransactionTid::unlock(v);
    }
    
    bool is_locked(version_type& v) {
        return TransactionTid::is_locked(v);
    }

    bool lock(TransItem& item, Transaction& txn) override {
        // this lock is useless given that we also lock the listversion_
        // currently
        // XXX: this isn't great, but I think we need it to update the size...
        return item.key<List1*>() != this
            || txn.try_lock(item, listversion_);
    }

    bool check(TransItem& item, Transaction&) override {
        if (item.key<List1*>() == this)
            return TransactionTid::check_version(listversion_, item.template read_value<version_type>());
        auto n = item.key<list_node*>();
        return n->is_valid() || has_insert(item);
    }

    void install(TransItem& item, Transaction& t) override {
        if (item.key<List1*>() == this)
            return;
        list_node *n = item.key<list_node*>();
        if (has_delete(item)) {
            remove<true>(n, true);
            listsize_--;
            // not super ideal that we have to change version
            // but we need to invalidate transSize() calls
            if (Opacity) {
                TransactionTid::set_version(listversion_, t.commit_tid());
            } else {
                TransactionTid::inc_nonopaque_version(listversion_);
            }
        } else if (has_doupdate(item)) {
            // XXX BUG
            n->val = item.template write_value<T>();
        } else {
            n->mark_valid();
            listsize_++;
            if (Opacity) {
                TransactionTid::set_version(listversion_, t.commit_tid());
            } else {
                TransactionTid::inc_nonopaque_version(listversion_);
            }
        }
    }
    
    void unlock(TransItem& item) override {
        if (item.key<List1*>() == this)
            unlock(listversion_);
    }

    void cleanup(TransItem& item, bool committed) override {
        if (!committed && (item.flags() & insert_bit)) {
            list_node *n = item.key<list_node*>();
            remove<true>(n);
        }
    }
    
    bool validityCheck(list_node *n, TransItem& item) {
        return n->is_valid() || (item.flags() & insert_bit);
    }
    
    template <typename PTR>
    TransProxy t_item(PTR *node) {
        // can switch this to fresh_item to not read our writes
        return Sto::item(this, node);
    }
    
    bool has_insert(const TransItem& item) {
        return item.has_write() && !has_delete(item) && !has_doupdate(item);
    }
    
    bool has_delete(const TransItem& item) {
        return item.flags() & delete_bit;
    }
    
    bool has_doupdate(const TransItem& item) {
        return item.flags() & doupdate_bit;
    }
    
    void add_lock_list_item() {
        auto item = t_item((void*)this);
        item.add_write(0);
    }
    
    void add_trans_size_offs(int size_offs) {
        // TODO: it would be more efficient to store this directly in Transaction,
        // since the "key" is fixed (rather than having to search the transset each time)
        auto item = t_item(size_key);
        item.template set_stash<int>(item.template stash_value<int>(0) + size_offs);
    }
    
    int trans_size_offs() {
        return t_item(size_key).template stash_value<int>(0);
    }
    
    list_node *head_;
    long listsize_;
    version_type listversion_;
    Compare comp_;
};
    
    
    
    
    template <typename T, bool Duplicates, typename Compare, bool Sorted, bool Opacity, typename Elem>
    class List1Iterator : public std::iterator<std::forward_iterator_tag, T> {
        typedef List1Iterator<T, Duplicates, Compare, Sorted, Opacity, Elem> iterator;
        typedef List1<T, Duplicates, Compare, Sorted, Opacity, Elem> list_type;
        typedef typename list_type::list_node list_node;
    public:
        List1Iterator(list_type * list, list_node* ptr) : myList(list), myPtr(ptr) {
            myList->verify_list(myList->listversion_);
        }
        List1Iterator(const List1Iterator& itr) : myList(itr.myList), myPtr(itr.myPtr) {}
        
        List1Iterator& operator= (const List1Iterator& v) {
            myList = v.myList;
            myPtr = v.myPtr;
            return *this;
        }
        
        bool operator==(iterator other) const {
            return (myList == other.myList) && (myPtr == other.myPtr);
        }
        
        bool operator!=(iterator other) const {
            return !(operator==(other));
        }
        
        Elem& operator*() {
            return myPtr->val; // Just returing the pointer to the value because this
            // list does not transactionally track updates to list values.
        }
        
        void increment_ptr() {
            if (myPtr)
                myPtr = myPtr->next;
            while (myPtr) {
                // need to check if this item already exists
                auto item = Sto::check_item(myList, myPtr);
                if (!myPtr->is_valid()) {
                    if (!item || !myList->has_insert(*item)) {
                        Sto::abort();
                        // TODO: do we continue in this situation or abort?
                        myPtr = myPtr->next;
                        continue;
                    }
                }
                if (item && myList->has_delete(*item)) {
                    myPtr = myPtr->next;
                    continue;
                }
                break;
            }
        }
        
        /* This is the prefix case */
        iterator& operator++() {
            increment_ptr();
            return *this;
        }
        
        /* This is the postfix case */
        iterator operator++(int) {
            iterator clone(*this);
            increment_ptr();
            return clone;
        }
        
    private:
        list_type * myList;
        list_node * myPtr;
    };


<|start_filename|>versioned_value.hh<|end_filename|>
#pragma once
#include <iostream>
#include "Interface.hh"
#include "masstree_print.hh"

// TODO(nate): ugh. really we should have a MassTrans subclass of this with the
// deallocate_rcu functions so we 1) don't have to include Masstree headers in
// nearly everything STO-related and 2) don't accidentally call a Masstree
// function (deallocate_rcu) in some other context.
#include "kvthread.hh"

template <typename T, typename=void>
struct versioned_value_struct /*: public threadinfo::rcu_callback*/ {
  typedef T value_type;
  typedef TransactionTid::type version_type;

  versioned_value_struct() : version_(), value_() {}
  // XXX Yihe: I made it public; is there any reason why it should be private?
  versioned_value_struct(const value_type& val, version_type v) : version_(v), value_(val) {}
  
  static versioned_value_struct* make(const value_type& val, version_type version) {
    return new versioned_value_struct<T>(val, version);
  }
  
  bool needsResize(const value_type&) {
    return false;
  }
  
  versioned_value_struct* resizeIfNeeded(const value_type&) {
    return NULL;
  }
  
  inline void set_value(const value_type& v) {
    value_ = v;
  }
  
  inline const value_type& read_value() const {
    return value_;
  }

  inline value_type& writeable_value() {
    return value_;
  }
  
  inline const version_type& version() const {
    return version_;
  }
  inline version_type& version() {
    return version_;
  }

  inline void deallocate_rcu(threadinfo& ti) {
    ti.deallocate_rcu(this, sizeof(versioned_value_struct), memtag_value);
  }

  // Masstree debug printer
  void print(FILE *f, const char *prefix, int indent, lcdf::Str key,
    kvtimestamp_t, char *suffix) {
    std::stringstream vss;
    vss << value_;
    fprintf(f, "%s%*s%.*s = %s%s\n", prefix, indent, "",
        key.len, key.s, vss.str().c_str(), suffix);
  }

#if 0
  // rcu_callback method to self-destruct ourself
  void operator()(threadinfo& ti) {
    // this will call value's destructor
    this->versioned_value_struct::~versioned_value_struct();
    // and free our memory too
    ti.deallocate(this, sizeof(versioned_value_struct), memtag_value);
  }
#endif
  
private: 
  version_type version_;
  value_type value_;
};

// double box for non trivially copyable types!
template<typename T>
struct versioned_value_struct<T, typename std::enable_if<!__has_trivial_copy(T)>::type> {
public:
  typedef T value_type;
  typedef TransactionTid::type version_type;

  static versioned_value_struct* make(const value_type& val, version_type version) {
    return new versioned_value_struct(val, version);
  }

  versioned_value_struct() : version_(), valueptr_() {}

  bool needsResize(const value_type&) {
    return false;
  }
  versioned_value_struct* resizeIfNeeded(const value_type&) {
    return this;
  }

  void set_value(const value_type& v) {
    //auto *old = valueptr_;
    valueptr_ = new value_type(std::move(v));
    // rcu free old (HOW without threadinfo access??)
  }

  const value_type& read_value() const {
    return *valueptr_;
  }

  inline const version_type& version() const {
    return version_;
  }
  version_type& version() {
    return version_;
  }

  inline void deallocate_rcu(threadinfo& ti) {
    // XXX: really this one needs to be a rcu_callback so we can call destructor
    ti.deallocate_rcu(this, sizeof(versioned_value_struct), memtag_value);
  }
  
  // Masstree debug printer
  void print(FILE *f, const char *prefix, int indent, lcdf::Str key,
    kvtimestamp_t, char *suffix) {
    std::stringstream vss;
    vss << *valueptr_;
    fprintf(f, "%s%*s%.*s = %s%s\n", prefix, indent, "",
        key.len, key.s, vss.str().c_str(), suffix);
  }

private:
  versioned_value_struct(const value_type& val, version_type version) : version_(version), valueptr_(new value_type(std::move(val))) {}

  version_type version_;
  value_type* valueptr_;
};


<|start_filename|>Packer.cc<|end_filename|>
#include "Packer.hh"

constexpr size_t TransactionBuffer::default_capacity;

void TransactionBuffer::hard_get_space(size_t needed) {
    size_t s = std::max(needed, e_ ? e_->capacity * 2 : default_capacity);
    elt* ne = (elt*) new char[sizeof(elthdr) + s];
    ne->next = e_;
    ne->pos = 0;
    ne->capacity = s;
    if (e_)
        linked_size_ += e_->pos;
    e_ = ne;
}

void TransactionBuffer::hard_clear(bool delete_all) {
    while (e_ && e_->next) {
        elt* e = e_->next;
        e_->next = e->next;
        e->clear();
        delete[] (char*) e;
    }
    if (e_)
        e_->clear();
    linked_size_ = 0;
    if (e_ && delete_all) {
        delete[] (char*) e_;
        e_ = 0;
    }
}


<|start_filename|>list1.cc<|end_filename|>
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include "Transaction.hh"
#include "List1.hh"

void testSimpleInt() {
    List1<int> f;

    {
	TransactionGuard t;
	f.transInsert(100);
    }

    {
	TransactionGuard t2;
	assert(f.transFind(100));
    }

    printf("PASS: testSimpleInt\n");
}

void testSimpleString() {
    List1<std::string> f;

    {
	TransactionGuard t;
	f.transInsert("100");
    }

    {
	TransactionGuard t2;
	assert(f.transFind("100"));
    }

    printf("PASS: testSimpleString\n");
}

void testIter() {
    std::vector<int> arr;
    List1<int> f;
    for (int i = 0; i < 10; i++) {
        int x = rand();
        arr.push_back(x);
        f.insert(x);
    }
    int max;
    TRANSACTION {
        max = *(std::max_element(f.begin(), f.end()));
    } RETRY(false);

    assert(max == *(std::max_element(arr.begin(), arr.end())));
    printf("Max is %i\n", max);
    printf("PASS: array max_element test\n");
}


void testConflictingIter() {
    List1<int> f;
    for (int i = 0; i < 10; i++) {
        f.insert(i);
    }

    {
        TestTransaction t(1);
        std::max_element(f.begin(), f.end());

        TestTransaction t1(2);
        f.transInsert(10);
        assert(t1.try_commit());
        assert(!t.try_commit());
    }

    printf("PASS: conflicting array max_element test\n");
}

void testModifyingIter() {
    List1<int> f;
    for (int i = 0; i < 10; i++) {
        f.insert(i);
    }

    {
        TransactionGuard t;
        std::replace(f.begin(), f.end(), 4, 6);
    }

    {
        TransactionGuard t1;
        assert(!f.transFind(4));
    }

    printf("PASS: array replace test\n");
}

void testConflictingModifyIter1() {
    List1<int, true> f;
    for (int i = 0; i < 10; i++) {
        f.insert(i);
    }

    TestTransaction t(1);
    std::replace(f.begin(), f.end(), 4, 6);

    TestTransaction t1(2);
    f.transInsert(4);
    assert(t1.try_commit());
    assert(!t.try_commit());

    {
        TransactionGuard t2;
        assert(f.transFind(4));
    }

    printf("PASS: array conflicting replace test1\n");
}

void testConflictingModifyIter2() {
    List1<int> f;
    for (int i = 0; i < 10; i++) {
        f.insert(i);
    }

    {
        TransactionGuard t;
        std::replace(f.begin(), f.end(), 4, 6);
    }

    {
        TransactionGuard t1;
        f.transInsert(4);
    }

    {
        TransactionGuard t2;
        assert(f.transFind(4));
    }

    printf("PASS: array conflicting replace test2\n");
}

void testConflictingModifyIter3() {
    List1<int> f;
    for (int i = 0; i < 10; i++) {
        f.insert(i);
    }

    TestTransaction t1(1);
    f.transFind(4);

    TestTransaction t(2);
    std::replace(f.begin(), f.end(), 4, 6);
    assert(t.try_commit());
    assert(!t1.try_commit());

    {
        TransactionGuard t2;
        assert(!f.transFind(4));
    }

    printf("PASS: array conflicting replace test3\n");
}


int main() {
	testSimpleInt();
	testSimpleString();
    testIter();
    testConflictingIter();
    testModifyingIter();
    testConflictingModifyIter1();
    testConflictingModifyIter2();
    testConflictingModifyIter3();
	return 0;
}


<|start_filename|>iterators.cc<|end_filename|>
#include <string>
#include <iostream>
#include <assert.h>
#include <vector>
#include <random>
#include <map>
#include "Transaction.hh"
#include "Vector.hh"
#include "clp.h"
#include "randgen.hh"

int max_value = 10000;
int global_seed = 11;
int nthreads = 16;
int ntrans = 1000000;
int opspertrans = 1;
int prepopulate = 1000;
int max_key = 1000;
double search_percent = 0.3;
double update_percent = 0.3;
bool use_iterators = false;


TransactionTid::type lock;

typedef Vector<int> data_structure;

template <typename T>
struct TesterPair {
    T* t;
    int me;
};


template <typename T>
int findK(T* q, int val) {
    if (use_iterators) {
        data_structure::iterator fit = q->begin();
        data_structure::iterator eit = q->end();
        data_structure::iterator it = std::find(fit, eit, val);
        return it-fit;
        
    } else {
        int first = 0;
        int last = q->size();
        while (first != last) {
            if (q->transGet(first) == val) return first;
            ++first;
        }
        return last;
    }
}

template <typename T>
void run(T* q, int me) {
    TThread::set_id(me);
    
    std::uniform_int_distribution<long> slotdist(0, max_value);
    int N = ntrans/nthreads;
    int OPS = opspertrans;

    for (int i = 0; i < N; ++i) {
        // so that retries of this transaction do the same thing
        auto transseed = i;
        while (1) {
        Sto::start_transaction();
        try {
            uint32_t seed = transseed*3 + (uint32_t)me*ntrans*7 + (uint32_t)global_seed*MAX_THREADS*ntrans*11;
            auto seedlow = seed & 0xffff;
            auto seedhigh = seed >> 16;
            Rand transgen(seed, seedlow << 16 | seedhigh);
            
            for (int j = 0; j < OPS; ++j) {
                int op = slotdist(transgen) % 100;
                if (op < search_percent * 100) {
                    int val = slotdist(transgen);
                    findK(q, val);
                } else if (op < (search_percent + update_percent) *100){
                    int key = slotdist(transgen) % max_key;
                    int val = slotdist(transgen) % max_value;
                    q->transUpdate(key, val);
                } else {
                    int key = slotdist(transgen) % max_key;
                    q->transGet(key);
                }

            }
            
            if (Sto::try_commit()) {
                break;
            }
        
        } catch (Transaction::Abort e) { }
        }
    }
}

template <typename T>
void* runFunc(void* x) {
    TesterPair<T>* tp = (TesterPair<T>*) x;
    run(tp->t, tp->me);
    return nullptr;
}

template <typename T>
void startAndWait(int n, T* queue) {
    pthread_t tids[nthreads];
    TesterPair<T> *testers = new TesterPair<T>[n];
    for (int i = 0; i < nthreads; ++i) {
        testers[i].t = queue;
        testers[i].me = i;
        pthread_create(&tids[i], NULL, runFunc<T>, &testers[i]);
    }
    pthread_t advancer;
    pthread_create(&advancer, NULL, Transaction::epoch_advancer, NULL);
    pthread_detach(advancer);
    
    for (int i = 0; i < nthreads; ++i) {
        pthread_join(tids[i], NULL);
    }
}

void print_time(struct timeval tv1, struct timeval tv2) {
    printf("%f\n", (tv2.tv_sec-tv1.tv_sec) + (tv2.tv_usec-tv1.tv_usec)/1000000.0);
}

enum {
    opt_nthreads, opt_ntrans, opt_opspertrans, opt_searchpercent, opt_updatepercent, opt_prepopulate, opt_seed, opt_useiterators
};

static const Clp_Option options[] = {
    { "nthreads", 0, opt_nthreads, Clp_ValInt, Clp_Optional },
    { "ntrans", 0, opt_ntrans, Clp_ValInt, Clp_Optional },
    { "opspertrans", 0, opt_opspertrans, Clp_ValInt, Clp_Optional },
    { "searchpercent", 0, opt_searchpercent, Clp_ValDouble, Clp_Optional },
    { "updatepercent", 0, opt_updatepercent, Clp_ValDouble, Clp_Optional },
    { "prepopulate", 0, opt_prepopulate, Clp_ValInt, Clp_Optional },
    { "seed", 0, opt_seed, Clp_ValInt, Clp_Optional },
    { "useiterators", 0, opt_useiterators, Clp_ValInt, Clp_Optional}
};

static void help() {
    printf("Usage: [OPTIONS]\n\
           Options:\n\
           --nthreads=NTHREADS (default %d)\n\
           --ntrans=NTRANS, how many total transactions to run (they'll be split between threads) (default %d)\n\
           --opspertrans=OPSPERTRANS, how many operations to run per transaction (default %d)\n\
           --searchpercent=SEARCHPERCENT, probability with which to do searches (default %f)\n\
           --updatepercent=UPDATEPERCENT, probability with which to do updates (default %f)\n\
           --prepopulate=PREPOPULATE, prepopulate table with given number of items (default %d)\n\
           --seed=SEED, global seed to run the experiment \n",
            nthreads, ntrans, opspertrans, search_percent, update_percent, prepopulate);
    exit(1);
}

template <typename T>
void init(T* q) {
    std::uniform_int_distribution<long> slotdist(0, max_value);
    uint32_t seed = global_seed * 11;
    auto seedlow = seed & 0xffff;
    auto seedhigh = seed >> 16;
    Rand transgen(seed, seedlow << 16 | seedhigh);
    for (int i = 0; i < prepopulate; i++) {
        TRANSACTION {
            q->push_back(slotdist(transgen));
        } RETRY(false);
    }
}

int main(int argc, char *argv[]) {
    lock = 0;
    struct timeval tv1,tv2;
    
    Clp_Parser *clp = Clp_NewParser(argc, argv, arraysize(options), options);
        
    int opt;
    while ((opt = Clp_Next(clp)) != Clp_Done) {
        switch (opt) {
            case opt_nthreads:
                nthreads = clp->val.i;
                break;
            case opt_ntrans:
                ntrans = clp->val.i;
                break;
            case opt_opspertrans:
                opspertrans = clp->val.i;
                break;
            case opt_searchpercent:
                search_percent = clp->val.d;
                break;
            case opt_updatepercent:
                update_percent = clp->val.d;
                break;
            case opt_prepopulate:
                prepopulate = clp->val.i;
                break;
            case opt_seed:
                global_seed = clp->val.i;
                break;
            case opt_useiterators:
                use_iterators = clp->val.i == 1;
                break;
            default:
                help();
        }
    }
    Clp_DeleteParser(clp);

    if (!use_iterators) {
    // Run a parallel test with lots of transactions doing pushes and pops
    data_structure q;
    init(&q);
    
    gettimeofday(&tv1, NULL);
    
    startAndWait(nthreads, &q);
    
    gettimeofday(&tv2, NULL);
    printf("Parallel PQ time: ");
    print_time(tv1, tv2);
    
#if STO_PROFILE_COUNTERS
    Transaction::print_stats();
    {
        txp_counters tc = Transaction::txp_counters_combined();
        printf("total_n: %llu, total_r: %llu, total_w: %llu, total_searched: %llu, total_aborts: %llu (%llu aborts at commit time)\n", tc.p(txp_total_n), tc.p(txp_total_r), tc.p(txp_total_w), tc.p(txp_total_searched), tc.p(txp_total_aborts), tc.p(txp_commit_time_aborts));
    }
    Transaction::clear_stats();
#endif
    } else {
    
    data_structure q2;
    init(&q2);
    gettimeofday(&tv1, NULL);
    
    startAndWait(nthreads, &q2);
    
    gettimeofday(&tv2, NULL);
    printf("Iterator parallel time: ");
    print_time(tv1, tv2);
    
#if STO_PROFILE_COUNTERS
    Transaction::print_stats();
    {
        txp_counters tc = Transaction::txp_counters_combined();
        printf("total_n: %llu, total_r: %llu, total_w: %llu, total_searched: %llu, total_aborts: %llu (%llu aborts at commit time)\n", tc.p(txp_total_n), tc.p(txp_total_r), tc.p(txp_total_w), tc.p(txp_total_searched), tc.p(txp_total_aborts), tc.p(txp_commit_time_aborts));
    }
    Transaction::clear_stats();
#endif
   }    
	return 0;
}


<|start_filename|>print_value.hh<|end_filename|>
#pragma once
#include "compiler.hh"
#include <sstream>

namespace mass {

template <typename T> class is_printable : public false_type {};
template <> class is_printable<unsigned char> : public true_type {};
template <> class is_printable<signed char> : public true_type {};
template <> class is_printable<char> : public true_type {};
template <> class is_printable<bool> : public true_type {};
template <> class is_printable<unsigned short> : public true_type {};
template <> class is_printable<short> : public true_type {};
template <> class is_printable<unsigned> : public true_type {};
template <> class is_printable<int> : public true_type {};
template <> class is_printable<unsigned long> : public true_type {};
template <> class is_printable<long> : public true_type {};
template <> class is_printable<unsigned long long> : public true_type {};
template <> class is_printable<long long> : public true_type {};
template <> class is_printable<float> : public true_type {};
template <> class is_printable<double> : public true_type {};
template <> class is_printable<long double> : public true_type {};
template <typename C, typename T, typename A> class is_printable<std::basic_string<C, T, A> > : public true_type {};
template <> class is_printable<const char*> : public true_type {};
template <> class is_printable<char*> : public true_type {};

template <typename T, bool printable = is_printable<typename std::remove_cv<T>::type>::value > class print_value_helper;
template <typename T> class print_value_helper<T, true> {
public:
    typedef const T& type;
    static const T& print_value(const T& x) {
        return x;
    }
};
template <typename T> class print_value_helper<T, false> {
public:
    typedef std::string type;
    static std::string print_value(const T& x) {
        std::ostringstream buf;
        buf << "<&" << (void*) &x << ">";
        return buf.str();
    }
};

template <typename T>
auto print_value(const T& x) -> typename print_value_helper<T>::type {
    return print_value_helper<T>::print_value(x);
}

}


<|start_filename|>Boosting_tl2.hh<|end_filename|>
#pragma once

#if defined(BOOSTING) && defined(STM)
#include "Boosting_common.hh"
#include "../../../tl2/stm.h"

#define DO_ABORT() TxAbort(STM_CUR_SELF)
#define POST_COMMIT(callback, context1, context2, context3) TxPostCommitHook(STM_CUR_SELF, (callback), (context1), (context2), (context3))
#define ON_ABORT(callback, context1, context2, context3) TxAbortHook(STM_CUR_SELF, (callback), (context1), (context2), (context3))
#endif


<|start_filename|>Queue.hh<|end_filename|>
#pragma once

#include <list>
#include "TaggedLow.hh"
#include "Transaction.hh"
#include "TWrapped.hh"

template <typename T, unsigned BUF_SIZE = 1000000,
          template <typename> class W = TOpaqueWrapped>
class Queue: public TObject {
public:
    typedef typename W<T>::version_type version_type;

    Queue() : head_(0), tail_(0), tailversion_(0), headversion_(0) {}

    static constexpr TransItem::flags_type delete_bit = TransItem::user0_bit;
    static constexpr TransItem::flags_type read_writes = TransItem::user0_bit<<1;
    static constexpr TransItem::flags_type list_bit = TransItem::user0_bit<<2;
    static constexpr TransItem::flags_type empty_bit = TransItem::user0_bit<<3;

    // NONTRANSACTIONAL PUSH/POP/EMPTY
    void nontrans_push(T v) {
        queueSlots[tail_] = v;
        tail_ = (tail_+1)%BUF_SIZE;
        assert(head_ != tail_);
    }
    
    T nontrans_pop() {
        assert(head_ != tail_);
        T v = queueSlots[head_];
        head_ = (head_+1)%BUF_SIZE;
        return v;
    }

    bool nontrans_empty() const {
        return head_ == tail_;
    }

    template <typename RandomGen>
    void nontrans_shuffle(RandomGen gen) {
        auto head = &queueSlots[head_];
        auto tail = &queueSlots[tail_];
        // don't support wrap-around shuffle
        assert(head < tail);
        std::shuffle(head, tail, gen);
    }

    void nontrans_clear() {
        while (!nontrans_empty())
            nontrans_pop();
    }

    // TRANSACTIONAL CALLS
    void transPush(const T& v) {
        auto item = Sto::item(this, -1);
        if (item.has_write()) {
            if (!is_list(item)) {
                auto& val = item.template write_value<T>();
                std::list<T> write_list;
                if (!is_empty(item)) {
                    write_list.push_back(val);
                    item.clear_flags(empty_bit);
                }
                write_list.push_back(v);
                item.clear_write();
                item.add_write(write_list);
                item.add_flags(list_bit);
            }
            else {
                auto& write_list = item.template write_value<std::list<T>>();
                write_list.push_back(v);
            }
        }
        else item.add_write(v);
    }

    bool transPop() {
        auto hv = headversion_;
        fence();
        auto index = head_;
        auto item = Sto::item(this, index);

        while (1) {
           if (index == tail_) {
               auto tv = tailversion_;
               fence();
                // if someone has pushed onto tail, can successfully do a front read, so don't read our own writes
                if (index == tail_) {
                    auto pushitem = Sto::item(this,-1);
                    if (!pushitem.has_read())
                        pushitem.observe(tv);
                    if (pushitem.has_write()) {
                        if (is_list(pushitem)) {
                            auto& write_list = pushitem.template write_value<std::list<T>>();
                            // if there is an element to be pushed on the queue, return addr of queue element
                            if (!write_list.empty()) {
                                write_list.pop_front();
                                item.add_flags(read_writes);
                                return true;
                            }
                            else return false;
                        }
                        // not a list, has exactly one element
                        else if (!is_empty(pushitem)) {
                            pushitem.add_flags(empty_bit);
                            return true;
                        }
                        else return false;
                    }
                    // fail if trying to read from an empty queue
                    else return false;  
                } 
            }
            if (has_delete(item)) {
                index = (index + 1) % BUF_SIZE;
                item = Sto::item(this, index);
            }
            else break;
        }
        // ensure that head is not modified by time of commit 
        auto lockitem = Sto::item(this, -2);
        if (!lockitem.has_read()) {
            lockitem.observe(hv);
        }
        lockitem.add_write(0);
        item.add_flags(delete_bit);
        item.add_write(0);
        return true;
    }

    bool transFront(T& val) {
        auto hv = headversion_;
        fence();
        unsigned index = head_;
        auto item = Sto::item(this, index);
        while (1) {
            // empty queue
            if (index == tail_) {
                auto tv = tailversion_;
                fence();
                // if someone has pushed onto tail, can successfully do a front read, so skip reading from our pushes 
                if (index == tail_) {
                    auto pushitem = Sto::item(this,-1);
                    if (!pushitem.has_read())
                        pushitem.observe(tv);
                    if (pushitem.has_write()) {
                        if (is_list(pushitem)) {
                            auto& write_list= pushitem.template write_value<std::list<T>>();
                            // if there is an element to be pushed on the queue, return addr of queue element
                            if (!write_list.empty()) {
                                val = write_list.front();
                                return true;
                            }
                            else return false;
                        }
                        // not a list, has exactly one element
                        else if (!is_empty(pushitem)) {
                            auto& v = pushitem.template write_value<T>();
                            val = v;
                            return true;
                        }
                        else return false;
                    }
                    return false;
                }
            }
            if (has_delete(item)) {
                index = (index + 1) % BUF_SIZE;
                item = Sto::item(this, index);
            }
            else break;
        }
        // ensure that head was not modified at time of commit
        auto lockitem = Sto::item(this, -2);
        if (!lockitem.has_read()) {
            lockitem.observe(hv);
        }  
        val = queueSlots[index];
        return true;
    }
    
private:
    bool has_delete(const TransItem& item) {
        return item.flags() & delete_bit;
    }
    
    bool is_rw(const TransItem& item) {
        return item.flags() & read_writes;
    }
 
    bool is_list(const TransItem& item) {
        return item.flags() & list_bit;
    }
 
    bool is_empty(const TransItem& item) {
        return item.flags() & empty_bit;
    }

    bool lock(TransItem& item, Transaction& txn) override {
        if (item.key<int>() == -1)
            return txn.try_lock(item, tailversion_);
        else if (item.key<int>() == -2)
            return txn.try_lock(item, headversion_);
        else
            return true;
    }

    bool check(TransItem& item, Transaction& t) override {
        (void) t;
        // check if was a pop or front 
        if (item.key<int>() == -2)
            return item.check_version(headversion_);
        // check if we read off the write_list (and locked tailversion)
        else if (item.key<int>() == -1)
            return item.check_version(tailversion_);
        // shouldn't reach this
        assert(0);
        return false;
    }

    void install(TransItem& item, Transaction& txn) override {
	    // ignore lock_headversion marker item
        if (item.key<int>() == -2)
            return;
        // install pops
        if (has_delete(item)) {
            // only increment head if item popped from actual q
            if (!is_rw(item))
                head_ = (head_+1) % BUF_SIZE;
            headversion_.set_version(txn.commit_tid());
        }
        // install pushes
        else if (item.key<int>() == -1) {
            auto head_index = head_;
            // write all the elements
            if (is_list(item)) {
                auto& write_list = item.template write_value<std::list<T>>();
                while (!write_list.empty()) {
                    // assert queue is not out of space            
                    assert(tail_ != (head_index-1) % BUF_SIZE);
                    queueSlots[tail_] = write_list.front();
                    write_list.pop_front();
                    tail_ = (tail_+1) % BUF_SIZE;
                }
            }
            else if (!is_empty(item)) {
                auto& val = item.template write_value<T>();
                queueSlots[tail_] = val;
                tail_ = (tail_+1) % BUF_SIZE;
            }

            tailversion_.set_version(txn.commit_tid());
        }
    }
    
    void unlock(TransItem& item) override {
        if (item.key<int>() == -1)
            tailversion_.unlock();
        else if (item.key<int>() == -2)
            headversion_.unlock();
    }

    T queueSlots[BUF_SIZE];

    unsigned head_;
    unsigned tail_;
    version_type tailversion_;
    version_type headversion_;
};


<|start_filename|>Tagged64.hh<|end_filename|>
#pragma once
#include <stdint.h>

// 64 bits including a pointer and 16 bits of flags
// (technically we have 19 flag bits on a 64 bit machine and 35 on a 32 bit machine but who cares)
template <typename T>
class Tagged64 {
    static constexpr int shift = 64 - 16;
#if SIZEOF_VOID_P == 8
    typedef T* packed_type;
    static constexpr uintptr_t ptrmask = 0xFFFFFFFFFFFFULL;
#elif SIZEOF_VOID_P == 4
    typedef uint64_t packed_type;
    static constexpr uintptr_t ptrmask = 0xFFFFFFFFU;
#else
# error "bad sizeof(void*)"
#endif
    typedef uint64_t flags_type;

    static packed_type pack(T* p, int flags) {
        return reinterpret_cast<packed_type>(reinterpret_cast<uintptr_t>(p)
                                             | (flags_type(flags) << shift));
    }

public:

    Tagged64(T* p)
        : p_(pack(p, 0)) {
    }

    T* ptr() const {
        return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(p_) & ptrmask);
    }

    uint16_t flags() const {
        return reinterpret_cast<flags_type>(p_) >> shift;
    }

    void assign_flags(uint16_t flags) {
        p_ = pack(ptr(), flags);
    }

    void or_flags(uint16_t flags) {
        p_ = reinterpret_cast<packed_type>(reinterpret_cast<flags_type>(p_)
                                           | (flags_type(flags) << shift));
    }

    void rm_flags(uint16_t flags) {
        p_ = reinterpret_cast<packed_type>(reinterpret_cast<flags_type>(p_)
                                           & ~(flags_type(flags) << shift));
    }

    bool operator<(Tagged64<T> x) const {
        return reinterpret_cast<flags_type>(p_) < reinterpret_cast<flags_type>(x.p_);
    }

  private:
    packed_type p_;
};
