Adding upstream version 16.2.upstream/16.2

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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.