include/am-linkedlist.h
author David Anderson <danderson@mozilla.com>
Fri Aug 23 20:34:17 2013 -0700 (2013-08-23)
changeset 0 ba3d4abaf3f1
child 11 cfe800908837
permissions -rw-r--r--
Initial import.
danderson@0
     1
// vim: set sts=8 ts=2 sw=2 tw=99 et:
danderson@0
     2
//
danderson@0
     3
// Copyright (C) 2013, David Anderson and AlliedModders LLC
danderson@0
     4
// All rights reserved.
danderson@0
     5
// 
danderson@0
     6
// Redistribution and use in source and binary forms, with or without
danderson@0
     7
// modification, are permitted provided that the following conditions are met:
danderson@0
     8
// 
danderson@0
     9
//  * Redistributions of source code must retain the above copyright notice, this
danderson@0
    10
//    list of conditions and the following disclaimer.
danderson@0
    11
//  * Redistributions in binary form must reproduce the above copyright notice,
danderson@0
    12
//    this list of conditions and the following disclaimer in the documentation
danderson@0
    13
//    and/or other materials provided with the distribution.
danderson@0
    14
//  * Neither the name of AlliedModders LLC nor the names of its contributors
danderson@0
    15
//    may be used to endorse or promote products derived from this software
danderson@0
    16
//    without specific prior written permission.
danderson@0
    17
//
danderson@0
    18
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
danderson@0
    19
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
danderson@0
    20
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
danderson@0
    21
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
danderson@0
    22
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
danderson@0
    23
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
danderson@0
    24
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
danderson@0
    25
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
danderson@0
    26
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
danderson@0
    27
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
danderson@0
    28
// POSSIBILITY OF SUCH DAMAGE.
danderson@0
    29
danderson@0
    30
#ifndef _include_amtl_linkedlist_h_
danderson@0
    31
#define _include_amtl_linkedlist_h_
danderson@0
    32
danderson@0
    33
#include <new>
danderson@0
    34
#include <stdlib.h>
danderson@0
    35
#include <am-allocator-policies.h>
danderson@0
    36
#include <am-utility.h>
danderson@0
    37
danderson@0
    38
namespace ke {
danderson@0
    39
danderson@0
    40
// LinkedList, analagous to std::list or SourceHook::List. Since it performs a
danderson@0
    41
// malloc() and free() on every contained node, it should be avoided unless
danderson@0
    42
// absolutely necessary, or for when allocation performance is not a factor. It
danderson@0
    43
// is provided here to safely port old AlliedModders code to AMTL.
danderson@0
    44
//
danderson@0
    45
// In order to use a circular chain, LinkedList's allocation size includes
danderson@0
    46
// exactly one T. If T is very large, LinkedList should be allocated on the
danderson@0
    47
// heap, to avoid using the stack.
danderson@0
    48
template <class T, class AllocPolicy = SystemAllocatorPolicy>
danderson@0
    49
class LinkedList : public AllocPolicy
danderson@0
    50
{
danderson@0
    51
 public:
danderson@0
    52
  friend class iterator;
danderson@0
    53
danderson@0
    54
  class Node
danderson@0
    55
  {
danderson@0
    56
   public:
danderson@0
    57
    Node(const T &o)
danderson@0
    58
     : obj(o)
danderson@0
    59
    {
danderson@0
    60
    }
danderson@0
    61
danderson@0
    62
    T obj;
danderson@0
    63
    Node *next;
danderson@0
    64
    Node *prev;
danderson@0
    65
  };
danderson@0
    66
danderson@0
    67
public:
danderson@0
    68
  LinkedList(AllocPolicy = AllocPolicy())
danderson@0
    69
   : length_(0)
danderson@0
    70
  {
danderson@0
    71
  }
danderson@0
    72
  ~LinkedList() {
danderson@0
    73
    clear();
danderson@0
    74
  }
danderson@0
    75
danderson@0
    76
  bool append(const T &obj) {
danderson@0
    77
    Node *node = allocNode(obj);
danderson@0
    78
    if (!node)
danderson@0
    79
      return false;
danderson@0
    80
danderson@0
    81
    node->prev = head()->prev;
danderson@0
    82
    node->next = head();
danderson@0
    83
    head()->prev->next = node;
danderson@0
    84
    head()->prev = node;
danderson@0
    85
danderson@0
    86
    length_++;
danderson@0
    87
  }
danderson@0
    88
danderson@0
    89
  bool prepend(const T &obj) {
danderson@0
    90
    return insert(begin(), obj);
danderson@0
    91
  }
danderson@0
    92
danderson@0
    93
  size_t size() const {
danderson@0
    94
    return length_;
danderson@0
    95
  }
danderson@0
    96
danderson@0
    97
  void clear() {
danderson@0
    98
    Node *node = head()->next;
danderson@0
    99
    Node *temp;
danderson@0
   100
    head()->next = head();
danderson@0
   101
    head()->prev = head();
danderson@0
   102
danderson@0
   103
    // Iterate through the nodes until we find the sentinel again.
danderson@0
   104
    while (node != head()) {
danderson@0
   105
      temp = node->next;
danderson@0
   106
      freeNode(node);
danderson@0
   107
      node = temp;
danderson@0
   108
    }
danderson@0
   109
    length_ = 0;
danderson@0
   110
  }
danderson@0
   111
danderson@0
   112
  bool empty() const {
danderson@0
   113
    return (length_ == 0);
danderson@0
   114
  }
danderson@0
   115
danderson@0
   116
  T &front() {
danderson@0
   117
    assert(!empty());
danderson@0
   118
    return head()->next->obj;
danderson@0
   119
  }
danderson@0
   120
  T &back() {
danderson@0
   121
    assert(!empty());
danderson@0
   122
    return head()->prev->obj;
danderson@0
   123
  }
danderson@0
   124
danderson@0
   125
 private:
danderson@0
   126
  const Node *head() const {
danderson@0
   127
    return sentinel_.address();
danderson@0
   128
  }
danderson@0
   129
  Node *head() {
danderson@0
   130
    return sentinel_.address();
danderson@0
   131
  }
danderson@0
   132
danderson@0
   133
  Node *allocNode(const T &obj) {
danderson@0
   134
    Node *node = (Node *)this->malloc(sizeof(Node));
danderson@0
   135
    if (!node)
danderson@0
   136
      return NULL;
danderson@0
   137
    new (node) Node(obj);
danderson@0
   138
    return node;
danderson@0
   139
  }
danderson@0
   140
danderson@0
   141
  void freeNode(Node *node) {
danderson@0
   142
    node->obj.~T();
danderson@0
   143
    this->free(node);
danderson@0
   144
  }
danderson@0
   145
danderson@0
   146
 private:
danderson@0
   147
  StorageBuffer<Node> sentinel_;
danderson@0
   148
  size_t length_;
danderson@0
   149
danderson@0
   150
 public:
danderson@0
   151
  class iterator
danderson@0
   152
  {
danderson@0
   153
    friend class LinkedList;
danderson@0
   154
danderson@0
   155
   public:
danderson@0
   156
    iterator()
danderson@0
   157
     : this_(NULL)
danderson@0
   158
    {
danderson@0
   159
    }
danderson@0
   160
    iterator(const LinkedList &src)
danderson@0
   161
     : this_(src.head())
danderson@0
   162
    {
danderson@0
   163
    }
danderson@0
   164
    iterator(Node *n)
danderson@0
   165
     : this_(n)
danderson@0
   166
    {
danderson@0
   167
    }
danderson@0
   168
    iterator(const iterator &where)
danderson@0
   169
     : this_(where.this_)
danderson@0
   170
    {
danderson@0
   171
    }
danderson@0
   172
danderson@0
   173
    iterator &operator --() {
danderson@0
   174
      if (this_)
danderson@0
   175
        this_ = this_->prev;
danderson@0
   176
      return *this;
danderson@0
   177
    }
danderson@0
   178
    iterator operator --(int) {
danderson@0
   179
      iterator old(*this);
danderson@0
   180
      if (this_)
danderson@0
   181
        this_ = this_->prev;
danderson@0
   182
      return old;
danderson@0
   183
    }  
danderson@0
   184
    iterator &operator ++() {
danderson@0
   185
      if (this_)
danderson@0
   186
        this_ = this_->next;
danderson@0
   187
      return *this;
danderson@0
   188
    }
danderson@0
   189
    iterator operator ++(int) {
danderson@0
   190
      iterator old(*this);
danderson@0
   191
      if (this_)
danderson@0
   192
        this_ = this_->next;
danderson@0
   193
      return old;
danderson@0
   194
    }
danderson@0
   195
    
danderson@0
   196
    const T &operator * () const {
danderson@0
   197
      return this_->obj;
danderson@0
   198
    }
danderson@0
   199
    T &operator * () {
danderson@0
   200
      return this_->obj;
danderson@0
   201
    }
danderson@0
   202
    T *operator ->() {
danderson@0
   203
      return &this_->obj;
danderson@0
   204
    }
danderson@0
   205
    const T *operator ->() const {
danderson@0
   206
      return &(this_->obj);
danderson@0
   207
    }
danderson@0
   208
    
danderson@0
   209
    bool operator !=(const iterator &where) const {
danderson@0
   210
      return (this_ != where.this_);
danderson@0
   211
    }
danderson@0
   212
    bool operator ==(const iterator &where) const {
danderson@0
   213
      return (this_ == where.this_);
danderson@0
   214
    }
danderson@0
   215
danderson@0
   216
    operator bool() {
danderson@0
   217
      return !!this_;
danderson@0
   218
    }
danderson@0
   219
danderson@0
   220
   private:
danderson@0
   221
    Node *this_;
danderson@0
   222
  };
danderson@0
   223
danderson@0
   224
 public:
danderson@0
   225
  iterator begin() const {
danderson@0
   226
    return iterator(head()->next);
danderson@0
   227
  }
danderson@0
   228
  iterator end() const {
danderson@0
   229
    return iterator(head());
danderson@0
   230
  }
danderson@0
   231
  iterator erase(iterator &where) {
danderson@0
   232
    Node *pNode = where.this_;
danderson@0
   233
    iterator iter(where);
danderson@0
   234
    iter++;
danderson@0
   235
danderson@0
   236
    pNode->prev->next = pNode->next;
danderson@0
   237
    pNode->next->prev = pNode->prev;
danderson@0
   238
danderson@0
   239
    freeNode(pNode);
danderson@0
   240
    length_--;
danderson@0
   241
danderson@0
   242
    return iter;
danderson@0
   243
  }
danderson@0
   244
  iterator insert(iterator where, const T &obj) {
danderson@0
   245
    // Insert obj right before where
danderson@0
   246
    Node *node = allocNode(obj);
danderson@0
   247
    if (!node)
danderson@0
   248
      return where;
danderson@0
   249
danderson@0
   250
    Node *pWhereNode = where.this_;
danderson@0
   251
    
danderson@0
   252
    pWhereNode->prev->next = node;
danderson@0
   253
    node->prev = pWhereNode->prev;
danderson@0
   254
    pWhereNode->prev = node;
danderson@0
   255
    node->next = pWhereNode;
danderson@0
   256
danderson@0
   257
    length_++;
danderson@0
   258
    return iterator(node);
danderson@0
   259
  }
danderson@0
   260
danderson@0
   261
 public:
danderson@0
   262
  void remove(const T &obj) {
danderson@0
   263
    for (iterator b = begin(); b != end(); b++) {
danderson@0
   264
      if (*b == obj) {
danderson@0
   265
        erase(b);
danderson@0
   266
        break;
danderson@0
   267
      }
danderson@0
   268
    }
danderson@0
   269
  }
danderson@0
   270
danderson@0
   271
  template <typename U>
danderson@0
   272
  iterator find(const U &equ) const {
danderson@0
   273
    for (iterator iter = begin(); iter != end(); iter++) {
danderson@0
   274
      if (*iter == equ)
danderson@0
   275
        return iter;
danderson@0
   276
    }
danderson@0
   277
    return end();
danderson@0
   278
  }
danderson@0
   279
danderson@0
   280
danderson@0
   281
 private:
danderson@0
   282
  // These are disallowed because they basically violate the failure handling
danderson@0
   283
  // model for AllocPolicies and are also likely to have abysmal performance.
danderson@0
   284
  LinkedList &operator =(const LinkedList<T> &other) KE_DELETE;
danderson@0
   285
  LinkedList(const LinkedList<T> &other) KE_DELETE;
danderson@0
   286
};
danderson@0
   287
danderson@0
   288
} // namespace ke
danderson@0
   289
danderson@0
   290
#endif //_INCLUDE_CSDM_LIST_H