-
Notifications
You must be signed in to change notification settings - Fork 18
Pools
In PawnPlus, a pool is a collection of identifiable and traversable heterogenous elements, essentially a linear indexed multiset. When a new object is added to a pool, it is assigned a unique previously unused index that can be used to refer to the object in the pool. Adding or removing elements does not change the indices of other elements, forming gaps in the container if necessary. Pools are optimized for indexed access, iteration, and finding an empty slot for a newly added element.
Pools are similar to lists and linked lists in their operations. You can add or remove elements in the pool, using an index:
new Pool:p = pool_new();
new a = pool_add(p, 1);
new b = pool_add(p, 2);
assert pool_size(p) == 2;
assert pool_remove(p, a);
assert pool_get(p, b) == 2;
assert pool_remove(p, b);
assert pool_size(p) == 0;
pool_delete(p);As you can see from the example, removing the element at a did not invalidate the element at b, instead forming a gap in the pool. When a new element is added to a pool, all empty slots (gaps) are used first before the pool is resized. pool_add might not necessarily return the smallest available index; that depends on the implementation (see below).
It is recommended to initialize a pool with a specific starting capacity, either via pool_new or pool_resize. This might take some amount of time depending on the set capacity, but adding new elements will remove the need to resize the pool when all slots are used, and will also not invalidate existing iterators.
Regardless of the initial capacity, new elements can always be added to a pool, and pool_set can be used to set the value at any (non-negative) index (however, all slots below the index still have to be initialized, so large indices will cause large memory allocations).
Iterating all elements in a pool is similar to other containers, but it skips unused slots more efficiently compared to lists (when VAR_NULL is used to represent a "gap"):
new Pool:p = pool_new();
pool_set(p, 10, 1);
pool_set(p, 20, 2);
pool_set(p, 30, 3);
for_pool(it : p)
{
print_s(str_val(it));
}Note that iteration can begin at the lowest existing index, but may not do so when some more elements are added or removed.
Similarly to maps, there are actually two available different pool implementation with a common interface. The default one is an unordered (linked) pool, which internally stores two linked lists, one for used slots and one for unused slots. Changing the used state of a slot will move it between the two linked lists, which means that the first considered slot (used for iterating or unused for pool_add) will be the slot that was linked the first, not the lowest one.
This may not be consistent with what many people are used to, therefore there is also an alternate implementation that guarantees the lowest index is always chosen, albeit with a small performance impairment (but still better than list lookup). The ordered (block) list uses a tree-like structure of blocks, where each block corresponds to a power of 4 elements (either directly 4 elements, or 4 blocks). Each block also tracks the number of used slots it corresponds to, thus looking for a non-empty or non-full block only requires traversing the tree structure (log_4 n blocks) in all cases, still much more efficient than linear list lookup.
new Pool:p = pool_new();
pool_add(p, 1), pool_add(p, 2), pool_add(p, 3);
pool_remove(p, 1);
pool_remove(p, 0);
assert pool_add(p, 4) == 1;
assert pool_add(p, 5) == 0;new Pool:p = pool_new();
pool_set_ordered(p, true);
pool_add(p, 1), pool_add(p, 2), pool_add(p, 3);
pool_remove(p, 1);
pool_remove(p, 0);
assert pool_add(p, 4) == 0;
assert pool_add(p, 5) == 1;| Container | Indexing | Adding | Removing | Iteration burden |
|---|---|---|---|---|
List (VAR_NULL for unused slots) |
O(1) | O(n) | O(1) | O(1) |
| Unordered pool | O(1) | O(1) | O(1) | 0 |
| Ordered pool | O(1) | O(log n) | O(log n) | O(log n) |
Like other larger data types, pools are not garbage-collected, so they must be explicitly deleted with pool_delete when they are no longer used. However, like with lists, objects stored in pools via references will not be deleted this way, so pool_delete_deep has to be used to recursively delete all objects inside the structure.
While usually pools are used for complex objects and thus generic pools aren't usable much, they can be still used:
new Pool<Float>:p = pool_new<Float>();
pool_add<Float>(p, 1.5);