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