README.md
author David Anderson <dvander@alliedmods.net>
Thu Aug 29 23:51:30 2013 -0700 (2013-08-29)
changeset 16 c513ef40773e
parent 10 0ac292cc1467
child 18 9b30f80f6e49
permissions -rw-r--r--
Sync from sourcemod.
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
dvander@10
    62
### Moveable (am-moveable.h)
dvander@10
    63
dvander@10
    64
Moveable<T> is a helper to emulate C++11 move semantics (rvalue references). A class can implement
dvander@10
    65
a move constructor like so:
dvander@10
    66
dvander@10
    67
    class X
dvander@10
    68
    {
dvander@10
    69
     public:
dvander@10
    70
      X(Moveable<X> other)
dvander@10
    71
dvander@10
    72
And a moveable value can be given like:
dvander@10
    73
dvander@10
    74
    vector.append(Moveable<X>(value));
dvander@10
    75
dvander@10
    76
Containers within AMTL all support move semantics; however, not all containers are moveable yet.
dvander@10
    77
If move semantics are critical for correctness or performance, it is wise to disallow copy
dvander@10
    78
construction entirely:
dvander@10
    79
dvander@10
    80
    class X
dvander@10
    81
    {
dvander@10
    82
     ...
dvander@10
    83
     private:
dvander@10
    84
      X(const X &other) KE_DELETE;
dvander@10
    85
danderson@0
    86
### Thread Utilities (am-thread-utils.h)
danderson@0
    87
danderson@0
    88
Thread utils provides access to common sychronization primitives: mutexes, condition variables,
danderson@0
    89
and threads. It also provides RAII objects for acquiring and releasing locks. More information is
danderson@0
    90
available at the top of am-thread-utils.h.
danderson@0
    91
danderson@0
    92
### Reference Counting (am-refcounting.h)
danderson@0
    93
danderson@0
    94
Two classes are available to help other classes implement reference counting. They are Refcounted
danderson@0
    95
and RefcountedThreadsafe. Both must be inherited recursively, for example:
danderson@0
    96
danderson@0
    97
    class MyObject : public Refcounted<MyObject>
danderson@0
    98
  
danderson@0
    99
The object is instantiated with a reference count of 1. A few RAII objects are provided for
danderson@0
   100
automatically retaining and releasing references:
danderson@0
   101
danderson@0
   102
* Ref<T>. Adds one reference upon construction and releases one reference on destruction.
danderson@0
   103
* PassRef<T>. Same as Ref<T>, except, when passed into a Ref<T> or into a PassRef<T>, the contained
danderson@0
   104
  reference is NULL'd, rather than performing an unnecessary extra AddRef()+Release(). PassRef<T>
danderson@0
   105
  is intended only for return values.
danderson@0
   106
* Newborn<T>. If a newly allocated Refcounted object is stored into a Ref<T>, it will have one
danderson@0
   107
  extra reference. When allocating new refcounted objects, they should be immediately wrapped in a
danderson@0
   108
  Newborn<T> to prevent this.
danderson@0
   109
danderson@0
   110
RefcountedThreadsafe provides the same accessors as Refcounted. However, the reference counting is
danderson@0
   111
performed using atomic operations, so that two threads racing do not accidentally result in a wrong
danderson@0
   112
reference count (since a read + write is not normally atomic). This does not make the actual object
danderson@0
   113
threadsafe, rather, it makes it safe for multiple threads to mutate the reference count.
danderson@0
   114
danderson@0
   115
### Allocator Policies (am-allocator-policies.h)
danderson@0
   116
danderson@0
   117
ke::HashTable and ke::Vector are both parameterized on an "AllocPolicy". It is accessed whenever a
danderson@0
   118
malloc(), free(), size overflow, or out-of-memory operation occurs. The default functionality of
danderson@0
   119
SystemAllocatorPolicy is to abort the process on any failure, which can be changed by implementing
danderson@0
   120
a new policy. As HashTable and Vector inherit from the AllocPolicy, it is possible to use custom
danderson@0
   121
allocators without accessing static variables.
danderson@0
   122
danderson@0
   123
### Vector (am-vector.h)
danderson@0
   124
danderson@0
   125
ke::Vector is roughly analagous to std::vector. A few method names are changed:
danderson@0
   126
* size() is length()
danderson@0
   127
* push\_back() is append() and returns boolean.
danderson@0
   128
* The underlying buffer of a vector can be "taken", which is sometimes useful for transferring
danderson@0
   129
  ownership of data.
danderson@0
   130
danderson@0
   131
Vector does not have an iterator type. It should be iterated through normal sequential indexing.
danderson@0
   132
danderson@0
   133
### HashTable (am-hashtable.h)
danderson@0
   134
danderson@0
   135
ke::HashTable is an open-addressing, linear-probing hash table. It is a bit more powerful than a
danderson@0
   136
generic key -> value map as it is templated on a "policy", rather than keys and values. A policy
danderson@0
   137
specifies what entries in the table look like, and how they are searched. Policies must have three
danderson@0
   138
members:
danderson@0
   139
danderson@0
   140
* Payload - the type that will be stored for each entry in the hash table.
danderson@0
   141
* static bool matches(const T &t, Payload &p); - Must return true if |t| is equal to the entry at |p|.
danderson@0
   142
* static uin32\_t hash(const T &t); - Must compute a hash for |t|.
danderson@0
   143
danderson@0
   144
The typename T in the policy applies for every key type that will be used in the hash table. For
danderson@0
   145
example, a hash table might store string keys, but have faster lookup using std::string versus a
danderson@0
   146
C-string, or even faster lookup for a string type that has its hash precomputed.
danderson@0
   147
danderson@0
   148
All key types must effectively compute the same hash; i.e., it would not be legal for Payload to
danderson@0
   149
match both |int| and |std::string| but compute different hashes.
danderson@0
   150
danderson@0
   151
HashTable returns either a Result or Insert object when performing lookups, depending on the type
danderson@0
   152
of lookup. A Result object is either found or not found. An Insert object, however, caches
danderson@0
   153
information about where it found the object, so that it doesn't have to repeat the hashing and
danderson@0
   154
lookup process for the subsequent add() call. Examples on how to use this are in am-hashmap.h, and
danderson@0
   155
the exact rules on how Result and Insert objects can be used are in am-hashtable.h.
danderson@0
   156
danderson@0
   157
HashTables can be iterated. If the table is mutated during iteration outside of the interface
danderson@0
   158
provided by the iterator, then the iterator may become corrupted. This is acceptable as long as the
danderson@0
   159
iterator is abandoned. However, the table must stay alive for as long as the iterator is active.
danderson@0
   160
danderson@0
   161
### HashMap (am-hashmap.h)
danderson@0
   162
dvander@10
   163
ke::HashMap is a key -> value map built upon HashTable. This saves you from having to implement all
dvander@10
   164
of a Policy and provides some more generic accessors. However it is still necessary to implement a
dvander@10
   165
hash and comparison function.
dvander@10
   166
dvander@10
   167
### HashSet (am-hashset.h)
dvander@10
   168
dvander@10
   169
ke::HashSet is a HashMap that only stores keys. Like HashMap, you must still implement a policy
dvander@10
   170
with comparison and hash functions.
danderson@0
   171
danderson@0
   172
### InlineList (am-inlinelist.h)
danderson@0
   173
danderson@0
   174
InlineList is a doubly-linked list that does use any calls to malloc(), with the caveat that list
danderson@0
   175
members can be members in at most one inline list at a time. Objects must recursively inherit from
danderson@0
   176
InlineListNode, which ensures that the object has prev/next pointers. Example:
danderson@0
   177
danderson@0
   178
    class MyObject : public InlineListNode<MyObject>
danderson@0
   179
    { };
danderson@0
   180
    InlineList<MyObject> list;
danderson@0
   181
danderson@0
   182
InlineList is ideal for situations where objects have already been allocated and will be a member
danderson@0
   183
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
   184
completely avoided.
danderson@0
   185
danderson@0
   186
An InlineList never claims ownership over its pointers. Its destructor is a no-op and it makes no
danderson@0
   187
attempt to destroy members of its list (though in debug builds it will unlink members in its
danderson@0
   188
destructor for assertion purposes).
danderson@0
   189
danderson@0
   190
### LinkedList (am-linkedlist.h)
danderson@0
   191
danderson@0
   192
LinkedList is a doubly-linked list that requires a malloc() for each entry. It is provided for
danderson@0
   193
backward compatibility, and it should be avoided in general, except in situations where it is
danderson@0
   194
absolutely necessary and allocation performance is not a factor. Otherwise, use InlineList or
danderson@0
   195
Vector.
danderson@0
   196
danderson@0
   197
### Strings (am-string.h)
danderson@0
   198
danderson@0
   199
The String API is still rather in flux. Currently, a simple std::string-like class is provided
danderson@0
   200
called AString (short for ASCII String).
danderson@0
   201
danderson@0
   202
# Replacing SourceHook Includes
danderson@0
   203
danderson@0
   204
AMTL is a spiritual successor to the SourceHook template library, used in many AlliedModders
danderson@0
   205
projects. AMTL is intended to deprecate it.
danderson@0
   206
danderson@0
   207
### CVector (sh\_vector.h)
danderson@0
   208
danderson@0
   209
CVector can be replaced with ke::Vector. ke::Vector does not provide an iterator (yet). A few
danderson@0
   210
method names have been changed, as CVector more closely models std::vector, however the classes are
danderson@0
   211
pretty similar. Any missing methods could be added quite easily.
danderson@0
   212
dvander@7
   213
### String (sh\_string.h)
danderson@0
   214
dvander@7
   215
String can be replaced with ke::AString, however some methods like trim() are not available yet.
dvander@7
   216
One notable difference is that AString caches the length of the string, whereas SH::String does
dvander@7
   217
not. That means AString is a larger data structure (by 4 bytes, on 32-bit), but is not prone to
dvander@7
   218
O(n^2) operations like String. This more closely matches the functionality of std::string.
danderson@0
   219
danderson@0
   220
### List (sh\_list.h)
danderson@0
   221
danderson@0
   222
List can be replaced with ke::LinkedList. A few methods have changed, similar to Vector. For
danderson@0
   223
example, push\_back() becomes append() and push\_front() becomes prepend(), and both return
danderson@0
   224
boolean.
danderson@0
   225
danderson@0
   226
Consider using ke::InlineList if your list contains already-allocated objects, and those objects
danderson@0
   227
are members of at most one list, LinkedList will call malloc() and free() for each node.
danderson@0
   228
danderson@0
   229
The implementation of SourceHook::List and ke::LinkedList are basically identical underneath the
danderson@0
   230
hood, however, copy construction and assignment are disallowed in the AMTL variant. This is because
danderson@0
   231
they violate the memory model and also have very poor performance impliciations.
danderson@0
   232
danderson@0
   233
### THash<K, V> (sh\_tinyhash.h)
danderson@0
   234
danderson@0
   235
TinyHash can be replaced with ke::HashMap, with minor changes. Comparators must be implemented as
danderson@0
   236
equality operators on the key type, and the hash function is specified as a template parameter.
danderson@0
   237
danderson@0
   238
TinyHash is disadvantageous for a number of reasons. It uses separate chaining, and chains are
danderson@0
   239
built on top of SourceHook::List, so it will use more memory on average. Inserts are also more
danderson@0
   240
expensive as a call to malloc() is almost guaranteed. Retrieval is more expensive as well, since it
danderson@0
   241
requires more indirection and has worse cache locality. It also has no ability to resize table
danderson@0
   242
downward when its density is very low.
danderson@0
   243
danderson@0
   244
### CStack (sh\_stack.h)
danderson@0
   245
danderson@0
   246
SourceHook::CStack is a stable-pointer stack. That is, if an element has been pushed, the address
danderson@0
   247
the element is stored at is guaranteed not to change unless the element is removed. This can be an
danderson@0
   248
important requirement in cases that involve re-entrancy. If you are relying on this feature of
danderson@0
   249
CStack, there is no replacement in AMTL. If your CStack entries are LIFO, and tied to local
danderson@0
   250
variables, you might consider simply linking objects together using RAII and avoiding CStack
danderson@0
   251
entirely (though CStack will have better cache performance if you need to walk the list of entries).
danderson@0
   252
danderson@0
   253
If you don't need stable pointers, CStack can be replaced with ke::Vector.
danderson@0
   254
danderson@0
   255
# License
danderson@0
   256
danderson@0
   257
All headers are licensed under a 3-clause BSD license.