machine/linkedlist.hpp

   1 #ifndef RBX_LINKEDLIST_HPP
   2 #define RBX_LINKEDLIST_HPP
   3
   4 #include "spinlock.hpp"
   5
   6 #include <stdio.h>
   7 #include <assert.h>
   8 #include <mutex>
   9
  10 namespace rubinius{
  11 class LinkedList {
  12 public:
  13
  14   class Node {
  15   private:
  16     Node* next_;
  17     Node* prev_;
  18
  19   public:
  20     Node()
  21       : next_(NULL)
  22       , prev_(NULL)
  23     { }
  24
  25     Node* next() const {
  26       return next_;
  27     }
  28
  29     Node* prev() const {
  30       return prev_;
  31     }
  32
  33     void set_next(Node* n) {
  34       next_ = n;
  35     }
  36
  37     void set_prev(Node* n) {
  38       prev_ = n;
  39     }
  40
  41     void remove_linkage() {
  42       if(next_) {
  43         assert(next_->prev() == this);
  44         next_->set_prev(prev_);
  45       }
  46
  47       if(prev_) {
  48         assert(prev_->next() == this);
  49         prev_->set_next(next_);
  50       }
  51
  52       next_ = NULL;
  53       prev_ = NULL;
  54     }
  55   };
  56
  57 private:
  58   Node* head_;
  59   size_t count_;
  60   locks::spinlock_mutex lock_;
  61
  62 public:
  63   LinkedList()
  64     : head_(NULL)
  65     , count_(0)
  66     , lock_()
  67   { }
  68
  69   Node* head() {
  70     std::lock_guard<locks::spinlock_mutex> guard(lock_);
  71
  72     return head_;
  73   }
  74
  75   size_t size() {
  76     std::lock_guard<locks::spinlock_mutex> guard(lock_);
  77
  78     return count_;
  79   }
  80
  81   void add(Node*);
  82   void remove(Node*);
  83
  84   // Utility templates
  85   template <typename Roots, typename Root>
  86   class Iterator {
  87     Roots& roots_;
  88     Root* current_;
  89
  90   public:
  91     Iterator(Roots& roots)
  92       : roots_(roots)
  93       , current_(roots.front())
  94     {}
  95
  96     bool more() const {
  97       return current_ != 0;
  98     }
  99
 100     void advance() {
 101       current_ = static_cast<Root*>(current_->next());
 102     }
 103
 104     Root* operator->() const {
 105       return current_;
 106     }
 107
 108     Root* current() const {
 109       return current_;
 110     }
 111
 112     Root* next() const {
 113       Root* ret = current_;
 114       if(current_) {
 115         current_ = static_cast<Root*>(current_->next());
 116       }
 117
 118       return ret;
 119     }
 120   };
 121
 122
 123 };
 124 }
 125
 126 #endif