README.md
author David Anderson <dvander@alliedmods.net>
Thu Aug 29 23:51:20 2013 -0700 (2013-08-29)
changeset 15 245a69265bd5
parent 10 0ac292cc1467
child 18 9b30f80f6e49
permissions -rw-r--r--
Fix race bug.
     1 The AlliedModders Template Library is a small set of C++ headers. It aims to be lightweight,
     2 supporting a minimalistic set of abstractions and data structures useful for high-performance C++
     3 systems code. It is the spiritual succesor to the SourceHook template library.
     4 
     5 # Goals
     6 
     7 * Performance Over Generality. Rather than accomodate every use case, AMTL strives to make
     8   performance explicit, and does not include features which are dangerous for performance, or
     9   features that make malloc() failure detection more difficult.
    10 
    11   For example, while STL provides copy constructors for most containers, AMTL does not, as these
    12   operations are unsafe for fallible malloc(), and can cause large unintentional performance hits.
    13 
    14   Another example is boost::shared\_ptr, which by default is atomic and threadsafe, and
    15   preprocessor macros can be used to eliminate the thread safety option. AMTL opts to use distinct
    16   types for threadsafe and non-threadsafe reference counting, as the cost of atomic refcounting
    17   is higher.
    18 
    19 * Safety. Most code in AlliedModders does not take advantage of RAII, and does not account for
    20   fallible malloc. While in general, infallible malloc is probably okay for game servers, the lack
    21   of RAII leads to very complicated and bloated pointer management. A major goal of AMTL is to
    22   introduce safer pointer management into its codebases, and to allow certain components to safely
    23   handle malloc failures when desired.
    24 
    25 * No linkage. EVerything is contained within headers so that tools don't need to link additional
    26   C++ files. This could be a drawback, for example, it could increase build time or codesize
    27   bloat. We may evaluate this decision in the future, but for now, it fits into our "lightweight"
    28   theme of usability.
    29 
    30   (On some platforms, system libraries may be needed for certain headers.)
    31 
    32 * No RTTI or EH. There are a few reasons for this:
    33   + Both features require linkage to libstdc++. On Linux, this can cause problems with binary
    34     distribution.
    35 
    36   + When using 32-bit Visual C++, try blocks are not zero-cost, as they are implemented using SEH.
    37 
    38 * Fallible malloc. In many cases it's not desirable to terminate the program or throw an
    39   exception when an allocation fails (for example, resizing a large vector). Thus, functions
    40   like ke::Vector::append (analagous to std::vector::push\_back) will usually return bool. Whether
    41   or not these functions return (i.e., abort the program or fail safely) can be specified in an
    42   allocation policy.
    43 
    44 * Room to grow. These templates are intended to be a baseline of features needed for various
    45   AlliedModders projects. They can and will grow as new features are needed, hopefully keeping the
    46   above principles in mind.
    47 
    48 # Overview
    49 
    50 All classes and functions reside in a "ke" namespace, and all macros are prefixed with "KE\_".
    51 
    52 ### Platform Utilities (am-utilities.h)
    53 
    54 This provides some common helper functions pretty much lumped together:
    55 * AutoPtr<T>, RAII for calling delete on a pointer.
    56 * AutoArray<T>, RAII for calling delete[] on a pointer.
    57 * Detectors for add or multiply overflow, useful for computing allocation sizes.
    58 * Fast Log2/Floor2 functions (also known as bitscan or count zeroes).
    59 * Integer alignment (useful for allocators or code generators).
    60 * KE\_DELETE and KE\_OVERRIDE which map to delete and override keywords if C++11 is available.
    61 
    62 ### Moveable (am-moveable.h)
    63 
    64 Moveable<T> is a helper to emulate C++11 move semantics (rvalue references). A class can implement
    65 a move constructor like so:
    66 
    67     class X
    68     {
    69      public:
    70       X(Moveable<X> other)
    71 
    72 And a moveable value can be given like:
    73 
    74     vector.append(Moveable<X>(value));
    75 
    76 Containers within AMTL all support move semantics; however, not all containers are moveable yet.
    77 If move semantics are critical for correctness or performance, it is wise to disallow copy
    78 construction entirely:
    79 
    80     class X
    81     {
    82      ...
    83      private:
    84       X(const X &other) KE_DELETE;
    85 
    86 ### Thread Utilities (am-thread-utils.h)
    87 
    88 Thread utils provides access to common sychronization primitives: mutexes, condition variables,
    89 and threads. It also provides RAII objects for acquiring and releasing locks. More information is
    90 available at the top of am-thread-utils.h.
    91 
    92 ### Reference Counting (am-refcounting.h)
    93 
    94 Two classes are available to help other classes implement reference counting. They are Refcounted
    95 and RefcountedThreadsafe. Both must be inherited recursively, for example:
    96 
    97     class MyObject : public Refcounted<MyObject>
    98   
    99 The object is instantiated with a reference count of 1. A few RAII objects are provided for
   100 automatically retaining and releasing references:
   101 
   102 * Ref<T>. Adds one reference upon construction and releases one reference on destruction.
   103 * PassRef<T>. Same as Ref<T>, except, when passed into a Ref<T> or into a PassRef<T>, the contained
   104   reference is NULL'd, rather than performing an unnecessary extra AddRef()+Release(). PassRef<T>
   105   is intended only for return values.
   106 * Newborn<T>. If a newly allocated Refcounted object is stored into a Ref<T>, it will have one
   107   extra reference. When allocating new refcounted objects, they should be immediately wrapped in a
   108   Newborn<T> to prevent this.
   109 
   110 RefcountedThreadsafe provides the same accessors as Refcounted. However, the reference counting is
   111 performed using atomic operations, so that two threads racing do not accidentally result in a wrong
   112 reference count (since a read + write is not normally atomic). This does not make the actual object
   113 threadsafe, rather, it makes it safe for multiple threads to mutate the reference count.
   114 
   115 ### Allocator Policies (am-allocator-policies.h)
   116 
   117 ke::HashTable and ke::Vector are both parameterized on an "AllocPolicy". It is accessed whenever a
   118 malloc(), free(), size overflow, or out-of-memory operation occurs. The default functionality of
   119 SystemAllocatorPolicy is to abort the process on any failure, which can be changed by implementing
   120 a new policy. As HashTable and Vector inherit from the AllocPolicy, it is possible to use custom
   121 allocators without accessing static variables.
   122 
   123 ### Vector (am-vector.h)
   124 
   125 ke::Vector is roughly analagous to std::vector. A few method names are changed:
   126 * size() is length()
   127 * push\_back() is append() and returns boolean.
   128 * The underlying buffer of a vector can be "taken", which is sometimes useful for transferring
   129   ownership of data.
   130 
   131 Vector does not have an iterator type. It should be iterated through normal sequential indexing.
   132 
   133 ### HashTable (am-hashtable.h)
   134 
   135 ke::HashTable is an open-addressing, linear-probing hash table. It is a bit more powerful than a
   136 generic key -> value map as it is templated on a "policy", rather than keys and values. A policy
   137 specifies what entries in the table look like, and how they are searched. Policies must have three
   138 members:
   139 
   140 * Payload - the type that will be stored for each entry in the hash table.
   141 * static bool matches(const T &t, Payload &p); - Must return true if |t| is equal to the entry at |p|.
   142 * static uin32\_t hash(const T &t); - Must compute a hash for |t|.
   143 
   144 The typename T in the policy applies for every key type that will be used in the hash table. For
   145 example, a hash table might store string keys, but have faster lookup using std::string versus a
   146 C-string, or even faster lookup for a string type that has its hash precomputed.
   147 
   148 All key types must effectively compute the same hash; i.e., it would not be legal for Payload to
   149 match both |int| and |std::string| but compute different hashes.
   150 
   151 HashTable returns either a Result or Insert object when performing lookups, depending on the type
   152 of lookup. A Result object is either found or not found. An Insert object, however, caches
   153 information about where it found the object, so that it doesn't have to repeat the hashing and
   154 lookup process for the subsequent add() call. Examples on how to use this are in am-hashmap.h, and
   155 the exact rules on how Result and Insert objects can be used are in am-hashtable.h.
   156 
   157 HashTables can be iterated. If the table is mutated during iteration outside of the interface
   158 provided by the iterator, then the iterator may become corrupted. This is acceptable as long as the
   159 iterator is abandoned. However, the table must stay alive for as long as the iterator is active.
   160 
   161 ### HashMap (am-hashmap.h)
   162 
   163 ke::HashMap is a key -> value map built upon HashTable. This saves you from having to implement all
   164 of a Policy and provides some more generic accessors. However it is still necessary to implement a
   165 hash and comparison function.
   166 
   167 ### HashSet (am-hashset.h)
   168 
   169 ke::HashSet is a HashMap that only stores keys. Like HashMap, you must still implement a policy
   170 with comparison and hash functions.
   171 
   172 ### InlineList (am-inlinelist.h)
   173 
   174 InlineList is a doubly-linked list that does use any calls to malloc(), with the caveat that list
   175 members can be members in at most one inline list at a time. Objects must recursively inherit from
   176 InlineListNode, which ensures that the object has prev/next pointers. Example:
   177 
   178     class MyObject : public InlineListNode<MyObject>
   179     { };
   180     InlineList<MyObject> list;
   181 
   182 InlineList is ideal for situations where objects have already been allocated and will be a member
   183 of at most one list at any time. If this is the case, the per-node malloc/free of std::list can be
   184 completely avoided.
   185 
   186 An InlineList never claims ownership over its pointers. Its destructor is a no-op and it makes no
   187 attempt to destroy members of its list (though in debug builds it will unlink members in its
   188 destructor for assertion purposes).
   189 
   190 ### LinkedList (am-linkedlist.h)
   191 
   192 LinkedList is a doubly-linked list that requires a malloc() for each entry. It is provided for
   193 backward compatibility, and it should be avoided in general, except in situations where it is
   194 absolutely necessary and allocation performance is not a factor. Otherwise, use InlineList or
   195 Vector.
   196 
   197 ### Strings (am-string.h)
   198 
   199 The String API is still rather in flux. Currently, a simple std::string-like class is provided
   200 called AString (short for ASCII String).
   201 
   202 # Replacing SourceHook Includes
   203 
   204 AMTL is a spiritual successor to the SourceHook template library, used in many AlliedModders
   205 projects. AMTL is intended to deprecate it.
   206 
   207 ### CVector (sh\_vector.h)
   208 
   209 CVector can be replaced with ke::Vector. ke::Vector does not provide an iterator (yet). A few
   210 method names have been changed, as CVector more closely models std::vector, however the classes are
   211 pretty similar. Any missing methods could be added quite easily.
   212 
   213 ### String (sh\_string.h)
   214 
   215 String can be replaced with ke::AString, however some methods like trim() are not available yet.
   216 One notable difference is that AString caches the length of the string, whereas SH::String does
   217 not. That means AString is a larger data structure (by 4 bytes, on 32-bit), but is not prone to
   218 O(n^2) operations like String. This more closely matches the functionality of std::string.
   219 
   220 ### List (sh\_list.h)
   221 
   222 List can be replaced with ke::LinkedList. A few methods have changed, similar to Vector. For
   223 example, push\_back() becomes append() and push\_front() becomes prepend(), and both return
   224 boolean.
   225 
   226 Consider using ke::InlineList if your list contains already-allocated objects, and those objects
   227 are members of at most one list, LinkedList will call malloc() and free() for each node.
   228 
   229 The implementation of SourceHook::List and ke::LinkedList are basically identical underneath the
   230 hood, however, copy construction and assignment are disallowed in the AMTL variant. This is because
   231 they violate the memory model and also have very poor performance impliciations.
   232 
   233 ### THash<K, V> (sh\_tinyhash.h)
   234 
   235 TinyHash can be replaced with ke::HashMap, with minor changes. Comparators must be implemented as
   236 equality operators on the key type, and the hash function is specified as a template parameter.
   237 
   238 TinyHash is disadvantageous for a number of reasons. It uses separate chaining, and chains are
   239 built on top of SourceHook::List, so it will use more memory on average. Inserts are also more
   240 expensive as a call to malloc() is almost guaranteed. Retrieval is more expensive as well, since it
   241 requires more indirection and has worse cache locality. It also has no ability to resize table
   242 downward when its density is very low.
   243 
   244 ### CStack (sh\_stack.h)
   245 
   246 SourceHook::CStack is a stable-pointer stack. That is, if an element has been pushed, the address
   247 the element is stored at is guaranteed not to change unless the element is removed. This can be an
   248 important requirement in cases that involve re-entrancy. If you are relying on this feature of
   249 CStack, there is no replacement in AMTL. If your CStack entries are LIFO, and tied to local
   250 variables, you might consider simply linking objects together using RAII and avoiding CStack
   251 entirely (though CStack will have better cache performance if you need to walk the list of entries).
   252 
   253 If you don't need stable pointers, CStack can be replaced with ke::Vector.
   254 
   255 # License
   256 
   257 All headers are licensed under a 3-clause BSD license.