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