Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitff53d7b

Browse files
committed
Allow users of simplehash.h to perform direct deletions
Previously simplehash.h only exposed a method to perform a hash tabledelete using the hash table key. This meant that the delete function hadto perform a hash lookup in order to find the entry to delete. Here weadd a new function so that users of simplehash.h can perform a hash deletedirectly using the entry pointer, thus saving the hash lookup.An upcoming patch that uses simplehash.h already has performed the hashlookup so already has the entry pointer. This change will allow thecode in that patch to perform the hash delete without the code insimplehash.h having to perform an additional hash lookup.Author: David RowleyReviewed-by: Andres FreundDiscussion:https://postgr.es/m/CAApHDvqFLXXge153WmPsjke5VGOSt7Ez0yD0c7eBXLfmWxs3Kw@mail.gmail.com
1 parentbc9f1af commitff53d7b

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
#defineSH_RESET SH_MAKE_NAME(reset)
111111
#defineSH_INSERT SH_MAKE_NAME(insert)
112112
#defineSH_INSERT_HASH SH_MAKE_NAME(insert_hash)
113+
#defineSH_DELETE_ITEM SH_MAKE_NAME(delete_item)
113114
#defineSH_DELETE SH_MAKE_NAME(delete)
114115
#defineSH_LOOKUP SH_MAKE_NAME(lookup)
115116
#defineSH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash)
@@ -217,6 +218,9 @@ SH_SCOPESH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key);
217218
SH_SCOPESH_ELEMENT_TYPE*SH_LOOKUP_HASH(SH_TYPE*tb,SH_KEY_TYPEkey,
218219
uint32hash);
219220

221+
/* void <prefix>_delete_item(<prefix>_hash *tb, <element> *entry) */
222+
SH_SCOPEvoidSH_DELETE_ITEM(SH_TYPE*tb,SH_ELEMENT_TYPE*entry);
223+
220224
/* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
221225
SH_SCOPEboolSH_DELETE(SH_TYPE*tb,SH_KEY_TYPEkey);
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_SCOPEbool
@@ -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_SCOPEvoid
911+
SH_DELETE_ITEM(SH_TYPE*tb,SH_ELEMENT_TYPE*entry)
912+
{
913+
SH_ELEMENT_TYPE*lastentry=entry;
914+
uint32hash=SH_ENTRY_HASH(tb,entry);
915+
uint32startelem=SH_INITIAL_BUCKET(tb,hash);
916+
uint32curelem;
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+
uint32curhash;
934+
uint32curoptimal;
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)
[8]ページ先頭
©2009-2025 Movatter.jp