PostgreSQL 12¶

Author: Jacob Park

PostgreSQL is a powerful, open source object-relational database system with over 30 years of active development that has earned it a strong reputation for reliability, feature robustness, and performance.

Table of Contents¶

Documentation
Presentations
Top-Level Directories
Backend
1. READMEs
2. Flowchart
Commons
General Purpose Data Structures
Shared Components and Utilities

Jupyter¶

%%HTML
<style>
table {
    width: 100%;
}
tr th:first-child, tr td:first-child {
    width: 25%;
    min-width: 25%;
    max-width: 25%;
}
</style>

Documentation ¶

Presentations ¶

Presenter	Slides	Videos
Bruce Momjian	PostgreSQL Internals Through Pictures	YouTube
Bruce Momjian	Explaining the Postgres Query Optimizer	YouTube
Bruce Momjian	MVCC Unmasked	YouTube
Bruce Momjian	Unlocking the Postgres Lock Manager	YouTube
Bruce Momjian	Inside PostgreSQL Shared Memory	YouTube
Bruce Momjian	PostgreSQL Performance Tuning	YouTube
Bruce Momjian	Will Postgres Live Forever	YouTube
Chris Travers	Introduction to Memory Contexts	YouTube
Melanie Plageman	Intro to Postgres Planner Hacking	YouTube
Neil Conway	Introduction to Hacking PostgreSQL (Handouts)	N/A.
Neil Conway	Query Execution Techniques in PostgreSQL	N/A.
Peter Eisentraut	How does PostgreSQL actually work?	YouTube
Stephen Frost	Hacking PostgreSQL	YouTube
Thomas Munro	Parallelism in PostgreSQL 11	YouTube

Top-Level Directories ¶

Root Directories: `/`¶

Directory	Description
/config	This directory contains the configuration files (`*.m4`) for building PostgreSQL.
/contrib	This directory contains the source codes of extensions, tools, and utilities separate from the core of PostgreSQL.
/doc	This directory contains the documentation files (`*.sgml`) for building the documentation of PostgreSQL.
/src	This directory contains the source codes of the core of PostgreSQL.

Source Directories: `/src`¶

Directory	Description
/src/backend	This directory contains the source codes of the server of PostgreSQL.
/src/bin	This directory contains the source codes of the binaries that DBAs use to administer and to monitor installations of PostgreSQL.
/src/common	This directory contains the source codes common to PostgreSQL's Backend and Frontend.
/src/fe_utils	This directory contains the source codes auxiliary to PostgreSQL's Frontend Utilities.
/src/include	This directory contains the header files (`.h`) of PostgreSQL's Backend*.
/src/interfaces	This directory contains the source codes of the clients of PostgreSQL: libpq and ECPG.
/src/makefiles	This directory contains the `make` files (`Makefile.*`) for building PostgreSQL on various platforms.
/src/pl	This directory contains the source codes of Procedural Languages supported by PostgreSQL: PL/pgSQL, PL/Tcl, PL/Perl, and PL/Python.
/src/port	This directory contains the source codes of the special-behavior functions required to port PostgreSQL to various platforms.
/src/template	This directory contains the template files for configuring the PostgreSQL source tree for various platforms: `configure`.
/src/test	This directory contains the source codes of the testing infrastructure of PostgreSQL.
/src/timezone	This directory contains the source codes of PostgreSQL's fork of IANA's Time Zone Database.
/src/tools	This directory contains the Perl/Shell scripts intended to assist contributors.
/src/tutorial	This directory contains the SQL scripts for PostgreSQL 12's Tutorial.

Backend Directories: `/src/backend`¶

Directory	Description
/src/backend/access	This directory contains the source codes related to the Access Methods of PostgreSQL: Table Access Method Interface Definition and Index Access Method Interface Definition.
/src/backend/bootstrap	This directory contains the source codes related to `initdb`.
/src/backend/catalog	This directory contains the source codes related to reading and writing the catalogs of PostgreSQL: System Catalogs.
/src/backend/commands	This directory contains the source codes related to user-level DDL statements: SQL Commands.
/src/backend/executor	This directory contains the source codes related to the Query Executor of PostgreSQL: Executor.
/src/backend/foreign	This directory contains the source codes related to the Foreign Data Wrappers API of PostgreSQL: postgres_fdw.
/src/backend/jit	This directory contains the source codes related to the Just-In-Time Compilation infrastructure of PostgreSQL: Just-in-Time Compilation (JIT).
/src/backend/lib	This directory contains the source codes of general purpose data structures available anywhere in `/src/backend`.
/src/backend/libpq	This directory contains the source codes related to the Frontend/Backend Protocol of PostgreSQL: How Connections Are Established and Frontend/Backend Protocol .
/src/backend/main	This directory contains the source codes related to the `main()` entrypoint of a `postgres`-affiliated process.
/src/backend/nodes	This directory contains the source codes related to the Nodes infrastructure of PostgreSQL.
/src/backend/optimizer	This directory contains the source codes related to the Query Optimizer of PostgreSQL: Planner/Optimizer and Genetic Query Optimizer.
/src/backend/parser	This directory contains the source codes related to the SQL Parser of PostgreSQL: The Parser Stage.
/src/backend/partitioning	This directory contains the source codes related to Declarative Partitioning in PostgreSQL: Table Partitioning.
/src/backend/po	This directory contains the translation files (`.po`) for translating the Backend* messages of PostgreSQL: Native Language Support.
/src/backend/port	This directory contains the source codes related to Backend-specific, special-behavior functions required to port PostgreSQL to various platforms.
/src/backend/postmaster	This directory contains the source codes related to the Dispatcher of PostgreSQL: `postmaster`.
/src/backend/regex	This directory contains the source codes related to regular expressions.
/src/backend/replication	This directory contains the source codes related to the Write-Ahead-Log Replication of PostgreSQL: Log-Shipping Standby Servers.
/src/backend/rewrite	This directory contains the source codes related to the Query Rewriter of PostgreSQL: The PostgreSQL Rule System.
/src/backend/snowball	This directory contains the source codes related to Snowball Stemming: Dictionaries: Snowball Dictionary.
/src/backend/statistics	This directory contains the source codes related to the Optimizer Statistics Gathering of PostgreSQL: Statistics Used by the Planner and How the Planner Uses Statistics.
/src/backend/storage	This directory contains the source codes related to the Transactional Storage Manager: Database Physical Storage.
/src/backend/tcop	This directory contains the source codes related to Traffic Cop which dispatches requests on behalf of the `postgres` process to the SQL Parser, Query Optimizer, Query Executor, and Commands of PostgreSQL.
/src/backend/tsearch	This directory contains the source codes related to Full-Text Search of PostgreSQL: Full Text Search.
/src/backend/utils	This directory contains the source codes related to various Backend utilities such as Abstract Data Types, Caches, Error Handling, Function Manager, Hashing, Global Variables, Strings, GUCs, Memory Contexts, Resource Owners, Sorting, and Tuple Timestamps.

Backend ¶

READMEs ¶

Flowchart ¶

Commons ¶

Header Files ¶

/src/include/c.h - Functional C Definitions.
/src/include/postgres.h - Primary Server-Side Commons.
/src/include/postgres_fe.h - Primary Client-Side Commons.
/src/include/postgres_ext.h - Everywhere Commons.

Functional C Definitions: `c.h`¶

C Standard Library¶

Standard Types¶

Type	Description
`bool`	A Boolean type with `true` and `false` literal macros.
`int8`	An exact 8-bit signed integer type.
`int16`	An exact 16-bit signed integer type.
`int32`	An exact 32-bit signed integer type.
`int64`	An exact 64-bit signed integer type.
`int128`	An exact 128-bit signed integer type.
`uint8`	An exact 8-bit unsigned integer type.
`uint16`	An exact 16-bit unsigned integer type.
`uint32`	An exact 32-bit unsigned integer type.
`uint64`	An exact 64-bit unsigned integer type.
`uint128`	An exact 128-bit unsigned integer type.
`bits8`	A minimum 8-bit bitwise type.
`bits16`	A minimum 16-bit bitwise type.
`bits32`	A minimum 32-bit bitwise type.
`float4`	A minimum 4-byte floating-point decimal type.
`float8`	A minimum 8-byte floating-point decimal type.
`Pointer`	A type representing the address of any memory resident object.
`Size`	A type representing the size of any memory resident object.
`Index`	A type representing an index into any memory resident array; a `Index` is nonnegative.
`Offset`	A type representing an offset into any memory resident array; a `Offset` may be negative.

System Types¶

Type	Description
`RegProcedure`	An Object Identifier type representing a function with arguments, per PostgreSQL's ADTs.
`TransactionId`	A 32-bit unsigned integer type representing a unique identifier per transaction.
`LocalTransactionId`	A 32-bit unsigned integer type representing a unique identifier per local transaction.
`SubTransactionId`	A 32-bit unsigned integer type representing a unique identifier per subtransaction.
`MultiXactId`	A 32-bit unsigned integer type representing a unique identifier per multixact (i.e., Row Locking by Multiple Transactions).
`MultiXactOffset`	A 32-bit unsigned integer type representing a unique offset to distinguish each transaction within a multixact.
`CommandId`	A 32-bit unsigned integer type representing a INSERT/DELETE ordering within a transaction.
`Name`	A C-string null-padded to exactly `NAMEDATALEN` bytes representing a Name; the `char*` value is accessible through `#define NameStr(name)`.

System Method Macros¶

Macro	Description
[`bool`] `BoolIsValid()` [`boolean`] `boolean`	Checks if `boolean` is a valid Boolean.
[`bool`] `PointerIsValid()` [`const void*`] `pointer`	Checks if `pointer` is a valid pointer.
[`bool`] `OidIsValid()` [`Oid`] `objectId`	Checks if `objectId` is a valid Object Identifier.
[`bool`] `RegProcedureIsValid()` [`RegProcedure`] `p`	Checks if `p` is a valid procedure.
[`bool`] `PointerIsAligned()` [`uintptr_t`] `pointer`, [Identifier] `type`	Checks if `pointer` is properly aligned to point to `type`.
[`void`] `OffsetToPointer()`* [`void*`] `base`, [`uint32`] `offset`	Offsets `base` by `offset`.

Offset, Length, and Alignment Method Macros¶

Macro	Description
[`Offset`] `offsetof()` [Identifier] `type`, [Identifier] `field`	Returns the offset of a structure/union field within that structure/union.
[`Size`] `lengthof()` [`_ ## *`] `array`	Returns the number of elements in an array.
[`Size`] `SHORTALIGN()` [`Size`] `LEN`	Align `LEN` to fit `short = 2?`-byte values.
[`Size`] `INTALIGN()` [`Size`] `LEN`	Align `LEN` to fit `int = 4?`-byte values.
[`Size`] `LONGALIGN()` [`Size`] `LEN`	Align `LEN` to fit `long = 4?`-byte values.
[`Size`] `DOUBLEALIGN()` [`Size`] `LEN`	Align `LEN` to fit `double = 8?`-byte values.
[`Size`] `MAXALIGN()` [`Size`] `LEN`	Align `LEN` to fit `MAXIMUM_ALIGNOF = 8?`-byte values.
[`Size`] `BUFFERALIGN()` [`Size`] `LEN`	Align `LEN` to fit `ALIGNOF_BUFFER = 32?`-byte values.
[`Size`] `CACHELINEALIGN()` [`Size`] `LEN`	Align `LEN` to fit `PG_CACHE_LINE_SIZE = 128?`-byte values.
[`Size`] `SHORTALIGN_DOWN()` [`Size`] `LEN`	Align `LEN` to fit `short = 2?`-byte values, by rounding down.
[`Size`] `INTALIGN_DOWN()` [`Size`] `LEN`	Align `LEN` to fit `int = 4?`-byte values, by rounding down.
[`Size`] `LONGALIGN_DOWN()` [`Size`] `LEN`	Align `LEN` to fit `long = 4?`-byte values, by rounding down.
[`Size`] `DOUBLEALIGN_DOWN()` [`Size`] `LEN`	Align `LEN` to fit `double = 8?`-byte values, by rounding down.
[`Size`] `MAXALIGN_DOWN()` [`Size`] `LEN`	Align `LEN` to fit `MAXIMUM_ALIGNOF = 8?`-byte values, by rounding down.
[`Size`] `BUFFERALIGN_DOWN()` [`Size`] `LEN`	Align `LEN` to fit `ALIGNOF_BUFFER = 32?`-byte values, by rounding down.

Assertions¶

Macro	Description
[Trap] `Assert()` [Scalar Expression] `condition`	A run-time general assertion; this assertion creates a trap with `errorType = \"FailedAssertion\"`.
[Trap] `AssertMacro()` [Macro] `p`	A run-time macro assertion; this assertion creates a trap with `errorType = \"FailedAssertion\"`.
[Trap] `AssertArg()` [Scalar Expression] `condition`	A run-time argument assertion; this assertion creates a trap with `errorType = \"BadArgument\"`.
[Trap] `AssertState()` [Scalar Expression] `condition`	A run-time state assertion; this assertion creates a trap with `errorType = \"BadState\"`.
[Trap] `AssertPointerAlignment()` [`Pointer`] `ptr`, [`uintptr_t`] `bndr`	A run-time assertion that checks that `ptr` is `bndr` aligned; this assertion creates a trap with `errorType = \"UnalignedPointer\"`.
[Compiler Error] `StaticAssertStmt()` [Scalar Expression] `condition`, [String Literal] `errmessage`	A compile-time assertion statement.
[Compiler Error] `StaticAssertExpr()` [Scalar Expression] `condition`, [String Literal] `errmessage`	A compile-time assertion expression.
[Compiler Error] `AssertVariableIsOfType()` [Identifier] `varname`, [Identifier] `typename`	A compile-time assertion statement that checks that a variable has the specified type.
[Compiler Error] `AssertVariableIsOfTypeMacro()` [Identifier] `varname`, [Identifier] `typename`	A compile-time assertion expression that checks that a variable has the specified type.

General Macros¶

Macro	Description
[Number] `Max()` [Number] `x`, [Number] `y`	Returns the maximum of two numbers.
[Number] `Min()` [Number] `x`, [Number] `y`	Returns the minimum of two numbers.
[Number] `Abs()` [Number] `x`	Return the absolute value of the argument.
`StrNCpy()` [`Pointer`] `dst`, [`Pointer`] `src`, [`Size`] `len`	See `strncpy()`; this method macro guarantees that the result string will be null-terminated.
`MemSet()` [`Pointer`] `start`, [`bits8`] `val`, [`Size`] `len`	See `memset()`; this method macro is faster than its standard library counterpart.
`MemSetAligned()` [`Pointer`] `start`, [`bits8`] `val`, [`Size`] `len`	See `memset()`; this method macro omits the test to see if `start` is word-aligned.
[`bool`] `FLOAT4_FITS_IN_INT16()` [`float4`] `num`	Checks whether a 4-byte floating-point decimal fits in a 16-bit signed integer range.
[`bool`] `FLOAT4_FITS_IN_INT32()` [`float4`] `num`	Checks whether a 4-byte floating-point decimal fits in a 32-bit signed integer range.
[`bool`] `FLOAT4_FITS_IN_INT64()` [`float4`] `num`	Checks whether a 4-byte floating-point decimal fits in a 64-bit signed integer range.
[`bool`] `FLOAT8_FITS_IN_INT16()` [`float8`] `num`	Checks whether a 8-byte floating-point decimal fits in a 16-bit signed integer range.
[`bool`] `FLOAT8_FITS_IN_INT32()` [`float8`] `num`	Checks whether a 8-byte floating-point decimal fits in a 32-bit signed integer range.
[`bool`] `FLOAT8_FITS_IN_INT64()` [`float8`] `num`	Checks whether a 8-byte floating-point decimal fits in a 64-bit signed integer range.

Miscellaneous Types¶

Type	Description
`PGAlignedBlock`	A type representing an aligned `BLCKSZ`-sized buffer.
`PGAlignedXLogBlock`	A type representing an aligned `XLOG_BLCK`-sized buffer.

Server-Side: `postgres.h`¶

TOAST: The Oversized-Attribute Storage Technique.

Includes¶

Variable-Length Data Types¶

Type	Description
`varlena`	The variable-length type inherited by all TOAST-able types.
`varattrib_4b`	A variable-length type representing the 4-byte length header of a `varlena` object that may have been TOASTed.
`varattrib_1b`	A variable-length type representing the 1-byte length header of a `varlena` object that may have been TOASTed.
`varattrib_1b_e`	A variable-length type representing the 1-byte length header, with an additional identifying tag byte, of a `varlena` object that may have been TOASTed.
`bytea`	A variable-length type representing a byte array.
`text`	A variable-length type representing a SQL `TEXT` type.
`BpChar`	A variable-length type representing a SQL `CHAR(n)` type.
`VarChar`	A variable-length type representing a SQL `VARCHAR(n)` type.

Variable-Length Constant Macros¶

Macro	Description
`VARHDRSZ`	The header size of a `varlena`.
`VARHDRSZ_SHORT`	The header size of a `varattrib_1b`.
`VARHDRSZ_EXTERNAL`	The header size of a `varattrib_1b_e`.

Aligned Variable-Length Method Macros¶

Macro	Description
[`char`] `VARDATA()`* [`varattrib_4b*`] `PTR`	Returns a pointer to the start of `varlena` 4-byte aligned data.
[`uint32`] `VARSIZE()` [`varattrib_4b*`] `PTR`	Returns the size, in bytes, of `varlena` 4-byte aligned data.
[`char`] `VARDATA_SHORT()`* [`varattrib_1b*`] `PTR`	Returns a pointer to the start of `varlena` 1-byte aligned data.
[`uint32`] `VARSIZE_SHORT()` [`varattrib_1b*`] `PTR`	Returns the size, in bytes, of `varlena` 1-byte aligned data.
[`vartag_external`] `VARTAG_EXTERNAL()` [`varattrib_1b_e`] `PTR`	Returns the type tag of an external TOAST Pointer.
[`char`] `VARDATA_EXTERNAL()`* [`varattrib_1b_e`] `PTR`	Returns a pointer to the start of an external TOAST Pointer.
[`uint32`] `VARSIZE_EXTERNAL()` [`varattrib_1b_e`] `PTR`	Returns the size, in bytes, of an external TOAST Pointer.
[`bool`] `VARATT_IS_EXTERNAL()` [`varattrib_1b_e`] `PTR`	Checks whether a `varlena` is an external TOAST Pointer.
[`bool`] `VARATT_IS_EXTERNAL_ONDISK()` [`varattrib_1b_e`] `PTR`	Checks whether a `varlena` is an external TOAST Pointer to on-disk data.
[`bool`] `VARATT_IS_EXTERNAL_INDIRECT()` [`varattrib_1b_e`] `PTR`	Checks whether a `varlena` is an external TOAST Pointer to in-memory, indirect data.
[`bool`] `VARATT_IS_EXTERNAL_EXPANDED_RO()` [`varattrib_1b_e`] `PTR`	Checks whether a `varlena` is an external TOAST Pointer to in-memory, expanded, read-only data.
[`bool`] `VARATT_IS_EXTERNAL_EXPANDED_RW()` [`varattrib_1b_e`] `PTR`	Checks whether a `varlena` is an external TOAST Pointer to in-memory, expanded, read-write data.
[`bool`] `VARATT_IS_EXTERNAL_EXPANDED()` [`varattrib_1b_e`] `PTR`	Checks whether a `varlena` is an external TOAST Pointer to in-memory, expanded data.
[`bool`] `VARATT_IS_EXTERNAL_NON_EXPANDED()` [`varattrib_1b_e`] `PTR`	Checks whether a `varlena` is an external TOAST Pointer to in-memory, non-expanded data.
[`bool`] `VARATT_IS_COMPRESSED()` [`varattrib_ ## T*`] `PTR`	Checks whether a `varlena` is compressed.
[`bool`] `VARATT_IS_SHORT()` [`varattrib_ ## T*`] `PTR`	Checks whether a `varlena` is short.
[`bool`] `VARATT_IS_EXTENDED()` [`varattrib_ ## T*`] `PTR`	Checks whether a `varlena` can be detoasted by calling `PG_DETOAST_DATUM()`.
`SET_VARSIZE()` [`varattrib_4b*`] `PTR`, [`uint32`] `len`	Sets the size, in bytes, of `varlena` data.
`SET_VARSIZE_SHORT()` [`varattrib_1b*`] `PTR`, [`uint8`] `len`	Sets the size, in bytes, of `varlena` short data.
`SET_VARSIZE_COMPRESSED()` [`varattrib_4b*`] `PTR`, [`uint32`] `len`	Sets the size, in bytes, of `varlena` compressed data.

Oblivious Variable-Length Method Macros¶

Macro	Description
[`char`] `VARDATA_ANY()`* [`varattrib_ ## T*`] `PTR`	Returns a pointer to the start of `varlena` 4-byte or 1-byte aligned data.
[`uint32`] `VARSIZE_ANY()` [`varattrib_ ## T*`] `PTR`	Returns the size, in bytes, of `varlena` 4-byte or 1-byte aligned data.
[`uint32`] `VARSIZE_ANY_EXHDR()` [`varattrib_ ## T*`] `PTR`	Returns the size, in bytes, of `varlena` 4-byte or 1-byte aligned data, excluding the header.

Datum Types¶

Type	Description
`Datum`	A type representing a pass-by-value type or a pass-by-reference type; `typedef uintptr_t Datum`.
`NullableDatum`	A type representing an nullable `Datum`.

Datum Method Macros¶

Macro	Description
[`bool`] `DatumGetBool()` [`Datum`] `X`	Returns Boolean value of a `Datum`.
[`Datum`] `BoolGetDatum()` [`bool`] `X`	Returns the `Datum` representation for a Boolean.
[`char`] `DatumGetChar()` [`Datum`] `X`	Returns character value of a `Datum`.
[`Datum`] `CharGetDatum()` [`char`] `X`	Returns the `Datum` representation for a character.
[`Datum`] `Int8GetDatum()` [`int8`] `X`	Returns the `Datum` representation for an 8-bit integer.
[`uint8`] `DatumGetUInt8()` [`Datum`] `X`	Returns 8-bit unsigned integer value of a `Datum`.
[`Datum`] `UInt8GetDatum()` [`uint8`] `X`	Returns the `Datum` representation for an 8-bit unsigned integer.
[`int16`] `DatumGetInt16()` [`Datum`] `X`	Returns 16-bit integer value of a `Datum`.
[`Datum`] `Int16GetDatum()` [`int16`] `X`	Returns the `Datum` representation for a 16-bit integer.
[`uint16`] `DatumGetUInt16()` [`Datum`] `X`	Returns 16-bit unsigned integer value of a `Datum`.
[`Datum`] `UInt16GetDatum()` [`uint16`] `X`	Returns the `Datum` representation for a 16-bit unsigned integer.
[`int32`] `DatumGetInt32()` [`Datum`] `X`	Returns 32-bit integer value of a `Datum`.
[`Datum`] `Int32GetDatum()` [`int32`] `X`	Returns the `Datum` representation for a 32-bit integer.
[`uint32`] `DatumGetUInt32()` [`Datum`] `X`	Returns 32-bit unsigned integer value of a `Datum`.
[`Datum`] `UInt32GetDatum()` [`uint32`] `X`	Returns the `Datum` representation for a 32-bit unsigned integer.
[`Oid`] `DatumGetObjectId()` [`Datum`] `X`	Returns Object Identifier value of a `Datum`.
[`Datum`] `ObjectIdGetDatum()` [`Oid`] `X`	Returns the `Datum` representation for an Object Identifier.
[`TransactionId`] `DatumGetTransactionId()` [`Datum`] `X`	Returns Transaction Identifier value of a `Datum`.
[`Datum`] `TransactionIdGetDatum()` [`TransactionId`] `X`	Returns the `Datum` representation for a Transaction Identifier.
[`Datum`] `MultiXactIdGetDatum()` [`MultiXactId`] `X`	Returns the `Datum` representation for a MultiXact Identifier.
[`CommandId`] `DatumGetCommandId()` [`Datum`] `X`	Returns Command Identifier value of a `Datum`.
[`Datum`] `CommandIdGetDatum()` [`CommandId`] `X`	Returns the `Datum` representation for a Command Identifier.
[`Pointer`] `DatumGetPointer()` [`Datum`] `X`	Returns pointer value of a `Datum`.
[`Datum`] `PointerGetDatum()` [`Pointer`] `X`	Returns the `Datum` representation for a pointer.
[`char`] `DatumGetCString()`* [`Datum`] `X`	Returns null-terminated string value of a `Datum`.
[`Datum`] `CStringGetDatum()` [`char*`] `X`	Returns the `Datum` representation for a null-terminated string.
[`Name`] `DatumGetName()` [`Datum`] `X`	Returns name value of a `Datum`.
[`Datum`] `NameGetDatum()` [`Name`] `X`	Returns the `Datum` representation for a pass-by-reference name.
[`int64`] `DatumGetInt64()` [`Datum`] `X`	Returns 64-bit integer value of a `Datum`.
[`Datum`] `Int64GetDatum()` [`int64`] `X`	Returns the `Datum` representation for a 64-bit integer.
[`uint64`] `DatumGetUInt64()` [`Datum`] `X`	Returns 64-bit unsigned integer value of a `Datum`.
[`Datum`] `UInt64GetDatum()` [`uint64`] `X`	Returns the `Datum` representation for a 64-bit unsigned integer.
[`float4`] `DatumGetFloat4()` [`Datum`] `X`	Returns 4-byte floating-point value of a `Datum`.
[`Datum`] `Float4GetDatum()` [`float4`] `X`	Returns the `Datum` representation for a 4-byte floating-point.
[`float8`] `DatumGetFloat8()` [`Datum`] `X`	Returns 8-byte floating-point value of a `Datum`.
[`Datum`] `Float8GetDatum()` [`float8`] `X`	Returns the `Datum` representation for a 8-byte floating-point.

Client-Side: `postgres_fe.h`¶

Includes¶

Everywhere: `postgres_ext.h`¶

Includes¶

#include "pg_config_ext.h"

PostgreSQL Types¶

Type	Description
`Oid`	A type representing an Object Identifier.

General Purpose Data Structures ¶

Header Files ¶

#include "lib/binaryheap.h" - Binary Heap.
#include "lib/bipartite_match.h" - Hopcroft-Karp Maximum Cardinality Algorithm.
#include "lib/bloomfilter.h" - Probabilistic Data Structure for Set Membership.
#include "lib/dshash.h" - Dynamic Shared Memory Concurrent Hash Table.
#include "lib/hyperloglog.h" - Probabilistic Data Structure for Set Cardinality.
#include "lib/ilist.h" - Inline Linked List.
#include "lib/integerset.h" - Integer Set.
#include "lib/knapsack.h" - 0-1 Knapsack Algorithm.
#include "lib/pairingheap.h" - Pairing Heap.
#include "lib/rbtree.h" - Red-Black Tree
#include "lib/stringinfo.h" - Extensible String.
#include "lib/simplehash.h" - Macro-Generated, Simple Hash Table.

Binary Heap: `binaryheap.h`¶

Wikipedia: Binary heap.

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg);

A comparison function, which imposes a total ordering on some collection of objects.
For a max-heap, a comparison function must hold the following properties. $$ \begin{cases} a b \iff& \text{Comparator} > 0\\ a = b \iff& \text{Comparator} = 0 \end{cases} $$
For a min-heap, a comparison function must hold the following properties. $$ \begin{cases} a 0\\ a > b \iff& \text{Comparator} < 0\\ a = b \iff& \text{Comparator} = 0 \end{cases} $$

Structures¶

`binaryheap`¶

Field	Description
`int bh_size`	The current number of elements within this binary heap.
`int bh_space`	The maximum number of elements within this binary heap.
`bool bh_has_heap_property`	A flag indicating that this binary heap satisfies the heap property; this flag is used for debugging.
`binaryheap_comparator bh_compare`	The comparison function used by this binary heap to define the heap property.
`void *bh_arg`	A user-provided context argument for the comparison function.
`Datum bh_nodes[]`	The variable-length array of `Datum` elements backing this binary heap.

Methods¶

extern binaryheap *
binaryheap_allocate(
    int capacity,
    binaryheap_comparator compare,
    void *arg);

Allocates a binary heap with the specified capacity that orders its elements according to the specified comparator and argument.

Parameters

capacity - The capacity for this binary heap.

compare - The comparator that will be used to order this binary heap.

arg - The argument that will be supplied to invocations of compare.

Returns

The binary heap.

extern void
binaryheap_reset(
    binaryheap *heap);

Resets the specified binary heap, retaining its parameters from binaryheap_allocate().

Parameters

binaryheap - The binary heap upon which to invoke.

extern void
binaryheap_free(
    binaryheap *heap);

Frees the specified binary heap.

Parameters

binaryheap - The binary heap upon which to invoke.

extern void
binaryheap_add_unordered(
    binaryheap *heap,
    Datum d);

Inserts the specified Datum element into the specified binary heap, without preserving the heap property.
Time Complexity: $O(1)$
Warning: binaryheap_build() must be invoked before calling any other subsequent methods.

Parameters

binaryheap - The binary heap upon which to invoke.

d - The Datum element to add.

extern void
binaryheap_build(
    binaryheap *heap);

Builds the specified binary heap to satisfy the heap property.
Time Complexity: $O(n)$

Parameters

binaryheap - The binary heap upon which to invoke.

extern void
binaryheap_add(
    binaryheap *heap,
    Datum d);

Inserts the specified Datum element into the specified binary heap, while preserving the heap property.
Time Complexity: $O(\log n)$

Parameters

binaryheap - The binary heap upon which to invoke.

d - The Datum element to add.

extern Datum
binaryheap_first(
    binaryheap *heap);

Retrieves, but does not remove, the root Datum element of the specified binary heap.
Time Complexity: $O(1)$

Parameters

binaryheap - The binary heap upon which to invoke.

Returns

The root Datum element of the specified binary heap.

extern Datum
binaryheap_remove_first(
    binaryheap *heap);

Retrieves and removes the root Datum element of the specified binary heap.
Time Complexity: $O(\log n)$

Parameters

binaryheap - The binary heap upon which to invoke.

Returns

The root Datum element of the specified binary heap.

extern void
binaryheap_replace_first(
    binaryheap *heap,
    Datum d);

Replace the root Datum element of the specified binary heap with the specified Datum element, while preserving the heap property.
Time Complexity: $O(\log n)$

Parameters

binaryheap - The binary heap upon which to invoke.

d - The Datum element to replace with.

Macros¶

Macro	Description
[`bool`] `binaryheap_empty()` [`binaryheap *`] `h`	Checks whether `h` is empty.

Hopcroft-Karp Maximum Cardinality Algorithm: `bipartite_match.h`¶

Wikipedia: Hopcroft–Karp algorithm.

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

N/A.

Structures¶

`BipartiteMatchState`¶

Field	Description
`int u_size`	Input State: The cardinality of the nodes $U$, numbered $\{1, ..., \lvert{U}\rvert\}$.
`int v_size`	Input State: The cardinality of the nodes $V$, numbered $\{1, ..., \lvert{V}\rvert\}$.
`short **adjacency`	Input State: The adjacency list of $U \to W \subseteq \mathcal{P}(V)$.
`int matching`	Output State: The cardinality of the matching.
`short *pair_uv`	Output State: Pairs of $U \to V$.
`short *pair_vu`	Output State: Pairs of $V \to U$.

Methods¶

extern BipartiteMatchState *
BipartiteMatch(
    int u_size,
    int v_size,
    short **adjacency);

Computes the maximum cardinality matching for the specified graph.

Parameters

u_size - The cardinality of the nodes $U$, numbered $\{1, ..., \lvert{U}\rvert\}$.

v_size - The cardinality of the nodes $V$, numbered $\{1, ..., \lvert{V}\rvert\}$.

adjacency - The adjacency list of $U \to W \subseteq \mathcal{P}(V)$.

Returns

The matching of the specified graph, encapsulated by BipartiteMatchState.

extern void
BipartiteMatchFree(
    BipartiteMatchState *state);

Frees the state returned by BipartiteMatch().

Parameters

state - The state upon which to invoke.

Macros¶

N/A.

Bloom Filter: `bloomfilter.h`¶

Wikipedia: Bloom filter.

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

N/A.

Structures¶

`bloom_filter`¶

Field	Description
`int k_hash_funcs`	The number of hash functions used by this Bloom filter.
`uint64 seed`	The seed for the hash functions used by this Bloom filter.
`uint64 m`	The number of bits backing this Bloom filter.
`unsigned char bitset[]`	The variable-length, byte array backing this Bloom filter.

Methods¶

extern bloom_filter *
bloom_create(
    int64 total_elems,
    int bloom_work_mem,
    uint64 seed);

Allocates a Bloom filter with an expected false positive rate of ~2% relative to the specified total number of elements and the specified working memory limit, using the specified seed for its hash functions.

Parameters

total_elems - The total number of unique elements expected to be added to this Bloom filter.

bloom_work_mem - The limit of working memory available for this Bloom filter, in KBs.

seed - The seed for the hash functions used by this Bloom filter.

Returns

The Bloom filter.

extern void
bloom_free(
    bloom_filter *filter);

Frees the specified Bloom filter.

Parameters

filter - The Bloom filter upon which to invoke.

extern void
bloom_add_element(
    bloom_filter *filter,
    unsigned char *elem,
    size_t len);

Adds the specified element into the specified Bloom filter.

Parameters

filter - The Bloom filter upon which to invoke.

elem - The element represented as a byte array.

len - The number of bytes representing the element.

extern bool
bloom_lacks_element(
    bloom_filter *filter,
    unsigned char *elem,
    size_t len);

Returns true for a true negative if the element is definitely not in the specified Bloom filter. Otherwise, returns false for a true positive or a false positive if the element is probably in the specified Bloom filter.

Parameters

filter - The Bloom filter upon which to invoke.

elem - The element represented as a byte array.

len - The number of bytes representing the element.

Returns

true for a true negative.

false for a true positive or a false positive.

extern double
bloom_prop_bits_set(
    bloom_filter *filter);

Calculates the proportion of set bits to unset bits in the specified Bloom filter.

Parameters

filter - The Bloom filter upon which to invoke.

Returns

The proportion of set bits to unset bits.

Macros¶

N/A.

Dynamic Shared Memory Concurrent Hash Table: `dshash.h`¶

Wikipedia: Concurrent hash table.

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

typedef struct dshash_table dshash_table;

A dynamic shared memory concurrent hash table.

typedef dsa_pointer dshash_table_handle;

A handle for a dshash_table which can be shared with other processes.

typedef uint32 dshash_hash;

A type representing the hash values used in a dshash_table.

typedef int (*dshash_compare_function) (const void *a, const void *b, size_t size, void *arg);

A comparison function, which imposes a total ordering on some collection of keys.
A comparison function must hold the following properties. $$ \begin{cases} a b \iff& \text{Comparator} > 0\\ a = b \iff& \text{Comparator} = 0 \end{cases} $$

typedef dshash_hash (*dshash_hash_function) (const void *v, size_t size, void *arg);

A hash function, which computes the hash values of keys.

Structures¶

`dshash_parameters`¶

Field	Description
`size_t key_size`	The preamble size, in bytes, of a key.
`size_t entry_size`	The total size, in bytes, of an entry.
`dshash_compare_function compare_function`	The comparison function of this concurrent hash table.
`dshash_hash_function hash_function`	The hash function of this concurrent hash table.
`int tranche_id`	The `tranche_id` for /src/include/storage/lwlock.h's `LWLock`.

Methods¶

extern dshash_table *
dshash_create(
    dsa_area *area,
    const dshash_parameters *params,
    void *arg);

Creates a concurrent hash table backed by the specified Dynamic Shared Area, with the specified parameters and argument.

Parameters

area - The Dynamic Shared Area backing this concurrent hash table.

params - The parameters to configure this concurrent hash table.

arg - The argument that will be supplied to invocations of compare_function and hash_function.

Returns

The concurrent hash table.

extern dshash_table *
dshash_attach(
    dsa_area *area,
    const dshash_parameters *params,
    dshash_table_handle handle,
    void *arg);

Attach this process to an existing concurrent hash table backed by the specified Dynamic Shared Area, with the specified parameters and argument, using the specified handle.

Parameters

area - The Dynamic Shared Area backing the existing concurrent hash table.

params - The parameters to configure the existing concurrent hash table.

handle - The handle to the existing concurrent hash table.

arg - The argument that will be supplied to invocations of compare_function and hash_function.

Returns

The concurrent hash table.

extern void
dshash_detach(
    dshash_table *hash_table);

Detach this process from the existing specified concurrent hash table.
Warning: This method frees all process-local memory associated with the concurrent hash table. Call dshash_destroy() to release shared memory back to the concurrent hash table's Dynamic Shared Area.

Parameters

hash_table - The concurrent hash table upon which to invoke.

extern void
dshash_destroy(
    dshash_table *hash_table);

Destroys the specified concurrent hash table.
Warning: This method releases all shared memory acquired by the concurrent hash table from its Dynamic Shared Area. Call dshash_detach() on all processes attached to the concurrent hash table before calling this method.

Parameters

hash_table - The concurrent hash table upon which to invoke.

extern dshash_table_handle
dshash_get_hash_table_handle(
    dshash_table *hash_table);

Returns a handle that can be used by other processes to attach to the specified concurrent hash table.

Parameters

hash_table - The concurrent hash table upon which to invoke.

Returns

A handle to the specified concurrent hash table.

extern void *
dshash_find(
    dshash_table *hash_table,
    const void *key,
    bool exclusive);

Returns a pointer to an entry if one can be found with the specified key.
Warning: The entry is locked, per the specified exclusivity, and it must be released by calling dshash_release_lock().

Parameters

hash_table - The concurrent hash table upon which to invoke.

key - The key for which an entry should be found.

exclusive - A flag indicating whether the caller requires a shared or an exclusive lock on the entry.

Returns

A pointer to an entry if one can be found with the specified key.

NULL if no entry can be found with the specified key.

extern void *
dshash_find_or_insert(
    dshash_table *hash_table,
    const void *key,
    bool *found);

Returns a pointer to an exclusively locked entry which must be released with dshash_release_lock(). If the key is found, then found is set to true and a pointer to the existing entry is returned. If the key is not found, then found is set to false and a pointer to a newly created entry is returned.

Parameters

hash_table - The concurrent hash table upon which to invoke.

key - The key for which an entry should be found or inserted.

found - An output flag indicating whether the returned pointer references an existing or newly created entry.

Returns

A pointer to an existing or newly created entry.

extern bool
dshash_delete_key(
    dshash_table *hash_table,
    const void *key);

Removes an entry by the specified key.

Parameters

hash_table - The concurrent hash table upon which to invoke.

key - The key for which an entry should be found and delete.

Returns

true if the specified key was found and deleted.

false if the specified key was not found and delete.

extern void
dshash_delete_entry(
    dshash_table *hash_table,
    void *entry);

Removes the specified entry.
Warning: The specified entry must have been obtained by calling dshash_find() or dshash_find_or_insert().

Parameters

hash_table - The concurrent hash table upon which to invoke.

entry - The entry which should be deleted.

extern void
dshash_release_lock(
    dshash_table *hash_table,
    void *entry);

Releases the lock held for the specified entry.
Warning: The specified entry must have been obtained by calling dshash_find() or dshash_find_or_insert().

Parameters

hash_table - The concurrent hash table upon which to invoke.

entry - The entry which should be released.

extern int
dshash_memcmp(
    const void *a,
    const void *b,
    size_t size,
    void *arg);

A default comparison function using memcmp().

extern dshash_hash
dshash_memhash(
    const void *v,
    size_t size,
    void *arg);

A default hash function using tag_hash().

Macros¶

N/A.

HyperLogLog: `hyperloglog.h`¶

Wikipedia: HyperLogLog.

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

N/A.

Structures¶

`hyperLogLogState`¶

Field	Description
`uint8 registerWidth`	The width, in bits, of registers used in this HyperLogLog.
`Size nRegisters`	The number of registers used in this HyperLogLog.
`double alphaMM`	The $\alpha_{m}$ constant used to correct systematic systematic multiplicative bias in this HyperLogLog.
`uint8 *hashesArr`	The variable-length array of hashes backing this HyperLogLog.
`Size arrSize`	The number of hashes backing this HyperLogLog.

Methods¶

extern void
initHyperLogLog(
    hyperLogLogState *cState,
    uint8 bwidth);

Initializes a HyperLogLog with the specified register bit width.

Parameters

cState - The HyperLogLog upon which to invoke.

bwidth - The width, in bits, of registers used in the HyperLogLog.

extern void
initHyperLogLogError(
    hyperLogLogState *cState,
    double error);

Initializes a HyperLogLog with the specified error rate.

Parameters

cState - The HyperLogLog upon which to invoke.

error - The error rate from which to calculate the register bit width.

extern void
freeHyperLogLog(
    hyperLogLogState *cState);

Frees the specified HyperLogLog.
Warning: This method frees resources internal to hyperLogLogState, not hyperLogLogState itself.

Parameters

cState - The HyperLogLog upon which to invoke.

extern void
addHyperLogLog(
    hyperLogLogState *cState,
    uint32 hash);

Adds the specified hash value into the specified HyperLogLog.

Parameters

cState - The HyperLogLog upon which to invoke.

hash - The hash value of an element.

extern double
estimateHyperLogLog(
    hyperLogLogState *cState);

Estimates the cardinality of the specified HyperLogLog.

Parameters

cState - The HyperLogLog upon which to invoke.

Returns

An estimate of the cardinality of the specified HyperLogLog.

Macros¶

N/A.

Inline Linked List: `ilist.h`¶

Wikipedia: Linked list.

Working with Doubly Linked Lists¶

To create a doubly linked list, inline a dlist_node in a structure.
To interface with the doubly linked list, call the various dlist_ ## T methods.
To access the encapsulating structure associated with a specified dlist_node, call the dlist_container() method macro.

Working with Singly Linked Lists¶

To create a singly linked list, inline a slist_node in a structure.
To interface with the singly linked list, call the various slist_ ## T methods.
To access the encapsulating structure associated with a specified slist_node, call the slist_container() method macro.

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

N/A.

Structures¶

`dlist_node` - Doubly Linked List Node¶

Field	Description
`dlist_node *prev`	A pointer to the previous node in a doubly linked list.
`dlist_node *next`	A pointer to the next node in a doubly linked list.

`dlist_head` - Doubly Linked List Head¶

Field	Description
`dlist_node *head`	A pointer to the head node in a circular, doubly linked list.

`dlist_iter` - Doubly Linked List Immutable Iterator¶

Field	Description
`dlist_node *cur`	A pointer to the current node in an immutable iterator of a circular, doubly linked list.
`dlist_node *end`	A pointer to the last node in an immutable iterator of a circular, doubly linked list.

`dlist_mutable_iter` - Doubly Linked List Mutable Iterator¶

Field	Description
`dlist_node *cur`	A pointer to the current node in a mutable iterator of a circular, doubly linked list.
`dlist_node *next`	A pointer to the next node in a mutable iterator of a circular, doubly linked list.
`dlist_node *end`	A pointer to the last node in a mutable iterator of a circular, doubly linked list.

`slist_node` - Singly Linked List Node¶

Field	Description
`slist_node *next`	A pointer to the next node in a singly linked list.

`slist_head` - Singly Linked List Head¶

Field	Description
`slist_node *head`	A pointer to the head node in a singly linked list.

`slist_iter` - Singly Linked List Immutable Iterator¶

Field	Description
`slist_node *cur`	A pointer to the current node in an immutable iterator of a singly linked list.

`slist_mutable_iter` - Singly Linked List Mutable Iterator¶

Field	Description
`slist_node *cur`	A pointer to the current node in a mutable iterator of a singly linked list.
`slist_node *next`	A pointer to the next node in a mutable iterator of a singly linked list.
`slist_node *prev`	A pointer to the previous node in a mutable iterator of a singly linked list.

Methods¶

static inline void
dlist_init(
    dlist_head *head);

Initialize the doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

static inline bool
dlist_is_empty(
    dlist_head *head);

Checks if the specified doubly linked list is empty.

Parameters

head - The doubly linked list's head upon which to invoke.

Returns

true if the doubly linked is empty.

false if the doubly linked is not empty.

static inline void
dlist_push_head(
    dlist_head *head,
    dlist_node *node);

Prepends the specified doubly linked list node to the start of the specified doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

node - The doubly linked list node to prepend.

static inline void
dlist_push_tail(
    dlist_head *head,
    dlist_node *node);

Appends the specified doubly linked list node to the end of the specified doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

node - The doubly linked list node to append.

static inline void
dlist_insert_after(
    dlist_node *after,
    dlist_node *node);

Appends the specified doubly linked list node after the specified doubly linked list node.

Parameters

after - The doubly linked list node from which to append after.

node - The doubly linked list node to append.

static inline void
dlist_insert_before(
    dlist_node *before,
    dlist_node *node);

Prepends the specified doubly linked list node before the specified doubly linked list node.

Parameters

before - The doubly linked list node from which to prepend before.

node - The doubly linked list node to prepend.

static inline void
dlist_delete(
    dlist_node *node);

Delete the specified doubly linked list node.

Parameters

node - The doubly linked list node to delete.

static inline dlist_node *
dlist_pop_head_node(
    dlist_head *head);

Retrieves and removes the head of the specified doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

Returns

The doubly linked list's head.

static inline void
dlist_move_head(
    dlist_head *head,
    dlist_node *node);

Move the specified doubly linked list node to the head of the specified doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

node - The doubly linked list node to move.

static inline bool
dlist_has_next(
    dlist_head *head,
    dlist_node *node);

Checks whether the specified doubly linked list node has a following node in the specified doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

node - The doubly linked list node to check for a following node.

Returns

true if the doubly linked list node has a following node.

false if the doubly linked list node does not have a following node.

static inline bool
dlist_has_prev(
    dlist_head *head,
    dlist_node *node);

Checks whether the specified doubly linked list node has a preceding node in the specified doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

node - The doubly linked list node to check for a preceding node.

Returns

true if the doubly linked list node has a preceding node.

false if the doubly linked list node does not have a preceding node.

static inline dlist_node *
dlist_next_node(
    dlist_head *head,
    dlist_node *node);

Returns the node following the specified doubly linked list node.

Parameters

head - The doubly linked list's head upon which to invoke.

node - The doubly linked list node from which a following node should be returned.

Returns

The node following the specified doubly linked list node.

static inline dlist_node *
dlist_prev_node(
    dlist_head *head,
    dlist_node *node);

Returns the node preceding the specified doubly linked list node.

Parameters

head - The doubly linked list's head upon which to invoke.

node - The doubly linked list node from which a preceding node should be returned.

Returns

The node preceding the specified doubly linked list node.

static inline dlist_node *
dlist_head_node(
    dlist_head *head);

Returns the first doubly linked list node in the specified doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

Returns

The first doubly linked list node in the specified doubly linked list.

static inline dlist_node *
dlist_tail_node(
    dlist_head *head);

Returns the last doubly linked list node in the specified doubly linked list.

Parameters

head - The doubly linked list's head upon which to invoke.

Returns

The last doubly linked list node in the specified doubly linked list.

static inline void
slist_init(
    slist_head *head);

Initialize the singly linked list.

Parameters

head - The singly linked list's head upon which to invoke.

static inline bool
slist_is_empty(
    slist_head *head);

Checks if the specified singly linked list is empty.

Parameters

head - The singly linked list's head upon which to invoke.

Returns

true if the singly linked is empty.

false if the singly linked is not empty.

static inline void
slist_push_head(
    slist_head *head,
    slist_node *node);

Prepends the specified singly linked list node to the start of the specified singly linked list.

Parameters

head - The singly linked list's head upon which to invoke.

node - The singly linked list node to prepend.

static inline void
slist_insert_after(
    slist_node *after,
    slist_node *node);

Appends the specified singly linked list node after the specified singly linked list node.

Parameters

after - The singly linked list node from which to append after.

node - The singly linked list node to append.

extern void
slist_delete(
    slist_head *head,
    slist_node *node);

Delete the specified singly linked list node from the specified singly linked list node.
Time Complexity: $O(n)$

Parameters

head - The singly linked list's head upon which to invoke.

node - The singly linked list node to delete.

static inline slist_node *
slist_pop_head_node(
    slist_head *head);

Retrieves and removes the head of the specified singly linked list.

Parameters

head - The singly linked list's head upon which to invoke.

Returns

The singly linked list's head..

static inline bool
slist_has_next(
    slist_head *head,
    slist_node *node);

Checks whether the specified singly linked list node has a following node in the specified singly linked list.

Parameters

head - The singly linked list's head upon which to invoke.

node - The singly linked list node to check for a following node.

Returns

true if the singly linked list node has a following node.

false if the singly linked list node does not have a following node.

static inline slist_node *
slist_next_node(
    slist_head *head,
    slist_node *node);

Returns the node following the specified singly linked list node.

Parameters

head - The singly linked list's head upon which to invoke.

node - The singly linked list node from which a following node should be returned.

Returns

The node following the specified singly linked list node.

static inline slist_node *
slist_head_node(
    slist_head *head);

Returns the first singly linked list node in the specified singly linked list.

Parameters

head - The singly linked list's head upon which to invoke.

Returns

The first singly linked list node in the specified singly linked list.

static inline void
slist_delete_current(
    slist_mutable_iter *iter);

Delete the current singly linked list node to which the specified singly linked list mutable iterator points.

Parameters

iter - The singly linked list mutable iterator.

Macros¶

Macro	Description
[`dlist_head`] `DLIST_STATIC_INIT()` [`dlist_head`] `name`	Statically initialize `name` as a doubly linked list.
[`type `] `dlist_container()`* [Identifier] `type`, [Identifier] `membername`, [`dlist_node *`] `ptr`	Return the encapsulating structure of `type` where `membername` is the `dlist_node` pointed by `ptr`.
[`type `] `dlist_head_element()`* [Identifier] `type`, [Identifier] `membername`, [`dlist_head *`] `lhead`	Returns a pointer to the first element (the encapsulating structure of `type` where `membername` is the `dlist_node`) in the doubly linked list.
[`type `] `dlist_tail_element()`* [Identifier] `type`, [Identifier] `membername`, [`dlist_head *`] `lhead`	Returns a pointer to the last element (the encapsulating structure of `type` where `membername` is the `dlist_node`) in the doubly linked list.
[`void`] `dlist_foreach()` [`dlist_iter`] `iter`, [`dlist_head *`] `lhead`	Forward through the doubly linked list pointed by `lhead` while storing state in `iter` and disallowing mutations.
[`void`] `dlist_foreach_modify()` [`dlist_mutable_iter`] `iter`, [`dlist_head *`] `lhead`	Forward through the doubly linked list pointed by `lhead` while storing state in `iter` and allowing mutations.
[`void`] `dlist_reverse_foreach()` [`dlist_iter`] `iter`, [`dlist_head *`] `lhead`	Reverse through the doubly linked list pointed by `lhead` while storing state in `iter` and disallowing mutations.
[`slist_head`] `SLIST_STATIC_INIT()` [`slist_head`] `name`	Statically initialize `name` as a singly linked list.
[`type `] `slist_container()`* [Identifier] `type`, [Identifier] `membername`, [`slist_node *`] `ptr`	Return the encapsulating structure of `type` where `membername` is the `slist_node` pointed by `ptr`.
[`type `] `slist_head_element()`* [Identifier] `type`, [Identifier] `membername`, [`slist_head *`] `lhead`	eturns a pointer to the first element (the encapsulating structure of `type` where `membername` is the `slist_node`) in the singly linked list.
[`void`] `slist_foreach()` [`slist_iter`] `iter`, [`slist_head *`] `lhead`	Forward through the singly linked list pointed by `lhead` while storing state in `iter` and disallowing mutations.
[`void`] `slist_foreach_modify()` [`slist_mutable_iter`] `iter`, [`slist_head *`] `lhead`	Forward through the singly linked list pointed by `lhead` while storing state in `iter` and allowing mutations.

Integer Set: `integerset.h`¶

Wikipedia: Set (abstract data type)&oldid=958494281).

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

typedef struct IntegerSet IntegerSet;

A set of integers.

Structures¶

N/A.

Methods¶

extern IntegerSet *
intset_create(void);

Allocate an empty integer set.

Returns

The integer set.

extern void
intset_add_member(
    IntegerSet *intset,
    uint64 x);

Inserts the specified integer into the specified integer set.
Warning: The integers inserted into the integer set must be monotonically increasing.
Warning: intset_begin_iterate() cannot be called before calling this method.

Parameters

intset - The integer set upon which to invoke.

x - The integer to insert.

extern bool
intset_is_member(
    IntegerSet *intset,
    uint64 x);

Checks whether the specified integer is a member of the specified integer set.

Parameters

intset - The integer set upon which to invoke.

x - The integer to check.

Returns

true if the specified integer is a member.

false if the specified integer is not a member.

extern uint64
intset_num_entries(
    IntegerSet *intset);

Returns the number of entries in the specified integer set.

Parameters

intset - The integer set upon which to invoke.

Returns

The number of entries in the specified integer set.

extern uint64
intset_memory_usage(
    IntegerSet *intset);

Returns the amount of memory, in bytes, allocated by the specified integer set.

Parameters

intset - The integer set upon which to invoke.

Returns

The amount of memory, in bytes, allocated by the specified integer set.

extern void
intset_begin_iterate(
    IntegerSet *intset);

Initializes an in-order scan of all the elements in the specified integer set.

Parameters

intset - The integer set upon which to invoke.

extern bool
intset_iterate_next(
    IntegerSet *intset,
    uint64 *next);

Seek the next integer in the integer set.
Warning: Call intset_begin_iterate() before calling this method.

Parameters

intset - The integer set upon which to invoke.

next - A pointer to an integer which will be updated with the next integer in the integer set.

Returns

true if there are remaining elements in the specified integer set.

false if there are no remaining elements in the specified integer set.

Macros¶

N/A.

0-1 Knapsack Algorithm: `knapsack.h`¶

Wikipedia: Knapsack problem.

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

N/A.

Structures¶

N/A.

Methods¶

extern Bitmapset *
DiscreteKnapsack(
    int max_weight,
    int num_items,
    int *item_weights,
    double *item_values);

Returns a bitmap of the indexes of the items chosen for the 0-1 Knapsack.

Parameters

max_weight - The maximum weight constraining the solution.

num_itmes - The number of items to consider for the solution.

item_weights - The weight of the items to minimize for the solution.

item_values - The value of the items to maximize for the solution. This parameter can be NULL; the weights will all be assumed to be 1.

Returns

A bitmap of the indexes of the items chosen for the 0-1 Knapsack.

Macros¶

N/A.

Pairing Heap: `pairingheap.h`¶

Wikipedia: Pairing heap.

Working with Pairing Heaps¶

To create a pairing heap, inline a pairingheap_node in a structure.
To interface with the pairing heap, call the various pairingheap_ ## T methods and method macros.
To access the encapsulating structure associated with a specified pairingheap_node, call the pairingheap_container() or the pairingheap_const_container() method macros.

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

typedef int (*pairingheap_comparator) (const pairingheap_node *a, const pairingheap_node *b, void *arg);

A comparison function, which imposes a total ordering on some collection of objects.
For a max-heap, a comparison function must hold the following properties. $$ \begin{cases} a b \iff& \text{Comparator} > 0\\ a = b \iff& \text{Comparator} = 0 \end{cases} $$
For a min-heap, a comparison function must hold the following properties. $$ \begin{cases} a 0\\ a > b \iff& \text{Comparator} < 0\\ a = b \iff& \text{Comparator} = 0 \end{cases} $$

Structures¶

`pairingheap_node`¶

Field	Description
`struct pairingheap_node *first_child`	The first child of this pairing heap node.
`struct pairingheap_node *next_sibling`	The next child of this pairing heap node.
`struct pairingheap_node *prev_or_parent`	The previous child or parent of this pairing heap node.

`pairingheap`¶

Field	Description
`pairingheap_comparator ph_compare`	The comparison function used by this pairing heap to define the heap property.
`void *ph_arg`	A user-provided context argument for the comparison function.
`pairingheap_node *ph_root`	The root pairing heap node of this pairing heap.

Methods¶

extern pairingheap *
pairingheap_allocate(
    pairingheap_comparator compare,
    void *arg);

Allocates a pairing heap that orders its elements according to the specified comparator and argument.

Parameters

compare - The comparator that will be used to order this pairing heap.

arg - The argument that will be supplied to invocations of compare.

Returns

The pairing heap.

extern void
pairingheap_free(
    pairingheap *heap);

Frees the specified pairing heap.

Parameters

heap - The pairing heap upon which to invoke.

extern void
pairingheap_add(
    pairingheap *heap,
    pairingheap_node *node);

Inserts the specified pairing heap node into the specified pairing heap, while preserving the heap property.
Time Complexity: $O(1)$

Parameters

heap - The pairing heap upon which to invoke.

node - The pairing heap node to insert.

extern pairingheap_node *
pairingheap_first(
    pairingheap *heap);

Retrieves, but does not remove, the root pairing heap node of the specified pairing heap.
Time Complexity: $O(1)$

Parameters

heap - The pairing heap upon which to invoke.

Returns

The root pairing heap node of the specified pairing heap.

extern pairingheap_node *
pairingheap_remove_first(
    pairingheap *heap);

Retrieves and removes the root pairing node of the specified pairing heap.
Time Complexity: $O(\log n)$

Parameters

heap - The pairing heap upon which to invoke.

Returns

The root pairing heap node of the specified pairing heap.

extern void
pairingheap_remove(
    pairingheap *heap,
    pairingheap_node *node);

Removes the specified pairing heap node from the specified pairing heap.
Time Complexity: $O(\log n)$

Parameters

heap - The pairing heap upon which to invoke.

node - The pairing heap node to remove.

Macros¶

Macro	Description
[`type `] `pairingheap_container()`* [Identifier] `type`, [Identifier] `membername`, [`pairingheap_node *`] `ptr`	Return the encapsulating structure of type where `membername` is the `pairingheap_node` pointed by `ptr`.
[`const type `] `pairingheap_const_container()`* [Identifier] `type`, [Identifier] `membername`, [`const pairingheap_node *`] `ptr`	Return the encapsulating structure of type where `membername` is the `pairingheap_node` pointed by `ptr`.
[`void`] `pairingheap_reset()` [`pairingheap *`] `h`	Resets `h`, retaining its parameters from `pairingheap_allocate()`.
[`bool`] `pairingheap_is_empty()` [`pairingheap *`] `h`	Checks whether `h` is empty.
[`bool`] `pairingheap_is_singular()` [`pairingheap *`] `h`	Checks whether `h` has exactly one node.

Red-Black Tree: `rbtree.h`¶

Wikipedia: Red–black tree.

Working with Red-Black Trees¶

To create a red-black tree node, inline a RBTNode as the FIRST FIELD in a structure.
To interface with the red-black tree, call the various rbt_ ## T methods.

Constants¶

N/A.

Enumerations¶

`RBTOrderControl`¶

Enum	Description
`LeftRightWalk`	An in-order tree iteration ordering: Left Child, Node, Right Child.
`RightLeftWalk`	A reverse in-order tree iteration ordering: Right Child, Node, Left Child.

Types¶

typedef struct RBTree RBTree;

A red-black binary search tree.

typedef int (*rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg);

A comparison function, which imposes a total ordering on some collection of keys.
A comparison function must hold the following properties. $$ \begin{cases} a b \iff& \text{Comparator} > 0\\ a = b \iff& \text{Comparator} = 0 \end{cases} $$

typedef void (*rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg);

A combine function that merges an existing red-black tree node with a new red-black tree node.

typedef RBTNode *(*rbt_allocfunc) (void *arg);

An allocate function for a new red-black tree node.

typedef void (*rbt_freefunc) (RBTNode *x, void *arg);

A free function for an old red-black tree node.

Structures¶

`RBTNode`¶

Field	Description
`char color`	The color of this red-black tree node: Red or Black.
`struct RBTNode *left`	The left child of this red-black tree node.
`struct RBTNode *right`	The right child of this red-black tree node.
`struct RBTNode *parent`	The parent of this red-black tree node.

`RBTreeIterator`¶

Field	Description
`RBTree *rbt`	The red-black tree backing this iterator.
`RBTNode (iterate) (RBTreeIterator *iter)`	The iteration function used by this iterator.
`RBTNode *last_visited`	A pointer to the last visited red-black tree node.
`bool is_over`	A flag indicating whether the iterator is finished.

Methods¶

extern RBTree *
rbt_create(
    Size node_size,
    rbt_comparator comparator,
    rbt_combiner combiner,
    rbt_allocfunc allocfunc,
    rbt_freefunc freefunc,
    void *arg);

Allocates an empty red-black tree with the specified comparator, combiner, allocate, and free functions and argument.

Parameters

node_size - The size of the red-black tree node. It must be greater than sizeof(RBTNode).

comparator - The comparator that will be used to order this red-black tree.

combiner - The combiner that will be used to merge this red-black tree with a new red-black tree.

allocfunc - The allocate function used to allocate a new red-black tree node.

freefunc - The free function used to free an old red-black tree node.

arg - The argument that will be supplied to invocations of all the callback functions.

Returns

The red-black tree.

extern RBTNode *
rbt_find(
    RBTree *rbt,
    const RBTNode *data);

Search for the specified data in the specified red-black tree.

Parameters

rbt - The red-black tree upon which to invoke.

data - The data for which to search. The RBTNode fields do not need to be valid.

Returns

A pointer to a red-black tree node if one can be found with the specified data.

NULL if no red-black tree node can be found with the specified data.

extern RBTNode *
rbt_leftmost(
    RBTree *rbt);

Returns the leftmost (smallest) red-black tree node.

Parameters

rbt - The red-black tree upon which to invoke.

Returns

A pointer to the leftmost red-black tree node if one can be found.

NULL if no leftmost red-black tree node can be found.

extern RBTNode *
rbt_insert(
    RBTree *rbt,
    const RBTNode *data,
    bool *isNew);

Inserts the specified data into the specified red-black tree.

Parameters

rbt - The red-black tree upon which to invoke.

data - The data for which to insert. The RBTNode fields do not need to be valid.

isNew - An output flag indicating whether the returned pointer references an existing or newly created red-black tree node.

Returns

A pointer to an existing or newly created red-black tree node.

extern void
rbt_delete(
    RBTree *rbt,
    RBTNode *node);

Removes the specified red-black tree node.

Parameters

rbt - The red-black tree upon which to invoke.

node - The red-black tree node to delete.

extern void
rbt_begin_iterate(
    RBTree *rbt,
    RBTOrderControl ctrl,
    RBTreeIterator *iter);

Initializes a traversal of the specified red-black tree.

Parameters

rbt - The red-black tree upon which to invoke.

ctrl - The ordering by which the traversal should be executed.

iter - The red-black tree iterator state backing the traversal.

extern RBTNode *
rbt_iterate(
    RBTreeIterator *iter);

Returns the next red-black tree node according to the specified red-black tree iterator.

Parameters

iter - The red-black iterator state backing the traversal.

Returns

A pointer to the next red-black tree node if one can be found.

NULL if no next red-black tree node can be found.

Macros¶

N/A.

Extensible String: `stringinfo.h`¶

Wikipedia: String (computer science)&oldid=968175773).

Constants¶

N/A.

Enumerations¶

N/A.

Types¶

typedef StringInfoData *StringInfo;

A pointer type to an extensible string.

Structures¶

`StringInfoData`¶

Field	Description
`char *data`	The current buffer allocated for this extensible string.
`int len`	The current length, in bytes, of this extensible string.
`int maxLen`	The max length, in bytes, of this extensible string, currently bounded by the buffer size.
`int cursor`	An internal state used by methods related to an extensible string.

Methods¶

extern StringInfo
makeStringInfo(void);

Allocates an empty extensible string.

Returns

The extensible string.

extern void
initStringInfo(
    StringInfo str);

Initializes an undefined extensible string to be empty.

Parameters

str - The extensible string upon which to invoke.

extern void
resetStringInfo(
    StringInfo str);

Resets the specified extensible string.

Parameters

str - The extensible string upon which to invoke.

extern void
appendStringInfo(
    StringInfo str,
    const char *fmt,...) pg_attribute_printf(2, 3);

Appends the specified formatted string to the specified extensible string.
Warning: If the specified extensible string does not have enough memory, then it will allocate more memory.

Parameters

str - The extensible string upon which to invoke.

fmt, ... - An sprintf-style format string and arguments.

extern int
appendStringInfoVA(
    StringInfo str,
    const char *fmt,
    va_list args) pg_attribute_printf(2, 0);

Appends the specified formatted string to the specified extensible string.
Warning: If the specified extensible string does not have enough memory, then it will not allocate more memory.

Parameters

str - The extensible string upon which to invoke.

fmt, ... - An sprintf-style format string.

args - The arguments for the format string.

Returns

$0$ if the specified format string was appended.

$>0$ if the specified format string was not appended because of insufficient memory. The returned value is an estimate of the required additional memory.

extern void
appendStringInfoString(
    StringInfo str,
    const char *s);

Appends the specified null-terminated string to the specified extensible string.

Parameters

str - The extensible string upon which to invoke.

s - The null-terminated string to append.

extern void
appendStringInfoChar(
    StringInfo str,
    char ch);

Appends the specified character to the specified extensible string.

Parameters

str - The extensible string upon which to invoke.

ch - The character to append.

extern void
appendStringInfoSpaces(
    StringInfo str,
    int count);

Appends the specified number of spaces to the specified extensible string.

Parameters

str - The extensible string upon which to invoke.

count - The number of spaces to append.

extern void
appendBinaryStringInfo(
    StringInfo str,
    const char *data,
    int datalen);

Appends an arbitrary binary string to the specified extensible string.

Parameters

str - The extensible string upon which to invoke.

data - The arbitrary binary string to append.

datalen - The length of the arbitrary binary string.

extern void
appendBinaryStringInfoNT(
    StringInfo str,
    const char *data,
    int datalen);

Appends an arbitrary binary string to the specified extensible string.
Warning: This method does not ensure that a trailing null-byte exists.

Parameters

str - The extensible string upon which to invoke.

data - The arbitrary binary string to append.

datalen - The length of the arbitrary binary string.

extern void
enlargeStringInfo(
    StringInfo str,
    int needed);

Enlarges the specified extensible string's buffer by the specified number of bytes.

Parameters

str - The extensible string upon which to invoke.

needed - The number of bytes needed.

Macros¶

Macro	Description
[`void`] `appendStringInfoCharMacro()` [`StringInfo`] `str`, [`char`] `ch`	Appends `ch` to `str`, minimizing function calls, yet requiring multiple evaluations of `str`.

Macro-Generated, Simple Hash Table: `simplehash.h`¶

Wikipedia: Hash table.

Working with Macro-Generated, Simple Hash Tables¶

To generate a simple hash table for a specified type, declare all the relevant #define macros and the final #include "lib/simplehash.h" macro.
To interface with the simple hash table, call the various SH_PREFIX ## _T methods.

Constants¶

N/A.

Enumerations¶

`SH_PREFIX ## _status`¶

Enum	Description
`SH_PREFIX ## _EMPTY`	An internal flag indicating whether a bucket is empty.
`SH_PREFIX ## _IN_USE`	An internal flag indicating whether a bucket is in use.

Types¶

N/A.

Structures¶

`SH_PREFIX ## _hash`¶

Field	Description
`uint64 size`	The maximum number of buckets currently allocated.
`uint32 members`	The current number of buckets currently in use.
`uint32 sizemask`	An internal mask for bucket and size calculations.
`uint32 grow_threshold`	An internal threshold after which the hash table is grown.
`SH_ELEMENT_TYPE *data`	The buckets backing this hash table.
`MemoryContext ctx`	The memory context backing this hash table.
`void *private_data`	A user-defined data to be stored with this hash table.

`SH_PREFIX ## _iterator`¶

Field	Description
`uint32 cur`	An index to the current element in an immutable iterator of a hash table.
`uint32 end`	An index to the last element in an immutable iterator of a hash table.
`bool done`	A flag indicating whether the iterator is finished.

Methods¶

SH_SCOPE SH_PREFIX ## _hash *
SH_PREFIX ## _create(
    MemoryContext ctx,
    uint32 nelements,
    void *private_data);

Allocates an empty hash table with the specified initial capacity, memory context, and argument.

Parameters

ctx - The memory context backing this hash table.

nelements - The initial capacity of this hash table.

private_data - A user-defined data to be stored with this hash table.

Returns

The hash table.

SH_SCOPE void
SH_PREFIX ## _destroy(
    SH_PREFIX ## _hash *tb);

Destroys the specified hash table.

Parameters

tb - The hash table upon which to invoke.

SH_SCOPE void
SH_PREFIX ## _reset(
    SH_PREFIX ## _hash *tb);

Resets the specified hash table, retaining its parameters from SH_PREFIX ## _create().

Parameters

tb - The hash table upon which to invoke.

SH_SCOPE void
SH_PREFIX ## _grow(
    SH_PREFIX ## _hash *tb,
    uint32 newsize);

Increases the size of the specified hash table to support the specified number of buckets.

Parameters

tb - The hash table upon which to invoke.

newsize - The minimum number of buckets the hash table should support.

SH_SCOPE SH_ELEMENT_TYPE *
SH_PREFIX ## _insert(
    SH_PREFIX ## _hash *tb,
    SH_KEY_TYPE key,
    bool *found);

Inserts the specified key into the specified hash table.

Parameters

tb - The hash table upon which to invoke.

key - The key to insert.

found - An output flag indicating whether the key already exists.

Returns

A pointer to a hash table entry for the specified key.

SH_SCOPE SH_ELEMENT_TYPE *
SH_PREFIX ## _lookup(
    SH_PREFIX ## _hash *tb,
    SH_KEY_TYPE key);

Retrieves a hash table entry for the specified key.

Parameters

tb - The hash table upon which to invoke.

key - The key for which to retrieve.

Returns

A pointer to a hash table entry if one can be found with the specified key.

NULL if no hash table entry can be found with the specified key.

SH_SCOPE bool
SH_PREFIX ## _delete(
    SH_PREFIX ## _hash *tb,
    SH_KEY_TYPE key);

Removes a hash table entry by the specified key.

Parameters

tb - The hash table upon which to invoke.

key - The key for which to remove.

Returns

true if a hash table entry was deleted with the specified key.

false if a hash table entry was not deleted with the specified key.

SH_SCOPE void
SH_PREFIX ## _start_iterate(
    SH_PREFIX ## _hash *tb,
    SH_PREFIX ## _iterator *iter);

Initializes a backwards scan of the specified hash table.

Parameters

tb - The hash table upon which to invoke.

iter - The hash table iterator state backing the iteration.

SH_SCOPE void
SH_PREFIX ## _start_iterate_at(
    SH_PREFIX ## _hash *tb,
    SH_PREFIX ## _iterator *iter,
    uint32 at);

Initializes a backwards scan of the specified hash table at the specified bucket index.

Parameters

tb - The hash table upon which to invoke.

iter - The hash table iterator state backing the iteration.

at - The bucket index at which the iteration should start.

SH_SCOPE SH_ELEMENT_TYPE *
SH_PREFIX ## _iterate(
    SH_PREFIX ## _hash *tb,
    SH_PREFIX ## _iterator *iter);

Returns the next in-use bucket according to the specified hash table iterator.

Parameters

tb - The hash table upon which to invoke.

iter - The hash table iterator state backing the iteration.

Returns

A pointer to a hash table entry if one can be found.

NULL if no hash table entry can be found.

Macros¶

Macro	Description
`#define SH_USE_NONDEFAULT_ALLOCATOR`	Optional: If defined, no hash table element allocator functions are defined. Thus, the user must supply their own.
`#define SH_PREFIX`	Required: The prefix for all generated symbol names for the hash table.
`#define SH_ELEMENT_TYPE`	Required: The type of contained elements.
`#define SH_KEY_TYPE`	Required: The type of contained keys.
`#define SH_KEY`	Required: The name of the field in `SH_ELEMENT_TYPE` containing the key.
`#define SH_EQUAL(tb, a, b)`	Required: Compares the hash table keys `a` and `b`.
`#define SH_HASH_KEY(tb, key)`	Required: Generates the hash for the hash table key `key`.
`#define SH_STORE_HASH`	Optional: If defined, stores the hash of a key in the field of its associated element.
`#define SH_GET_HASH(tb, a)`	Optional: If defined, retrieves the hash of a key from the field of its associated element.
`#define SH_SCOPE`	Required: When defined, configures the scope in which function declarations reside.
`#define SH_DECLARE`	Required: When defined, hash table function prototypes and type declarations are generated.
`#define SH_DEFINE`	Required: When defined, hash table function definitions are generated.

Shared Components and Utilities ¶

Header Files ¶

Caches: /src/backend/utils/cache ¶

Header Files¶

/src/include/utils/attoptcache.h - Attribute Options Cache.
/src/include/utils/catcache.h - Low-Level Catalog Cache.
/src/include/utils/evtcache.h - Event Trigger Cache.
/src/include/utils/lsyscache.h - Convenient System Catalog Cache.
/src/include/utils/partcache.h - Partition Key Cache.
/src/include/utils/plancache.h - Plan Cache.
/src/include/utils/relcache.h - Relation Descriptor Cache.
/src/include/utils/spccache.h - Tablespace Cache.
/src/include/utils/syscache.h - System Catalog Cache.
/src/include/utils/typcache.h - Type Cache.

PostgreSQL 12¶

Table of Contents¶

Jupyter¶

Documentation¶

Presentations¶

Top-Level Directories¶

Root Directories: /¶

Source Directories: /src¶

Backend Directories: /src/backend¶

Backend¶

READMEs¶

Flowchart¶

Commons¶

Header Files¶

Functional C Definitions: c.h¶

C Standard Library¶

Standard Types¶

System Types¶

System Method Macros¶

Offset, Length, and Alignment Method Macros¶

Assertions¶

General Macros¶

Miscellaneous Types¶

Server-Side: postgres.h¶

Includes¶

Variable-Length Data Types¶

Variable-Length Constant Macros¶

Aligned Variable-Length Method Macros¶

Oblivious Variable-Length Method Macros¶

Datum Types¶

Datum Method Macros¶

Client-Side: postgres_fe.h¶

Includes¶

Everywhere: postgres_ext.h¶

Includes¶

PostgreSQL Types¶

General Purpose Data Structures¶

Header Files¶

Binary Heap: binaryheap.h¶

Constants¶

Enumerations¶

Types¶

Structures¶

binaryheap¶

Methods¶

Macros¶

Hopcroft-Karp Maximum Cardinality Algorithm: bipartite_match.h¶

Constants¶

Enumerations¶

Types¶

Structures¶

BipartiteMatchState¶

Methods¶

Macros¶

Bloom Filter: bloomfilter.h¶

Constants¶

Enumerations¶

Types¶

Structures¶

bloom_filter¶

Methods¶

Macros¶

Dynamic Shared Memory Concurrent Hash Table: dshash.h¶

Constants¶

Enumerations¶

Types¶

Structures¶

dshash_parameters¶

Methods¶

Macros¶

HyperLogLog: hyperloglog.h¶

Constants¶

Enumerations¶

Types¶

Structures¶

hyperLogLogState¶

Methods¶

Macros¶

Inline Linked List: ilist.h¶

Working with Doubly Linked Lists¶

Documentation ¶

Presentations ¶

Top-Level Directories ¶

Root Directories: `/`¶

Source Directories: `/src`¶

Backend Directories: `/src/backend`¶

Backend ¶

READMEs ¶

Flowchart ¶

Commons ¶

Header Files ¶

Functional C Definitions: `c.h`¶

Server-Side: `postgres.h`¶

Client-Side: `postgres_fe.h`¶

Everywhere: `postgres_ext.h`¶

General Purpose Data Structures ¶

Header Files ¶

Binary Heap: `binaryheap.h`¶

`binaryheap`¶

Hopcroft-Karp Maximum Cardinality Algorithm: `bipartite_match.h`¶

`BipartiteMatchState`¶

Bloom Filter: `bloomfilter.h`¶

`bloom_filter`¶

Dynamic Shared Memory Concurrent Hash Table: `dshash.h`¶

`dshash_parameters`¶

HyperLogLog: `hyperloglog.h`¶

`hyperLogLogState`¶

Inline Linked List: `ilist.h`¶

`dlist_node` - Doubly Linked List Node¶

`dlist_head` - Doubly Linked List Head¶

`dlist_iter` - Doubly Linked List Immutable Iterator¶

`dlist_mutable_iter` - Doubly Linked List Mutable Iterator¶

`slist_node` - Singly Linked List Node¶

`slist_head` - Singly Linked List Head¶

`slist_iter` - Singly Linked List Immutable Iterator¶

`slist_mutable_iter` - Singly Linked List Mutable Iterator¶

Integer Set: `integerset.h`¶

0-1 Knapsack Algorithm: `knapsack.h`¶

Pairing Heap: `pairingheap.h`¶

`pairingheap_node`¶

`pairingheap`¶

Red-Black Tree: `rbtree.h`¶

`RBTOrderControl`¶

`RBTNode`¶

`RBTreeIterator`¶

Extensible String: `stringinfo.h`¶

`StringInfoData`¶

Macro-Generated, Simple Hash Table: `simplehash.h`¶

`SH_PREFIX ## _status`¶

`SH_PREFIX ## _hash`¶

`SH_PREFIX ## _iterator`¶

Shared Components and Utilities ¶