# HG changeset patch # User David Anderson # Date 1377574918 25200 # Node ID 0ac292cc1467cf728bcd5782c96263ab5730e018 # Parent 4cd655ff4c2cd955cca3543e011883556752b636 Add move semantics and fix some bugs. diff -r 4cd655ff4c2c -r 0ac292cc1467 README.md --- a/README.md Sat Aug 24 02:36:11 2013 -0700 +++ b/README.md Mon Aug 26 20:41:58 2013 -0700 @@ -59,6 +59,30 @@ * Integer alignment (useful for allocators or code generators). * KE\_DELETE and KE\_OVERRIDE which map to delete and override keywords if C++11 is available. +### Moveable (am-moveable.h) + +Moveable is a helper to emulate C++11 move semantics (rvalue references). A class can implement +a move constructor like so: + + class X + { + public: + X(Moveable other) + +And a moveable value can be given like: + + vector.append(Moveable(value)); + +Containers within AMTL all support move semantics; however, not all containers are moveable yet. +If move semantics are critical for correctness or performance, it is wise to disallow copy +construction entirely: + + class X + { + ... + private: + X(const X &other) KE_DELETE; + ### Thread Utilities (am-thread-utils.h) Thread utils provides access to common sychronization primitives: mutexes, condition variables, @@ -136,9 +160,14 @@ ### HashMap (am-hashmap.h) -ke::HashMap is a key -> value map built upon HashTable. This saves you from having to implement our -own Policy and provides some more generic accessors. However it is still necessary to implement a -hash function. +ke::HashMap is a key -> value map built upon HashTable. This saves you from having to implement all +of a Policy and provides some more generic accessors. However it is still necessary to implement a +hash and comparison function. + +### HashSet (am-hashset.h) + +ke::HashSet is a HashMap that only stores keys. Like HashMap, you must still implement a policy +with comparison and hash functions. ### InlineList (am-inlinelist.h) diff -r 4cd655ff4c2c -r 0ac292cc1467 include/am-hashmap.h --- a/include/am-hashmap.h Sat Aug 24 02:36:11 2013 -0700 +++ b/include/am-hashmap.h Mon Aug 26 20:41:58 2013 -0700 @@ -60,12 +60,28 @@ Entry() { } + Entry(Moveable other) + : key(Moveable(other->key)), + value(Moveable(other->value)) + { + } Entry(const K &aKey, const V &aValue) : key(aKey), value(aValue) - { - } + { } + Entry(const K &aKey, Moveable aValue) + : key(aKey), + value(aValue) + { } + Entry(Moveable aKey, const V &aValue) + : key(aKey), + value(aValue) + { } + Entry(Moveable aKey, Moveable aValue) + : key(aKey), + value(aValue) + { } }; struct Policy @@ -98,6 +114,7 @@ typedef typename Internal::Result Result; typedef typename Internal::Insert Insert; + typedef typename Internal::iterator iterator; template Result find(const Lookup &key) { @@ -123,6 +140,15 @@ bool add(Insert &i, const K &key, const V &value) { return table_.add(i, Entry(key, value)); } + bool add(Insert &i, Moveable key, const V &value) { + return table_.add(i, Entry(key, value)); + } + bool add(Insert &i, const K &key, Moveable value) { + return table_.add(i, Entry(key, value)); + } + bool add(Insert &i, Moveable key, Moveable value) { + return table_.add(i, Entry(key, value)); + } // This can be used to avoid compiler constructed temporaries, since AMTL // does not yet support move semantics. If you use this, the key and value @@ -131,10 +157,18 @@ return table_.add(i); } + iterator iter() { + return iterator(&table_); + } + void clear() { table_.clear(); } + size_t elements() const { + return table_.elements(); + } + size_t estimateMemoryUse() const { return table_.estimateMemoryUse(); } @@ -143,6 +177,17 @@ Internal table_; }; +template +struct PointerPolicy +{ + static inline uint32_t hash(T *p) { + return HashPointer(p); + } + static inline bool matches(T *p1, T *p2) { + return p1 == p2; + } +}; + } #endif // _include_amtl_hashmap_h_ diff -r 4cd655ff4c2c -r 0ac292cc1467 include/am-hashset.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/include/am-hashset.h Mon Aug 26 20:41:58 2013 -0700 @@ -0,0 +1,129 @@ +// vim: set sts=8 ts=2 sw=2 tw=99 et: +// +// Copyright (C) 2013, David Anderson and AlliedModders LLC +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// * Redistributions of source code must retain the above copyright notice, this +// list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// * Neither the name of AlliedModders LLC nor the names of its contributors +// may be used to endorse or promote products derived from this software +// without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +// POSSIBILITY OF SUCH DAMAGE. + +#ifndef _include_amtl_hashmap_h_ +#define _include_amtl_hashmap_h_ + +#include + +namespace ke { + +// Template parameters: +// +// K - Key type. +// HashPolicy - A struct with a hash and comparator function for each lookup type: +// static uint32_t hash(const Type &value); +// static bool matches(const Type &value, const K &key); +// +// Like HashMap and HashTable, init() must be called to construct the set. +template +class HashSet : public AllocPolicy +{ + struct Policy { + typedef K Payload; + + template + static uint32_t hash(const Lookup &key) { + return HashPolicy::hash(key); + } + + template + static bool matches(const Lookup &key, const Payload &payload) { + return HashPolicy::matches(key, payload); + } + }; + + typedef HashTable Internal; + + public: + HashSet(AllocPolicy ap = AllocPolicy()) + : table_(ap) + { + } + + // capacity must be a power of two. + bool init(size_t capacity = 16) { + return table_.init(capacity); + } + + typedef typename Internal::Result Result; + typedef typename Internal::Insert Insert; + + template + Result find(const Lookup &key) { + return table_.find(key); + } + + template + Insert findForAdd(const Lookup &key) { + return table_.findForAdd(key); + } + + template + void removeIfExists(const Lookup &key) { + return table_.remove(key); + } + + void remove(Result &r) { + table_.remove(r); + } + + // The map must not have been mutated in between findForAdd() and add(). + // The Insert object is still valid after add() returns, however. + bool add(Insert &i, const K &key) { + return table_.add(i, key); + } + bool add(Insert &i, Moveable key) { + return table_.add(i, key); + } + + // This can be used to avoid compiler constructed temporaries, since AMTL + // does not yet support move semantics. If you use this, the key and value + // must be set after. + bool add(Insert &i) { + return table_.add(i); + } + + void clear() { + table_.clear(); + } + + size_t estimateMemoryUse() const { + return table_.estimateMemoryUse(); + } + + private: + Internal table_; +}; + +} + +#endif // _include_amtl_hashset_h_ diff -r 4cd655ff4c2c -r 0ac292cc1467 include/am-hashtable.h --- a/include/am-hashtable.h Sat Aug 24 02:36:11 2013 -0700 +++ b/include/am-hashtable.h Mon Aug 26 20:41:58 2013 -0700 @@ -33,7 +33,9 @@ #include #include #include +#include "am-allocator-policies.h" #include "am-utility.h" +#include "am-moveable.h" namespace ke { @@ -49,8 +51,16 @@ static const uint32_t kRemovedHash = 1; public: - void setHash(uint32_t hash, const T &t) { + void setHash(uint32_t hash) { hash_ = hash; + } + void construct() { + new (&t_) T(); + } + void construct(const T &t) { + new (&t_) T(t); + } + void construct(Moveable t) { new (&t_) T(t); } uint32_t hash() const { @@ -256,7 +266,8 @@ Entry &oldEntry = oldTable[i]; if (oldEntry.isLive()) { Insert p = insertUnique(oldEntry.hash()); - p.entry().setHash(p.hash(), oldEntry.payload()); + p.entry().setHash(p.hash()); + p.entry().construct(Moveable(oldEntry.payload())); } oldEntry.destruct(); } @@ -289,8 +300,8 @@ if (e->free()) break; if (e->isLive() && - e->sameHash(hash) && - HashPolicy::matches(key, e->payload())) + e->sameHash(hash) && + HashPolicy::matches(key, e->payload())) { return Result(e); } @@ -317,7 +328,7 @@ return Insert(e, hash); } - bool internalAdd(Insert &i, const Payload &payload) { + bool internalAdd(Insert &i) { assert(!i.found()); // If the entry is deleted, just re-use the slot. @@ -344,8 +355,8 @@ i = insertUnique(i.hash()); } - i.entry().setHash(i.hash(), payload); nelements_++; + i.entry().setHash(i.hash()); return true; } @@ -422,10 +433,22 @@ // The table must not have been mutated in between findForAdd() and add(). // The Insert object is still valid after add() returns, however. bool add(Insert &i, const Payload &payload) { - return internalAdd(i, payload); + if (!internalAdd(i)) + return false; + i.entry().construct(payload); + return true; + } + bool add(Insert &i, Moveable payload) { + if (!internalAdd(i)) + return false; + i.entry().construct(payload); + return true; } bool add(Insert &i) { - return internalAdd(i, Payload()); + if (!internalAdd(i)) + return false; + i.entry().construct(); + return true; } bool checkDensity() { @@ -444,6 +467,10 @@ nelements_ = 0; } + size_t elements() const { + return nelements_; + } + size_t estimateMemoryUse() const { return sizeof(Entry) * capacity_; } @@ -471,7 +498,10 @@ table_->removeEntry(*i_); } - const Payload &operator *() const { + Payload *operator ->() const { + return &i_->payload(); + } + Payload &operator *() const { return i_->payload(); } @@ -564,12 +594,12 @@ HashInt64(int64_t key) { key = (~key) + (key << 18); // key = (key << 18) - key - 1; - key = key ^ (uint64(key) >> 31); + key = key ^ (uint64_t(key) >> 31); key = key * 21; // key = (key + (key << 2)) + (key << 4); - key = key ^ (uint64(key) >> 11); + key = key ^ (uint64_t(key) >> 11); key = key + (key << 6); - key = key ^ (uint64(key) >> 22); - return uint32(key); + key = key ^ (uint64_t(key) >> 22); + return uint32_t(key); } template diff -r 4cd655ff4c2c -r 0ac292cc1467 include/am-moveable.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/include/am-moveable.h Mon Aug 26 20:41:58 2013 -0700 @@ -0,0 +1,66 @@ +// vim: set sts=8 ts=2 sw=2 tw=99 et: +// +// Copyright (C) 2013, David Anderson and AlliedModders LLC +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are met: +// +// * Redistributions of source code must retain the above copyright notice, this +// list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// * Neither the name of AlliedModders LLC nor the names of its contributors +// may be used to endorse or promote products derived from this software +// without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +// POSSIBILITY OF SUCH DAMAGE. + +#ifndef _include_amtl_moveable_h_ +#define _include_amtl_moveable_h_ + +namespace ke { + +// This is a feature in C++11, but since AM projects do not have access to +// C++11 yet, we provide templates to implement move semantics. A class can +// provide a constructor for (ke::Moveable t) which containers will try +// to use. +// +// When implementing a constructor that takes a Moveable, the object being +// moved should be left in a state that is safe, since its destructor will +// be called even though it has been moved. + +template +struct Moveable +{ + public: + explicit Moveable(T &t) + : t_(t) + { + } + + T *operator ->() { + return &t_; + } + operator T &() { + return t_; + } + + private: + T &t_; +}; + +} // namespace ke + +#endif // _include_amtl_moveable_h_ diff -r 4cd655ff4c2c -r 0ac292cc1467 include/am-string.h --- a/include/am-string.h Sat Aug 24 02:36:11 2013 -0700 +++ b/include/am-string.h Mon Aug 26 20:41:58 2013 -0700 @@ -33,6 +33,7 @@ #include #include #include +#include namespace ke { @@ -54,6 +55,12 @@ if (other.length_) set(other.chars_, other.length_); } + AString(Moveable other) + : chars_(other->chars_.take()), + length_(other->length_) + { + other->length_ = 0; + } AString &operator =(const char *str) { if (str && str[0]) { diff -r 4cd655ff4c2c -r 0ac292cc1467 include/am-utility.h --- a/include/am-utility.h Sat Aug 24 02:36:11 2013 -0700 +++ b/include/am-utility.h Mon Aug 26 20:41:58 2013 -0700 @@ -48,18 +48,12 @@ static const size_t kMallocAlignment = sizeof(void *) * 2; -typedef uint8_t uint8; -typedef int32_t int32; -typedef uint32_t uint32; -typedef int64_t int64; -typedef uint64_t uint64; - -typedef uint8 * Address; - static const size_t kKB = 1024; static const size_t kMB = 1024 * kKB; static const size_t kGB = 1024 * kMB; +typedef uint8_t * Address; + template T ReturnAndVoid(T &t) { diff -r 4cd655ff4c2c -r 0ac292cc1467 include/am-vector.h --- a/include/am-vector.h Sat Aug 24 02:36:11 2013 -0700 +++ b/include/am-vector.h Mon Aug 26 20:41:58 2013 -0700 @@ -34,6 +34,7 @@ #include #include #include +#include namespace ke { @@ -163,7 +164,7 @@ if (newdata == NULL) return false; for (size_t i = 0; i < nitems_; i++) { - new (&newdata[i]) T(data_[i]); + new (&newdata[i]) T(Moveable(data_[i])); data_[i].~T(); } this->free(data_);