text: /**
   *  Copyright (C) 2011
   *  University of Rochester Department of Computer Science
   *    and
   *  Lehigh University Department of Computer Science and Engineering
   *
   * License: Modified BSD
   *          Please see the file LICENSE.RSTM for licensing information
   */
  
  #ifndef DLIST_HPP__
  #define DLIST_HPP__
  
  #include <limits.h>
  #include <api/api.hpp>
  
  // Doubly-Linked List workload
  class DList
  {
      // Node is a node in the DList
      struct Node
      {
          int   m_val;
          Node* m_prev;
          Node* m_next;
  
          // basic constructor
          Node(int val) : m_val(val), m_prev(), m_next() { }
      };
  
    public:
  
      // the dlist keeps head and tail pointers, for bidirectional traversal
      Node* head;
      Node* tail;
  
      DList();
  
      // insert a node if it doesn't already exist
      TM_CALLABLE
      bool insert(int val TM_ARG);
  
      // true iff val is in the data structure
      TM_CALLABLE
      bool lookup(int val TM_ARG) const;
  
      // remove a node if its value = val
      TM_CALLABLE
      bool remove(int val TM_ARG);
  
      // make sure the list is in sorted order
      bool isSane() const;
  
      // increment all elements, moving forward
      TM_CALLABLE
      void increment_forward(TM_ARG_ALONE);
  
      // increment all elements, moving in reverse
      TM_CALLABLE
      void increment_backward(TM_ARG_ALONE);
  
      // increment every seqth element, starting with start, moving forward
      TM_CALLABLE
      void increment_forward_pattern(int start, int seq TM_ARG);
  
      // increment every seqth element, starting with start, moving backward
      TM_CALLABLE
      void increment_backward_pattern(int start, int seq TM_ARG);
  
      // read the whole list, then increment every element in the chunk
      // starting at chunk_num*chunk_size
      TM_CALLABLE
      void increment_chunk(int chunk_num, int chunk_size TM_ARG);
  };
  
  
  // constructor: head and tail have extreme values, point to each other
  DList::DList()// : head(new Node(-1)), tail(new Node(INT_MAX))
  {
    head = (Node*)hcmalloc(sizeof(Node));
    tail = (Node*)hcmalloc(sizeof(Node));
    //std::cout << "alloc " << sentinel << std::endl;
    new (head) Node(-1);
    new (tail) Node(INT_MAX);
  
      head->m_next = tail;
      tail->m_prev = head;
  }
  
  // simple sanity check: make sure all elements of the list are in sorted order
  bool DList::isSane(void) const
  {
    bool sane = false;
    sane = true;
    int elems = -1;
  
      // forward traversal
      const Node* prev(head);
      const Node* curr((prev->m_next));
      while (curr != NULL) {
        elems++;
          // ensure sorted order
          if ((prev->m_val) >= (curr->m_val)) {
              sane = false;
              break;
          }
          // ensure curr->prev->next == curr
          const Node* p ((curr->m_prev));
          if ((p->m_next) != curr) {
              sane = false;
              break;
          }
  
          prev = curr;
          curr = (curr->m_next);
      }
      std::cout << "Elements in the List at End: " << elems << std::endl;
  
      // backward traversal
      prev = tail;
      curr = (prev->m_prev);
      while (curr != NULL) {
          // ensure sorted order
          if ((prev->m_val) < (curr->m_val)) {
              sane = false;
              break;
          }
          // ensure curr->next->prev == curr
          const Node* n ((curr->m_next));
          if ((n->m_prev) != curr) {
              sane = false;
              break;
          }
  
          prev = curr;
          curr = (curr->m_prev);
      }
      return sane;
  }
  
  // insert method; find the right place in the list, add val so that it is in
  // sorted order; if val is already in the list, exit without inserting
  TM_CALLABLE
  bool DList::insert(int val TM_ARG){
      // traverse the list to find the insertion point
      const Node* prev(head);
      const Node* curr(TM_READ_PROMO(prev->m_next));
  
      while (curr != NULL) {
          if (TM_READ(curr->m_val) >= val)
              break;
  
          prev = curr;
          curr = TM_READ_PROMO(prev->m_next);
      }
  
      // now insert new_node between prev and curr
      if (TM_READ(curr->m_val) > val) {
          Node* before = const_cast<Node*>(prev);
          Node* after = const_cast<Node*>(curr);
  
          // create the node
          Node* between = (Node*)TM_ALLOC(sizeof(Node));
          between->m_val = val;
          between->m_prev = before;
          between->m_next = after;
  
          TM_WRITE(before->m_next, between);
          TM_WRITE(after->m_prev, between);
  	return true;
      }
      return false;
  }
  
  // search for a value
  TM_CALLABLE
  bool DList::lookup(int val TM_ARG) const
  {
      bool found = false;
  
      const Node* curr(head);
      curr = TM_READ(curr->m_next);
      while (curr != NULL) {
          if (TM_READ(curr->m_val) >= val)
              break;
          curr = TM_READ(curr->m_next);
      }
      found = ((curr != NULL) && (TM_READ(curr->m_val) == val));
  
      return found;
  }
  
  // remove a node if its value == val
  TM_CALLABLE
  bool DList::remove(int val TM_ARG){
      // find the node whose val matches the request
      const Node* prev(head);
      const Node* curr(TM_READ_PROMO(prev->m_next));
  
      while (curr != NULL) {
          // if we find the node, disconnect it and end the search
          if (TM_READ(curr->m_val) == val) {
              Node* before = const_cast<Node*>(prev);
              Node* after(TM_READ(curr->m_next));
              TM_WRITE(before->m_next, after);
              TM_WRITE(after->m_prev, before);
  
              // delete curr...
              TM_FREE(const_cast<Node*>(curr));
              return true;
              break;
          }
          else if (TM_READ(curr->m_val) > val) {
              // this means the search failed
  	  return false;
              break;
          }
  
          prev = curr;
          curr = TM_READ_PROMO(prev->m_next);
      }
      return false;
  }
  
  TM_CALLABLE
  void DList::increment_forward(TM_ARG_ALONE)
  {
      // forward traversal
      const Node* prev(head);
      Node* curr(TM_READ(prev->m_next));
      while (curr != tail) {
          // increment curr
          TM_WRITE(curr->m_val, 1 + TM_READ(curr->m_val));
          curr = TM_READ(curr->m_next);
      }
  }
  
  TM_CALLABLE
  void DList::increment_backward(TM_ARG_ALONE)
  {
      // backward traversal
      const Node* prev(tail);
      Node* curr(TM_READ(prev->m_prev));
      while (curr != head) {
          // increment curr
          TM_WRITE(curr->m_val, 1 + TM_READ(curr->m_val));
          curr = TM_READ(curr->m_prev);
      }
  }
  
  // increment every seqth element, starting with start, moving forward
  TM_CALLABLE
  void DList::increment_forward_pattern(int start, int seq TM_ARG)
  {
      int sum = 0;
      // forward traversal to element # start
      const Node* prev(head);
      const Node* curr(TM_READ(prev->m_next));
      for (int i = 0; i < start; i++) {
          curr = TM_READ(curr->m_next);
      }
      // now do the remainder of the traversal, incrementing every seqth
      // element
      int ctr = seq;
      while (curr != tail) {
          // increment the seqth element
          if (ctr == seq) {
              ctr = 0;
              Node* cw = const_cast<Node*>(curr);
              TM_WRITE(cw->m_val, 1 + TM_READ(cw->m_val));
              curr = cw;
          }
          ctr++;
          sum += TM_READ(curr->m_val);
          curr = TM_READ(curr->m_next);
      }
  }
  
  // increment every element, starting with start, moving backward
  TM_CALLABLE
  void DList::increment_backward_pattern(int start, int seq TM_ARG)
  {
      int sum = 0;
      // backward traversal to element # start
      const Node* prev(tail);
      const Node* curr(TM_READ(prev->m_prev));
      for (int i = 0; i < start; i++) {
          curr = TM_READ(curr->m_prev);
      }
      // now do the remainder of the traversal, incrementing every seqth
      // element
      int ctr = seq;
      while (curr != head) {
          // increment the seqth element
          if (ctr == seq) {
              ctr = 0;
              Node* cw = const_cast<Node*>(curr);
              TM_WRITE(cw->m_val, 1 + TM_READ(cw->m_val));
              curr = cw;
          }
          ctr++;
          sum += TM_READ(curr->m_val);
          curr = TM_READ(curr->m_prev);
      }
  }
  
  // increment every seqth element, starting with start, moving forward
  TM_CALLABLE
  void DList::increment_chunk(int chunk_num, int chunk_size TM_ARG)
  {
      int startpoint = chunk_num * chunk_size;
  
      int sum = 0;
      Node* chunk_start(NULL);
      int ctr = 0;
  
      // forward traversal to compute sum and to find chunk_start
      const Node* prev(head);
      const Node* curr(TM_READ(prev->m_next));
      while (curr != tail) {
          // if this is the start of our chunk, save the pointer
          if (ctr++ == startpoint)
              chunk_start = const_cast<Node*>(curr);
          // add this value to the sum
          sum += TM_READ(curr->m_val);
          // move to next node
          curr = TM_READ(curr->m_next);
      }
      // OK, at this point we should have the ID of the chunk we're going to
      // work on.  increment everything in our chunk
      if (chunk_start != NULL) {
          // avoid TLS overhead on every loop iteration:
          Node* wr(chunk_start);
          // increment /chunk_size/ elements
          for (int i = 0; i < chunk_size; i++) {
              // don't increment if we reach the tail
              if (chunk_start == tail)
                  break;
              // increment, move to next
              TM_WRITE(wr->m_val, 1 + TM_READ(wr->m_val));
              wr = TM_READ(wr->m_next);
          }
      }
  }
  
  #endif // DLIST_HPP__
  