8000 Improve programmer docs for simplehash and dynahash. · postgrespro/postgres@84c0e4b · GitHub
[go: up one dir, main page]
Skip to content

    • Commit 84c0e4b

    Browse files
    macdicemacdice
    committed
    Improve programmer docs for simplehash and dynahash.
    When reading the code it's not obvious when one should prefer dynahash over simplehash and vice-versa, so, for programmer-friendliness, add comments to inform that decision. Show sample simplehash method signatures. Author: James Coleman <jtc331@gmail.com> Discussion: https://postgr.es/m/CAAaqYe_dOF39gAJ8rL-a3YO3Qo96MHMRQ2whFjK5ZcU6YvMQSA%40mail.gmail.com
    1 parent c79aed4 commit 84c0e4b

    File tree

    2 files changed

    +80
    -5
    lines changed

    2 files changed

    +80
    -5
    lines changed

    ‎src/backend/utils/hash/dynahash.c

    Lines changed: 11 additions & 1 deletion
    Original file line numberDiff line numberDiff line change
    @@ -1,7 +1,7 @@
    11
    /*-------------------------------------------------------------------------
    22
    *
    33
    * dynahash.c
    4-
    * dynamic hash tables
    4+
    * dynamic chained hash tables
    55
    *
    66
    * dynahash.c supports both local-to-a-backend hash tables and hash tables in
    77
    * shared memory. For shared hash tables, it is the caller's responsibility
    @@ -41,6 +41,16 @@
    4141
    * function must be supplied; comparison defaults to memcmp() and key copying
    4242
    * to memcpy() when a user-defined hashing function is selected.
    4343
    *
    44+
    * Compared to simplehash, dynahash has the following benefits:
    45+
    *
    46+
    * - It supports partitioning, which is useful for shared memory access using
    47+
    * locks.
    48+
    * - Shared memory hashes are allocated in a fixed size area at startup and
    49+
    * are discoverable by name from other processes.
    50+
    * - Because entries don't need to be moved in the case of hash conflicts, has
    51+
    * better performance for large entries
    52+
    * - Guarantees stable pointers to entries.
    53+
    *
    4454
    * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
    4555
    * Portions Copyright (c) 1994, Regents of the University of California
    4656
    *

    ‎src/include/lib/simplehash.h

    Lines changed: 69 additions & 4 deletions
    Original file line numberDiff line numberDiff line change
    @@ -1,10 +1,27 @@
    11
    /*
    22
    * simplehash.h
    33
    *
    4-
    * Hash table implementation which will be specialized to user-defined
    5-
    * types, by including this file to generate the required code. It's
    6-
    * probably not worthwhile to do so for hash tables that aren't performance
    7-
    * or space sensitive.
    4+
    * When included this file generates a "templated" (by way of macros)
    5+
    * open-addressing hash table implementation specialized to user-defined
    6+
    * types.
    7+
    *
    8+
    * It's probably not worthwhile to generate such a specialized implementation
    9+
    * for hash tables that aren't performance or space sensitive.
    10+
    *
    11+
    * Compared to dynahash, simplehash has the following benefits:
    12+
    *
    13+
    * - Due to the "templated" code generation has known structure sizes and no
    14+
    * indirect function calls (which show up substantially in dynahash
    15+
    * profiles). These features considerably increase speed for small
    16+
    * entries.
    17+
    * - Open addressing has better CPU cache behavior than dynahash's chained
    18+
    * hashtables.
    19+
    * - The generated interface is type-safe and easier to use than dynahash,
    20+
    * though at the cost of more complex setup.
    21+
    * - Allocates memory in a MemoryContext or another allocator with a
    22+
    * malloc/free style interface (which isn't easily usable in a shared
    23+
    * memory context)
    24+
    * - Does not require the overhead of a separate memory context.
    825
    *
    926
    * Usage notes:
    1027
    *
    @@ -34,6 +51,19 @@
    3451
    * - SH_STORE_HASH - if defined the hash is stored in the elements
    3552
    * - SH_GET_HASH(tb, a) - return the field to store the hash in
    3653
    *
    54+
    * The element type is required to contain a "uint32 status" member.
    55+
    *
    56+
    * While SH_STORE_HASH (and subsequently SH_GET_HASH) are optional, because
    57+
    * the hash table implementation needs to compare hashes to move elements
    58+
    * (particularly when growing the hash), it's preferable, if possible, to
    59+
    * store the element's hash in the element's data type. If the hash is so
    60+
    * stored, the hash table will also compare hashes before calling SH_EQUAL
    61+
    * when comparing two keys.
    62+
    *
    63+
    * For convenience the hash table create functions accept a void pointer
    64+
    * that will be stored in the hash table type's member private_data. This
    65+
    * allows callbacks to reference caller provided data.
    66+
    *
    3767
    * For examples of usage look at tidbitmap.c (file local definition) and
    3868
    * execnodes.h/execGrouping.c (exposed declaration, file local
    3969
    * implementation).
    @@ -149,24 +179,59 @@ typedef struct SH_ITERATOR
    149179

    150180
    /* externally visible function prototypes */
    151181
    #ifdef SH_RAW_ALLOCATOR
    182+
    /* <prefix>_hash <prefix>_create(uint32 nelements, void *private_data) */
    152183
    SH_SCOPE SH_TYPE *SH_CREATE(uint32 nelements, void *private_data);
    153184
    #else
    185+
    /*
    186+
    * <prefix>_hash <prefix>_create(MemoryContext ctx, uint32 nelements,
    187+
    * void *private_data)
    188+
    */
    154189
    SH_SCOPE SH_TYPE *SH_CREATE(MemoryContext ctx, uint32 nelements,
    155190
    void *private_data);
    156191
    #endif
    192+
    193+
    /* void <prefix>_destroy(<prefix>_hash *tb) */
    157194
    SH_SCOPE void SH_DESTROY(SH_TYPE * tb);
    195+
    196+
    /* void <prefix>_reset(<prefix>_hash *tb) */
    158197
    SH_SCOPE void SH_RESET(SH_TYPE * tb);
    198+
    199+
    /* void <prefix>_grow(<prefix>_hash *tb) */
    159200
    SH_SCOPE void SH_GROW(SH_TYPE * tb, uint32 newsize);
    201+
    202+
    /* <element> *<prefix>_insert(<prefix>_hash *tb, <key> key, bool *found) */
    160203
    SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found);
    204+
    205+
    /*
    206+
    * <element> *<prefix>_insert_hash(<prefix>_hash *tb, <key> key, uint32 hash,
    207+
    * bool *found)
    208+
    */
    161209
    SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
    162210
    uint32 hash, bool *found);
    211+
    212+
    /* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
    163213
    SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key);
    214+
    215+
    /* <element> *<prefix>_lookup_hash(<prefix>_hash *tb, <key> key, uint32 hash) */
    164216
    SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
    165217
    uint32 hash);
    218+
    219+
    /* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
    166220
    SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key);
    221+
    222+
    /* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
    167223
    SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
    224+
    225+
    /*
    226+
    * void <prefix>_start_iterate_at(<prefix>_hash *tb, <prefix>_iterator *iter,
    227+
    * uint32 at)
    228+
    */
    168229
    SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at);
    230+
    231+
    /* <element> *<prefix>_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
    169232
    SH_SCOPE SH_ELEMENT_TYPE *SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
    233+
    234+
    /* void <prefix>_stat(<prefix>_hash *tb */
    170235
    SH_SCOPE void SH_STAT(SH_TYPE * tb);
    171236

    172237
    #endif /* SH_DECLARE */

    0 commit comments

    Comments
     (0)
    0