include/am-inlinelist.h
author David Anderson <danderson@mozilla.com>
Tue Aug 27 00:49:33 2013 -0700 (2013-08-27)
changeset 12 cebfc7eeafa5
parent 11 cfe800908837
child 17 563aea5eba06
permissions -rw-r--r--
Added hash table 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_inline_list_h_
danderson@0
    31
#define _include_amtl_inline_list_h_
danderson@0
    32
danderson@0
    33
#include <stddef.h>
danderson@11
    34
#include <assert.h>
danderson@0
    35
danderson@0
    36
namespace ke {
danderson@0
    37
danderson@0
    38
template <typename T> class InlineList;
danderson@0
    39
danderson@11
    40
// Objects can recursively inherit from InlineListNode in order to have
danderson@11
    41
// membership in an InlineList<T>.
danderson@0
    42
template <typename T>
danderson@0
    43
class InlineListNode
danderson@0
    44
{
danderson@0
    45
  friend class InlineList<T>;
danderson@0
    46
danderson@0
    47
  public:
danderson@0
    48
  InlineListNode()
danderson@11
    49
   : next_(NULL),
danderson@11
    50
     prev_(NULL)
danderson@0
    51
  {
danderson@0
    52
  }
danderson@0
    53
danderson@0
    54
  InlineListNode(InlineListNode *next, InlineListNode *prev)
danderson@11
    55
   : next_(next),
danderson@11
    56
     prev_(prev)
danderson@0
    57
  {
danderson@0
    58
  }
danderson@0
    59
danderson@0
    60
  protected:
danderson@0
    61
  InlineListNode *next_;
danderson@0
    62
  InlineListNode *prev_;
danderson@0
    63
};
danderson@0
    64
danderson@11
    65
// An InlineList is a linked list that threads link pointers through objects,
danderson@11
    66
// rather than allocating node memory. A node can be in at most one list at
danderson@11
    67
// any time.
danderson@11
    68
//
danderson@11
    69
// Since InlineLists are designed to be very cheap, there is no requirement
danderson@11
    70
// that elements be removed from a list once the list is destructed. However,
danderson@11
    71
// for as long as the list is alive, all of its contained nodes must also
danderson@11
    72
// be alive.
danderson@0
    73
template <typename T>
danderson@0
    74
class InlineList
danderson@0
    75
{
danderson@0
    76
  typedef InlineListNode<T> Node;
danderson@0
    77
danderson@0
    78
  Node head_;
danderson@0
    79
danderson@11
    80
  // Work around a clang bug where we can't initialize with &head_ in the ctor.
danderson@11
    81
  inline Node *head() {
danderson@11
    82
    return &head_;
danderson@11
    83
  }
danderson@11
    84
danderson@0
    85
 public:
danderson@0
    86
  InlineList()
danderson@11
    87
    : head_(head(), head())
danderson@11
    88
  {
danderson@11
    89
  }
danderson@11
    90
danderson@11
    91
  ~InlineList()
danderson@0
    92
  {
danderson@11
    93
#if !defined(NDEBUG)
danderson@11
    94
    // Remove all items to clear their next/prev fields.
danderson@11
    95
    while (begin() != end())
danderson@11
    96
      remove(*begin());
danderson@11
    97
#endif
danderson@0
    98
  }
danderson@0
    99
danderson@0
   100
 public:
danderson@0
   101
  class iterator
danderson@0
   102
  {
danderson@0
   103
    friend class InlineList;
danderson@0
   104
    Node *iter_;
danderson@0
   105
danderson@0
   106
   public:
danderson@0
   107
    iterator(Node *iter)
danderson@0
   108
      : iter_(iter)
danderson@0
   109
    {
danderson@0
   110
    }
danderson@0
   111
danderson@0
   112
    iterator & operator ++() {
danderson@0
   113
      iter_ = iter_->next;
danderson@11
   114
      return *this;
danderson@0
   115
    }
danderson@0
   116
    iterator operator ++(int) {
danderson@0
   117
      iterator old(*this);
danderson@0
   118
      iter_ = iter_->next_;
danderson@0
   119
      return old;
danderson@0
   120
    }
danderson@0
   121
    T * operator *() {
danderson@0
   122
      return static_cast<T *>(iter_);
danderson@0
   123
    }
danderson@0
   124
    T * operator ->() {
danderson@0
   125
      return static_cast<T *>(iter_);
danderson@0
   126
    }
danderson@0
   127
    bool operator !=(const iterator &where) const {
danderson@0
   128
      return iter_ != where.iter_;
danderson@0
   129
    }
danderson@0
   130
    bool operator ==(const iterator &where) const {
danderson@0
   131
      return iter_ == where.iter_;
danderson@0
   132
    }
danderson@0
   133
  };
danderson@0
   134
danderson@0
   135
  iterator begin() {
danderson@0
   136
    return iterator(head_.next_);
danderson@0
   137
  }
danderson@0
   138
danderson@0
   139
  iterator end() {
danderson@0
   140
    return iterator(&head_);
danderson@0
   141
  }
danderson@0
   142
danderson@11
   143
  void remove(Node *t) {
danderson@0
   144
    t->prev_->next_ = t->next_;
danderson@0
   145
    t->next_->prev_ = t->prev_;
danderson@11
   146
danderson@11
   147
#if !defined(NDEBUG)
danderson@11
   148
    t->next_ = NULL;
danderson@11
   149
    t->prev_ = NULL;
danderson@11
   150
#endif
danderson@0
   151
  }
danderson@0
   152
danderson@11
   153
  void append(Node *t) {
danderson@11
   154
    assert(!t->next_);
danderson@11
   155
    assert(!t->prev_);
danderson@11
   156
danderson@0
   157
    t->prev_ = head_.prev_;
danderson@0
   158
    t->next_ = &head_;
danderson@0
   159
    head_.prev_->next_ = t;
danderson@0
   160
    head_.prev_ = t;
danderson@0
   161
  }
danderson@0
   162
};
danderson@0
   163
danderson@0
   164
}
danderson@0
   165
danderson@0
   166
#endif // _include_amtl_inline_list_h_
danderson@0
   167