| This directory contains a general purpose data structures, for use anywhere |
| in the backend: |
| |
| binaryheap.c - a binary heap |
| |
| bipartite_match.c - Hopcroft-Karp maximum cardinality algorithm for bipartite graphs |
| |
| bloomfilter.c - probabilistic, space-efficient set membership testing |
| |
| dshash.c - concurrent hash tables backed by dynamic shared memory areas |
| |
| hyperloglog.c - a streaming cardinality estimator |
| |
| ilist.c - single and double-linked lists |
| |
| integerset.c - a data structure for holding large set of integers |
| |
| knapsack.c - knapsack problem solver |
| |
| pairingheap.c - a pairing heap |
| |
| rbtree.c - a red-black tree |
| |
| stringinfo.c - an extensible string type |
| |
| |
| Aside from the inherent characteristics of the data structures, there are a |
| few practical differences between the binary heap and the pairing heap. The |
| binary heap is fully allocated at creation, and cannot be expanded beyond the |
| allocated size. The pairing heap on the other hand has no inherent maximum |
| size, but the caller needs to allocate each element being stored in the heap, |
| while the binary heap works with plain Datums or pointers. |
| |
| The linked-lists in ilist.c can be embedded directly into other structs, as |
| opposed to the List interface in nodes/pg_list.h. |
