danderson@0: The AlliedModders Template Library is a small set of C++ headers. It aims to be lightweight, danderson@0: supporting a minimalistic set of abstractions and data structures useful for high-performance C++ danderson@0: systems code. It is the spiritual succesor to the SourceHook template library. danderson@0: danderson@0: # Goals danderson@0: danderson@0: * Performance Over Generality. Rather than accomodate every use case, AMTL strives to make danderson@0: performance explicit, and does not include features which are dangerous for performance, or danderson@0: features that make malloc() failure detection more difficult. danderson@0: danderson@0: For example, while STL provides copy constructors for most containers, AMTL does not, as these danderson@0: operations are unsafe for fallible malloc(), and can cause large unintentional performance hits. danderson@0: danderson@0: Another example is boost::shared\_ptr, which by default is atomic and threadsafe, and danderson@0: preprocessor macros can be used to eliminate the thread safety option. AMTL opts to use distinct danderson@0: types for threadsafe and non-threadsafe reference counting, as the cost of atomic refcounting danderson@0: is higher. danderson@0: danderson@0: * Safety. Most code in AlliedModders does not take advantage of RAII, and does not account for danderson@0: fallible malloc. While in general, infallible malloc is probably okay for game servers, the lack danderson@0: of RAII leads to very complicated and bloated pointer management. A major goal of AMTL is to danderson@0: introduce safer pointer management into its codebases, and to allow certain components to safely danderson@0: handle malloc failures when desired. danderson@0: danderson@0: * No linkage. EVerything is contained within headers so that tools don't need to link additional danderson@0: C++ files. This could be a drawback, for example, it could increase build time or codesize danderson@0: bloat. We may evaluate this decision in the future, but for now, it fits into our "lightweight" danderson@0: theme of usability. danderson@0: danderson@0: (On some platforms, system libraries may be needed for certain headers.) danderson@0: danderson@0: * No RTTI or EH. There are a few reasons for this: danderson@0: + Both features require linkage to libstdc++. On Linux, this can cause problems with binary danderson@0: distribution. danderson@0: danderson@0: + When using 32-bit Visual C++, try blocks are not zero-cost, as they are implemented using SEH. danderson@0: danderson@0: * Fallible malloc. In many cases it's not desirable to terminate the program or throw an danderson@0: exception when an allocation fails (for example, resizing a large vector). Thus, functions danderson@0: like ke::Vector::append (analagous to std::vector::push\_back) will usually return bool. Whether danderson@0: or not these functions return (i.e., abort the program or fail safely) can be specified in an danderson@0: allocation policy. danderson@0: danderson@0: * Room to grow. These templates are intended to be a baseline of features needed for various danderson@0: AlliedModders projects. They can and will grow as new features are needed, hopefully keeping the danderson@0: above principles in mind. danderson@0: danderson@0: # Overview danderson@0: danderson@0: All classes and functions reside in a "ke" namespace, and all macros are prefixed with "KE\_". danderson@0: danderson@0: ### Platform Utilities (am-utilities.h) danderson@0: danderson@0: This provides some common helper functions pretty much lumped together: danderson@0: * AutoPtr, RAII for calling delete on a pointer. danderson@0: * AutoArray, RAII for calling delete[] on a pointer. danderson@0: * Detectors for add or multiply overflow, useful for computing allocation sizes. danderson@0: * Fast Log2/Floor2 functions (also known as bitscan or count zeroes). danderson@0: * Integer alignment (useful for allocators or code generators). danderson@0: * KE\_DELETE and KE\_OVERRIDE which map to delete and override keywords if C++11 is available. danderson@0: dvander@10: ### Moveable (am-moveable.h) dvander@10: dvander@10: Moveable is a helper to emulate C++11 move semantics (rvalue references). A class can implement dvander@10: a move constructor like so: dvander@10: dvander@10: class X dvander@10: { dvander@10: public: dvander@10: X(Moveable other) dvander@10: dvander@10: And a moveable value can be given like: dvander@10: dvander@10: vector.append(Moveable(value)); dvander@10: dvander@10: Containers within AMTL all support move semantics; however, not all containers are moveable yet. dvander@10: If move semantics are critical for correctness or performance, it is wise to disallow copy dvander@10: construction entirely: dvander@10: dvander@10: class X dvander@10: { dvander@10: ... dvander@10: private: dvander@10: X(const X &other) KE_DELETE; dvander@10: danderson@0: ### Thread Utilities (am-thread-utils.h) danderson@0: danderson@0: Thread utils provides access to common sychronization primitives: mutexes, condition variables, danderson@0: and threads. It also provides RAII objects for acquiring and releasing locks. More information is danderson@0: available at the top of am-thread-utils.h. danderson@0: danderson@0: ### Reference Counting (am-refcounting.h) danderson@0: danderson@0: Two classes are available to help other classes implement reference counting. They are Refcounted danderson@0: and RefcountedThreadsafe. Both must be inherited recursively, for example: danderson@0: danderson@0: class MyObject : public Refcounted danderson@0: danderson@0: The object is instantiated with a reference count of 1. A few RAII objects are provided for danderson@0: automatically retaining and releasing references: danderson@0: danderson@0: * Ref. Adds one reference upon construction and releases one reference on destruction. danderson@0: * PassRef. Same as Ref, except, when passed into a Ref or into a PassRef, the contained danderson@0: reference is NULL'd, rather than performing an unnecessary extra AddRef()+Release(). PassRef danderson@0: is intended only for return values. danderson@0: * Newborn. If a newly allocated Refcounted object is stored into a Ref, it will have one danderson@0: extra reference. When allocating new refcounted objects, they should be immediately wrapped in a danderson@0: Newborn to prevent this. danderson@0: danderson@0: RefcountedThreadsafe provides the same accessors as Refcounted. However, the reference counting is danderson@0: performed using atomic operations, so that two threads racing do not accidentally result in a wrong danderson@0: reference count (since a read + write is not normally atomic). This does not make the actual object danderson@0: threadsafe, rather, it makes it safe for multiple threads to mutate the reference count. danderson@0: danderson@0: ### Allocator Policies (am-allocator-policies.h) danderson@0: danderson@0: ke::HashTable and ke::Vector are both parameterized on an "AllocPolicy". It is accessed whenever a danderson@0: malloc(), free(), size overflow, or out-of-memory operation occurs. The default functionality of danderson@0: SystemAllocatorPolicy is to abort the process on any failure, which can be changed by implementing danderson@0: a new policy. As HashTable and Vector inherit from the AllocPolicy, it is possible to use custom danderson@0: allocators without accessing static variables. danderson@0: danderson@0: ### Vector (am-vector.h) danderson@0: danderson@0: ke::Vector is roughly analagous to std::vector. A few method names are changed: danderson@0: * size() is length() danderson@0: * push\_back() is append() and returns boolean. danderson@0: * The underlying buffer of a vector can be "taken", which is sometimes useful for transferring danderson@0: ownership of data. danderson@0: danderson@0: Vector does not have an iterator type. It should be iterated through normal sequential indexing. danderson@0: danderson@0: ### HashTable (am-hashtable.h) danderson@0: danderson@0: ke::HashTable is an open-addressing, linear-probing hash table. It is a bit more powerful than a danderson@0: generic key -> value map as it is templated on a "policy", rather than keys and values. A policy danderson@0: specifies what entries in the table look like, and how they are searched. Policies must have three danderson@0: members: danderson@0: danderson@0: * Payload - the type that will be stored for each entry in the hash table. danderson@0: * static bool matches(const T &t, Payload &p); - Must return true if |t| is equal to the entry at |p|. danderson@0: * static uin32\_t hash(const T &t); - Must compute a hash for |t|. danderson@0: danderson@0: The typename T in the policy applies for every key type that will be used in the hash table. For danderson@0: example, a hash table might store string keys, but have faster lookup using std::string versus a danderson@0: C-string, or even faster lookup for a string type that has its hash precomputed. danderson@0: danderson@0: All key types must effectively compute the same hash; i.e., it would not be legal for Payload to danderson@0: match both |int| and |std::string| but compute different hashes. danderson@0: danderson@0: HashTable returns either a Result or Insert object when performing lookups, depending on the type danderson@0: of lookup. A Result object is either found or not found. An Insert object, however, caches danderson@0: information about where it found the object, so that it doesn't have to repeat the hashing and danderson@0: lookup process for the subsequent add() call. Examples on how to use this are in am-hashmap.h, and danderson@0: the exact rules on how Result and Insert objects can be used are in am-hashtable.h. danderson@0: danderson@0: HashTables can be iterated. If the table is mutated during iteration outside of the interface danderson@0: provided by the iterator, then the iterator may become corrupted. This is acceptable as long as the danderson@0: iterator is abandoned. However, the table must stay alive for as long as the iterator is active. danderson@0: danderson@0: ### HashMap (am-hashmap.h) danderson@0: dvander@10: ke::HashMap is a key -> value map built upon HashTable. This saves you from having to implement all dvander@10: of a Policy and provides some more generic accessors. However it is still necessary to implement a dvander@10: hash and comparison function. dvander@10: dvander@10: ### HashSet (am-hashset.h) dvander@10: dvander@10: ke::HashSet is a HashMap that only stores keys. Like HashMap, you must still implement a policy dvander@10: with comparison and hash functions. danderson@0: danderson@0: ### InlineList (am-inlinelist.h) danderson@0: danderson@0: InlineList is a doubly-linked list that does use any calls to malloc(), with the caveat that list danderson@0: members can be members in at most one inline list at a time. Objects must recursively inherit from danderson@0: InlineListNode, which ensures that the object has prev/next pointers. Example: danderson@0: danderson@0: class MyObject : public InlineListNode danderson@0: { }; danderson@0: InlineList list; danderson@0: danderson@0: InlineList is ideal for situations where objects have already been allocated and will be a member danderson@0: of at most one list at any time. If this is the case, the per-node malloc/free of std::list can be danderson@0: completely avoided. danderson@0: danderson@0: An InlineList never claims ownership over its pointers. Its destructor is a no-op and it makes no danderson@0: attempt to destroy members of its list (though in debug builds it will unlink members in its danderson@0: destructor for assertion purposes). danderson@0: danderson@0: ### LinkedList (am-linkedlist.h) danderson@0: danderson@0: LinkedList is a doubly-linked list that requires a malloc() for each entry. It is provided for danderson@0: backward compatibility, and it should be avoided in general, except in situations where it is danderson@0: absolutely necessary and allocation performance is not a factor. Otherwise, use InlineList or danderson@0: Vector. danderson@0: danderson@0: ### Strings (am-string.h) danderson@0: danderson@0: The String API is still rather in flux. Currently, a simple std::string-like class is provided danderson@0: called AString (short for ASCII String). danderson@0: danderson@0: # Replacing SourceHook Includes danderson@0: danderson@0: AMTL is a spiritual successor to the SourceHook template library, used in many AlliedModders danderson@0: projects. AMTL is intended to deprecate it. danderson@0: danderson@0: ### CVector (sh\_vector.h) danderson@0: danderson@0: CVector can be replaced with ke::Vector. ke::Vector does not provide an iterator (yet). A few danderson@0: method names have been changed, as CVector more closely models std::vector, however the classes are danderson@0: pretty similar. Any missing methods could be added quite easily. danderson@0: dvander@7: ### String (sh\_string.h) danderson@0: dvander@7: String can be replaced with ke::AString, however some methods like trim() are not available yet. dvander@7: One notable difference is that AString caches the length of the string, whereas SH::String does dvander@7: not. That means AString is a larger data structure (by 4 bytes, on 32-bit), but is not prone to dvander@7: O(n^2) operations like String. This more closely matches the functionality of std::string. danderson@0: danderson@0: ### List (sh\_list.h) danderson@0: danderson@0: List can be replaced with ke::LinkedList. A few methods have changed, similar to Vector. For danderson@0: example, push\_back() becomes append() and push\_front() becomes prepend(), and both return danderson@0: boolean. danderson@0: danderson@0: Consider using ke::InlineList if your list contains already-allocated objects, and those objects danderson@0: are members of at most one list, LinkedList will call malloc() and free() for each node. danderson@0: danderson@0: The implementation of SourceHook::List and ke::LinkedList are basically identical underneath the danderson@0: hood, however, copy construction and assignment are disallowed in the AMTL variant. This is because danderson@0: they violate the memory model and also have very poor performance impliciations. danderson@0: danderson@0: ### THash (sh\_tinyhash.h) danderson@0: danderson@0: TinyHash can be replaced with ke::HashMap, with minor changes. Comparators must be implemented as danderson@0: equality operators on the key type, and the hash function is specified as a template parameter. danderson@0: danderson@0: TinyHash is disadvantageous for a number of reasons. It uses separate chaining, and chains are danderson@0: built on top of SourceHook::List, so it will use more memory on average. Inserts are also more danderson@0: expensive as a call to malloc() is almost guaranteed. Retrieval is more expensive as well, since it danderson@0: requires more indirection and has worse cache locality. It also has no ability to resize table danderson@0: downward when its density is very low. danderson@0: danderson@0: ### CStack (sh\_stack.h) danderson@0: danderson@0: SourceHook::CStack is a stable-pointer stack. That is, if an element has been pushed, the address danderson@0: the element is stored at is guaranteed not to change unless the element is removed. This can be an danderson@0: important requirement in cases that involve re-entrancy. If you are relying on this feature of danderson@0: CStack, there is no replacement in AMTL. If your CStack entries are LIFO, and tied to local danderson@0: variables, you might consider simply linking objects together using RAII and avoiding CStack danderson@0: entirely (though CStack will have better cache performance if you need to walk the list of entries). danderson@0: danderson@0: If you don't need stable pointers, CStack can be replaced with ke::Vector. danderson@0: danderson@0: # License danderson@0: danderson@0: All headers are licensed under a 3-clause BSD license.