8000 Allow users of simplehash.h to perform direct deletions · postgrespro/postgres@ff53d7b · GitHub
[go: up one dir, main page]
Skip to content

    • Commit ff53d7b

    Browse files
    david-rowleydavid-rowley
    committed
    Allow users of simplehash.h to perform direct deletions
    Previously simplehash.h only exposed a method to perform a hash table delete using the hash table key. This meant that the delete function had to perform a hash lookup in order to find the entry to delete. Here we add a new function so that users of simplehash.h can perform a hash delete directly using the entry pointer, thus saving the hash lookup. An upcoming patch that uses simplehash.h already has performed the hash lookup so already has the entry pointer. This change will allow the code in that patch to perform the hash delete without the code in simplehash.h having to perform an additional hash lookup. Author: David Rowley Reviewed-by: Andres Freund Discussion: https://postgr.es/m/CAApHDvqFLXXge153WmPsjke5VGOSt7Ez0yD0c7eBXLfmWxs3Kw@mail.gmail.com
    1 parent bc9f1af commit ff53d7b

    File tree

    1 file changed

    +61
    -1
    lines changed

    1 file changed

    +61
    -1
    lines changed

    ‎src/include/lib/simplehash.h

    Lines changed: 61 additions & 1 deletion
    Original file line numberDiff line numberDiff line change
    @@ -110,6 +110,7 @@
    110110
    #define SH_RESET SH_MAKE_NAME(reset)
    111111
    #define SH_INSERT SH_MAKE_NAME(insert)
    112112
    #define SH_INSERT_HASH SH_MAKE_NAME(insert_hash)
    113+
    #define SH_DELETE_ITEM SH_MAKE_NAME(delete_item)
    113114
    #define SH_DELETE SH_MAKE_NAME(delete)
    114115
    #define SH_LOOKUP SH_MAKE_NAME(lookup)
    115116
    #define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash)
    @@ -217,6 +218,9 @@ SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key);
    217218
    SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
    218219
    uint32 hash);
    219220

    221+
    /* void <prefix>_delete_item(<prefix>_hash *tb, <element> *entry) */
    222+
    SH_SCOPE void SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry);
    223+
    220224
    /* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
    221225
    SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key);
    222226

    @@ -829,7 +833,7 @@ SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
    829833
    }
    830834

    831835
    /*
    832-
    * Delete entry from hash table. Returns whether to-be-deleted key was
    836+
    * Delete entry from hash table by key. Returns whether to-be-deleted key was
    833837
    * present.
    834838
    */
    835839
    SH_SCOPE bool
    @@ -900,6 +904,61 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
    900904
    }
    901905
    }
    902906

    907+
    /*
    908+
    * Delete entry from hash table by entry pointer
    909+
    */
    910+
    SH_SCOPE void
    911+
    SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
    912+
    {
    913+
    SH_ELEMENT_TYPE *lastentry = entry;
    914+
    uint32 hash = SH_ENTRY_HASH(tb, entry);
    915+
    uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
    916+
    uint32 curelem;
    917+
    918+
    /* Calculate the index of 'entry' */
    919+
    curelem = entry - &tb->data[0];
    920+
    921+
    tb->members--;
    922+
    923+
    /*
    924+
    * Backward shift following elements till either an empty element or an
    925+
    * element at its optimal position is encountered.
    926+
    *
    927+
    * While that sounds expensive, the average chain length is short, and
    928+
    * deletions would otherwise require tombstones.
    929+
    */
    930+
    while (true)
    931+
    {
    932+
    SH_ELEMENT_TYPE *curentry;
    933+
    uint32 curhash;
    934+
    uint32 curoptimal;
    935+
    936+
    curelem = SH_NEXT(tb, curelem, startelem);
    937+
    curentry = &tb->data[curelem];
    938+
    939+
    if (curentry->status != SH_STATUS_IN_USE)
    940+
    {
    941+
    lastentry->status = SH_STATUS_EMPTY;
    942+
    break;
    943+
    }
    944+
    945+
    curhash = SH_ENTRY_HASH(tb, curentry);
    946+
    curoptimal = SH_INITIAL_BUCKET(tb, curhash);
    947+
    948+
    /* current is at optimal position, done */
    949+
    if (curoptimal == curelem)
    950+
    {
    951+
    lastentry->status = SH_STATUS_EMPTY;
    952+
    break;
    953+
    }
    954+
    955+
    /* shift */
    956+
    memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));
    957+
    958+
    lastentry = curentry;
    959+
    }
    960+
    }
    961+
    903962
    /*
    904963
    * Initialize iterator.
    905964
    */
    @@ -1102,6 +1161,7 @@ SH_STAT(SH_TYPE * tb)
    11021161
    #undef SH_RESET
    11031162
    #undef SH_INSERT
    11041163
    #undef SH_INSERT_HASH
    1164+
    #undef SH_DELETE_ITEM
    11051165
    #undef SH_DELETE
    11061166
    #undef SH_LOOKUP
    11071167
    #undef SH_LOOKUP_HASH

    0 commit comments

    Comments
     (0)
    0