From 293913568e6a7a86fd1479e1cff8e2ecb58d6568 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 13 Apr 2024 15:44:03 +0200 Subject: Adding upstream version 16.2. Signed-off-by: Daniel Baumann --- src/include/lib/binaryheap.h | 54 ++ src/include/lib/bipartite_match.h | 46 ++ src/include/lib/bloomfilter.h | 27 + src/include/lib/dshash.h | 115 ++++ src/include/lib/hyperloglog.h | 68 +++ src/include/lib/ilist.h | 1159 ++++++++++++++++++++++++++++++++++++ src/include/lib/integerset.h | 24 + src/include/lib/knapsack.h | 16 + src/include/lib/pairingheap.h | 102 ++++ src/include/lib/qunique.h | 67 +++ src/include/lib/rbtree.h | 81 +++ src/include/lib/simplehash.h | 1184 +++++++++++++++++++++++++++++++++++++ src/include/lib/sort_template.h | 432 ++++++++++++++ src/include/lib/stringinfo.h | 161 +++++ 14 files changed, 3536 insertions(+) create mode 100644 src/include/lib/binaryheap.h create mode 100644 src/include/lib/bipartite_match.h create mode 100644 src/include/lib/bloomfilter.h create mode 100644 src/include/lib/dshash.h create mode 100644 src/include/lib/hyperloglog.h create mode 100644 src/include/lib/ilist.h create mode 100644 src/include/lib/integerset.h create mode 100644 src/include/lib/knapsack.h create mode 100644 src/include/lib/pairingheap.h create mode 100644 src/include/lib/qunique.h create mode 100644 src/include/lib/rbtree.h create mode 100644 src/include/lib/simplehash.h create mode 100644 src/include/lib/sort_template.h create mode 100644 src/include/lib/stringinfo.h (limited to 'src/include/lib') diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h new file mode 100644 index 0000000..52f7b06 --- /dev/null +++ b/src/include/lib/binaryheap.h @@ -0,0 +1,54 @@ +/* + * binaryheap.h + * + * A simple binary heap implementation + * + * Portions Copyright (c) 2012-2023, PostgreSQL Global Development Group + * + * src/include/lib/binaryheap.h + */ + +#ifndef BINARYHEAP_H +#define BINARYHEAP_H + +/* + * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b, + * and >0 iff a > b. For a min-heap, the conditions are reversed. + */ +typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg); + +/* + * binaryheap + * + * bh_size how many nodes are currently in "nodes" + * bh_space how many nodes can be stored in "nodes" + * bh_has_heap_property no unordered operations since last heap build + * bh_compare comparison function to define the heap property + * bh_arg user data for comparison function + * bh_nodes variable-length array of "space" nodes + */ +typedef struct binaryheap +{ + int bh_size; + int bh_space; + bool bh_has_heap_property; /* debugging cross-check */ + binaryheap_comparator bh_compare; + void *bh_arg; + Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER]; +} binaryheap; + +extern binaryheap *binaryheap_allocate(int capacity, + binaryheap_comparator compare, + void *arg); +extern void binaryheap_reset(binaryheap *heap); +extern void binaryheap_free(binaryheap *heap); +extern void binaryheap_add_unordered(binaryheap *heap, Datum d); +extern void binaryheap_build(binaryheap *heap); +extern void binaryheap_add(binaryheap *heap, Datum d); +extern Datum binaryheap_first(binaryheap *heap); +extern Datum binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_replace_first(binaryheap *heap, Datum d); + +#define binaryheap_empty(h) ((h)->bh_size == 0) + +#endif /* BINARYHEAP_H */ diff --git a/src/include/lib/bipartite_match.h b/src/include/lib/bipartite_match.h new file mode 100644 index 0000000..8fbbcae --- /dev/null +++ b/src/include/lib/bipartite_match.h @@ -0,0 +1,46 @@ +/* + * bipartite_match.h + * + * Copyright (c) 2015-2023, PostgreSQL Global Development Group + * + * src/include/lib/bipartite_match.h + */ +#ifndef BIPARTITE_MATCH_H +#define BIPARTITE_MATCH_H + +/* + * Given a bipartite graph consisting of nodes U numbered 1..nU, nodes V + * numbered 1..nV, and an adjacency map of undirected edges in the form + * adjacency[u] = [k, v1, v2, v3, ... vk], we wish to find a "maximum + * cardinality matching", which is defined as follows: a matching is a subset + * of the original edges such that no node has more than one edge, and a + * matching has maximum cardinality if there exists no other matching with a + * greater number of edges. + * + * This matching has various applications in graph theory, but the motivating + * example here is Dilworth's theorem: a partially-ordered set can be divided + * into the minimum number of chains (i.e. subsets X where x1 < x2 < x3 ...) by + * a bipartite graph construction. This gives us a polynomial-time solution to + * the problem of planning a collection of grouping sets with the provably + * minimal number of sort operations. + */ +typedef struct BipartiteMatchState +{ + /* inputs: */ + int u_size; /* size of U */ + int v_size; /* size of V */ + short **adjacency; /* adjacency[u] = [k, v1,v2,v3,...,vk] */ + /* outputs: */ + int matching; /* number of edges in matching */ + short *pair_uv; /* pair_uv[u] -> v */ + short *pair_vu; /* pair_vu[v] -> u */ + /* private state for matching algorithm: */ + short *distance; /* distance[u] */ + short *queue; /* queue storage for breadth search */ +} BipartiteMatchState; + +extern BipartiteMatchState *BipartiteMatch(int u_size, int v_size, short **adjacency); + +extern void BipartiteMatchFree(BipartiteMatchState *state); + +#endif /* BIPARTITE_MATCH_H */ diff --git a/src/include/lib/bloomfilter.h b/src/include/lib/bloomfilter.h new file mode 100644 index 0000000..5a98c09 --- /dev/null +++ b/src/include/lib/bloomfilter.h @@ -0,0 +1,27 @@ +/*------------------------------------------------------------------------- + * + * bloomfilter.h + * Space-efficient set membership testing + * + * Copyright (c) 2018-2023, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/include/lib/bloomfilter.h + * + *------------------------------------------------------------------------- + */ +#ifndef BLOOMFILTER_H +#define BLOOMFILTER_H + +typedef struct bloom_filter bloom_filter; + +extern bloom_filter *bloom_create(int64 total_elems, int bloom_work_mem, + uint64 seed); +extern void bloom_free(bloom_filter *filter); +extern void bloom_add_element(bloom_filter *filter, unsigned char *elem, + size_t len); +extern bool bloom_lacks_element(bloom_filter *filter, unsigned char *elem, + size_t len); +extern double bloom_prop_bits_set(bloom_filter *filter); + +#endif /* BLOOMFILTER_H */ diff --git a/src/include/lib/dshash.h b/src/include/lib/dshash.h new file mode 100644 index 0000000..ece5552 --- /dev/null +++ b/src/include/lib/dshash.h @@ -0,0 +1,115 @@ +/*------------------------------------------------------------------------- + * + * dshash.h + * Concurrent hash tables backed by dynamic shared memory areas. + * + * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/include/lib/dshash.h + * + *------------------------------------------------------------------------- + */ +#ifndef DSHASH_H +#define DSHASH_H + +#include "utils/dsa.h" + +/* The opaque type representing a hash table. */ +struct dshash_table; +typedef struct dshash_table dshash_table; + +/* A handle for a dshash_table which can be shared with other processes. */ +typedef dsa_pointer dshash_table_handle; + +/* Sentinel value to use for invalid dshash_table handles. */ +#define DSHASH_HANDLE_INVALID ((dshash_table_handle) InvalidDsaPointer) + +/* The type for hash values. */ +typedef uint32 dshash_hash; + +/* A function type for comparing keys. */ +typedef int (*dshash_compare_function) (const void *a, const void *b, + size_t size, void *arg); + +/* A function type for computing hash values for keys. */ +typedef dshash_hash (*dshash_hash_function) (const void *v, size_t size, + void *arg); + +/* + * The set of parameters needed to create or attach to a hash table. The + * members tranche_id and tranche_name do not need to be initialized when + * attaching to an existing hash table. + * + * Compare and hash functions must be supplied even when attaching, because we + * can't safely share function pointers between backends in general. Either + * the arg variants or the non-arg variants should be supplied; the other + * function pointers should be NULL. If the arg variants are supplied then the + * user data pointer supplied to the create and attach functions will be + * passed to the hash and compare functions. + */ +typedef struct dshash_parameters +{ + size_t key_size; /* Size of the key (initial bytes of entry) */ + size_t entry_size; /* Total size of entry */ + dshash_compare_function compare_function; /* Compare function */ + dshash_hash_function hash_function; /* Hash function */ + int tranche_id; /* The tranche ID to use for locks */ +} dshash_parameters; + +/* Forward declaration of private types for use only by dshash.c. */ +struct dshash_table_item; +typedef struct dshash_table_item dshash_table_item; + +/* + * Sequential scan state. The detail is exposed to let users know the storage + * size but it should be considered as an opaque type by callers. + */ +typedef struct dshash_seq_status +{ + dshash_table *hash_table; /* dshash table working on */ + int curbucket; /* bucket number we are at */ + int nbuckets; /* total number of buckets in the dshash */ + dshash_table_item *curitem; /* item we are currently at */ + dsa_pointer pnextitem; /* dsa-pointer to the next item */ + int curpartition; /* partition number we are at */ + bool exclusive; /* locking mode */ +} dshash_seq_status; + +/* Creating, sharing and destroying from hash tables. */ +extern dshash_table *dshash_create(dsa_area *area, + const dshash_parameters *params, + void *arg); +extern dshash_table *dshash_attach(dsa_area *area, + const dshash_parameters *params, + dshash_table_handle handle, + void *arg); +extern void dshash_detach(dshash_table *hash_table); +extern dshash_table_handle dshash_get_hash_table_handle(dshash_table *hash_table); +extern void dshash_destroy(dshash_table *hash_table); + +/* Finding, creating, deleting entries. */ +extern void *dshash_find(dshash_table *hash_table, + const void *key, bool exclusive); +extern void *dshash_find_or_insert(dshash_table *hash_table, + const void *key, bool *found); +extern bool dshash_delete_key(dshash_table *hash_table, const void *key); +extern void dshash_delete_entry(dshash_table *hash_table, void *entry); +extern void dshash_release_lock(dshash_table *hash_table, void *entry); + +/* seq scan support */ +extern void dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table, + bool exclusive); +extern void *dshash_seq_next(dshash_seq_status *status); +extern void dshash_seq_term(dshash_seq_status *status); +extern void dshash_delete_current(dshash_seq_status *status); + +/* Convenience hash and compare functions wrapping memcmp and tag_hash. */ +extern int dshash_memcmp(const void *a, const void *b, size_t size, void *arg); +extern dshash_hash dshash_memhash(const void *v, size_t size, void *arg); + +/* Debugging support. */ +extern void dshash_dump(dshash_table *hash_table); + +#endif /* DSHASH_H */ diff --git a/src/include/lib/hyperloglog.h b/src/include/lib/hyperloglog.h new file mode 100644 index 0000000..f4150f0 --- /dev/null +++ b/src/include/lib/hyperloglog.h @@ -0,0 +1,68 @@ +/* + * hyperloglog.h + * + * A simple HyperLogLog cardinality estimator implementation + * + * Portions Copyright (c) 2014-2023, PostgreSQL Global Development Group + * + * Based on Hideaki Ohno's C++ implementation. The copyright terms of Ohno's + * original version (the MIT license) follow. + * + * src/include/lib/hyperloglog.h + */ + +/* + * Copyright (c) 2013 Hideaki Ohno + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the 'Software'), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#ifndef HYPERLOGLOG_H +#define HYPERLOGLOG_H + +/* + * HyperLogLog is an approximate technique for computing the number of distinct + * entries in a set. Importantly, it does this by using a fixed amount of + * memory. See the 2007 paper "HyperLogLog: the analysis of a near-optimal + * cardinality estimation algorithm" for more. + * + * hyperLogLogState + * + * registerWidth register width, in bits ("k") + * nRegisters number of registers + * alphaMM alpha * m ^ 2 (see initHyperLogLog()) + * hashesArr array of hashes + * arrSize size of hashesArr + */ +typedef struct hyperLogLogState +{ + uint8 registerWidth; + Size nRegisters; + double alphaMM; + uint8 *hashesArr; + Size arrSize; +} hyperLogLogState; + +extern void initHyperLogLog(hyperLogLogState *cState, uint8 bwidth); +extern void initHyperLogLogError(hyperLogLogState *cState, double error); +extern void addHyperLogLog(hyperLogLogState *cState, uint32 hash); +extern double estimateHyperLogLog(hyperLogLogState *cState); +extern void freeHyperLogLog(hyperLogLogState *cState); + +#endif /* HYPERLOGLOG_H */ diff --git a/src/include/lib/ilist.h b/src/include/lib/ilist.h new file mode 100644 index 0000000..095107a --- /dev/null +++ b/src/include/lib/ilist.h @@ -0,0 +1,1159 @@ +/*------------------------------------------------------------------------- + * + * ilist.h + * integrated/inline doubly- and singly-linked lists + * + * These list types are useful when there are only a predetermined set of + * lists that an object could be in. List links are embedded directly into + * the objects, and thus no extra memory management overhead is required. + * (Of course, if only a small proportion of existing objects are in a list, + * the link fields in the remainder would be wasted space. But usually, + * it saves space to not have separately-allocated list nodes.) + * + * The doubly-linked list comes in 2 forms. dlist_head defines a head of a + * doubly-linked list of dlist_nodes, whereas dclist_head defines the head of + * a doubly-linked list of dlist_nodes with an additional 'count' field to + * keep track of how many items are contained within the given list. For + * simplicity, dlist_head and dclist_head share the same node and iterator + * types. The functions to manipulate a dlist_head always have a name + * starting with "dlist", whereas functions to manipulate a dclist_head have a + * name starting with "dclist". dclist_head comes with an additional function + * (dclist_count) to return the number of entries in the list. dclists are + * able to store a maximum of PG_UINT32_MAX elements. It is up to the caller + * to ensure no more than this many items are added to a dclist. + * + * None of the functions here allocate any memory; they just manipulate + * externally managed memory. With the exception doubly-linked count lists + * providing the ability to obtain the number of items in the list, the APIs + * for singly and both doubly linked lists are identical as far as + * capabilities of both allow. + * + * Each list has a list header, which exists even when the list is empty. + * An empty singly-linked list has a NULL pointer in its header. + * + * For both doubly-linked list types, there are two valid ways to represent an + * empty list. The head's 'next' pointer can either be NULL or the head's + * 'next' and 'prev' links can both point back to the list head (circular). + * (If a dlist is modified and then all its elements are deleted, it will be + * in the circular state.). We prefer circular dlists because there are some + * operations that can be done without branches (and thus faster) on lists + * that use circular representation. However, it is often convenient to + * initialize list headers to zeroes rather than setting them up with an + * explicit initialization function, so we also allow the NULL initialization. + * + * EXAMPLES + * + * Here's a simple example demonstrating how this can be used. Let's assume + * we want to store information about the tables contained in a database. + * + * #include "lib/ilist.h" + * + * // Define struct for the databases including a list header that will be + * // used to access the nodes in the table list later on. + * typedef struct my_database + * { + * char *datname; + * dlist_head tables; + * // ... + * } my_database; + * + * // Define struct for the tables. Note the list_node element which stores + * // prev/next list links. The list_node element need not be first. + * typedef struct my_table + * { + * char *tablename; + * dlist_node list_node; + * perm_t permissions; + * // ... + * } my_table; + * + * // create a database + * my_database *db = create_database(); + * + * // and add a few tables to its table list + * dlist_push_head(&db->tables, &create_table(db, "a")->list_node); + * ... + * dlist_push_head(&db->tables, &create_table(db, "b")->list_node); + * + * + * To iterate over the table list, we allocate an iterator variable and use + * a specialized looping construct. Inside a dlist_foreach, the iterator's + * 'cur' field can be used to access the current element. iter.cur points to + * a 'dlist_node', but most of the time what we want is the actual table + * information; dlist_container() gives us that, like so: + * + * dlist_iter iter; + * dlist_foreach(iter, &db->tables) + * { + * my_table *tbl = dlist_container(my_table, list_node, iter.cur); + * printf("we have a table: %s in database %s\n", + * tbl->tablename, db->datname); + * } + * + * + * While a simple iteration is useful, we sometimes also want to manipulate + * the list while iterating. There is a different iterator element and looping + * construct for that. Suppose we want to delete tables that meet a certain + * criterion: + * + * dlist_mutable_iter miter; + * dlist_foreach_modify(miter, &db->tables) + * { + * my_table *tbl = dlist_container(my_table, list_node, miter.cur); + * + * if (!tbl->to_be_deleted) + * continue; // don't touch this one + * + * // unlink the current table from the linked list + * dlist_delete(miter.cur); + * // as these lists never manage memory, we can still access the table + * // after it's been unlinked + * drop_table(db, tbl); + * } + * + * + * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/include/lib/ilist.h + *------------------------------------------------------------------------- + */ +#ifndef ILIST_H +#define ILIST_H + +/* + * Enable for extra debugging. This is rather expensive, so it's not enabled by + * default even when USE_ASSERT_CHECKING. + */ +/* #define ILIST_DEBUG */ + +/* + * Node of a doubly linked list. + * + * Embed this in structs that need to be part of a doubly linked list. + */ +typedef struct dlist_node dlist_node; +struct dlist_node +{ + dlist_node *prev; + dlist_node *next; +}; + +/* + * Head of a doubly linked list. + * + * Non-empty lists are internally circularly linked. Circular lists have the + * advantage of not needing any branches in the most common list manipulations. + * An empty list can also be represented as a pair of NULL pointers, making + * initialization easier. + */ +typedef struct dlist_head +{ + /* + * head.next either points to the first element of the list; to &head if + * it's a circular empty list; or to NULL if empty and not circular. + * + * head.prev either points to the last element of the list; to &head if + * it's a circular empty list; or to NULL if empty and not circular. + */ + dlist_node head; +} dlist_head; + + +/* + * Doubly linked list iterator type for dlist_head and dclist_head types. + * + * Used as state in dlist_foreach() and dlist_reverse_foreach() (and the + * dclist variant thereof). + * + * To get the current element of the iteration use the 'cur' member. + * + * Iterations using this are *not* allowed to change the list while iterating! + * + * NB: We use an extra "end" field here to avoid multiple evaluations of + * arguments in the dlist_foreach() and dclist_foreach() macros. + */ +typedef struct dlist_iter +{ + dlist_node *cur; /* current element */ + dlist_node *end; /* last node we'll iterate to */ +} dlist_iter; + +/* + * Doubly linked list iterator for both dlist_head and dclist_head types. + * This iterator type allows some modifications while iterating. + * + * Used as state in dlist_foreach_modify() and dclist_foreach_modify(). + * + * To get the current element of the iteration use the 'cur' member. + * + * Iterations using this are only allowed to change the list at the current + * point of iteration. It is fine to delete the current node, but it is *not* + * fine to insert or delete adjacent nodes. + * + * NB: We need a separate type for mutable iterations so that we can store + * the 'next' node of the current node in case it gets deleted or modified. + */ +typedef struct dlist_mutable_iter +{ + dlist_node *cur; /* current element */ + dlist_node *next; /* next node we'll iterate to */ + dlist_node *end; /* last node we'll iterate to */ +} dlist_mutable_iter; + +/* + * Head of a doubly linked list with a count of the number of items + * + * This internally makes use of a dlist to implement the actual list. When + * items are added or removed from the list the count is updated to reflect + * the current number of items in the list. + */ +typedef struct dclist_head +{ + dlist_head dlist; /* the actual list header */ + uint32 count; /* the number of items in the list */ +} dclist_head; + +/* + * Node of a singly linked list. + * + * Embed this in structs that need to be part of a singly linked list. + */ +typedef struct slist_node slist_node; +struct slist_node +{ + slist_node *next; +}; + +/* + * Head of a singly linked list. + * + * Singly linked lists are not circularly linked, in contrast to doubly linked + * lists; we just set head.next to NULL if empty. This doesn't incur any + * additional branches in the usual manipulations. + */ +typedef struct slist_head +{ + slist_node head; +} slist_head; + +/* + * Singly linked list iterator. + * + * Used as state in slist_foreach(). To get the current element of the + * iteration use the 'cur' member. + * + * It's allowed to modify the list while iterating, with the exception of + * deleting the iterator's current node; deletion of that node requires + * care if the iteration is to be continued afterward. (Doing so and also + * deleting or inserting adjacent list elements might misbehave; also, if + * the user frees the current node's storage, continuing the iteration is + * not safe.) + * + * NB: this wouldn't really need to be an extra struct, we could use an + * slist_node * directly. We prefer a separate type for consistency. + */ +typedef struct slist_iter +{ + slist_node *cur; +} slist_iter; + +/* + * Singly linked list iterator allowing some modifications while iterating. + * + * Used as state in slist_foreach_modify(). To get the current element of the + * iteration use the 'cur' member. + * + * The only list modification allowed while iterating is to remove the current + * node via slist_delete_current() (*not* slist_delete()). Insertion or + * deletion of nodes adjacent to the current node would misbehave. + */ +typedef struct slist_mutable_iter +{ + slist_node *cur; /* current element */ + slist_node *next; /* next node we'll iterate to */ + slist_node *prev; /* prev node, for deletions */ +} slist_mutable_iter; + + +/* Static initializers */ +#define DLIST_STATIC_INIT(name) {{&(name).head, &(name).head}} +#define DCLIST_STATIC_INIT(name) {{{&(name).dlist.head, &(name).dlist.head}}, 0} +#define SLIST_STATIC_INIT(name) {{NULL}} + + +/* Prototypes for functions too big to be inline */ + +/* Caution: this is O(n); consider using slist_delete_current() instead */ +extern void slist_delete(slist_head *head, const slist_node *node); + +#ifdef ILIST_DEBUG +extern void dlist_member_check(const dlist_head *head, const dlist_node *node); +extern void dlist_check(const dlist_head *head); +extern void slist_check(const slist_head *head); +#else +/* + * These seemingly useless casts to void are here to keep the compiler quiet + * about the argument being unused in many functions in a non-debug compile, + * in which functions the only point of passing the list head pointer is to be + * able to run these checks. + */ +#define dlist_member_check(head, node) ((void) (head)) +#define dlist_check(head) ((void) (head)) +#define slist_check(head) ((void) (head)) +#endif /* ILIST_DEBUG */ + +/* doubly linked list implementation */ + +/* + * Initialize a doubly linked list. + * Previous state will be thrown away without any cleanup. + */ +static inline void +dlist_init(dlist_head *head) +{ + head->head.next = head->head.prev = &head->head; +} + +/* + * Initialize a doubly linked list element. + * + * This is only needed when dlist_node_is_detached() may be needed. + */ +static inline void +dlist_node_init(dlist_node *node) +{ + node->next = node->prev = NULL; +} + +/* + * Is the list empty? + * + * An empty list has either its first 'next' pointer set to NULL, or to itself. + */ +static inline bool +dlist_is_empty(const dlist_head *head) +{ + dlist_check(head); + + return head->head.next == NULL || head->head.next == &(head->head); +} + +/* + * Insert a node at the beginning of the list. + */ +static inline void +dlist_push_head(dlist_head *head, dlist_node *node) +{ + if (head->head.next == NULL) /* convert NULL header to circular */ + dlist_init(head); + + node->next = head->head.next; + node->prev = &head->head; + node->next->prev = node; + head->head.next = node; + + dlist_check(head); +} + +/* + * Insert a node at the end of the list. + */ +static inline void +dlist_push_tail(dlist_head *head, dlist_node *node) +{ + if (head->head.next == NULL) /* convert NULL header to circular */ + dlist_init(head); + + node->next = &head->head; + node->prev = head->head.prev; + node->prev->next = node; + head->head.prev = node; + + dlist_check(head); +} + +/* + * Insert a node after another *in the same list* + */ +static inline void +dlist_insert_after(dlist_node *after, dlist_node *node) +{ + node->prev = after; + node->next = after->next; + after->next = node; + node->next->prev = node; +} + +/* + * Insert a node before another *in the same list* + */ +static inline void +dlist_insert_before(dlist_node *before, dlist_node *node) +{ + node->prev = before->prev; + node->next = before; + before->prev = node; + node->prev->next = node; +} + +/* + * Delete 'node' from its list (it must be in one). + */ +static inline void +dlist_delete(dlist_node *node) +{ + node->prev->next = node->next; + node->next->prev = node->prev; +} + +/* + * Like dlist_delete(), but also sets next/prev to NULL to signal not being in + * a list. + */ +static inline void +dlist_delete_thoroughly(dlist_node *node) +{ + node->prev->next = node->next; + node->next->prev = node->prev; + node->next = NULL; + node->prev = NULL; +} + +/* + * Same as dlist_delete, but performs checks in ILIST_DEBUG builds to ensure + * that 'node' belongs to 'head'. + */ +static inline void +dlist_delete_from(dlist_head *head, dlist_node *node) +{ + dlist_member_check(head, node); + dlist_delete(node); +} + +/* + * Like dlist_delete_from, but also sets next/prev to NULL to signal not + * being in a list. + */ +static inline void +dlist_delete_from_thoroughly(dlist_head *head, dlist_node *node) +{ + dlist_member_check(head, node); + dlist_delete_thoroughly(node); +} + +/* + * Remove and return the first node from a list (there must be one). + */ +static inline dlist_node * +dlist_pop_head_node(dlist_head *head) +{ + dlist_node *node; + + Assert(!dlist_is_empty(head)); + node = head->head.next; + dlist_delete(node); + return node; +} + +/* + * Move element from its current position in the list to the head position in + * the same list. + * + * Undefined behaviour if 'node' is not already part of the list. + */ +static inline void +dlist_move_head(dlist_head *head, dlist_node *node) +{ + /* fast path if it's already at the head */ + if (head->head.next == node) + return; + + dlist_delete(node); + dlist_push_head(head, node); + + dlist_check(head); +} + +/* + * Move element from its current position in the list to the tail position in + * the same list. + * + * Undefined behaviour if 'node' is not already part of the list. + */ +static inline void +dlist_move_tail(dlist_head *head, dlist_node *node) +{ + /* fast path if it's already at the tail */ + if (head->head.prev == node) + return; + + dlist_delete(node); + dlist_push_tail(head, node); + + dlist_check(head); +} + +/* + * Check whether 'node' has a following node. + * Caution: unreliable if 'node' is not in the list. + */ +static inline bool +dlist_has_next(const dlist_head *head, const dlist_node *node) +{ + return node->next != &head->head; +} + +/* + * Check whether 'node' has a preceding node. + * Caution: unreliable if 'node' is not in the list. + */ +static inline bool +dlist_has_prev(const dlist_head *head, const dlist_node *node) +{ + return node->prev != &head->head; +} + +/* + * Check if node is detached. A node is only detached if it either has been + * initialized with dlist_init_node(), or deleted with + * dlist_delete_thoroughly() / dlist_delete_from_thoroughly() / + * dclist_delete_from_thoroughly(). + */ +static inline bool +dlist_node_is_detached(const dlist_node *node) +{ + Assert((node->next == NULL && node->prev == NULL) || + (node->next != NULL && node->prev != NULL)); + + return node->next == NULL; +} + +/* + * Return the next node in the list (there must be one). + */ +static inline dlist_node * +dlist_next_node(dlist_head *head, dlist_node *node) +{ + Assert(dlist_has_next(head, node)); + return node->next; +} + +/* + * Return previous node in the list (there must be one). + */ +static inline dlist_node * +dlist_prev_node(dlist_head *head, dlist_node *node) +{ + Assert(dlist_has_prev(head, node)); + return node->prev; +} + +/* internal support function to get address of head element's struct */ +static inline void * +dlist_head_element_off(dlist_head *head, size_t off) +{ + Assert(!dlist_is_empty(head)); + return (char *) head->head.next - off; +} + +/* + * Return the first node in the list (there must be one). + */ +static inline dlist_node * +dlist_head_node(dlist_head *head) +{ + return (dlist_node *) dlist_head_element_off(head, 0); +} + +/* internal support function to get address of tail element's struct */ +static inline void * +dlist_tail_element_off(dlist_head *head, size_t off) +{ + Assert(!dlist_is_empty(head)); + return (char *) head->head.prev - off; +} + +/* + * Return the last node in the list (there must be one). + */ +static inline dlist_node * +dlist_tail_node(dlist_head *head) +{ + return (dlist_node *) dlist_tail_element_off(head, 0); +} + +/* + * Return the containing struct of 'type' where 'membername' is the dlist_node + * pointed at by 'ptr'. + * + * This is used to convert a dlist_node * back to its containing struct. + */ +#define dlist_container(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(ptr, dlist_node *), \ + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ + ((type *) ((char *) (ptr) - offsetof(type, membername)))) + +/* + * Return the address of the first element in the list. + * + * The list must not be empty. + */ +#define dlist_head_element(type, membername, lhead) \ + (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ + (type *) dlist_head_element_off(lhead, offsetof(type, membername))) + +/* + * Return the address of the last element in the list. + * + * The list must not be empty. + */ +#define dlist_tail_element(type, membername, lhead) \ + (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ + ((type *) dlist_tail_element_off(lhead, offsetof(type, membername)))) + +/* + * Iterate through the list pointed at by 'lhead' storing the state in 'iter'. + * + * Access the current element with iter.cur. + * + * It is *not* allowed to manipulate the list during iteration. + */ +#define dlist_foreach(iter, lhead) \ + for (AssertVariableIsOfTypeMacro(iter, dlist_iter), \ + AssertVariableIsOfTypeMacro(lhead, dlist_head *), \ + (iter).end = &(lhead)->head, \ + (iter).cur = (iter).end->next ? (iter).end->next : (iter).end; \ + (iter).cur != (iter).end; \ + (iter).cur = (iter).cur->next) + +/* + * Iterate through the list pointed at by 'lhead' storing the state in 'iter'. + * + * Access the current element with iter.cur. + * + * Iterations using this are only allowed to change the list at the current + * point of iteration. It is fine to delete the current node, but it is *not* + * fine to insert or delete adjacent nodes. + */ +#define dlist_foreach_modify(iter, lhead) \ + for (AssertVariableIsOfTypeMacro(iter, dlist_mutable_iter), \ + AssertVariableIsOfTypeMacro(lhead, dlist_head *), \ + (iter).end = &(lhead)->head, \ + (iter).cur = (iter).end->next ? (iter).end->next : (iter).end, \ + (iter).next = (iter).cur->next; \ + (iter).cur != (iter).end; \ + (iter).cur = (iter).next, (iter).next = (iter).cur->next) + +/* + * Iterate through the list in reverse order. + * + * It is *not* allowed to manipulate the list during iteration. + */ +#define dlist_reverse_foreach(iter, lhead) \ + for (AssertVariableIsOfTypeMacro(iter, dlist_iter), \ + AssertVariableIsOfTypeMacro(lhead, dlist_head *), \ + (iter).end = &(lhead)->head, \ + (iter).cur = (iter).end->prev ? (iter).end->prev : (iter).end; \ + (iter).cur != (iter).end; \ + (iter).cur = (iter).cur->prev) + +/* doubly-linked count list implementation */ + +/* + * dclist_init + * Initialize a doubly linked count list. + * + * Previous state will be thrown away without any cleanup. + */ +static inline void +dclist_init(dclist_head *head) +{ + dlist_init(&head->dlist); + head->count = 0; +} + +/* + * dclist_is_empty + * Returns true if the list is empty, otherwise false. + */ +static inline bool +dclist_is_empty(const dclist_head *head) +{ + Assert(dlist_is_empty(&head->dlist) == (head->count == 0)); + return (head->count == 0); +} + +/* + * dclist_push_head + * Insert a node at the beginning of the list. + */ +static inline void +dclist_push_head(dclist_head *head, dlist_node *node) +{ + if (head->dlist.head.next == NULL) /* convert NULL header to circular */ + dclist_init(head); + + dlist_push_head(&head->dlist, node); + head->count++; + + Assert(head->count > 0); /* count overflow check */ +} + +/* + * dclist_push_tail + * Insert a node at the end of the list. + */ +static inline void +dclist_push_tail(dclist_head *head, dlist_node *node) +{ + if (head->dlist.head.next == NULL) /* convert NULL header to circular */ + dclist_init(head); + + dlist_push_tail(&head->dlist, node); + head->count++; + + Assert(head->count > 0); /* count overflow check */ +} + +/* + * dclist_insert_after + * Insert a node after another *in the same list* + * + * Caution: 'after' must be a member of 'head'. + */ +static inline void +dclist_insert_after(dclist_head *head, dlist_node *after, dlist_node *node) +{ + dlist_member_check(&head->dlist, after); + Assert(head->count > 0); /* must be at least 1 already */ + + dlist_insert_after(after, node); + head->count++; + + Assert(head->count > 0); /* count overflow check */ +} + +/* + * dclist_insert_before + * Insert a node before another *in the same list* + * + * Caution: 'before' must be a member of 'head'. + */ +static inline void +dclist_insert_before(dclist_head *head, dlist_node *before, dlist_node *node) +{ + dlist_member_check(&head->dlist, before); + Assert(head->count > 0); /* must be at least 1 already */ + + dlist_insert_before(before, node); + head->count++; + + Assert(head->count > 0); /* count overflow check */ +} + +/* + * dclist_delete_from + * Deletes 'node' from 'head'. + * + * Caution: 'node' must be a member of 'head'. + */ +static inline void +dclist_delete_from(dclist_head *head, dlist_node *node) +{ + Assert(head->count > 0); + + dlist_delete_from(&head->dlist, node); + head->count--; +} + +/* + * Like dclist_delete_from(), but also sets next/prev to NULL to signal not + * being in a list. + */ +static inline void +dclist_delete_from_thoroughly(dclist_head *head, dlist_node *node) +{ + Assert(head->count > 0); + + dlist_delete_from_thoroughly(&head->dlist, node); + head->count--; +} + +/* + * dclist_pop_head_node + * Remove and return the first node from a list (there must be one). + */ +static inline dlist_node * +dclist_pop_head_node(dclist_head *head) +{ + dlist_node *node; + + Assert(head->count > 0); + + node = dlist_pop_head_node(&head->dlist); + head->count--; + return node; +} + +/* + * dclist_move_head + * Move 'node' from its current position in the list to the head position + * in 'head'. + * + * Caution: 'node' must be a member of 'head'. + */ +static inline void +dclist_move_head(dclist_head *head, dlist_node *node) +{ + dlist_member_check(&head->dlist, node); + Assert(head->count > 0); + + dlist_move_head(&head->dlist, node); +} + +/* + * dclist_move_tail + * Move 'node' from its current position in the list to the tail position + * in 'head'. + * + * Caution: 'node' must be a member of 'head'. + */ +static inline void +dclist_move_tail(dclist_head *head, dlist_node *node) +{ + dlist_member_check(&head->dlist, node); + Assert(head->count > 0); + + dlist_move_tail(&head->dlist, node); +} + +/* + * dclist_has_next + * Check whether 'node' has a following node. + * + * Caution: 'node' must be a member of 'head'. + */ +static inline bool +dclist_has_next(const dclist_head *head, const dlist_node *node) +{ + dlist_member_check(&head->dlist, node); + Assert(head->count > 0); + + return dlist_has_next(&head->dlist, node); +} + +/* + * dclist_has_prev + * Check whether 'node' has a preceding node. + * + * Caution: 'node' must be a member of 'head'. + */ +static inline bool +dclist_has_prev(const dclist_head *head, const dlist_node *node) +{ + dlist_member_check(&head->dlist, node); + Assert(head->count > 0); + + return dlist_has_prev(&head->dlist, node); +} + +/* + * dclist_next_node + * Return the next node in the list (there must be one). + */ +static inline dlist_node * +dclist_next_node(dclist_head *head, dlist_node *node) +{ + Assert(head->count > 0); + + return dlist_next_node(&head->dlist, node); +} + +/* + * dclist_prev_node + * Return the prev node in the list (there must be one). + */ +static inline dlist_node * +dclist_prev_node(dclist_head *head, dlist_node *node) +{ + Assert(head->count > 0); + + return dlist_prev_node(&head->dlist, node); +} + +/* internal support function to get address of head element's struct */ +static inline void * +dclist_head_element_off(dclist_head *head, size_t off) +{ + Assert(!dclist_is_empty(head)); + + return (char *) head->dlist.head.next - off; +} + +/* + * dclist_head_node + * Return the first node in the list (there must be one). + */ +static inline dlist_node * +dclist_head_node(dclist_head *head) +{ + Assert(head->count > 0); + + return (dlist_node *) dlist_head_element_off(&head->dlist, 0); +} + +/* internal support function to get address of tail element's struct */ +static inline void * +dclist_tail_element_off(dclist_head *head, size_t off) +{ + Assert(!dclist_is_empty(head)); + + return (char *) head->dlist.head.prev - off; +} + +/* + * Return the last node in the list (there must be one). + */ +static inline dlist_node * +dclist_tail_node(dclist_head *head) +{ + Assert(head->count > 0); + + return (dlist_node *) dlist_tail_element_off(&head->dlist, 0); +} + +/* + * dclist_count + * Returns the stored number of entries in 'head' + */ +static inline uint32 +dclist_count(const dclist_head *head) +{ + Assert(dlist_is_empty(&head->dlist) == (head->count == 0)); + + return head->count; +} + +/* + * Return the containing struct of 'type' where 'membername' is the dlist_node + * pointed at by 'ptr'. + * + * This is used to convert a dlist_node * back to its containing struct. + * + * Note: This is effectively just the same as dlist_container, so reuse that. + */ +#define dclist_container(type, membername, ptr) \ + dlist_container(type, membername, ptr) + + /* + * Return the address of the first element in the list. + * + * The list must not be empty. + */ +#define dclist_head_element(type, membername, lhead) \ + (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ + (type *) dclist_head_element_off(lhead, offsetof(type, membername))) + + /* + * Return the address of the last element in the list. + * + * The list must not be empty. + */ +#define dclist_tail_element(type, membername, lhead) \ + (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ + ((type *) dclist_tail_element_off(lhead, offsetof(type, membername)))) + + +/* Iterators for dclists */ +#define dclist_foreach(iter, lhead) \ + dlist_foreach(iter, &((lhead)->dlist)) + +#define dclist_foreach_modify(iter, lhead) \ + dlist_foreach_modify(iter, &((lhead)->dlist)) + +#define dclist_reverse_foreach(iter, lhead) \ + dlist_reverse_foreach(iter, &((lhead)->dlist)) + +/* singly linked list implementation */ + +/* + * Initialize a singly linked list. + * Previous state will be thrown away without any cleanup. + */ +static inline void +slist_init(slist_head *head) +{ + head->head.next = NULL; +} + +/* + * Is the list empty? + */ +static inline bool +slist_is_empty(const slist_head *head) +{ + slist_check(head); + + return head->head.next == NULL; +} + +/* + * Insert a node at the beginning of the list. + */ +static inline void +slist_push_head(slist_head *head, slist_node *node) +{ + node->next = head->head.next; + head->head.next = node; + + slist_check(head); +} + +/* + * Insert a node after another *in the same list* + */ +static inline void +slist_insert_after(slist_node *after, slist_node *node) +{ + node->next = after->next; + after->next = node; +} + +/* + * Remove and return the first node from a list (there must be one). + */ +static inline slist_node * +slist_pop_head_node(slist_head *head) +{ + slist_node *node; + + Assert(!slist_is_empty(head)); + node = head->head.next; + head->head.next = node->next; + slist_check(head); + return node; +} + +/* + * Check whether 'node' has a following node. + */ +static inline bool +slist_has_next(const slist_head *head, const slist_node *node) +{ + slist_check(head); + + return node->next != NULL; +} + +/* + * Return the next node in the list (there must be one). + */ +static inline slist_node * +slist_next_node(slist_head *head, slist_node *node) +{ + Assert(slist_has_next(head, node)); + return node->next; +} + +/* internal support function to get address of head element's struct */ +static inline void * +slist_head_element_off(slist_head *head, size_t off) +{ + Assert(!slist_is_empty(head)); + return (char *) head->head.next - off; +} + +/* + * Return the first node in the list (there must be one). + */ +static inline slist_node * +slist_head_node(slist_head *head) +{ + return (slist_node *) slist_head_element_off(head, 0); +} + +/* + * Delete the list element the iterator currently points to. + * + * Caution: this modifies iter->cur, so don't use that again in the current + * loop iteration. + */ +static inline void +slist_delete_current(slist_mutable_iter *iter) +{ + /* + * Update previous element's forward link. If the iteration is at the + * first list element, iter->prev will point to the list header's "head" + * field, so we don't need a special case for that. + */ + iter->prev->next = iter->next; + + /* + * Reset cur to prev, so that prev will continue to point to the prior + * valid list element after slist_foreach_modify() advances to the next. + */ + iter->cur = iter->prev; +} + +/* + * Return the containing struct of 'type' where 'membername' is the slist_node + * pointed at by 'ptr'. + * + * This is used to convert a slist_node * back to its containing struct. + */ +#define slist_container(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(ptr, slist_node *), \ + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \ + ((type *) ((char *) (ptr) - offsetof(type, membername)))) + +/* + * Return the address of the first element in the list. + * + * The list must not be empty. + */ +#define slist_head_element(type, membername, lhead) \ + (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \ + (type *) slist_head_element_off(lhead, offsetof(type, membername))) + +/* + * Iterate through the list pointed at by 'lhead' storing the state in 'iter'. + * + * Access the current element with iter.cur. + * + * It's allowed to modify the list while iterating, with the exception of + * deleting the iterator's current node; deletion of that node requires + * care if the iteration is to be continued afterward. (Doing so and also + * deleting or inserting adjacent list elements might misbehave; also, if + * the user frees the current node's storage, continuing the iteration is + * not safe.) + */ +#define slist_foreach(iter, lhead) \ + for (AssertVariableIsOfTypeMacro(iter, slist_iter), \ + AssertVariableIsOfTypeMacro(lhead, slist_head *), \ + (iter).cur = (lhead)->head.next; \ + (iter).cur != NULL; \ + (iter).cur = (iter).cur->next) + +/* + * Iterate through the list pointed at by 'lhead' storing the state in 'iter'. + * + * Access the current element with iter.cur. + * + * The only list modification allowed while iterating is to remove the current + * node via slist_delete_current() (*not* slist_delete()). Insertion or + * deletion of nodes adjacent to the current node would misbehave. + */ +#define slist_foreach_modify(iter, lhead) \ + for (AssertVariableIsOfTypeMacro(iter, slist_mutable_iter), \ + AssertVariableIsOfTypeMacro(lhead, slist_head *), \ + (iter).prev = &(lhead)->head, \ + (iter).cur = (iter).prev->next, \ + (iter).next = (iter).cur ? (iter).cur->next : NULL; \ + (iter).cur != NULL; \ + (iter).prev = (iter).cur, \ + (iter).cur = (iter).next, \ + (iter).next = (iter).next ? (iter).next->next : NULL) + +#endif /* ILIST_H */ diff --git a/src/include/lib/integerset.h b/src/include/lib/integerset.h new file mode 100644 index 0000000..d7f711e --- /dev/null +++ b/src/include/lib/integerset.h @@ -0,0 +1,24 @@ +/* + * integerset.h + * In-memory data structure to hold a large set of integers efficiently + * + * Portions Copyright (c) 2012-2023, PostgreSQL Global Development Group + * + * src/include/lib/integerset.h + */ +#ifndef INTEGERSET_H +#define INTEGERSET_H + +typedef struct IntegerSet IntegerSet; + +extern IntegerSet *intset_create(void); +extern void intset_add_member(IntegerSet *intset, uint64 x); +extern bool intset_is_member(IntegerSet *intset, uint64 x); + +extern uint64 intset_num_entries(IntegerSet *intset); +extern uint64 intset_memory_usage(IntegerSet *intset); + +extern void intset_begin_iterate(IntegerSet *intset); +extern bool intset_iterate_next(IntegerSet *intset, uint64 *next); + +#endif /* INTEGERSET_H */ diff --git a/src/include/lib/knapsack.h b/src/include/lib/knapsack.h new file mode 100644 index 0000000..04427ba --- /dev/null +++ b/src/include/lib/knapsack.h @@ -0,0 +1,16 @@ +/* + * knapsack.h + * + * Copyright (c) 2017-2023, PostgreSQL Global Development Group + * + * src/include/lib/knapsack.h + */ +#ifndef KNAPSACK_H +#define KNAPSACK_H + +#include "nodes/bitmapset.h" + +extern Bitmapset *DiscreteKnapsack(int max_weight, int num_items, + int *item_weights, double *item_values); + +#endif /* KNAPSACK_H */ diff --git a/src/include/lib/pairingheap.h b/src/include/lib/pairingheap.h new file mode 100644 index 0000000..5691e10 --- /dev/null +++ b/src/include/lib/pairingheap.h @@ -0,0 +1,102 @@ +/* + * pairingheap.h + * + * A Pairing Heap implementation + * + * Portions Copyright (c) 2012-2023, PostgreSQL Global Development Group + * + * src/include/lib/pairingheap.h + */ + +#ifndef PAIRINGHEAP_H +#define PAIRINGHEAP_H + +#include "lib/stringinfo.h" + +/* Enable if you need the pairingheap_dump() debug function */ +/* #define PAIRINGHEAP_DEBUG */ + +/* + * This represents an element stored in the heap. Embed this in a larger + * struct containing the actual data you're storing. + * + * A node can have multiple children, which form a double-linked list. + * first_child points to the node's first child, and the subsequent children + * can be found by following the next_sibling pointers. The last child has + * next_sibling == NULL. The prev_or_parent pointer points to the node's + * previous sibling, or if the node is its parent's first child, to the + * parent. + */ +typedef struct pairingheap_node +{ + struct pairingheap_node *first_child; + struct pairingheap_node *next_sibling; + struct pairingheap_node *prev_or_parent; +} pairingheap_node; + +/* + * Return the containing struct of 'type' where 'membername' is the + * pairingheap_node pointed at by 'ptr'. + * + * This is used to convert a pairingheap_node * back to its containing struct. + */ +#define pairingheap_container(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(ptr, pairingheap_node *), \ + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \ + ((type *) ((char *) (ptr) - offsetof(type, membername)))) + +/* + * Like pairingheap_container, but used when the pointer is 'const ptr' + */ +#define pairingheap_const_container(type, membername, ptr) \ + (AssertVariableIsOfTypeMacro(ptr, const pairingheap_node *), \ + AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node), \ + ((const type *) ((const char *) (ptr) - offsetof(type, membername)))) + +/* + * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b, + * and >0 iff a > b. For a min-heap, the conditions are reversed. + */ +typedef int (*pairingheap_comparator) (const pairingheap_node *a, + const pairingheap_node *b, + void *arg); + +/* + * A pairing heap. + * + * You can use pairingheap_allocate() to create a new palloc'd heap, or embed + * this in a larger struct, set ph_compare and ph_arg directly and initialize + * ph_root to NULL. + */ +typedef struct pairingheap +{ + pairingheap_comparator ph_compare; /* comparison function */ + void *ph_arg; /* opaque argument to ph_compare */ + pairingheap_node *ph_root; /* current root of the heap */ +} pairingheap; + +extern pairingheap *pairingheap_allocate(pairingheap_comparator compare, + void *arg); +extern void pairingheap_free(pairingheap *heap); +extern void pairingheap_add(pairingheap *heap, pairingheap_node *node); +extern pairingheap_node *pairingheap_first(pairingheap *heap); +extern pairingheap_node *pairingheap_remove_first(pairingheap *heap); +extern void pairingheap_remove(pairingheap *heap, pairingheap_node *node); + +#ifdef PAIRINGHEAP_DEBUG +extern char *pairingheap_dump(pairingheap *heap, + void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque), + void *opaque); +#endif + +/* Resets the heap to be empty. */ +#define pairingheap_reset(h) ((h)->ph_root = NULL) + +/* Is the heap empty? */ +#define pairingheap_is_empty(h) ((h)->ph_root == NULL) + +/* Is there exactly one node in the heap? */ +#define pairingheap_is_singular(h) \ + ((h)->ph_root && (h)->ph_root->first_child == NULL) + +#endif /* PAIRINGHEAP_H */ diff --git a/src/include/lib/qunique.h b/src/include/lib/qunique.h new file mode 100644 index 0000000..30b67c7 --- /dev/null +++ b/src/include/lib/qunique.h @@ -0,0 +1,67 @@ +/*------------------------------------------------------------------------- + * + * qunique.h + * inline array unique functions + * Portions Copyright (c) 2019-2023, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/include/lib/qunique.h + *------------------------------------------------------------------------- + */ + +#ifndef QUNIQUE_H +#define QUNIQUE_H + +/* + * Remove duplicates from a pre-sorted array, according to a user-supplied + * comparator. Usually the array should have been sorted with qsort() using + * the same arguments. Return the new size. + */ +static inline size_t +qunique(void *array, size_t elements, size_t width, + int (*compare) (const void *, const void *)) +{ + char *bytes = (char *) array; + size_t i, + j; + + if (elements <= 1) + return elements; + + for (i = 1, j = 0; i < elements; ++i) + { + if (compare(bytes + i * width, bytes + j * width) != 0 && + ++j != i) + memcpy(bytes + j * width, bytes + i * width, width); + } + + return j + 1; +} + +/* + * Like qunique(), but takes a comparator with an extra user data argument + * which is passed through, for compatibility with qsort_arg(). + */ +static inline size_t +qunique_arg(void *array, size_t elements, size_t width, + int (*compare) (const void *, const void *, void *), + void *arg) +{ + char *bytes = (char *) array; + size_t i, + j; + + if (elements <= 1) + return elements; + + for (i = 1, j = 0; i < elements; ++i) + { + if (compare(bytes + i * width, bytes + j * width, arg) != 0 && + ++j != i) + memcpy(bytes + j * width, bytes + i * width, width); + } + + return j + 1; +} + +#endif /* QUNIQUE_H */ diff --git a/src/include/lib/rbtree.h b/src/include/lib/rbtree.h new file mode 100644 index 0000000..b339d6e --- /dev/null +++ b/src/include/lib/rbtree.h @@ -0,0 +1,81 @@ +/*------------------------------------------------------------------------- + * + * rbtree.h + * interface for PostgreSQL generic Red-Black binary tree package + * + * Copyright (c) 2009-2023, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/include/lib/rbtree.h + * + *------------------------------------------------------------------------- + */ +#ifndef RBTREE_H +#define RBTREE_H + +/* + * RBTNode is intended to be used as the first field of a larger struct, + * whose additional fields carry whatever payload data the caller needs + * for a tree entry. (The total size of that larger struct is passed to + * rbt_create.) RBTNode is declared here to support this usage, but + * callers must treat it as an opaque struct. + */ +typedef struct RBTNode +{ + char color; /* node's current color, red or black */ + struct RBTNode *left; /* left child, or RBTNIL if none */ + struct RBTNode *right; /* right child, or RBTNIL if none */ + struct RBTNode *parent; /* parent, or NULL (not RBTNIL!) if none */ +} RBTNode; + +/* Opaque struct representing a whole tree */ +typedef struct RBTree RBTree; + +/* Available tree iteration orderings */ +typedef enum RBTOrderControl +{ + LeftRightWalk, /* inorder: left child, node, right child */ + RightLeftWalk /* reverse inorder: right, node, left */ +} RBTOrderControl; + +/* + * RBTreeIterator holds state while traversing a tree. This is declared + * here so that callers can stack-allocate this, but must otherwise be + * treated as an opaque struct. + */ +typedef struct RBTreeIterator RBTreeIterator; + +struct RBTreeIterator +{ + RBTree *rbt; + RBTNode *(*iterate) (RBTreeIterator *iter); + RBTNode *last_visited; + bool is_over; +}; + +/* Support functions to be provided by caller */ +typedef int (*rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg); +typedef void (*rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg); +typedef RBTNode *(*rbt_allocfunc) (void *arg); +typedef void (*rbt_freefunc) (RBTNode *x, void *arg); + +extern RBTree *rbt_create(Size node_size, + rbt_comparator comparator, + rbt_combiner combiner, + rbt_allocfunc allocfunc, + rbt_freefunc freefunc, + void *arg); + +extern RBTNode *rbt_find(RBTree *rbt, const RBTNode *data); +extern RBTNode *rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match); +extern RBTNode *rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match); +extern RBTNode *rbt_leftmost(RBTree *rbt); + +extern RBTNode *rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew); +extern void rbt_delete(RBTree *rbt, RBTNode *node); + +extern void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, + RBTreeIterator *iter); +extern RBTNode *rbt_iterate(RBTreeIterator *iter); + +#endif /* RBTREE_H */ diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h new file mode 100644 index 0000000..b7adc16 --- /dev/null +++ b/src/include/lib/simplehash.h @@ -0,0 +1,1184 @@ +/* + * simplehash.h + * + * When included this file generates a "templated" (by way of macros) + * open-addressing hash table implementation specialized to user-defined + * types. + * + * It's probably not worthwhile to generate such a specialized implementation + * for hash tables that aren't performance or space sensitive. + * + * Compared to dynahash, simplehash has the following benefits: + * + * - Due to the "templated" code generation has known structure sizes and no + * indirect function calls (which show up substantially in dynahash + * profiles). These features considerably increase speed for small + * entries. + * - Open addressing has better CPU cache behavior than dynahash's chained + * hashtables. + * - The generated interface is type-safe and easier to use than dynahash, + * though at the cost of more complex setup. + * - Allocates memory in a MemoryContext or another allocator with a + * malloc/free style interface (which isn't easily usable in a shared + * memory context) + * - Does not require the overhead of a separate memory context. + * + * Usage notes: + * + * To generate a hash-table and associated functions for a use case several + * macros have to be #define'ed before this file is included. Including + * the file #undef's all those, so a new hash table can be generated + * afterwards. + * The relevant parameters are: + * - SH_PREFIX - prefix for all symbol names generated. A prefix of 'foo' + * will result in hash table type 'foo_hash' and functions like + * 'foo_insert'/'foo_lookup' and so forth. + * - SH_ELEMENT_TYPE - type of the contained elements + * - SH_KEY_TYPE - type of the hashtable's key + * - SH_DECLARE - if defined function prototypes and type declarations are + * generated + * - SH_DEFINE - if defined function definitions are generated + * - SH_SCOPE - in which scope (e.g. extern, static inline) do function + * declarations reside + * - SH_RAW_ALLOCATOR - if defined, memory contexts are not used; instead, + * use this to allocate bytes. The allocator must zero the returned space. + * - SH_USE_NONDEFAULT_ALLOCATOR - if defined no element allocator functions + * are defined, so you can supply your own + * The following parameters are only relevant when SH_DEFINE is defined: + * - SH_KEY - name of the element in SH_ELEMENT_TYPE containing the hash key + * - SH_EQUAL(table, a, b) - compare two table keys + * - SH_HASH_KEY(table, key) - generate hash for the key + * - SH_STORE_HASH - if defined the hash is stored in the elements + * - SH_GET_HASH(tb, a) - return the field to store the hash in + * + * The element type is required to contain a "status" member that can store + * the range of values defined in the SH_STATUS enum. + * + * While SH_STORE_HASH (and subsequently SH_GET_HASH) are optional, because + * the hash table implementation needs to compare hashes to move elements + * (particularly when growing the hash), it's preferable, if possible, to + * store the element's hash in the element's data type. If the hash is so + * stored, the hash table will also compare hashes before calling SH_EQUAL + * when comparing two keys. + * + * For convenience the hash table create functions accept a void pointer + * that will be stored in the hash table type's member private_data. This + * allows callbacks to reference caller provided data. + * + * For examples of usage look at tidbitmap.c (file local definition) and + * execnodes.h/execGrouping.c (exposed declaration, file local + * implementation). + * + * Hash table design: + * + * The hash table design chosen is a variant of linear open-addressing. The + * reason for doing so is that linear addressing is CPU cache & pipeline + * friendly. The biggest disadvantage of simple linear addressing schemes + * are highly variable lookup times due to clustering, and deletions + * leaving a lot of tombstones around. To address these issues a variant + * of "robin hood" hashing is employed. Robin hood hashing optimizes + * chaining lengths by moving elements close to their optimal bucket + * ("rich" elements), out of the way if a to-be-inserted element is further + * away from its optimal position (i.e. it's "poor"). While that can make + * insertions slower, the average lookup performance is a lot better, and + * higher fill factors can be used in a still performant manner. To avoid + * tombstones - which normally solve the issue that a deleted node's + * presence is relevant to determine whether a lookup needs to continue + * looking or is done - buckets following a deleted element are shifted + * backwards, unless they're empty or already at their optimal position. + * + * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * src/include/lib/simplehash.h + */ + +#include "port/pg_bitutils.h" + +/* helpers */ +#define SH_MAKE_PREFIX(a) CppConcat(a,_) +#define SH_MAKE_NAME(name) SH_MAKE_NAME_(SH_MAKE_PREFIX(SH_PREFIX),name) +#define SH_MAKE_NAME_(a,b) CppConcat(a,b) + +/* name macros for: */ + +/* type declarations */ +#define SH_TYPE SH_MAKE_NAME(hash) +#define SH_STATUS SH_MAKE_NAME(status) +#define SH_STATUS_EMPTY SH_MAKE_NAME(SH_EMPTY) +#define SH_STATUS_IN_USE SH_MAKE_NAME(SH_IN_USE) +#define SH_ITERATOR SH_MAKE_NAME(iterator) + +/* function declarations */ +#define SH_CREATE SH_MAKE_NAME(create) +#define SH_DESTROY SH_MAKE_NAME(destroy) +#define SH_RESET SH_MAKE_NAME(reset) +#define SH_INSERT SH_MAKE_NAME(insert) +#define SH_INSERT_HASH SH_MAKE_NAME(insert_hash) +#define SH_DELETE_ITEM SH_MAKE_NAME(delete_item) +#define SH_DELETE SH_MAKE_NAME(delete) +#define SH_LOOKUP SH_MAKE_NAME(lookup) +#define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash) +#define SH_GROW SH_MAKE_NAME(grow) +#define SH_START_ITERATE SH_MAKE_NAME(start_iterate) +#define SH_START_ITERATE_AT SH_MAKE_NAME(start_iterate_at) +#define SH_ITERATE SH_MAKE_NAME(iterate) +#define SH_ALLOCATE SH_MAKE_NAME(allocate) +#define SH_FREE SH_MAKE_NAME(free) +#define SH_STAT SH_MAKE_NAME(stat) + +/* internal helper functions (no externally visible prototypes) */ +#define SH_COMPUTE_PARAMETERS SH_MAKE_NAME(compute_parameters) +#define SH_NEXT SH_MAKE_NAME(next) +#define SH_PREV SH_MAKE_NAME(prev) +#define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance) +#define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket) +#define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash) +#define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal) +#define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal) + +/* generate forward declarations necessary to use the hash table */ +#ifdef SH_DECLARE + +/* type definitions */ +typedef struct SH_TYPE +{ + /* + * Size of data / bucket array, 64 bits to handle UINT32_MAX sized hash + * tables. Note that the maximum number of elements is lower + * (SH_MAX_FILLFACTOR) + */ + uint64 size; + + /* how many elements have valid contents */ + uint32 members; + + /* mask for bucket and size calculations, based on size */ + uint32 sizemask; + + /* boundary after which to grow hashtable */ + uint32 grow_threshold; + + /* hash buckets */ + SH_ELEMENT_TYPE *data; + +#ifndef SH_RAW_ALLOCATOR + /* memory context to use for allocations */ + MemoryContext ctx; +#endif + + /* user defined data, useful for callbacks */ + void *private_data; +} SH_TYPE; + +typedef enum SH_STATUS +{ + SH_STATUS_EMPTY = 0x00, + SH_STATUS_IN_USE = 0x01 +} SH_STATUS; + +typedef struct SH_ITERATOR +{ + uint32 cur; /* current element */ + uint32 end; + bool done; /* iterator exhausted? */ +} SH_ITERATOR; + +/* externally visible function prototypes */ +#ifdef SH_RAW_ALLOCATOR +/* _hash _create(uint32 nelements, void *private_data) */ +SH_SCOPE SH_TYPE *SH_CREATE(uint32 nelements, void *private_data); +#else +/* + * _hash _create(MemoryContext ctx, uint32 nelements, + * void *private_data) + */ +SH_SCOPE SH_TYPE *SH_CREATE(MemoryContext ctx, uint32 nelements, + void *private_data); +#endif + +/* void _destroy(_hash *tb) */ +SH_SCOPE void SH_DESTROY(SH_TYPE * tb); + +/* void _reset(_hash *tb) */ +SH_SCOPE void SH_RESET(SH_TYPE * tb); + +/* void _grow(_hash *tb, uint64 newsize) */ +SH_SCOPE void SH_GROW(SH_TYPE * tb, uint64 newsize); + +/* *_insert(_hash *tb, key, bool *found) */ +SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found); + +/* + * *_insert_hash(_hash *tb, key, uint32 hash, + * bool *found) + */ +SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, + uint32 hash, bool *found); + +/* *_lookup(_hash *tb, key) */ +SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key); + +/* *_lookup_hash(_hash *tb, key, uint32 hash) */ +SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, + uint32 hash); + +/* void _delete_item(_hash *tb, *entry) */ +SH_SCOPE void SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry); + +/* bool _delete(_hash *tb, key) */ +SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key); + +/* void _start_iterate(_hash *tb, _iterator *iter) */ +SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter); + +/* + * void _start_iterate_at(_hash *tb, _iterator *iter, + * uint32 at) + */ +SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at); + +/* *_iterate(_hash *tb, _iterator *iter) */ +SH_SCOPE SH_ELEMENT_TYPE *SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter); + +/* void _stat(_hash *tb */ +SH_SCOPE void SH_STAT(SH_TYPE * tb); + +#endif /* SH_DECLARE */ + + +/* generate implementation of the hash table */ +#ifdef SH_DEFINE + +#ifndef SH_RAW_ALLOCATOR +#include "utils/memutils.h" +#endif + +/* max data array size,we allow up to PG_UINT32_MAX buckets, including 0 */ +#define SH_MAX_SIZE (((uint64) PG_UINT32_MAX) + 1) + +/* normal fillfactor, unless already close to maximum */ +#ifndef SH_FILLFACTOR +#define SH_FILLFACTOR (0.9) +#endif +/* increase fillfactor if we otherwise would error out */ +#define SH_MAX_FILLFACTOR (0.98) +/* grow if actual and optimal location bigger than */ +#ifndef SH_GROW_MAX_DIB +#define SH_GROW_MAX_DIB 25 +#endif +/* grow if more than elements to move when inserting */ +#ifndef SH_GROW_MAX_MOVE +#define SH_GROW_MAX_MOVE 150 +#endif +#ifndef SH_GROW_MIN_FILLFACTOR +/* but do not grow due to SH_GROW_MAX_* if below */ +#define SH_GROW_MIN_FILLFACTOR 0.1 +#endif + +#ifdef SH_STORE_HASH +#define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey)) +#else +#define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey)) +#endif + +/* + * Wrap the following definitions in include guards, to avoid multiple + * definition errors if this header is included more than once. The rest of + * the file deliberately has no include guards, because it can be included + * with different parameters to define functions and types with non-colliding + * names. + */ +#ifndef SIMPLEHASH_H +#define SIMPLEHASH_H + +#ifdef FRONTEND +#define sh_error(...) pg_fatal(__VA_ARGS__) +#define sh_log(...) pg_log_info(__VA_ARGS__) +#else +#define sh_error(...) elog(ERROR, __VA_ARGS__) +#define sh_log(...) elog(LOG, __VA_ARGS__) +#endif + +#endif + +/* + * Compute sizing parameters for hashtable. Called when creating and growing + * the hashtable. + */ +static inline void +SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint64 newsize) +{ + uint64 size; + + /* supporting zero sized hashes would complicate matters */ + size = Max(newsize, 2); + + /* round up size to the next power of 2, that's how bucketing works */ + size = pg_nextpower2_64(size); + Assert(size <= SH_MAX_SIZE); + + /* + * Verify that allocation of ->data is possible on this platform, without + * overflowing Size. + */ + if (unlikely((((uint64) sizeof(SH_ELEMENT_TYPE)) * size) >= SIZE_MAX / 2)) + sh_error("hash table too large"); + + /* now set size */ + tb->size = size; + tb->sizemask = (uint32) (size - 1); + + /* + * Compute the next threshold at which we need to grow the hash table + * again. + */ + if (tb->size == SH_MAX_SIZE) + tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR; + else + tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR; +} + +/* return the optimal bucket for the hash */ +static inline uint32 +SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash) +{ + return hash & tb->sizemask; +} + +/* return next bucket after the current, handling wraparound */ +static inline uint32 +SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem) +{ + curelem = (curelem + 1) & tb->sizemask; + + Assert(curelem != startelem); + + return curelem; +} + +/* return bucket before the current, handling wraparound */ +static inline uint32 +SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem) +{ + curelem = (curelem - 1) & tb->sizemask; + + Assert(curelem != startelem); + + return curelem; +} + +/* return distance between bucket and its optimal position */ +static inline uint32 +SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket) +{ + if (optimal <= bucket) + return bucket - optimal; + else + return (tb->size + bucket) - optimal; +} + +static inline uint32 +SH_ENTRY_HASH(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) +{ +#ifdef SH_STORE_HASH + return SH_GET_HASH(tb, entry); +#else + return SH_HASH_KEY(tb, entry->SH_KEY); +#endif +} + +/* default memory allocator function */ +static inline void *SH_ALLOCATE(SH_TYPE * type, Size size); +static inline void SH_FREE(SH_TYPE * type, void *pointer); + +#ifndef SH_USE_NONDEFAULT_ALLOCATOR + +/* default memory allocator function */ +static inline void * +SH_ALLOCATE(SH_TYPE * type, Size size) +{ +#ifdef SH_RAW_ALLOCATOR + return SH_RAW_ALLOCATOR(size); +#else + return MemoryContextAllocExtended(type->ctx, size, + MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO); +#endif +} + +/* default memory free function */ +static inline void +SH_FREE(SH_TYPE * type, void *pointer) +{ + pfree(pointer); +} + +#endif + +/* + * Create a hash table with enough space for `nelements` distinct members. + * Memory for the hash table is allocated from the passed-in context. If + * desired, the array of elements can be allocated using a passed-in allocator; + * this could be useful in order to place the array of elements in a shared + * memory, or in a context that will outlive the rest of the hash table. + * Memory other than for the array of elements will still be allocated from + * the passed-in context. + */ +#ifdef SH_RAW_ALLOCATOR +SH_SCOPE SH_TYPE * +SH_CREATE(uint32 nelements, void *private_data) +#else +SH_SCOPE SH_TYPE * +SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data) +#endif +{ + SH_TYPE *tb; + uint64 size; + +#ifdef SH_RAW_ALLOCATOR + tb = (SH_TYPE *) SH_RAW_ALLOCATOR(sizeof(SH_TYPE)); +#else + tb = (SH_TYPE *) MemoryContextAllocZero(ctx, sizeof(SH_TYPE)); + tb->ctx = ctx; +#endif + tb->private_data = private_data; + + /* increase nelements by fillfactor, want to store nelements elements */ + size = Min((double) SH_MAX_SIZE, ((double) nelements) / SH_FILLFACTOR); + + SH_COMPUTE_PARAMETERS(tb, size); + + tb->data = (SH_ELEMENT_TYPE *) SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size); + + return tb; +} + +/* destroy a previously created hash table */ +SH_SCOPE void +SH_DESTROY(SH_TYPE * tb) +{ + SH_FREE(tb, tb->data); + pfree(tb); +} + +/* reset the contents of a previously created hash table */ +SH_SCOPE void +SH_RESET(SH_TYPE * tb) +{ + memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size); + tb->members = 0; +} + +/* + * Grow a hash table to at least `newsize` buckets. + * + * Usually this will automatically be called by insertions/deletions, when + * necessary. But resizing to the exact input size can be advantageous + * performance-wise, when known at some point. + */ +SH_SCOPE void +SH_GROW(SH_TYPE * tb, uint64 newsize) +{ + uint64 oldsize = tb->size; + SH_ELEMENT_TYPE *olddata = tb->data; + SH_ELEMENT_TYPE *newdata; + uint32 i; + uint32 startelem = 0; + uint32 copyelem; + + Assert(oldsize == pg_nextpower2_64(oldsize)); + Assert(oldsize != SH_MAX_SIZE); + Assert(oldsize < newsize); + + /* compute parameters for new table */ + SH_COMPUTE_PARAMETERS(tb, newsize); + + tb->data = (SH_ELEMENT_TYPE *) SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size); + + newdata = tb->data; + + /* + * Copy entries from the old data to newdata. We theoretically could use + * SH_INSERT here, to avoid code duplication, but that's more general than + * we need. We neither want tb->members increased, nor do we need to do + * deal with deleted elements, nor do we need to compare keys. So a + * special-cased implementation is lot faster. As resizing can be time + * consuming and frequent, that's worthwhile to optimize. + * + * To be able to simply move entries over, we have to start not at the + * first bucket (i.e olddata[0]), but find the first bucket that's either + * empty, or is occupied by an entry at its optimal position. Such a + * bucket has to exist in any table with a load factor under 1, as not all + * buckets are occupied, i.e. there always has to be an empty bucket. By + * starting at such a bucket we can move the entries to the larger table, + * without having to deal with conflicts. + */ + + /* search for the first element in the hash that's not wrapped around */ + for (i = 0; i < oldsize; i++) + { + SH_ELEMENT_TYPE *oldentry = &olddata[i]; + uint32 hash; + uint32 optimal; + + if (oldentry->status != SH_STATUS_IN_USE) + { + startelem = i; + break; + } + + hash = SH_ENTRY_HASH(tb, oldentry); + optimal = SH_INITIAL_BUCKET(tb, hash); + + if (optimal == i) + { + startelem = i; + break; + } + } + + /* and copy all elements in the old table */ + copyelem = startelem; + for (i = 0; i < oldsize; i++) + { + SH_ELEMENT_TYPE *oldentry = &olddata[copyelem]; + + if (oldentry->status == SH_STATUS_IN_USE) + { + uint32 hash; + uint32 startelem2; + uint32 curelem; + SH_ELEMENT_TYPE *newentry; + + hash = SH_ENTRY_HASH(tb, oldentry); + startelem2 = SH_INITIAL_BUCKET(tb, hash); + curelem = startelem2; + + /* find empty element to put data into */ + while (true) + { + newentry = &newdata[curelem]; + + if (newentry->status == SH_STATUS_EMPTY) + { + break; + } + + curelem = SH_NEXT(tb, curelem, startelem2); + } + + /* copy entry to new slot */ + memcpy(newentry, oldentry, sizeof(SH_ELEMENT_TYPE)); + } + + /* can't use SH_NEXT here, would use new size */ + copyelem++; + if (copyelem >= oldsize) + { + copyelem = 0; + } + } + + SH_FREE(tb, olddata); +} + +/* + * This is a separate static inline function, so it can be reliably be inlined + * into its wrapper functions even if SH_SCOPE is extern. + */ +static inline SH_ELEMENT_TYPE * +SH_INSERT_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found) +{ + uint32 startelem; + uint32 curelem; + SH_ELEMENT_TYPE *data; + uint32 insertdist; + +restart: + insertdist = 0; + + /* + * We do the grow check even if the key is actually present, to avoid + * doing the check inside the loop. This also lets us avoid having to + * re-find our position in the hashtable after resizing. + * + * Note that this also reached when resizing the table due to + * SH_GROW_MAX_DIB / SH_GROW_MAX_MOVE. + */ + if (unlikely(tb->members >= tb->grow_threshold)) + { + if (unlikely(tb->size == SH_MAX_SIZE)) + sh_error("hash table size exceeded"); + + /* + * When optimizing, it can be very useful to print these out. + */ + /* SH_STAT(tb); */ + SH_GROW(tb, tb->size * 2); + /* SH_STAT(tb); */ + } + + /* perform insert, start bucket search at optimal location */ + data = tb->data; + startelem = SH_INITIAL_BUCKET(tb, hash); + curelem = startelem; + while (true) + { + uint32 curdist; + uint32 curhash; + uint32 curoptimal; + SH_ELEMENT_TYPE *entry = &data[curelem]; + + /* any empty bucket can directly be used */ + if (entry->status == SH_STATUS_EMPTY) + { + tb->members++; + entry->SH_KEY = key; +#ifdef SH_STORE_HASH + SH_GET_HASH(tb, entry) = hash; +#endif + entry->status = SH_STATUS_IN_USE; + *found = false; + return entry; + } + + /* + * If the bucket is not empty, we either found a match (in which case + * we're done), or we have to decide whether to skip over or move the + * colliding entry. When the colliding element's distance to its + * optimal position is smaller than the to-be-inserted entry's, we + * shift the colliding entry (and its followers) forward by one. + */ + + if (SH_COMPARE_KEYS(tb, hash, key, entry)) + { + Assert(entry->status == SH_STATUS_IN_USE); + *found = true; + return entry; + } + + curhash = SH_ENTRY_HASH(tb, entry); + curoptimal = SH_INITIAL_BUCKET(tb, curhash); + curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem); + + if (insertdist > curdist) + { + SH_ELEMENT_TYPE *lastentry = entry; + uint32 emptyelem = curelem; + uint32 moveelem; + int32 emptydist = 0; + + /* find next empty bucket */ + while (true) + { + SH_ELEMENT_TYPE *emptyentry; + + emptyelem = SH_NEXT(tb, emptyelem, startelem); + emptyentry = &data[emptyelem]; + + if (emptyentry->status == SH_STATUS_EMPTY) + { + lastentry = emptyentry; + break; + } + + /* + * To avoid negative consequences from overly imbalanced + * hashtables, grow the hashtable if collisions would require + * us to move a lot of entries. The most likely cause of such + * imbalance is filling a (currently) small table, from a + * currently big one, in hash-table order. Don't grow if the + * hashtable would be too empty, to prevent quick space + * explosion for some weird edge cases. + */ + if (unlikely(++emptydist > SH_GROW_MAX_MOVE) && + ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR) + { + tb->grow_threshold = 0; + goto restart; + } + } + + /* shift forward, starting at last occupied element */ + + /* + * TODO: This could be optimized to be one memcpy in many cases, + * excepting wrapping around at the end of ->data. Hasn't shown up + * in profiles so far though. + */ + moveelem = emptyelem; + while (moveelem != curelem) + { + SH_ELEMENT_TYPE *moveentry; + + moveelem = SH_PREV(tb, moveelem, startelem); + moveentry = &data[moveelem]; + + memcpy(lastentry, moveentry, sizeof(SH_ELEMENT_TYPE)); + lastentry = moveentry; + } + + /* and fill the now empty spot */ + tb->members++; + + entry->SH_KEY = key; +#ifdef SH_STORE_HASH + SH_GET_HASH(tb, entry) = hash; +#endif + entry->status = SH_STATUS_IN_USE; + *found = false; + return entry; + } + + curelem = SH_NEXT(tb, curelem, startelem); + insertdist++; + + /* + * To avoid negative consequences from overly imbalanced hashtables, + * grow the hashtable if collisions lead to large runs. The most + * likely cause of such imbalance is filling a (currently) small + * table, from a currently big one, in hash-table order. Don't grow + * if the hashtable would be too empty, to prevent quick space + * explosion for some weird edge cases. + */ + if (unlikely(insertdist > SH_GROW_MAX_DIB) && + ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR) + { + tb->grow_threshold = 0; + goto restart; + } + } +} + +/* + * Insert the key key into the hash-table, set *found to true if the key + * already exists, false otherwise. Returns the hash-table entry in either + * case. + */ +SH_SCOPE SH_ELEMENT_TYPE * +SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found) +{ + uint32 hash = SH_HASH_KEY(tb, key); + + return SH_INSERT_HASH_INTERNAL(tb, key, hash, found); +} + +/* + * Insert the key key into the hash-table using an already-calculated + * hash. Set *found to true if the key already exists, false + * otherwise. Returns the hash-table entry in either case. + */ +SH_SCOPE SH_ELEMENT_TYPE * +SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found) +{ + return SH_INSERT_HASH_INTERNAL(tb, key, hash, found); +} + +/* + * This is a separate static inline function, so it can be reliably be inlined + * into its wrapper functions even if SH_SCOPE is extern. + */ +static inline SH_ELEMENT_TYPE * +SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash) +{ + const uint32 startelem = SH_INITIAL_BUCKET(tb, hash); + uint32 curelem = startelem; + + while (true) + { + SH_ELEMENT_TYPE *entry = &tb->data[curelem]; + + if (entry->status == SH_STATUS_EMPTY) + { + return NULL; + } + + Assert(entry->status == SH_STATUS_IN_USE); + + if (SH_COMPARE_KEYS(tb, hash, key, entry)) + return entry; + + /* + * TODO: we could stop search based on distance. If the current + * buckets's distance-from-optimal is smaller than what we've skipped + * already, the entry doesn't exist. Probably only do so if + * SH_STORE_HASH is defined, to avoid re-computing hashes? + */ + + curelem = SH_NEXT(tb, curelem, startelem); + } +} + +/* + * Lookup entry in hash table. Returns NULL if key not present. + */ +SH_SCOPE SH_ELEMENT_TYPE * +SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key) +{ + uint32 hash = SH_HASH_KEY(tb, key); + + return SH_LOOKUP_HASH_INTERNAL(tb, key, hash); +} + +/* + * Lookup entry in hash table using an already-calculated hash. + * + * Returns NULL if key not present. + */ +SH_SCOPE SH_ELEMENT_TYPE * +SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash) +{ + return SH_LOOKUP_HASH_INTERNAL(tb, key, hash); +} + +/* + * Delete entry from hash table by key. Returns whether to-be-deleted key was + * present. + */ +SH_SCOPE bool +SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) +{ + uint32 hash = SH_HASH_KEY(tb, key); + uint32 startelem = SH_INITIAL_BUCKET(tb, hash); + uint32 curelem = startelem; + + while (true) + { + SH_ELEMENT_TYPE *entry = &tb->data[curelem]; + + if (entry->status == SH_STATUS_EMPTY) + return false; + + if (entry->status == SH_STATUS_IN_USE && + SH_COMPARE_KEYS(tb, hash, key, entry)) + { + SH_ELEMENT_TYPE *lastentry = entry; + + tb->members--; + + /* + * Backward shift following elements till either an empty element + * or an element at its optimal position is encountered. + * + * While that sounds expensive, the average chain length is short, + * and deletions would otherwise require tombstones. + */ + while (true) + { + SH_ELEMENT_TYPE *curentry; + uint32 curhash; + uint32 curoptimal; + + curelem = SH_NEXT(tb, curelem, startelem); + curentry = &tb->data[curelem]; + + if (curentry->status != SH_STATUS_IN_USE) + { + lastentry->status = SH_STATUS_EMPTY; + break; + } + + curhash = SH_ENTRY_HASH(tb, curentry); + curoptimal = SH_INITIAL_BUCKET(tb, curhash); + + /* current is at optimal position, done */ + if (curoptimal == curelem) + { + lastentry->status = SH_STATUS_EMPTY; + break; + } + + /* shift */ + memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE)); + + lastentry = curentry; + } + + return true; + } + + /* TODO: return false; if distance too big */ + + curelem = SH_NEXT(tb, curelem, startelem); + } +} + +/* + * Delete entry from hash table by entry pointer + */ +SH_SCOPE void +SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) +{ + SH_ELEMENT_TYPE *lastentry = entry; + uint32 hash = SH_ENTRY_HASH(tb, entry); + uint32 startelem = SH_INITIAL_BUCKET(tb, hash); + uint32 curelem; + + /* Calculate the index of 'entry' */ + curelem = entry - &tb->data[0]; + + tb->members--; + + /* + * Backward shift following elements till either an empty element or an + * element at its optimal position is encountered. + * + * While that sounds expensive, the average chain length is short, and + * deletions would otherwise require tombstones. + */ + while (true) + { + SH_ELEMENT_TYPE *curentry; + uint32 curhash; + uint32 curoptimal; + + curelem = SH_NEXT(tb, curelem, startelem); + curentry = &tb->data[curelem]; + + if (curentry->status != SH_STATUS_IN_USE) + { + lastentry->status = SH_STATUS_EMPTY; + break; + } + + curhash = SH_ENTRY_HASH(tb, curentry); + curoptimal = SH_INITIAL_BUCKET(tb, curhash); + + /* current is at optimal position, done */ + if (curoptimal == curelem) + { + lastentry->status = SH_STATUS_EMPTY; + break; + } + + /* shift */ + memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE)); + + lastentry = curentry; + } +} + +/* + * Initialize iterator. + */ +SH_SCOPE void +SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) +{ + uint64 startelem = PG_UINT64_MAX; + + /* + * Search for the first empty element. As deletions during iterations are + * supported, we want to start/end at an element that cannot be affected + * by elements being shifted. + */ + for (uint32 i = 0; i < tb->size; i++) + { + SH_ELEMENT_TYPE *entry = &tb->data[i]; + + if (entry->status != SH_STATUS_IN_USE) + { + startelem = i; + break; + } + } + + /* we should have found an empty element */ + Assert(startelem < SH_MAX_SIZE); + + /* + * Iterate backwards, that allows the current element to be deleted, even + * if there are backward shifts + */ + iter->cur = startelem; + iter->end = iter->cur; + iter->done = false; +} + +/* + * Initialize iterator to a specific bucket. That's really only useful for + * cases where callers are partially iterating over the hashspace, and that + * iteration deletes and inserts elements based on visited entries. Doing that + * repeatedly could lead to an unbalanced keyspace when always starting at the + * same position. + */ +SH_SCOPE void +SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at) +{ + /* + * Iterate backwards, that allows the current element to be deleted, even + * if there are backward shifts. + */ + iter->cur = at & tb->sizemask; /* ensure at is within a valid range */ + iter->end = iter->cur; + iter->done = false; +} + +/* + * Iterate over all entries in the hash-table. Return the next occupied entry, + * or NULL if done. + * + * During iteration the current entry in the hash table may be deleted, + * without leading to elements being skipped or returned twice. Additionally + * the rest of the table may be modified (i.e. there can be insertions or + * deletions), but if so, there's neither a guarantee that all nodes are + * visited at least once, nor a guarantee that a node is visited at most once. + */ +SH_SCOPE SH_ELEMENT_TYPE * +SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) +{ + while (!iter->done) + { + SH_ELEMENT_TYPE *elem; + + elem = &tb->data[iter->cur]; + + /* next element in backward direction */ + iter->cur = (iter->cur - 1) & tb->sizemask; + + if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask)) + iter->done = true; + if (elem->status == SH_STATUS_IN_USE) + { + return elem; + } + } + + return NULL; +} + +/* + * Report some statistics about the state of the hashtable. For + * debugging/profiling purposes only. + */ +SH_SCOPE void +SH_STAT(SH_TYPE * tb) +{ + uint32 max_chain_length = 0; + uint32 total_chain_length = 0; + double avg_chain_length; + double fillfactor; + uint32 i; + + uint32 *collisions = (uint32 *) palloc0(tb->size * sizeof(uint32)); + uint32 total_collisions = 0; + uint32 max_collisions = 0; + double avg_collisions; + + for (i = 0; i < tb->size; i++) + { + uint32 hash; + uint32 optimal; + uint32 dist; + SH_ELEMENT_TYPE *elem; + + elem = &tb->data[i]; + + if (elem->status != SH_STATUS_IN_USE) + continue; + + hash = SH_ENTRY_HASH(tb, elem); + optimal = SH_INITIAL_BUCKET(tb, hash); + dist = SH_DISTANCE_FROM_OPTIMAL(tb, optimal, i); + + if (dist > max_chain_length) + max_chain_length = dist; + total_chain_length += dist; + + collisions[optimal]++; + } + + for (i = 0; i < tb->size; i++) + { + uint32 curcoll = collisions[i]; + + if (curcoll == 0) + continue; + + /* single contained element is not a collision */ + curcoll--; + total_collisions += curcoll; + if (curcoll > max_collisions) + max_collisions = curcoll; + } + + if (tb->members > 0) + { + fillfactor = tb->members / ((double) tb->size); + avg_chain_length = ((double) total_chain_length) / tb->members; + avg_collisions = ((double) total_collisions) / tb->members; + } + else + { + fillfactor = 0; + avg_chain_length = 0; + avg_collisions = 0; + } + + sh_log("size: " UINT64_FORMAT ", members: %u, filled: %f, total chain: %u, max chain: %u, avg chain: %f, total_collisions: %u, max_collisions: %u, avg_collisions: %f", + tb->size, tb->members, fillfactor, total_chain_length, max_chain_length, avg_chain_length, + total_collisions, max_collisions, avg_collisions); +} + +#endif /* SH_DEFINE */ + + +/* undefine external parameters, so next hash table can be defined */ +#undef SH_PREFIX +#undef SH_KEY_TYPE +#undef SH_KEY +#undef SH_ELEMENT_TYPE +#undef SH_HASH_KEY +#undef SH_SCOPE +#undef SH_DECLARE +#undef SH_DEFINE +#undef SH_GET_HASH +#undef SH_STORE_HASH +#undef SH_USE_NONDEFAULT_ALLOCATOR +#undef SH_EQUAL + +/* undefine locally declared macros */ +#undef SH_MAKE_PREFIX +#undef SH_MAKE_NAME +#undef SH_MAKE_NAME_ +#undef SH_FILLFACTOR +#undef SH_MAX_FILLFACTOR +#undef SH_GROW_MAX_DIB +#undef SH_GROW_MAX_MOVE +#undef SH_GROW_MIN_FILLFACTOR +#undef SH_MAX_SIZE + +/* types */ +#undef SH_TYPE +#undef SH_STATUS +#undef SH_STATUS_EMPTY +#undef SH_STATUS_IN_USE +#undef SH_ITERATOR + +/* external function names */ +#undef SH_CREATE +#undef SH_DESTROY +#undef SH_RESET +#undef SH_INSERT +#undef SH_INSERT_HASH +#undef SH_DELETE_ITEM +#undef SH_DELETE +#undef SH_LOOKUP +#undef SH_LOOKUP_HASH +#undef SH_GROW +#undef SH_START_ITERATE +#undef SH_START_ITERATE_AT +#undef SH_ITERATE +#undef SH_ALLOCATE +#undef SH_FREE +#undef SH_STAT + +/* internal function names */ +#undef SH_COMPUTE_PARAMETERS +#undef SH_COMPARE_KEYS +#undef SH_INITIAL_BUCKET +#undef SH_NEXT +#undef SH_PREV +#undef SH_DISTANCE_FROM_OPTIMAL +#undef SH_ENTRY_HASH +#undef SH_INSERT_HASH_INTERNAL +#undef SH_LOOKUP_HASH_INTERNAL diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h new file mode 100644 index 0000000..1edd05c --- /dev/null +++ b/src/include/lib/sort_template.h @@ -0,0 +1,432 @@ +/*------------------------------------------------------------------------- + * + * sort_template.h + * + * A template for a sort algorithm that supports varying degrees of + * specialization. + * + * Copyright (c) 2021-2023, PostgreSQL Global Development Group + * Portions Copyright (c) 1992-1994, Regents of the University of California + * + * Usage notes: + * + * To generate functions specialized for a type, the following parameter + * macros should be #define'd before this file is included. + * + * - ST_SORT - the name of a sort function to be generated + * - ST_ELEMENT_TYPE - type of the referenced elements + * - ST_DECLARE - if defined the functions and types are declared + * - ST_DEFINE - if defined the functions and types are defined + * - ST_SCOPE - scope (e.g. extern, static inline) for functions + * - ST_CHECK_FOR_INTERRUPTS - if defined the sort is interruptible + * + * Instead of ST_ELEMENT_TYPE, ST_ELEMENT_TYPE_VOID can be defined. Then + * the generated functions will automatically gain an "element_size" + * parameter. This allows us to generate a traditional qsort function. + * + * One of the following macros must be defined, to show how to compare + * elements. The first two options are arbitrary expressions depending + * on whether an extra pass-through argument is desired, and the third + * option should be defined if the sort function should receive a + * function pointer at runtime. + * + * - ST_COMPARE(a, b) - a simple comparison expression + * - ST_COMPARE(a, b, arg) - variant that takes an extra argument + * - ST_COMPARE_RUNTIME_POINTER - sort function takes a function pointer + * + * To say that the comparator and therefore also sort function should + * receive an extra pass-through argument, specify the type of the + * argument. + * + * - ST_COMPARE_ARG_TYPE - type of extra argument + * + * The prototype of the generated sort function is: + * + * void ST_SORT(ST_ELEMENT_TYPE *data, size_t n, + * [size_t element_size,] + * [ST_SORT_compare_function compare,] + * [ST_COMPARE_ARG_TYPE *arg]); + * + * ST_SORT_compare_function is a function pointer of the following type: + * + * int (*)(const ST_ELEMENT_TYPE *a, const ST_ELEMENT_TYPE *b, + * [ST_COMPARE_ARG_TYPE *arg]) + * + * HISTORY + * + * Modifications from vanilla NetBSD source: + * - Add do ... while() macro fix + * - Remove __inline, _DIAGASSERTs, __P + * - Remove ill-considered "swap_cnt" switch to insertion sort, in favor + * of a simple check for presorted input. + * - Take care to recurse on the smaller partition, to bound stack usage + * - Convert into a header that can generate specialized functions + * + * IDENTIFICATION + * src/include/lib/sort_template.h + * + *------------------------------------------------------------------------- + */ + +/* $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $ */ + +/*- + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +/* + * Qsort routine based on J. L. Bentley and M. D. McIlroy, + * "Engineering a sort function", + * Software--Practice and Experience 23 (1993) 1249-1265. + * + * We have modified their original by adding a check for already-sorted + * input, which seems to be a win per discussions on pgsql-hackers around + * 2006-03-21. + * + * Also, we recurse on the smaller partition and iterate on the larger one, + * which ensures we cannot recurse more than log(N) levels (since the + * partition recursed to is surely no more than half of the input). Bentley + * and McIlroy explicitly rejected doing this on the grounds that it's "not + * worth the effort", but we have seen crashes in the field due to stack + * overrun, so that judgment seems wrong. + */ + +#define ST_MAKE_PREFIX(a) CppConcat(a,_) +#define ST_MAKE_NAME(a,b) ST_MAKE_NAME_(ST_MAKE_PREFIX(a),b) +#define ST_MAKE_NAME_(a,b) CppConcat(a,b) + +/* + * If the element type is void, we'll also need an element_size argument + * because we don't know the size. + */ +#ifdef ST_ELEMENT_TYPE_VOID +#define ST_ELEMENT_TYPE void +#define ST_SORT_PROTO_ELEMENT_SIZE , size_t element_size +#define ST_SORT_INVOKE_ELEMENT_SIZE , element_size +#else +#define ST_SORT_PROTO_ELEMENT_SIZE +#define ST_SORT_INVOKE_ELEMENT_SIZE +#endif + +/* + * If the user wants to be able to pass in compare functions at runtime, + * we'll need to make that an argument of the sort and med3 functions. + */ +#ifdef ST_COMPARE_RUNTIME_POINTER +/* + * The type of the comparator function pointer that ST_SORT will take, unless + * you've already declared a type name manually and want to use that instead of + * having a new one defined. + */ +#ifndef ST_COMPARATOR_TYPE_NAME +#define ST_COMPARATOR_TYPE_NAME ST_MAKE_NAME(ST_SORT, compare_function) +#endif +#define ST_COMPARE compare +#ifndef ST_COMPARE_ARG_TYPE +#define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare +#define ST_SORT_INVOKE_COMPARE , compare +#else +#define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare +#define ST_SORT_INVOKE_COMPARE , compare +#endif +#else +#define ST_SORT_PROTO_COMPARE +#define ST_SORT_INVOKE_COMPARE +#endif + +/* + * If the user wants to use a compare function or expression that takes an + * extra argument, we'll need to make that an argument of the sort, compare and + * med3 functions. + */ +#ifdef ST_COMPARE_ARG_TYPE +#define ST_SORT_PROTO_ARG , ST_COMPARE_ARG_TYPE *arg +#define ST_SORT_INVOKE_ARG , arg +#else +#define ST_SORT_PROTO_ARG +#define ST_SORT_INVOKE_ARG +#endif + +#ifdef ST_DECLARE + +#ifdef ST_COMPARE_RUNTIME_POINTER +typedef int (*ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE *, + const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG); +#endif + +/* Declare the sort function. Note optional arguments at end. */ +ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n + ST_SORT_PROTO_ELEMENT_SIZE + ST_SORT_PROTO_COMPARE + ST_SORT_PROTO_ARG); + +#endif + +#ifdef ST_DEFINE + +/* sort private helper functions */ +#define ST_MED3 ST_MAKE_NAME(ST_SORT, med3) +#define ST_SWAP ST_MAKE_NAME(ST_SORT, swap) +#define ST_SWAPN ST_MAKE_NAME(ST_SORT, swapn) + +/* Users expecting to run very large sorts may need them to be interruptible. */ +#ifdef ST_CHECK_FOR_INTERRUPTS +#define DO_CHECK_FOR_INTERRUPTS() CHECK_FOR_INTERRUPTS() +#else +#define DO_CHECK_FOR_INTERRUPTS() +#endif + +/* + * Create wrapper macros that know how to invoke compare, med3 and sort with + * the right arguments. + */ +#ifdef ST_COMPARE_RUNTIME_POINTER +#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG) +#elif defined(ST_COMPARE_ARG_TYPE) +#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg) +#else +#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_)) +#endif +#define DO_MED3(a_, b_, c_) \ + ST_MED3((a_), (b_), (c_) \ + ST_SORT_INVOKE_COMPARE \ + ST_SORT_INVOKE_ARG) +#define DO_SORT(a_, n_) \ + ST_SORT((a_), (n_) \ + ST_SORT_INVOKE_ELEMENT_SIZE \ + ST_SORT_INVOKE_COMPARE \ + ST_SORT_INVOKE_ARG) + +/* + * If we're working with void pointers, we'll use pointer arithmetic based on + * uint8, and use the runtime element_size to step through the array and swap + * elements. Otherwise we'll work with ST_ELEMENT_TYPE. + */ +#ifndef ST_ELEMENT_TYPE_VOID +#define ST_POINTER_TYPE ST_ELEMENT_TYPE +#define ST_POINTER_STEP 1 +#define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_)) +#define DO_SWAP(a_, b_) ST_SWAP((a_), (b_)) +#else +#define ST_POINTER_TYPE uint8 +#define ST_POINTER_STEP element_size +#define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_)) +#define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size) +#endif + +/* + * Find the median of three values. Currently, performance seems to be best + * if the comparator is inlined here, but the med3 function is not inlined + * in the qsort function. + */ +static pg_noinline ST_ELEMENT_TYPE * +ST_MED3(ST_ELEMENT_TYPE * a, + ST_ELEMENT_TYPE * b, + ST_ELEMENT_TYPE * c + ST_SORT_PROTO_COMPARE + ST_SORT_PROTO_ARG) +{ + return DO_COMPARE(a, b) < 0 ? + (DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a)) + : (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c)); +} + +static inline void +ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b) +{ + ST_POINTER_TYPE tmp = *a; + + *a = *b; + *b = tmp; +} + +static inline void +ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n) +{ + for (size_t i = 0; i < n; ++i) + ST_SWAP(&a[i], &b[i]); +} + +/* + * Sort an array. + */ +ST_SCOPE void +ST_SORT(ST_ELEMENT_TYPE * data, size_t n + ST_SORT_PROTO_ELEMENT_SIZE + ST_SORT_PROTO_COMPARE + ST_SORT_PROTO_ARG) +{ + ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data, + *pa, + *pb, + *pc, + *pd, + *pl, + *pm, + *pn; + size_t d1, + d2; + int r, + presorted; + +loop: + DO_CHECK_FOR_INTERRUPTS(); + if (n < 7) + { + for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP; + pm += ST_POINTER_STEP) + for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0; + pl -= ST_POINTER_STEP) + DO_SWAP(pl, pl - ST_POINTER_STEP); + return; + } + presorted = 1; + for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP; + pm += ST_POINTER_STEP) + { + DO_CHECK_FOR_INTERRUPTS(); + if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0) + { + presorted = 0; + break; + } + } + if (presorted) + return; + pm = a + (n / 2) * ST_POINTER_STEP; + if (n > 7) + { + pl = a; + pn = a + (n - 1) * ST_POINTER_STEP; + if (n > 40) + { + size_t d = (n / 8) * ST_POINTER_STEP; + + pl = DO_MED3(pl, pl + d, pl + 2 * d); + pm = DO_MED3(pm - d, pm, pm + d); + pn = DO_MED3(pn - 2 * d, pn - d, pn); + } + pm = DO_MED3(pl, pm, pn); + } + DO_SWAP(a, pm); + pa = pb = a + ST_POINTER_STEP; + pc = pd = a + (n - 1) * ST_POINTER_STEP; + for (;;) + { + while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0) + { + if (r == 0) + { + DO_SWAP(pa, pb); + pa += ST_POINTER_STEP; + } + pb += ST_POINTER_STEP; + DO_CHECK_FOR_INTERRUPTS(); + } + while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0) + { + if (r == 0) + { + DO_SWAP(pc, pd); + pd -= ST_POINTER_STEP; + } + pc -= ST_POINTER_STEP; + DO_CHECK_FOR_INTERRUPTS(); + } + if (pb > pc) + break; + DO_SWAP(pb, pc); + pb += ST_POINTER_STEP; + pc -= ST_POINTER_STEP; + } + pn = a + n * ST_POINTER_STEP; + d1 = Min(pa - a, pb - pa); + DO_SWAPN(a, pb - d1, d1); + d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP); + DO_SWAPN(pb, pn - d1, d1); + d1 = pb - pa; + d2 = pd - pc; + if (d1 <= d2) + { + /* Recurse on left partition, then iterate on right partition */ + if (d1 > ST_POINTER_STEP) + DO_SORT(a, d1 / ST_POINTER_STEP); + if (d2 > ST_POINTER_STEP) + { + /* Iterate rather than recurse to save stack space */ + /* DO_SORT(pn - d2, d2 / ST_POINTER_STEP) */ + a = pn - d2; + n = d2 / ST_POINTER_STEP; + goto loop; + } + } + else + { + /* Recurse on right partition, then iterate on left partition */ + if (d2 > ST_POINTER_STEP) + DO_SORT(pn - d2, d2 / ST_POINTER_STEP); + if (d1 > ST_POINTER_STEP) + { + /* Iterate rather than recurse to save stack space */ + /* DO_SORT(a, d1 / ST_POINTER_STEP) */ + n = d1 / ST_POINTER_STEP; + goto loop; + } + } +} +#endif + +#undef DO_CHECK_FOR_INTERRUPTS +#undef DO_COMPARE +#undef DO_MED3 +#undef DO_SORT +#undef DO_SWAP +#undef DO_SWAPN +#undef ST_CHECK_FOR_INTERRUPTS +#undef ST_COMPARATOR_TYPE_NAME +#undef ST_COMPARE +#undef ST_COMPARE_ARG_TYPE +#undef ST_COMPARE_RUNTIME_POINTER +#undef ST_ELEMENT_TYPE +#undef ST_ELEMENT_TYPE_VOID +#undef ST_MAKE_NAME +#undef ST_MAKE_NAME_ +#undef ST_MAKE_PREFIX +#undef ST_MED3 +#undef ST_POINTER_STEP +#undef ST_POINTER_TYPE +#undef ST_SCOPE +#undef ST_SORT +#undef ST_SORT_INVOKE_ARG +#undef ST_SORT_INVOKE_COMPARE +#undef ST_SORT_INVOKE_ELEMENT_SIZE +#undef ST_SORT_PROTO_ARG +#undef ST_SORT_PROTO_COMPARE +#undef ST_SORT_PROTO_ELEMENT_SIZE +#undef ST_SWAP +#undef ST_SWAPN diff --git a/src/include/lib/stringinfo.h b/src/include/lib/stringinfo.h new file mode 100644 index 0000000..36a416f --- /dev/null +++ b/src/include/lib/stringinfo.h @@ -0,0 +1,161 @@ +/*------------------------------------------------------------------------- + * + * stringinfo.h + * Declarations/definitions for "StringInfo" functions. + * + * StringInfo provides an extensible string data type (currently limited to a + * length of 1GB). It can be used to buffer either ordinary C strings + * (null-terminated text) or arbitrary binary data. All storage is allocated + * with palloc() (falling back to malloc in frontend code). + * + * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * src/include/lib/stringinfo.h + * + *------------------------------------------------------------------------- + */ +#ifndef STRINGINFO_H +#define STRINGINFO_H + +/*------------------------- + * StringInfoData holds information about an extensible string. + * data is the current buffer for the string (allocated with palloc). + * len is the current string length. There is guaranteed to be + * a terminating '\0' at data[len], although this is not very + * useful when the string holds binary data rather than text. + * maxlen is the allocated size in bytes of 'data', i.e. the maximum + * string size (including the terminating '\0' char) that we can + * currently store in 'data' without having to reallocate + * more space. We must always have maxlen > len. + * cursor is initialized to zero by makeStringInfo or initStringInfo, + * but is not otherwise touched by the stringinfo.c routines. + * Some routines use it to scan through a StringInfo. + *------------------------- + */ +typedef struct StringInfoData +{ + char *data; + int len; + int maxlen; + int cursor; +} StringInfoData; + +typedef StringInfoData *StringInfo; + + +/*------------------------ + * There are two ways to create a StringInfo object initially: + * + * StringInfo stringptr = makeStringInfo(); + * Both the StringInfoData and the data buffer are palloc'd. + * + * StringInfoData string; + * initStringInfo(&string); + * The data buffer is palloc'd but the StringInfoData is just local. + * This is the easiest approach for a StringInfo object that will + * only live as long as the current routine. + * + * To destroy a StringInfo, pfree() the data buffer, and then pfree() the + * StringInfoData if it was palloc'd. There's no special support for this. + * + * NOTE: some routines build up a string using StringInfo, and then + * release the StringInfoData but return the data string itself to their + * caller. At that point the data string looks like a plain palloc'd + * string. + *------------------------- + */ + +/*------------------------ + * makeStringInfo + * Create an empty 'StringInfoData' & return a pointer to it. + */ +extern StringInfo makeStringInfo(void); + +/*------------------------ + * initStringInfo + * Initialize a StringInfoData struct (with previously undefined contents) + * to describe an empty string. + */ +extern void initStringInfo(StringInfo str); + +/*------------------------ + * resetStringInfo + * Clears the current content of the StringInfo, if any. The + * StringInfo remains valid. + */ +extern void resetStringInfo(StringInfo str); + +/*------------------------ + * appendStringInfo + * Format text data under the control of fmt (an sprintf-style format string) + * and append it to whatever is already in str. More space is allocated + * to str if necessary. This is sort of like a combination of sprintf and + * strcat. + */ +extern void appendStringInfo(StringInfo str, const char *fmt,...) pg_attribute_printf(2, 3); + +/*------------------------ + * appendStringInfoVA + * Attempt to format text data under the control of fmt (an sprintf-style + * format string) and append it to whatever is already in str. If successful + * return zero; if not (because there's not enough space), return an estimate + * of the space needed, without modifying str. Typically the caller should + * pass the return value to enlargeStringInfo() before trying again; see + * appendStringInfo for standard usage pattern. + */ +extern int appendStringInfoVA(StringInfo str, const char *fmt, va_list args) pg_attribute_printf(2, 0); + +/*------------------------ + * appendStringInfoString + * Append a null-terminated string to str. + * Like appendStringInfo(str, "%s", s) but faster. + */ +extern void appendStringInfoString(StringInfo str, const char *s); + +/*------------------------ + * appendStringInfoChar + * Append a single byte to str. + * Like appendStringInfo(str, "%c", ch) but much faster. + */ +extern void appendStringInfoChar(StringInfo str, char ch); + +/*------------------------ + * appendStringInfoCharMacro + * As above, but a macro for even more speed where it matters. + * Caution: str argument will be evaluated multiple times. + */ +#define appendStringInfoCharMacro(str,ch) \ + (((str)->len + 1 >= (str)->maxlen) ? \ + appendStringInfoChar(str, ch) : \ + (void)((str)->data[(str)->len] = (ch), (str)->data[++(str)->len] = '\0')) + +/*------------------------ + * appendStringInfoSpaces + * Append a given number of spaces to str. + */ +extern void appendStringInfoSpaces(StringInfo str, int count); + +/*------------------------ + * appendBinaryStringInfo + * Append arbitrary binary data to a StringInfo, allocating more space + * if necessary. + */ +extern void appendBinaryStringInfo(StringInfo str, + const void *data, int datalen); + +/*------------------------ + * appendBinaryStringInfoNT + * Append arbitrary binary data to a StringInfo, allocating more space + * if necessary. Does not ensure a trailing null-byte exists. + */ +extern void appendBinaryStringInfoNT(StringInfo str, + const void *data, int datalen); + +/*------------------------ + * enlargeStringInfo + * Make sure a StringInfo's buffer can hold at least 'needed' more bytes. + */ +extern void enlargeStringInfo(StringInfo str, int needed); + +#endif /* STRINGINFO_H */ -- cgit v1.2.3