| 1 |
This directory contains a general purpose data structures, for use anywhere |
| 2 |
in the backend: |
| 3 |
|
| 4 |
bipartite_match.c - Hopcroft-Karp maximum cardinality algorithm for bipartite graphs |
| 5 |
|
| 6 |
bloomfilter.c - probabilistic, space-efficient set membership testing |
| 7 |
|
| 8 |
dshash.c - concurrent hash tables backed by dynamic shared memory areas |
| 9 |
|
| 10 |
hyperloglog.c - a streaming cardinality estimator |
| 11 |
|
| 12 |
ilist.c - single and double-linked lists |
| 13 |
|
| 14 |
integerset.c - a data structure for holding large set of integers |
| 15 |
|
| 16 |
knapsack.c - knapsack problem solver |
| 17 |
|
| 18 |
pairingheap.c - a pairing heap |
| 19 |
|
| 20 |
rbtree.c - a red-black tree |
| 21 |
|
| 22 |
|
| 23 |
Aside from the inherent characteristics of the data structures, there are a |
| 24 |
few practical differences between the binary heap and the pairing heap. The |
| 25 |
binary heap is fully allocated at creation, and cannot be expanded beyond the |
| 26 |
allocated size. The pairing heap on the other hand has no inherent maximum |
| 27 |
size, but the caller needs to allocate each element being stored in the heap, |
| 28 |
while the binary heap works with plain Datums or pointers. |
| 29 |
|
| 30 |
The linked-lists in ilist.c can be embedded directly into other structs, as |
| 31 |
opposed to the List interface in nodes/pg_list.h. |