include/am-linkedlist.h
author David Anderson <danderson@mozilla.com>
Tue Aug 27 00:55:44 2013 -0700 (2013-08-27)
changeset 13 ef6b69693bab
parent 11 cfe800908837
permissions -rw-r--r--
Added missing hashmap tests.
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@11
    37
#include <am-moveable.h>
danderson@0
    38
danderson@0
    39
namespace ke {
danderson@0
    40
danderson@0
    41
// LinkedList, analagous to std::list or SourceHook::List. Since it performs a
danderson@0
    42
// malloc() and free() on every contained node, it should be avoided unless
danderson@0
    43
// absolutely necessary, or for when allocation performance is not a factor. It
danderson@0
    44
// is provided here to safely port old AlliedModders code to AMTL.
danderson@0
    45
//
danderson@0
    46
// In order to use a circular chain, LinkedList's allocation size includes
danderson@0
    47
// exactly one T. If T is very large, LinkedList should be allocated on the
danderson@0
    48
// heap, to avoid using the stack.
danderson@0
    49
template <class T, class AllocPolicy = SystemAllocatorPolicy>
danderson@0
    50
class LinkedList : public AllocPolicy
danderson@0
    51
{
danderson@0
    52
 public:
danderson@0
    53
  friend class iterator;
danderson@0
    54
danderson@0
    55
  class Node
danderson@0
    56
  {
danderson@0
    57
   public:
danderson@0
    58
    Node(const T &o)
danderson@0
    59
     : obj(o)
danderson@0
    60
    {
danderson@0
    61
    }
danderson@11
    62
    Node(Moveable<T> o)
danderson@11
    63
     : obj(o)
danderson@11
    64
    {
danderson@11
    65
    }
danderson@0
    66
danderson@0
    67
    T obj;
danderson@0
    68
    Node *next;
danderson@0
    69
    Node *prev;
danderson@0
    70
  };
danderson@0
    71
danderson@0
    72
public:
danderson@0
    73
  LinkedList(AllocPolicy = AllocPolicy())
danderson@0
    74
   : length_(0)
danderson@0
    75
  {
danderson@11
    76
    head()->prev = head();
danderson@11
    77
    head()->next = head();
danderson@0
    78
  }
danderson@0
    79
  ~LinkedList() {
danderson@0
    80
    clear();
danderson@0
    81
  }
danderson@0
    82
danderson@0
    83
  bool append(const T &obj) {
danderson@11
    84
    return insertBefore(end(), obj) != end();
danderson@11
    85
  }
danderson@11
    86
  bool append(Moveable<T> obj) {
danderson@11
    87
    return insertBefore(end(), obj) != end();
danderson@0
    88
  }
danderson@0
    89
danderson@0
    90
  bool prepend(const T &obj) {
danderson@11
    91
    return insertBefore(begin(), obj) != begin();
danderson@11
    92
  }
danderson@11
    93
  bool prepend(Moveable<T> obj) {
danderson@11
    94
    return insertBefore(begin(), obj) != begin();
danderson@0
    95
  }
danderson@0
    96
danderson@11
    97
  size_t length() const {
danderson@0
    98
    return length_;
danderson@0
    99
  }
danderson@0
   100
danderson@0
   101
  void clear() {
danderson@0
   102
    Node *node = head()->next;
danderson@0
   103
    Node *temp;
danderson@0
   104
    head()->next = head();
danderson@0
   105
    head()->prev = head();
danderson@0
   106
danderson@0
   107
    // Iterate through the nodes until we find the sentinel again.
danderson@0
   108
    while (node != head()) {
danderson@0
   109
      temp = node->next;
danderson@0
   110
      freeNode(node);
danderson@0
   111
      node = temp;
danderson@0
   112
    }
danderson@0
   113
    length_ = 0;
danderson@0
   114
  }
danderson@0
   115
danderson@0
   116
  bool empty() const {
danderson@0
   117
    return (length_ == 0);
danderson@0
   118
  }
danderson@0
   119
danderson@0
   120
  T &front() {
danderson@0
   121
    assert(!empty());
danderson@0
   122
    return head()->next->obj;
danderson@0
   123
  }
danderson@0
   124
  T &back() {
danderson@0
   125
    assert(!empty());
danderson@0
   126
    return head()->prev->obj;
danderson@0
   127
  }
danderson@0
   128
danderson@0
   129
 private:
danderson@0
   130
  const Node *head() const {
danderson@0
   131
    return sentinel_.address();
danderson@0
   132
  }
danderson@0
   133
  Node *head() {
danderson@0
   134
    return sentinel_.address();
danderson@0
   135
  }
danderson@0
   136
danderson@0
   137
  Node *allocNode(const T &obj) {
danderson@0
   138
    Node *node = (Node *)this->malloc(sizeof(Node));
danderson@0
   139
    if (!node)
danderson@0
   140
      return NULL;
danderson@0
   141
    new (node) Node(obj);
danderson@0
   142
    return node;
danderson@0
   143
  }
danderson@11
   144
  Node *allocNode(Moveable<T> obj) {
danderson@11
   145
    Node *node = (Node *)this->malloc(sizeof(Node));
danderson@11
   146
    if (!node)
danderson@11
   147
      return NULL;
danderson@11
   148
    new (node) Node(obj);
danderson@11
   149
    return node;
danderson@11
   150
  }
danderson@0
   151
danderson@0
   152
  void freeNode(Node *node) {
danderson@0
   153
    node->obj.~T();
danderson@0
   154
    this->free(node);
danderson@0
   155
  }
danderson@0
   156
danderson@0
   157
 private:
danderson@0
   158
  StorageBuffer<Node> sentinel_;
danderson@0
   159
  size_t length_;
danderson@0
   160
danderson@0
   161
 public:
danderson@0
   162
  class iterator
danderson@0
   163
  {
danderson@0
   164
    friend class LinkedList;
danderson@0
   165
danderson@0
   166
   public:
danderson@0
   167
    iterator()
danderson@0
   168
     : this_(NULL)
danderson@0
   169
    {
danderson@0
   170
    }
danderson@0
   171
    iterator(const LinkedList &src)
danderson@0
   172
     : this_(src.head())
danderson@0
   173
    {
danderson@0
   174
    }
danderson@0
   175
    iterator(Node *n)
danderson@0
   176
     : this_(n)
danderson@0
   177
    {
danderson@0
   178
    }
danderson@0
   179
    iterator(const iterator &where)
danderson@0
   180
     : this_(where.this_)
danderson@0
   181
    {
danderson@0
   182
    }
danderson@0
   183
danderson@0
   184
    iterator &operator --() {
danderson@0
   185
      if (this_)
danderson@0
   186
        this_ = this_->prev;
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_->prev;
danderson@0
   193
      return old;
danderson@0
   194
    }  
danderson@0
   195
    iterator &operator ++() {
danderson@0
   196
      if (this_)
danderson@0
   197
        this_ = this_->next;
danderson@0
   198
      return *this;
danderson@0
   199
    }
danderson@0
   200
    iterator operator ++(int) {
danderson@0
   201
      iterator old(*this);
danderson@0
   202
      if (this_)
danderson@0
   203
        this_ = this_->next;
danderson@0
   204
      return old;
danderson@0
   205
    }
danderson@0
   206
    
danderson@0
   207
    const T &operator * () const {
danderson@0
   208
      return this_->obj;
danderson@0
   209
    }
danderson@0
   210
    T &operator * () {
danderson@0
   211
      return this_->obj;
danderson@0
   212
    }
danderson@0
   213
    T *operator ->() {
danderson@0
   214
      return &this_->obj;
danderson@0
   215
    }
danderson@0
   216
    const T *operator ->() const {
danderson@0
   217
      return &(this_->obj);
danderson@0
   218
    }
danderson@0
   219
    
danderson@0
   220
    bool operator !=(const iterator &where) const {
danderson@0
   221
      return (this_ != where.this_);
danderson@0
   222
    }
danderson@0
   223
    bool operator ==(const iterator &where) const {
danderson@0
   224
      return (this_ == where.this_);
danderson@0
   225
    }
danderson@0
   226
danderson@0
   227
    operator bool() {
danderson@0
   228
      return !!this_;
danderson@0
   229
    }
danderson@0
   230
danderson@0
   231
   private:
danderson@0
   232
    Node *this_;
danderson@0
   233
  };
danderson@0
   234
danderson@11
   235
 private:
danderson@11
   236
  // Insert obj right before where.
danderson@11
   237
  iterator insert(iterator where, Node *node) {
danderson@0
   238
    if (!node)
danderson@0
   239
      return where;
danderson@0
   240
danderson@0
   241
    Node *pWhereNode = where.this_;
danderson@0
   242
    
danderson@0
   243
    pWhereNode->prev->next = node;
danderson@0
   244
    node->prev = pWhereNode->prev;
danderson@0
   245
    pWhereNode->prev = node;
danderson@0
   246
    node->next = pWhereNode;
danderson@0
   247
danderson@0
   248
    length_++;
danderson@0
   249
    return iterator(node);
danderson@0
   250
  }
danderson@0
   251
danderson@0
   252
 public:
danderson@11
   253
  iterator begin() {
danderson@11
   254
    return iterator(head()->next);
danderson@11
   255
  }
danderson@11
   256
  iterator end() {
danderson@11
   257
    return iterator(head());
danderson@11
   258
  }
danderson@11
   259
  iterator erase(iterator where) {
danderson@11
   260
    Node *pNode = where.this_;
danderson@11
   261
    iterator iter(where);
danderson@11
   262
    iter++;
danderson@11
   263
danderson@11
   264
    pNode->prev->next = pNode->next;
danderson@11
   265
    pNode->next->prev = pNode->prev;
danderson@11
   266
danderson@11
   267
    freeNode(pNode);
danderson@11
   268
    length_--;
danderson@11
   269
danderson@11
   270
    return iter;
danderson@11
   271
  }
danderson@11
   272
  iterator insertBefore(iterator where, const T &obj) {
danderson@11
   273
    return insert(where, allocNode(obj));
danderson@11
   274
  }
danderson@11
   275
  iterator insertBefore(iterator where, Moveable<T> obj) {
danderson@11
   276
    return insert(where, allocNode(obj));
danderson@11
   277
  }
danderson@11
   278
danderson@11
   279
 public:
danderson@11
   280
  // Removes one instance of |obj| from the list, if found.
danderson@0
   281
  void remove(const T &obj) {
danderson@0
   282
    for (iterator b = begin(); b != end(); b++) {
danderson@0
   283
      if (*b == obj) {
danderson@0
   284
        erase(b);
danderson@0
   285
        break;
danderson@0
   286
      }
danderson@0
   287
    }
danderson@0
   288
  }
danderson@0
   289
danderson@0
   290
  template <typename U>
danderson@11
   291
  iterator find(const U &equ) {
danderson@0
   292
    for (iterator iter = begin(); iter != end(); iter++) {
danderson@0
   293
      if (*iter == equ)
danderson@0
   294
        return iter;
danderson@0
   295
    }
danderson@0
   296
    return end();
danderson@0
   297
  }
danderson@0
   298
danderson@0
   299
danderson@0
   300
 private:
danderson@0
   301
  // These are disallowed because they basically violate the failure handling
danderson@0
   302
  // model for AllocPolicies and are also likely to have abysmal performance.
danderson@0
   303
  LinkedList &operator =(const LinkedList<T> &other) KE_DELETE;
danderson@0
   304
  LinkedList(const LinkedList<T> &other) KE_DELETE;
danderson@0
   305
};
danderson@0
   306
danderson@0
   307
} // namespace ke
danderson@0
   308
danderson@0
   309
#endif //_INCLUDE_CSDM_LIST_H