include/am-inlinelist.h
author David Anderson <dvander@alliedmods.net>
Sat Aug 24 02:36:11 2013 -0700 (2013-08-24)
changeset 9 4cd655ff4c2c
parent 0 ba3d4abaf3f1
child 11 cfe800908837
permissions -rw-r--r--
Fix HashTable/HashMap bugs, and add a clear() method.
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@0
    34
danderson@0
    35
namespace ke {
danderson@0
    36
danderson@0
    37
template <typename T> class InlineList;
danderson@0
    38
danderson@0
    39
template <typename T>
danderson@0
    40
class InlineListNode
danderson@0
    41
{
danderson@0
    42
  friend class InlineList<T>;
danderson@0
    43
danderson@0
    44
  public:
danderson@0
    45
  InlineListNode()
danderson@0
    46
    : next_(NULL),
danderson@0
    47
    prev_(NULL)
danderson@0
    48
  {
danderson@0
    49
  }
danderson@0
    50
danderson@0
    51
  InlineListNode(InlineListNode *next, InlineListNode *prev)
danderson@0
    52
    : next_(next),
danderson@0
    53
    prev_(prev)
danderson@0
    54
  {
danderson@0
    55
  }
danderson@0
    56
danderson@0
    57
  protected:
danderson@0
    58
  InlineListNode *next_;
danderson@0
    59
  InlineListNode *prev_;
danderson@0
    60
};
danderson@0
    61
danderson@0
    62
template <typename T>
danderson@0
    63
class InlineList
danderson@0
    64
{
danderson@0
    65
  typedef InlineListNode<T> Node;
danderson@0
    66
danderson@0
    67
  Node head_;
danderson@0
    68
danderson@0
    69
 public:
danderson@0
    70
  InlineList()
danderson@0
    71
    : head_(&head_, &head_)
danderson@0
    72
  {
danderson@0
    73
  }
danderson@0
    74
danderson@0
    75
 public:
danderson@0
    76
  class iterator
danderson@0
    77
  {
danderson@0
    78
    friend class InlineList;
danderson@0
    79
    Node *iter_;
danderson@0
    80
danderson@0
    81
   public:
danderson@0
    82
    iterator(Node *iter)
danderson@0
    83
      : iter_(iter)
danderson@0
    84
    {
danderson@0
    85
    }
danderson@0
    86
danderson@0
    87
    iterator & operator ++() {
danderson@0
    88
      iter_ = iter_->next;
danderson@0
    89
      return *iter_;
danderson@0
    90
    }
danderson@0
    91
    iterator operator ++(int) {
danderson@0
    92
      iterator old(*this);
danderson@0
    93
      iter_ = iter_->next_;
danderson@0
    94
      return old;
danderson@0
    95
    }
danderson@0
    96
    T * operator *() {
danderson@0
    97
      return static_cast<T *>(iter_);
danderson@0
    98
    }
danderson@0
    99
    T * operator ->() {
danderson@0
   100
      return static_cast<T *>(iter_);
danderson@0
   101
    }
danderson@0
   102
    bool operator !=(const iterator &where) const {
danderson@0
   103
      return iter_ != where.iter_;
danderson@0
   104
    }
danderson@0
   105
    bool operator ==(const iterator &where) const {
danderson@0
   106
      return iter_ == where.iter_;
danderson@0
   107
    }
danderson@0
   108
    iterator prev() const {
danderson@0
   109
      iterator p(iter_->prev_);
danderson@0
   110
      return p;
danderson@0
   111
    }
danderson@0
   112
    iterator next() const {
danderson@0
   113
      iterator p(iter_->next_);
danderson@0
   114
      return p;
danderson@0
   115
    }
danderson@0
   116
  };
danderson@0
   117
danderson@0
   118
  iterator begin() {
danderson@0
   119
    return iterator(head_.next_);
danderson@0
   120
  }
danderson@0
   121
danderson@0
   122
  iterator end() {
danderson@0
   123
    return iterator(&head_);
danderson@0
   124
  }
danderson@0
   125
danderson@0
   126
  void erase(Node *t) {
danderson@0
   127
    t->prev_->next_ = t->next_;
danderson@0
   128
    t->next_->prev_ = t->prev_;
danderson@0
   129
  }
danderson@0
   130
danderson@0
   131
  void insert(Node *t) {
danderson@0
   132
    t->prev_ = head_.prev_;
danderson@0
   133
    t->next_ = &head_;
danderson@0
   134
    head_.prev_->next_ = t;
danderson@0
   135
    head_.prev_ = t;
danderson@0
   136
  }
danderson@0
   137
};
danderson@0
   138
danderson@0
   139
}
danderson@0
   140
danderson@0
   141
#endif // _include_amtl_inline_list_h_
danderson@0
   142