Add move semantics and fix some bugs.
Add move semantics and fix some bugs.
1.1 --- a/README.md Sat Aug 24 02:36:11 2013 -0700
1.2 +++ b/README.md Mon Aug 26 20:41:58 2013 -0700
1.3 @@ -59,6 +59,30 @@
1.4 * Integer alignment (useful for allocators or code generators).
1.5 * KE\_DELETE and KE\_OVERRIDE which map to delete and override keywords if C++11 is available.
1.6
1.7 +### Moveable (am-moveable.h)
1.8 +
1.9 +Moveable<T> is a helper to emulate C++11 move semantics (rvalue references). A class can implement
1.10 +a move constructor like so:
1.11 +
1.12 + class X
1.13 + {
1.14 + public:
1.15 + X(Moveable<X> other)
1.16 +
1.17 +And a moveable value can be given like:
1.18 +
1.19 + vector.append(Moveable<X>(value));
1.20 +
1.21 +Containers within AMTL all support move semantics; however, not all containers are moveable yet.
1.22 +If move semantics are critical for correctness or performance, it is wise to disallow copy
1.23 +construction entirely:
1.24 +
1.25 + class X
1.26 + {
1.27 + ...
1.28 + private:
1.29 + X(const X &other) KE_DELETE;
1.30 +
1.31 ### Thread Utilities (am-thread-utils.h)
1.32
1.33 Thread utils provides access to common sychronization primitives: mutexes, condition variables,
1.34 @@ -136,9 +160,14 @@
1.35
1.36 ### HashMap (am-hashmap.h)
1.37
1.38 -ke::HashMap is a key -> value map built upon HashTable. This saves you from having to implement our
1.39 -own Policy and provides some more generic accessors. However it is still necessary to implement a
1.40 -hash function.
1.41 +ke::HashMap is a key -> value map built upon HashTable. This saves you from having to implement all
1.42 +of a Policy and provides some more generic accessors. However it is still necessary to implement a
1.43 +hash and comparison function.
1.44 +
1.45 +### HashSet (am-hashset.h)
1.46 +
1.47 +ke::HashSet is a HashMap that only stores keys. Like HashMap, you must still implement a policy
1.48 +with comparison and hash functions.
1.49
1.50 ### InlineList (am-inlinelist.h)
1.51
2.1 --- a/include/am-hashmap.h Sat Aug 24 02:36:11 2013 -0700
2.2 +++ b/include/am-hashmap.h Mon Aug 26 20:41:58 2013 -0700
2.3 @@ -60,12 +60,28 @@
2.4 Entry()
2.5 {
2.6 }
2.7 + Entry(Moveable<Entry> other)
2.8 + : key(Moveable<K>(other->key)),
2.9 + value(Moveable<V>(other->value))
2.10 + {
2.11 + }
2.12
2.13 Entry(const K &aKey, const V &aValue)
2.14 : key(aKey),
2.15 value(aValue)
2.16 - {
2.17 - }
2.18 + { }
2.19 + Entry(const K &aKey, Moveable<V> aValue)
2.20 + : key(aKey),
2.21 + value(aValue)
2.22 + { }
2.23 + Entry(Moveable<K> aKey, const V &aValue)
2.24 + : key(aKey),
2.25 + value(aValue)
2.26 + { }
2.27 + Entry(Moveable<K> aKey, Moveable<V> aValue)
2.28 + : key(aKey),
2.29 + value(aValue)
2.30 + { }
2.31 };
2.32
2.33 struct Policy
2.34 @@ -98,6 +114,7 @@
2.35
2.36 typedef typename Internal::Result Result;
2.37 typedef typename Internal::Insert Insert;
2.38 + typedef typename Internal::iterator iterator;
2.39
2.40 template <typename Lookup>
2.41 Result find(const Lookup &key) {
2.42 @@ -123,6 +140,15 @@
2.43 bool add(Insert &i, const K &key, const V &value) {
2.44 return table_.add(i, Entry(key, value));
2.45 }
2.46 + bool add(Insert &i, Moveable<K> key, const V &value) {
2.47 + return table_.add(i, Entry(key, value));
2.48 + }
2.49 + bool add(Insert &i, const K &key, Moveable<V> value) {
2.50 + return table_.add(i, Entry(key, value));
2.51 + }
2.52 + bool add(Insert &i, Moveable<K> key, Moveable<V> value) {
2.53 + return table_.add(i, Entry(key, value));
2.54 + }
2.55
2.56 // This can be used to avoid compiler constructed temporaries, since AMTL
2.57 // does not yet support move semantics. If you use this, the key and value
2.58 @@ -131,10 +157,18 @@
2.59 return table_.add(i);
2.60 }
2.61
2.62 + iterator iter() {
2.63 + return iterator(&table_);
2.64 + }
2.65 +
2.66 void clear() {
2.67 table_.clear();
2.68 }
2.69
2.70 + size_t elements() const {
2.71 + return table_.elements();
2.72 + }
2.73 +
2.74 size_t estimateMemoryUse() const {
2.75 return table_.estimateMemoryUse();
2.76 }
2.77 @@ -143,6 +177,17 @@
2.78 Internal table_;
2.79 };
2.80
2.81 +template <typename T>
2.82 +struct PointerPolicy
2.83 +{
2.84 + static inline uint32_t hash(T *p) {
2.85 + return HashPointer(p);
2.86 + }
2.87 + static inline bool matches(T *p1, T *p2) {
2.88 + return p1 == p2;
2.89 + }
2.90 +};
2.91 +
2.92 }
2.93
2.94 #endif // _include_amtl_hashmap_h_
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/include/am-hashset.h Mon Aug 26 20:41:58 2013 -0700
3.3 @@ -0,0 +1,129 @@
3.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
3.5 +//
3.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
3.7 +// All rights reserved.
3.8 +//
3.9 +// Redistribution and use in source and binary forms, with or without
3.10 +// modification, are permitted provided that the following conditions are met:
3.11 +//
3.12 +// * Redistributions of source code must retain the above copyright notice, this
3.13 +// list of conditions and the following disclaimer.
3.14 +// * Redistributions in binary form must reproduce the above copyright notice,
3.15 +// this list of conditions and the following disclaimer in the documentation
3.16 +// and/or other materials provided with the distribution.
3.17 +// * Neither the name of AlliedModders LLC nor the names of its contributors
3.18 +// may be used to endorse or promote products derived from this software
3.19 +// without specific prior written permission.
3.20 +//
3.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
3.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
3.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
3.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
3.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
3.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
3.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
3.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
3.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
3.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
3.31 +// POSSIBILITY OF SUCH DAMAGE.
3.32 +
3.33 +#ifndef _include_amtl_hashmap_h_
3.34 +#define _include_amtl_hashmap_h_
3.35 +
3.36 +#include <am-hashtable.h>
3.37 +
3.38 +namespace ke {
3.39 +
3.40 +// Template parameters:
3.41 +//
3.42 +// K - Key type.
3.43 +// HashPolicy - A struct with a hash and comparator function for each lookup type:
3.44 +// static uint32_t hash(const Type &value);
3.45 +// static bool matches(const Type &value, const K &key);
3.46 +//
3.47 +// Like HashMap and HashTable, init() must be called to construct the set.
3.48 +template <typename K,
3.49 + typename HashPolicy,
3.50 + typename AllocPolicy = SystemAllocatorPolicy>
3.51 +class HashSet : public AllocPolicy
3.52 +{
3.53 + struct Policy {
3.54 + typedef K Payload;
3.55 +
3.56 + template <typename Lookup>
3.57 + static uint32_t hash(const Lookup &key) {
3.58 + return HashPolicy::hash(key);
3.59 + }
3.60 +
3.61 + template <typename Lookup>
3.62 + static bool matches(const Lookup &key, const Payload &payload) {
3.63 + return HashPolicy::matches(key, payload);
3.64 + }
3.65 + };
3.66 +
3.67 + typedef HashTable<Policy, AllocPolicy> Internal;
3.68 +
3.69 + public:
3.70 + HashSet(AllocPolicy ap = AllocPolicy())
3.71 + : table_(ap)
3.72 + {
3.73 + }
3.74 +
3.75 + // capacity must be a power of two.
3.76 + bool init(size_t capacity = 16) {
3.77 + return table_.init(capacity);
3.78 + }
3.79 +
3.80 + typedef typename Internal::Result Result;
3.81 + typedef typename Internal::Insert Insert;
3.82 +
3.83 + template <typename Lookup>
3.84 + Result find(const Lookup &key) {
3.85 + return table_.find(key);
3.86 + }
3.87 +
3.88 + template <typename Lookup>
3.89 + Insert findForAdd(const Lookup &key) {
3.90 + return table_.findForAdd(key);
3.91 + }
3.92 +
3.93 + template <typename Lookup>
3.94 + void removeIfExists(const Lookup &key) {
3.95 + return table_.remove(key);
3.96 + }
3.97 +
3.98 + void remove(Result &r) {
3.99 + table_.remove(r);
3.100 + }
3.101 +
3.102 + // The map must not have been mutated in between findForAdd() and add().
3.103 + // The Insert object is still valid after add() returns, however.
3.104 + bool add(Insert &i, const K &key) {
3.105 + return table_.add(i, key);
3.106 + }
3.107 + bool add(Insert &i, Moveable<K> key) {
3.108 + return table_.add(i, key);
3.109 + }
3.110 +
3.111 + // This can be used to avoid compiler constructed temporaries, since AMTL
3.112 + // does not yet support move semantics. If you use this, the key and value
3.113 + // must be set after.
3.114 + bool add(Insert &i) {
3.115 + return table_.add(i);
3.116 + }
3.117 +
3.118 + void clear() {
3.119 + table_.clear();
3.120 + }
3.121 +
3.122 + size_t estimateMemoryUse() const {
3.123 + return table_.estimateMemoryUse();
3.124 + }
3.125 +
3.126 + private:
3.127 + Internal table_;
3.128 +};
3.129 +
3.130 +}
3.131 +
3.132 +#endif // _include_amtl_hashset_h_
4.1 --- a/include/am-hashtable.h Sat Aug 24 02:36:11 2013 -0700
4.2 +++ b/include/am-hashtable.h Mon Aug 26 20:41:58 2013 -0700
4.3 @@ -33,7 +33,9 @@
4.4 #include <new>
4.5 #include <limits.h>
4.6 #include <stdlib.h>
4.7 +#include "am-allocator-policies.h"
4.8 #include "am-utility.h"
4.9 +#include "am-moveable.h"
4.10
4.11 namespace ke {
4.12
4.13 @@ -49,8 +51,16 @@
4.14 static const uint32_t kRemovedHash = 1;
4.15
4.16 public:
4.17 - void setHash(uint32_t hash, const T &t) {
4.18 + void setHash(uint32_t hash) {
4.19 hash_ = hash;
4.20 + }
4.21 + void construct() {
4.22 + new (&t_) T();
4.23 + }
4.24 + void construct(const T &t) {
4.25 + new (&t_) T(t);
4.26 + }
4.27 + void construct(Moveable<T> t) {
4.28 new (&t_) T(t);
4.29 }
4.30 uint32_t hash() const {
4.31 @@ -256,7 +266,8 @@
4.32 Entry &oldEntry = oldTable[i];
4.33 if (oldEntry.isLive()) {
4.34 Insert p = insertUnique(oldEntry.hash());
4.35 - p.entry().setHash(p.hash(), oldEntry.payload());
4.36 + p.entry().setHash(p.hash());
4.37 + p.entry().construct(Moveable<Payload>(oldEntry.payload()));
4.38 }
4.39 oldEntry.destruct();
4.40 }
4.41 @@ -289,8 +300,8 @@
4.42 if (e->free())
4.43 break;
4.44 if (e->isLive() &&
4.45 - e->sameHash(hash) &&
4.46 - HashPolicy::matches(key, e->payload()))
4.47 + e->sameHash(hash) &&
4.48 + HashPolicy::matches(key, e->payload()))
4.49 {
4.50 return Result(e);
4.51 }
4.52 @@ -317,7 +328,7 @@
4.53 return Insert(e, hash);
4.54 }
4.55
4.56 - bool internalAdd(Insert &i, const Payload &payload) {
4.57 + bool internalAdd(Insert &i) {
4.58 assert(!i.found());
4.59
4.60 // If the entry is deleted, just re-use the slot.
4.61 @@ -344,8 +355,8 @@
4.62 i = insertUnique(i.hash());
4.63 }
4.64
4.65 - i.entry().setHash(i.hash(), payload);
4.66 nelements_++;
4.67 + i.entry().setHash(i.hash());
4.68 return true;
4.69 }
4.70
4.71 @@ -422,10 +433,22 @@
4.72 // The table must not have been mutated in between findForAdd() and add().
4.73 // The Insert object is still valid after add() returns, however.
4.74 bool add(Insert &i, const Payload &payload) {
4.75 - return internalAdd(i, payload);
4.76 + if (!internalAdd(i))
4.77 + return false;
4.78 + i.entry().construct(payload);
4.79 + return true;
4.80 + }
4.81 + bool add(Insert &i, Moveable<Payload> payload) {
4.82 + if (!internalAdd(i))
4.83 + return false;
4.84 + i.entry().construct(payload);
4.85 + return true;
4.86 }
4.87 bool add(Insert &i) {
4.88 - return internalAdd(i, Payload());
4.89 + if (!internalAdd(i))
4.90 + return false;
4.91 + i.entry().construct();
4.92 + return true;
4.93 }
4.94
4.95 bool checkDensity() {
4.96 @@ -444,6 +467,10 @@
4.97 nelements_ = 0;
4.98 }
4.99
4.100 + size_t elements() const {
4.101 + return nelements_;
4.102 + }
4.103 +
4.104 size_t estimateMemoryUse() const {
4.105 return sizeof(Entry) * capacity_;
4.106 }
4.107 @@ -471,7 +498,10 @@
4.108 table_->removeEntry(*i_);
4.109 }
4.110
4.111 - const Payload &operator *() const {
4.112 + Payload *operator ->() const {
4.113 + return &i_->payload();
4.114 + }
4.115 + Payload &operator *() const {
4.116 return i_->payload();
4.117 }
4.118
4.119 @@ -564,12 +594,12 @@
4.120 HashInt64(int64_t key)
4.121 {
4.122 key = (~key) + (key << 18); // key = (key << 18) - key - 1;
4.123 - key = key ^ (uint64(key) >> 31);
4.124 + key = key ^ (uint64_t(key) >> 31);
4.125 key = key * 21; // key = (key + (key << 2)) + (key << 4);
4.126 - key = key ^ (uint64(key) >> 11);
4.127 + key = key ^ (uint64_t(key) >> 11);
4.128 key = key + (key << 6);
4.129 - key = key ^ (uint64(key) >> 22);
4.130 - return uint32(key);
4.131 + key = key ^ (uint64_t(key) >> 22);
4.132 + return uint32_t(key);
4.133 }
4.134
4.135 template <size_t Size>
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/include/am-moveable.h Mon Aug 26 20:41:58 2013 -0700
5.3 @@ -0,0 +1,66 @@
5.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
5.5 +//
5.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
5.7 +// All rights reserved.
5.8 +//
5.9 +// Redistribution and use in source and binary forms, with or without
5.10 +// modification, are permitted provided that the following conditions are met:
5.11 +//
5.12 +// * Redistributions of source code must retain the above copyright notice, this
5.13 +// list of conditions and the following disclaimer.
5.14 +// * Redistributions in binary form must reproduce the above copyright notice,
5.15 +// this list of conditions and the following disclaimer in the documentation
5.16 +// and/or other materials provided with the distribution.
5.17 +// * Neither the name of AlliedModders LLC nor the names of its contributors
5.18 +// may be used to endorse or promote products derived from this software
5.19 +// without specific prior written permission.
5.20 +//
5.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
5.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
5.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
5.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
5.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
5.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
5.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
5.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
5.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
5.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
5.31 +// POSSIBILITY OF SUCH DAMAGE.
5.32 +
5.33 +#ifndef _include_amtl_moveable_h_
5.34 +#define _include_amtl_moveable_h_
5.35 +
5.36 +namespace ke {
5.37 +
5.38 +// This is a feature in C++11, but since AM projects do not have access to
5.39 +// C++11 yet, we provide templates to implement move semantics. A class can
5.40 +// provide a constructor for (ke::Moveable<T> t) which containers will try
5.41 +// to use.
5.42 +//
5.43 +// When implementing a constructor that takes a Moveable, the object being
5.44 +// moved should be left in a state that is safe, since its destructor will
5.45 +// be called even though it has been moved.
5.46 +
5.47 +template <typename T>
5.48 +struct Moveable
5.49 +{
5.50 + public:
5.51 + explicit Moveable(T &t)
5.52 + : t_(t)
5.53 + {
5.54 + }
5.55 +
5.56 + T *operator ->() {
5.57 + return &t_;
5.58 + }
5.59 + operator T &() {
5.60 + return t_;
5.61 + }
5.62 +
5.63 + private:
5.64 + T &t_;
5.65 +};
5.66 +
5.67 +} // namespace ke
5.68 +
5.69 +#endif // _include_amtl_moveable_h_
6.1 --- a/include/am-string.h Sat Aug 24 02:36:11 2013 -0700
6.2 +++ b/include/am-string.h Mon Aug 26 20:41:58 2013 -0700
6.3 @@ -33,6 +33,7 @@
6.4 #include <stdlib.h>
6.5 #include <string.h>
6.6 #include <am-utility.h>
6.7 +#include <am-moveable.h>
6.8
6.9 namespace ke {
6.10
6.11 @@ -54,6 +55,12 @@
6.12 if (other.length_)
6.13 set(other.chars_, other.length_);
6.14 }
6.15 + AString(Moveable<AString> other)
6.16 + : chars_(other->chars_.take()),
6.17 + length_(other->length_)
6.18 + {
6.19 + other->length_ = 0;
6.20 + }
6.21
6.22 AString &operator =(const char *str) {
6.23 if (str && str[0]) {
7.1 --- a/include/am-utility.h Sat Aug 24 02:36:11 2013 -0700
7.2 +++ b/include/am-utility.h Mon Aug 26 20:41:58 2013 -0700
7.3 @@ -48,18 +48,12 @@
7.4
7.5 static const size_t kMallocAlignment = sizeof(void *) * 2;
7.6
7.7 -typedef uint8_t uint8;
7.8 -typedef int32_t int32;
7.9 -typedef uint32_t uint32;
7.10 -typedef int64_t int64;
7.11 -typedef uint64_t uint64;
7.12 -
7.13 -typedef uint8 * Address;
7.14 -
7.15 static const size_t kKB = 1024;
7.16 static const size_t kMB = 1024 * kKB;
7.17 static const size_t kGB = 1024 * kMB;
7.18
7.19 +typedef uint8_t * Address;
7.20 +
7.21 template <typename T> T
7.22 ReturnAndVoid(T &t)
7.23 {
8.1 --- a/include/am-vector.h Sat Aug 24 02:36:11 2013 -0700
8.2 +++ b/include/am-vector.h Mon Aug 26 20:41:58 2013 -0700
8.3 @@ -34,6 +34,7 @@
8.4 #include <stdlib.h>
8.5 #include <am-allocator-policies.h>
8.6 #include <am-utility.h>
8.7 +#include <am-moveable.h>
8.8
8.9 namespace ke {
8.10
8.11 @@ -163,7 +164,7 @@
8.12 if (newdata == NULL)
8.13 return false;
8.14 for (size_t i = 0; i < nitems_; i++) {
8.15 - new (&newdata[i]) T(data_[i]);
8.16 + new (&newdata[i]) T(Moveable<T>(data_[i]));
8.17 data_[i].~T();
8.18 }
8.19 this->free(data_);