1.1 --- a/public/amtl/am-inlinelist.h	Thu Aug 29 14:16:18 2013 -0400
     1.2 +++ b/public/amtl/am-inlinelist.h	Thu Aug 29 11:45:28 2013 -0700
     1.3 @@ -31,11 +31,14 @@
     1.4  #define _include_amtl_inline_list_h_
     1.5  
     1.6  #include <stddef.h>
     1.7 +#include <assert.h>
     1.8  
     1.9  namespace ke {
    1.10  
    1.11  template <typename T> class InlineList;
    1.12  
    1.13 +// Objects can recursively inherit from InlineListNode in order to have
    1.14 +// membership in an InlineList<T>.
    1.15  template <typename T>
    1.16  class InlineListNode
    1.17  {
    1.18 @@ -43,14 +46,14 @@
    1.19  
    1.20    public:
    1.21    InlineListNode()
    1.22 -    : next_(NULL),
    1.23 -    prev_(NULL)
    1.24 +   : next_(NULL),
    1.25 +     prev_(NULL)
    1.26    {
    1.27    }
    1.28  
    1.29    InlineListNode(InlineListNode *next, InlineListNode *prev)
    1.30 -    : next_(next),
    1.31 -    prev_(prev)
    1.32 +   : next_(next),
    1.33 +     prev_(prev)
    1.34    {
    1.35    }
    1.36  
    1.37 @@ -59,6 +62,14 @@
    1.38    InlineListNode *prev_;
    1.39  };
    1.40  
    1.41 +// An InlineList is a linked list that threads link pointers through objects,
    1.42 +// rather than allocating node memory. A node can be in at most one list at
    1.43 +// any time.
    1.44 +//
    1.45 +// Since InlineLists are designed to be very cheap, there is no requirement
    1.46 +// that elements be removed from a list once the list is destructed. However,
    1.47 +// for as long as the list is alive, all of its contained nodes must also
    1.48 +// be alive.
    1.49  template <typename T>
    1.50  class InlineList
    1.51  {
    1.52 @@ -66,10 +77,24 @@
    1.53  
    1.54    Node head_;
    1.55  
    1.56 +  // Work around a clang bug where we can't initialize with &head_ in the ctor.
    1.57 +  inline Node *head() {
    1.58 +    return &head_;
    1.59 +  }
    1.60 +
    1.61   public:
    1.62    InlineList()
    1.63 -    : head_(&head_, &head_)
    1.64 +    : head_(head(), head())
    1.65 +  {
    1.66 +  }
    1.67 +
    1.68 +  ~InlineList()
    1.69    {
    1.70 +#if !defined(NDEBUG)
    1.71 +    // Remove all items to clear their next/prev fields.
    1.72 +    while (begin() != end())
    1.73 +      remove(*begin());
    1.74 +#endif
    1.75    }
    1.76  
    1.77   public:
    1.78 @@ -86,7 +111,7 @@
    1.79  
    1.80      iterator & operator ++() {
    1.81        iter_ = iter_->next;
    1.82 -      return *iter_;
    1.83 +      return *this;
    1.84      }
    1.85      iterator operator ++(int) {
    1.86        iterator old(*this);
    1.87 @@ -105,14 +130,6 @@
    1.88      bool operator ==(const iterator &where) const {
    1.89        return iter_ == where.iter_;
    1.90      }
    1.91 -    iterator prev() const {
    1.92 -      iterator p(iter_->prev_);
    1.93 -      return p;
    1.94 -    }
    1.95 -    iterator next() const {
    1.96 -      iterator p(iter_->next_);
    1.97 -      return p;
    1.98 -    }
    1.99    };
   1.100  
   1.101    iterator begin() {
   1.102 @@ -126,9 +143,17 @@
   1.103    void remove(Node *t) {
   1.104      t->prev_->next_ = t->next_;
   1.105      t->next_->prev_ = t->prev_;
   1.106 +
   1.107 +#if !defined(NDEBUG)
   1.108 +    t->next_ = NULL;
   1.109 +    t->prev_ = NULL;
   1.110 +#endif
   1.111    }
   1.112  
   1.113 -  void insert(Node *t) {
   1.114 +  void append(Node *t) {
   1.115 +    assert(!t->next_);
   1.116 +    assert(!t->prev_);
   1.117 +
   1.118      t->prev_ = head_.prev_;
   1.119      t->next_ = &head_;
   1.120      head_.prev_->next_ = t;

     2.1 --- a/public/amtl/am-linkedlist.h	Thu Aug 29 14:16:18 2013 -0400
     2.2 +++ b/public/amtl/am-linkedlist.h	Thu Aug 29 11:45:28 2013 -0700
     2.3 @@ -34,6 +34,7 @@
     2.4  #include <stdlib.h>
     2.5  #include <am-allocator-policies.h>
     2.6  #include <am-utility.h>
     2.7 +#include <am-moveable.h>
     2.8  
     2.9  namespace ke {
    2.10  
    2.11 @@ -58,6 +59,10 @@
    2.12       : obj(o)
    2.13      {
    2.14      }
    2.15 +    Node(Moveable<T> o)
    2.16 +     : obj(o)
    2.17 +    {
    2.18 +    }
    2.19  
    2.20      T obj;
    2.21      Node *next;
    2.22 @@ -68,29 +73,28 @@
    2.23    LinkedList(AllocPolicy = AllocPolicy())
    2.24     : length_(0)
    2.25    {
    2.26 +    head()->prev = head();
    2.27 +    head()->next = head();
    2.28    }
    2.29    ~LinkedList() {
    2.30      clear();
    2.31    }
    2.32  
    2.33    bool append(const T &obj) {
    2.34 -    Node *node = allocNode(obj);
    2.35 -    if (!node)
    2.36 -      return false;
    2.37 -
    2.38 -    node->prev = head()->prev;
    2.39 -    node->next = head();
    2.40 -    head()->prev->next = node;
    2.41 -    head()->prev = node;
    2.42 -
    2.43 -    length_++;
    2.44 +    return insertBefore(end(), obj) != end();
    2.45 +  }
    2.46 +  bool append(Moveable<T> obj) {
    2.47 +    return insertBefore(end(), obj) != end();
    2.48    }
    2.49  
    2.50    bool prepend(const T &obj) {
    2.51 -    return insert(begin(), obj);
    2.52 +    return insertBefore(begin(), obj) != begin();
    2.53 +  }
    2.54 +  bool prepend(Moveable<T> obj) {
    2.55 +    return insertBefore(begin(), obj) != begin();
    2.56    }
    2.57  
    2.58 -  size_t size() const {
    2.59 +  size_t length() const {
    2.60      return length_;
    2.61    }
    2.62  
    2.63 @@ -137,6 +141,13 @@
    2.64      new (node) Node(obj);
    2.65      return node;
    2.66    }
    2.67 +  Node *allocNode(Moveable<T> obj) {
    2.68 +    Node *node = (Node *)this->malloc(sizeof(Node));
    2.69 +    if (!node)
    2.70 +      return NULL;
    2.71 +    new (node) Node(obj);
    2.72 +    return node;
    2.73 +  }
    2.74  
    2.75    void freeNode(Node *node) {
    2.76      node->obj.~T();
    2.77 @@ -221,29 +232,9 @@
    2.78      Node *this_;
    2.79    };
    2.80  
    2.81 - public:
    2.82 -  iterator begin() const {
    2.83 -    return iterator(head()->next);
    2.84 -  }
    2.85 -  iterator end() const {
    2.86 -    return iterator(head());
    2.87 -  }
    2.88 -  iterator erase(iterator &where) {
    2.89 -    Node *pNode = where.this_;
    2.90 -    iterator iter(where);
    2.91 -    iter++;
    2.92 -
    2.93 -    pNode->prev->next = pNode->next;
    2.94 -    pNode->next->prev = pNode->prev;
    2.95 -
    2.96 -    freeNode(pNode);
    2.97 -    length_--;
    2.98 -
    2.99 -    return iter;
   2.100 -  }
   2.101 -  iterator insert(iterator where, const T &obj) {
   2.102 -    // Insert obj right before where
   2.103 -    Node *node = allocNode(obj);
   2.104 + private:
   2.105 +  // Insert obj right before where.
   2.106 +  iterator insert(iterator where, Node *node) {
   2.107      if (!node)
   2.108        return where;
   2.109  
   2.110 @@ -259,6 +250,34 @@
   2.111    }
   2.112  
   2.113   public:
   2.114 +  iterator begin() {
   2.115 +    return iterator(head()->next);
   2.116 +  }
   2.117 +  iterator end() {
   2.118 +    return iterator(head());
   2.119 +  }
   2.120 +  iterator erase(iterator where) {
   2.121 +    Node *pNode = where.this_;
   2.122 +    iterator iter(where);
   2.123 +    iter++;
   2.124 +
   2.125 +    pNode->prev->next = pNode->next;
   2.126 +    pNode->next->prev = pNode->prev;
   2.127 +
   2.128 +    freeNode(pNode);
   2.129 +    length_--;
   2.130 +
   2.131 +    return iter;
   2.132 +  }
   2.133 +  iterator insertBefore(iterator where, const T &obj) {
   2.134 +    return insert(where, allocNode(obj));
   2.135 +  }
   2.136 +  iterator insertBefore(iterator where, Moveable<T> obj) {
   2.137 +    return insert(where, allocNode(obj));
   2.138 +  }
   2.139 +
   2.140 + public:
   2.141 +  // Removes one instance of |obj| from the list, if found.
   2.142    void remove(const T &obj) {
   2.143      for (iterator b = begin(); b != end(); b++) {
   2.144        if (*b == obj) {
   2.145 @@ -269,7 +288,7 @@
   2.146    }
   2.147  
   2.148    template <typename U>
   2.149 -  iterator find(const U &equ) const {
   2.150 +  iterator find(const U &equ) {
   2.151      for (iterator iter = begin(); iter != end(); iter++) {
   2.152        if (*iter == equ)
   2.153          return iter;

     3.1 --- a/public/amtl/am-moveable.h	Thu Aug 29 14:16:18 2013 -0400
     3.2 +++ b/public/amtl/am-moveable.h	Thu Aug 29 11:45:28 2013 -0700
     3.3 @@ -61,6 +61,13 @@
     3.4    T &t_;
     3.5  };
     3.6  
     3.7 +template <typename T>
     3.8 +static inline Moveable<T>
     3.9 +Move(T &t)
    3.10 +{
    3.11 +  return Moveable<T>(t);
    3.12 +}
    3.13 +
    3.14  } // namespace ke
    3.15  
    3.16  #endif // _include_amtl_moveable_h_

     4.1 --- a/public/amtl/am-string.h	Thu Aug 29 14:16:18 2013 -0400
     4.2 +++ b/public/amtl/am-string.h	Thu Aug 29 11:45:28 2013 -0700
     4.3 @@ -81,6 +81,9 @@
     4.4      return *this;
     4.5    }
     4.6  
     4.7 +  int compare(const char *str) const {
     4.8 +    return strcmp(chars(), str);
     4.9 +  }
    4.10    int compare(const AString &other) const {
    4.11      return strcmp(chars(), other.chars());
    4.12    }

     5.1 --- a/public/amtl/am-vector.h	Thu Aug 29 14:16:18 2013 -0400
     5.2 +++ b/public/amtl/am-vector.h	Thu Aug 29 11:45:28 2013 -0700
     5.3 @@ -43,25 +43,31 @@
     5.4  {
     5.5   public:
     5.6    Vector(AllocPolicy = AllocPolicy())
     5.7 -  : data_(NULL),
     5.8 -    nitems_(0),
     5.9 -    maxsize_(0)
    5.10 +   : data_(NULL),
    5.11 +     nitems_(0),
    5.12 +     maxsize_(0)
    5.13    {
    5.14    }
    5.15  
    5.16 +  Vector(Moveable<Vector<T, AllocPolicy> > other) {
    5.17 +    data_ = other->data_;
    5.18 +    nitems_ = other->nitems_;
    5.19 +    maxsize_ = other->maxsize_;
    5.20 +    other->reset();
    5.21 +  }
    5.22 +
    5.23    ~Vector() {
    5.24      zap();
    5.25    }
    5.26  
    5.27 -  void steal(Vector &other) {
    5.28 -    zap();
    5.29 -    data_ = other.data_;
    5.30 -    nitems_ = other.nitems_;
    5.31 -    maxsize_ = other.maxsize_;
    5.32 -    other.reset();
    5.33 +  bool append(const T &item) {
    5.34 +    if (!growIfNeeded(1))
    5.35 +      return false;
    5.36 +    new (&data_[nitems_]) T(item);
    5.37 +    nitems_++;
    5.38 +    return true;
    5.39    }
    5.40 -
    5.41 -  bool append(const T &item) {
    5.42 +  bool append(Moveable<T> item) {
    5.43      if (!growIfNeeded(1))
    5.44        return false;
    5.45      new (&data_[nitems_]) T(item);
    5.46 @@ -73,6 +79,12 @@
    5.47      new (&data_[nitems_]) T(item);
    5.48      nitems_++;
    5.49    }
    5.50 +  void infallibleAppend(Moveable<T> item) {
    5.51 +    assert(growIfNeeded(1));
    5.52 +    new (&data_[nitems_]) T(item);
    5.53 +    nitems_++;
    5.54 +  }
    5.55 +
    5.56    T popCopy() {
    5.57      T t = at(length() - 1);
    5.58      pop();