Subversion Repositories ESP8266_P1_Meter

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 raymond 1 
// Simple intrusive list class
2 
#pragma once
3 
 
4 
template<typename T> class SimpleIntrusiveList {
5 
  static_assert(std::is_same<decltype(std::declval<T>().next), T *>::value, "Template type must have public 'T* next' member");
6 
 
7 
public:
8 
  typedef T value_type;
9 
  typedef value_type *value_ptr_type;
10 
  typedef value_ptr_type *value_ptr_ptr_type;
11 
 
12 
  // Static utility methods
13 
  static size_t list_size(value_ptr_type chain) {
14 
    size_t count = 0;
15 
    for (auto c = chain; c != nullptr; c = c->next) {
16 
      ++count;
17 
    }
18 
    return count;
19 
  }
20 
 
21 
  static void delete_list(value_ptr_type chain) {
22 
    while (chain) {
23 
      auto t = chain;
24 
      chain = chain->next;
25 
      delete t;
26 
    }
27 
  }
28 
 
29 
public:
30 
  // Object methods
31 
 
32 
  SimpleIntrusiveList() : _head(nullptr), _tail(&_head) {}
33 
  ~SimpleIntrusiveList() {
34 
    clear();
35 
  }
36 
 
37 
  // Noncopyable, nonmovable
38 
  SimpleIntrusiveList(const SimpleIntrusiveList<T> &) = delete;
39 
  SimpleIntrusiveList(SimpleIntrusiveList<T> &&) = delete;
40 
  SimpleIntrusiveList<T> &operator=(const SimpleIntrusiveList<T> &) = delete;
41 
  SimpleIntrusiveList<T> &operator=(SimpleIntrusiveList<T> &&) = delete;
42 
 
43 
  inline void push_back(value_ptr_type obj) {
44 
    if (obj) {
45 
      *_tail = obj;
46 
      _tail = &obj->next;
47 
      ++_size;
48 
    }
49 
  }
50 
 
51 
  inline void push_front(value_ptr_type obj) {
52 
    if (obj) {
53 
      if (_head == nullptr) {
54 
        _tail = &obj->next;
55 
      }
56 
      obj->next = _head;
57 
      _head = obj;
58 
      ++_size;
59 
    }
60 
  }
61 
 
62 
  inline value_ptr_type pop_front() {
63 
    auto rv = _head;
64 
    if (_head) {
65 
      if (_tail == &_head->next) {
66 
        _tail = &_head;
67 
      }
68 
      _head = _head->next;
69 
      --_size;
70 
    }
71 
    return rv;
72 
  }
73 
 
74 
  inline void clear() {
75 
    // Assumes all elements were allocated with "new"
76 
    delete_list(_head);
77 
    _head = nullptr;
78 
    _tail = &_head;
79 
    _size = 0;
80 
  }
81 
 
82 
  inline size_t size() const {
83 
    return _size;
84 
  }
85 
 
86 
  template<typename function_type> inline value_ptr_type remove_if(const function_type &condition) {
87 
    value_ptr_type removed = nullptr;
88 
    value_ptr_ptr_type current_ptr = &_head;
89 
    while (*current_ptr != nullptr) {
90 
      value_ptr_type current = *current_ptr;
91 
      if (condition(*current)) {
92 
        // Remove this item from the list by moving the next item in
93 
        *current_ptr = current->next;
94 
        // If we were the last item, reset tail
95 
        if (current->next == nullptr) {
96 
          _tail = current_ptr;
97 
        }
98 
        --_size;
99 
        // Prepend this item to the removed list
100 
        current->next = removed;
101 
        removed = current;
102 
        // do not advance current_ptr
103 
      } else {
104 
        // advance current_ptr
105 
        current_ptr = &(*current_ptr)->next;
106 
      }
107 
    }
108 
 
109 
    // Return the removed entries
110 
    return removed;
111 
  }
112 
 
113 
  inline value_ptr_type begin() const {
114 
    return _head;
115 
  }
116 
 
117 
  bool validate_tail() const {
118 
    if (_head == nullptr) {
119 
      return (_tail == &_head);
120 
    }
121 
    auto p = _head;
122 
    while (p->next != nullptr) {
123 
      p = p->next;
124 
    }
125 
    return _tail == &p->next;
126 
  }
127 
 
128 
private:
129 
  // Data members
130 
  value_ptr_type _head;
131 
  value_ptr_ptr_type _tail;
132 
  size_t _size;
133 
 
134 
};  // class simple_intrusive_list