36 lines
1.2 KiB
Plaintext
36 lines
1.2 KiB
Plaintext
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.
|