Debian Codegraph @

src/backend/lib/README

raw
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.