l7vsd/include/lockfree_queue.h

   1 #ifndef LOCKFREE_QUEUE_H
   2 #define LOCKFREE_QUEUE_H
   3
   4 #include <boost/noncopyable.hpp>
   5
   6 #include "utility.h"
   7
   8 namespace l7vs
   9 {
  10
  11 template<class Tvalue>
  12 class lockfree_queue : protected boost::noncopyable
  13 {
  14 protected:
  15         struct node_type {
  16                 Tvalue            *value;
  17                 node_type() : value(NULL) {}
  18         };
  19         mutable volatile size_t    counter;
  20         volatile size_t            headloc;
  21         volatile size_t            tailloc;
  22
  23         volatile node_type        *node;
  24         const size_t            element_num;
  25 public:
  26         // constructor
  27         explicit lockfree_queue(size_t num = 65535) : counter(0), element_num(num) {
  28                 node = new node_type[element_num];
  29                 headloc = tailloc = 0;
  30         }
  31
  32         // destructor
  33         ~lockfree_queue() {
  34                 delete [] node;
  35         }
  36
  37         //pusher
  38         bool push(const Tvalue *value) {
  39                 size_t tail, nexttail;
  40                 //transaction st
  41                 while (true) {
  42 start:
  43                         tail = tailloc;
  44                         nexttail = get_num_next(tail);
  45                         if (unlikely(node[tail].value)) {
  46                                 //return false;
  47                                 //do spin case of full queue
  48                                 goto start;
  49                         }
  50                         if (likely(__sync_bool_compare_and_swap(&tailloc, tail, nexttail))) break;
  51                 }
  52                 //transaction ed
  53                 node[tail].value = const_cast<Tvalue *>(value);
  54                 __sync_add_and_fetch(&counter, 1);
  55                 return true;
  56         }
  57
  58         //popper
  59         Tvalue *pop() {
  60                 size_t head, nexthead;
  61                 Tvalue *rtnvalue;
  62                 //transaction st
  63                 while (true) {
  64                         head = headloc;
  65                         nexthead = get_num_next(head);
  66                         if (unlikely(!(node[head].value))) {
  67                                 if (unlikely(headloc == tailloc)) {
  68                                         //false
  69                                         return NULL;
  70                                 }
  71                         } else {
  72                                 if (likely(__sync_bool_compare_and_swap(&headloc, head, nexthead))) {
  73                                         rtnvalue = node[head].value;
  74                                         break;
  75                                 }
  76                         }
  77                 }
  78                 //transaction ed
  79                 __sync_sub_and_fetch(&counter, 1);
  80                 node[head].value = NULL;
  81                 return rtnvalue;
  82         }
  83
  84         //size
  85         size_t size() const {
  86                 return counter;
  87         }
  88
  89         //empty
  90         bool empty() const {
  91                 return !counter;
  92         }
  93
  94 private:
  95         //get next value head and tail cyclic over elemental number
  96         size_t get_num_next(const size_t num) {
  97                 if (unlikely(num + 1 >= element_num)) {
  98                         return 0;
  99                 } else {
 100                         return num + 1;
 101                 }
 102         }
 103 };
 104
 105 } // namespace l7vs
 106
 107 #endif    // LOCKFREE_QUEUE_H