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