diff options
Diffstat (limited to 'src/backend/lib/README')
-rw-r--r-- | src/backend/lib/README | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/src/backend/lib/README b/src/backend/lib/README new file mode 100644 index 0000000..f2fb591 --- /dev/null +++ b/src/backend/lib/README @@ -0,0 +1,35 @@ +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. |