LCOV - code coverage report
Current view: | top level - Python - hashtable.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 105 | 172 | 61.0 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 11 | 19 | 57.9 %
|  |  | Branches: | 37 | 68 | 54.4 %

               Branch data     Line data    Source code
           1                 :            : /* The implementation of the hash table (_Py_hashtable_t) is based on the
           2                 :            :    cfuhash project:
           3                 :            :    http://sourceforge.net/projects/libcfu/
           4                 :            :
           5                 :            :    Copyright of cfuhash:
           6                 :            :    ----------------------------------
           7                 :            :    Creation date: 2005-06-24 21:22:40
           8                 :            :    Authors: Don
           9                 :            :    Change log:
          10                 :            :
          11                 :            :    Copyright (c) 2005 Don Owens
          12                 :            :    All rights reserved.
          13                 :            :
          14                 :            :    This code is released under the BSD license:
          15                 :            :
          16                 :            :    Redistribution and use in source and binary forms, with or without
          17                 :            :    modification, are permitted provided that the following conditions
          18                 :            :    are met:
          19                 :            :
          20                 :            :      * Redistributions of source code must retain the above copyright
          21                 :            :        notice, this list of conditions and the following disclaimer.
          22                 :            :
          23                 :            :      * Redistributions in binary form must reproduce the above
          24                 :            :        copyright notice, this list of conditions and the following
          25                 :            :        disclaimer in the documentation and/or other materials provided
          26                 :            :        with the distribution.
          27                 :            :
          28                 :            :      * Neither the name of the author nor the names of its
          29                 :            :        contributors may be used to endorse or promote products derived
          30                 :            :        from this software without specific prior written permission.
          31                 :            :
          32                 :            :    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
          33                 :            :    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
          34                 :            :    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
          35                 :            :    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
          36                 :            :    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
          37                 :            :    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
          38                 :            :    (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
          39                 :            :    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
          40                 :            :    HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
          41                 :            :    STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
          42                 :            :    ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
          43                 :            :    OF THE POSSIBILITY OF SUCH DAMAGE.
          44                 :            :    ----------------------------------
          45                 :            : */
          46                 :            :
          47                 :            : #include "Python.h"
          48                 :            : #include "pycore_hashtable.h"
          49                 :            :
          50                 :            : #define HASHTABLE_MIN_SIZE 16
          51                 :            : #define HASHTABLE_HIGH 0.50
          52                 :            : #define HASHTABLE_LOW 0.10
          53                 :            : #define HASHTABLE_REHASH_FACTOR 2.0 / (HASHTABLE_LOW + HASHTABLE_HIGH)
          54                 :            :
          55                 :            : #define BUCKETS_HEAD(SLIST) \
          56                 :            :         ((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(SLIST)))
          57                 :            : #define TABLE_HEAD(HT, BUCKET) \
          58                 :            :         ((_Py_hashtable_entry_t *)_Py_SLIST_HEAD(&(HT)->buckets[BUCKET]))
          59                 :            : #define ENTRY_NEXT(ENTRY) \
          60                 :            :         ((_Py_hashtable_entry_t *)_Py_SLIST_ITEM_NEXT(ENTRY))
          61                 :            :
          62                 :            : /* Forward declaration */
          63                 :            : static int hashtable_rehash(_Py_hashtable_t *ht);
          64                 :            :
          65                 :            : static void
          66                 :          0 : _Py_slist_init(_Py_slist_t *list)
          67                 :            : {
          68                 :          0 :     list->head = NULL;
          69                 :          0 : }
          70                 :            :
          71                 :            :
          72                 :            : static void
          73                 :     110183 : _Py_slist_prepend(_Py_slist_t *list, _Py_slist_item_t *item)
          74                 :            : {
          75                 :     110183 :     item->next = list->head;
          76                 :     110183 :     list->head = item;
          77                 :     110183 : }
          78                 :            :
          79                 :            :
          80                 :            : static void
          81                 :          0 : _Py_slist_remove(_Py_slist_t *list, _Py_slist_item_t *previous,
          82                 :            :                  _Py_slist_item_t *item)
          83                 :            : {
          84         [ #  # ]:          0 :     if (previous != NULL)
          85                 :          0 :         previous->next = item->next;
          86                 :            :     else
          87                 :          0 :         list->head = item->next;
          88                 :          0 : }
          89                 :            :
          90                 :            :
          91                 :            : Py_uhash_t
          92                 :     174401 : _Py_hashtable_hash_ptr(const void *key)
          93                 :            : {
          94                 :     174401 :     return (Py_uhash_t)_Py_HashPointerRaw(key);
          95                 :            : }
          96                 :            :
          97                 :            :
          98                 :            : int
          99                 :          0 : _Py_hashtable_compare_direct(const void *key1, const void *key2)
         100                 :            : {
         101                 :          0 :     return (key1 == key2);
         102                 :            : }
         103                 :            :
         104                 :            :
         105                 :            : /* makes sure the real size of the buckets array is a power of 2 */
         106                 :            : static size_t
         107                 :        854 : round_size(size_t s)
         108                 :            : {
         109                 :            :     size_t i;
         110         [ -  + ]:        854 :     if (s < HASHTABLE_MIN_SIZE)
         111                 :          0 :         return HASHTABLE_MIN_SIZE;
         112                 :        854 :     i = 1;
         113         [ +  + ]:       6985 :     while (i < s)
         114                 :       6131 :         i <<= 1;
         115                 :        854 :     return i;
         116                 :            : }
         117                 :            :
         118                 :            :
         119                 :            : size_t
         120                 :          0 : _Py_hashtable_size(const _Py_hashtable_t *ht)
         121                 :            : {
         122                 :          0 :     size_t size = sizeof(_Py_hashtable_t);
         123                 :            :     /* buckets */
         124                 :          0 :     size += ht->nbuckets * sizeof(_Py_hashtable_entry_t *);
         125                 :            :     /* entries */
         126                 :          0 :     size += ht->nentries * sizeof(_Py_hashtable_entry_t);
         127                 :          0 :     return size;
         128                 :            : }
         129                 :            :
         130                 :            :
         131                 :            : _Py_hashtable_entry_t *
         132                 :         12 : _Py_hashtable_get_entry_generic(_Py_hashtable_t *ht, const void *key)
         133                 :            : {
         134                 :         12 :     Py_uhash_t key_hash = ht->hash_func(key);
         135                 :         12 :     size_t index = key_hash & (ht->nbuckets - 1);
         136                 :         12 :     _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);
         137                 :            :     while (1) {
         138         [ -  + ]:         15 :         if (entry == NULL) {
         139                 :          0 :             return NULL;
         140                 :            :         }
         141   [ +  +  +  - ]:         15 :         if (entry->key_hash == key_hash && ht->compare_func(key, entry->key)) {
         142                 :         12 :             break;
         143                 :            :         }
         144                 :          3 :         entry = ENTRY_NEXT(entry);
         145                 :            :     }
         146                 :         12 :     return entry;
         147                 :            : }
         148                 :            :
         149                 :            :
         150                 :            : // Specialized for:
         151                 :            : // hash_func == _Py_hashtable_hash_ptr
         152                 :            : // compare_func == _Py_hashtable_compare_direct
         153                 :            : static _Py_hashtable_entry_t *
         154                 :     129326 : _Py_hashtable_get_entry_ptr(_Py_hashtable_t *ht, const void *key)
         155                 :            : {
         156                 :     129326 :     Py_uhash_t key_hash = _Py_hashtable_hash_ptr(key);
         157                 :     129326 :     size_t index = key_hash & (ht->nbuckets - 1);
         158                 :     129326 :     _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);
         159                 :            :     while (1) {
         160         [ +  + ]:     166992 :         if (entry == NULL) {
         161                 :      45075 :             return NULL;
         162                 :            :         }
         163                 :            :         // Compare directly keys (ignore entry->key_hash)
         164         [ +  + ]:     121917 :         if (entry->key == key) {
         165                 :      84251 :             break;
         166                 :            :         }
         167                 :      37666 :         entry = ENTRY_NEXT(entry);
         168                 :            :     }
         169                 :      84251 :     return entry;
         170                 :            : }
         171                 :            :
         172                 :            :
         173                 :            : void*
         174                 :          0 : _Py_hashtable_steal(_Py_hashtable_t *ht, const void *key)
         175                 :            : {
         176                 :          0 :     Py_uhash_t key_hash = ht->hash_func(key);
         177                 :          0 :     size_t index = key_hash & (ht->nbuckets - 1);
         178                 :            :
         179                 :          0 :     _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, index);
         180                 :          0 :     _Py_hashtable_entry_t *previous = NULL;
         181                 :            :     while (1) {
         182         [ #  # ]:          0 :         if (entry == NULL) {
         183                 :            :             // not found
         184                 :          0 :             return NULL;
         185                 :            :         }
         186   [ #  #  #  # ]:          0 :         if (entry->key_hash == key_hash && ht->compare_func(key, entry->key)) {
         187                 :          0 :             break;
         188                 :            :         }
         189                 :          0 :         previous = entry;
         190                 :          0 :         entry = ENTRY_NEXT(entry);
         191                 :            :     }
         192                 :            :
         193                 :          0 :     _Py_slist_remove(&ht->buckets[index], (_Py_slist_item_t *)previous,
         194                 :            :                      (_Py_slist_item_t *)entry);
         195                 :          0 :     ht->nentries--;
         196                 :            :
         197                 :          0 :     void *value = entry->value;
         198                 :          0 :     ht->alloc.free(entry);
         199                 :            :
         200         [ #  # ]:          0 :     if ((float)ht->nentries / (float)ht->nbuckets < HASHTABLE_LOW) {
         201                 :            :         // Ignore failure: error cannot be reported to the caller
         202                 :          0 :         hashtable_rehash(ht);
         203                 :            :     }
         204                 :          0 :     return value;
         205                 :            : }
         206                 :            :
         207                 :            :
         208                 :            : int
         209                 :      45127 : _Py_hashtable_set(_Py_hashtable_t *ht, const void *key, void *value)
         210                 :            : {
         211                 :            :     _Py_hashtable_entry_t *entry;
         212                 :            :
         213                 :            : #ifndef NDEBUG
         214                 :            :     /* Don't write the assertion on a single line because it is interesting
         215                 :            :        to know the duplicated entry if the assertion failed. The entry can
         216                 :            :        be read using a debugger. */
         217                 :            :     entry = ht->get_entry_func(ht, key);
         218                 :            :     assert(entry == NULL);
         219                 :            : #endif
         220                 :            :
         221                 :            :
         222                 :      45127 :     entry = ht->alloc.malloc(sizeof(_Py_hashtable_entry_t));
         223         [ -  + ]:      45127 :     if (entry == NULL) {
         224                 :            :         /* memory allocation failed */
         225                 :          0 :         return -1;
         226                 :            :     }
         227                 :            :
         228                 :      45127 :     entry->key_hash = ht->hash_func(key);
         229                 :      45127 :     entry->key = (void *)key;
         230                 :      45127 :     entry->value = value;
         231                 :            :
         232                 :      45127 :     ht->nentries++;
         233         [ +  + ]:      45127 :     if ((float)ht->nentries / (float)ht->nbuckets > HASHTABLE_HIGH) {
         234         [ -  + ]:        854 :         if (hashtable_rehash(ht) < 0) {
         235                 :          0 :             ht->nentries--;
         236                 :          0 :             ht->alloc.free(entry);
         237                 :          0 :             return -1;
         238                 :            :         }
         239                 :            :     }
         240                 :            :
         241                 :      45127 :     size_t index = entry->key_hash & (ht->nbuckets - 1);
         242                 :      45127 :     _Py_slist_prepend(&ht->buckets[index], (_Py_slist_item_t*)entry);
         243                 :      45127 :     return 0;
         244                 :            : }
         245                 :            :
         246                 :            :
         247                 :            : void*
         248                 :         12 : _Py_hashtable_get(_Py_hashtable_t *ht, const void *key)
         249                 :            : {
         250                 :         12 :     _Py_hashtable_entry_t *entry = ht->get_entry_func(ht, key);
         251         [ +  - ]:         12 :     if (entry != NULL) {
         252                 :         12 :         return entry->value;
         253                 :            :     }
         254                 :            :     else {
         255                 :          0 :         return NULL;
         256                 :            :     }
         257                 :            : }
         258                 :            :
         259                 :            :
         260                 :            : int
         261                 :          0 : _Py_hashtable_foreach(_Py_hashtable_t *ht,
         262                 :            :                       _Py_hashtable_foreach_func func,
         263                 :            :                       void *user_data)
         264                 :            : {
         265         [ #  # ]:          0 :     for (size_t hv = 0; hv < ht->nbuckets; hv++) {
         266                 :          0 :         _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, hv);
         267         [ #  # ]:          0 :         while (entry != NULL) {
         268                 :          0 :             int res = func(ht, entry->key, entry->value, user_data);
         269         [ #  # ]:          0 :             if (res) {
         270                 :          0 :                 return res;
         271                 :            :             }
         272                 :          0 :             entry = ENTRY_NEXT(entry);
         273                 :            :         }
         274                 :            :     }
         275                 :          0 :     return 0;
         276                 :            : }
         277                 :            :
         278                 :            :
         279                 :            : static int
         280                 :        854 : hashtable_rehash(_Py_hashtable_t *ht)
         281                 :            : {
         282                 :        854 :     size_t new_size = round_size((size_t)(ht->nentries * HASHTABLE_REHASH_FACTOR));
         283         [ -  + ]:        854 :     if (new_size == ht->nbuckets) {
         284                 :          0 :         return 0;
         285                 :            :     }
         286                 :            :
         287                 :        854 :     size_t buckets_size = new_size * sizeof(ht->buckets[0]);
         288                 :        854 :     _Py_slist_t *new_buckets = ht->alloc.malloc(buckets_size);
         289         [ -  + ]:        854 :     if (new_buckets == NULL) {
         290                 :            :         /* memory allocation failed */
         291                 :          0 :         return -1;
         292                 :            :     }
         293                 :        854 :     memset(new_buckets, 0, buckets_size);
         294                 :            :
         295         [ +  + ]:     130966 :     for (size_t bucket = 0; bucket < ht->nbuckets; bucket++) {
         296                 :     130112 :         _Py_hashtable_entry_t *entry = BUCKETS_HEAD(ht->buckets[bucket]);
         297         [ +  + ]:     195168 :         while (entry != NULL) {
         298                 :            :             assert(ht->hash_func(entry->key) == entry->key_hash);
         299                 :      65056 :             _Py_hashtable_entry_t *next = ENTRY_NEXT(entry);
         300                 :      65056 :             size_t entry_index = entry->key_hash & (new_size - 1);
         301                 :            :
         302                 :      65056 :             _Py_slist_prepend(&new_buckets[entry_index], (_Py_slist_item_t*)entry);
         303                 :            :
         304                 :      65056 :             entry = next;
         305                 :            :         }
         306                 :            :     }
         307                 :            :
         308                 :        854 :     ht->alloc.free(ht->buckets);
         309                 :        854 :     ht->nbuckets = new_size;
         310                 :        854 :     ht->buckets = new_buckets;
         311                 :        854 :     return 0;
         312                 :            : }
         313                 :            :
         314                 :            :
         315                 :            : _Py_hashtable_t *
         316                 :        295 : _Py_hashtable_new_full(_Py_hashtable_hash_func hash_func,
         317                 :            :                        _Py_hashtable_compare_func compare_func,
         318                 :            :                        _Py_hashtable_destroy_func key_destroy_func,
         319                 :            :                        _Py_hashtable_destroy_func value_destroy_func,
         320                 :            :                        _Py_hashtable_allocator_t *allocator)
         321                 :            : {
         322                 :            :     _Py_hashtable_allocator_t alloc;
         323         [ +  + ]:        295 :     if (allocator == NULL) {
         324                 :        291 :         alloc.malloc = PyMem_Malloc;
         325                 :        291 :         alloc.free = PyMem_Free;
         326                 :            :     }
         327                 :            :     else {
         328                 :          4 :         alloc = *allocator;
         329                 :            :     }
         330                 :            :
         331                 :        295 :     _Py_hashtable_t *ht = (_Py_hashtable_t *)alloc.malloc(sizeof(_Py_hashtable_t));
         332         [ -  + ]:        295 :     if (ht == NULL) {
         333                 :          0 :         return ht;
         334                 :            :     }
         335                 :            :
         336                 :        295 :     ht->nbuckets = HASHTABLE_MIN_SIZE;
         337                 :        295 :     ht->nentries = 0;
         338                 :            :
         339                 :        295 :     size_t buckets_size = ht->nbuckets * sizeof(ht->buckets[0]);
         340                 :        295 :     ht->buckets = alloc.malloc(buckets_size);
         341         [ -  + ]:        295 :     if (ht->buckets == NULL) {
         342                 :          0 :         alloc.free(ht);
         343                 :          0 :         return NULL;
         344                 :            :     }
         345                 :        295 :     memset(ht->buckets, 0, buckets_size);
         346                 :            :
         347                 :        295 :     ht->get_entry_func = _Py_hashtable_get_entry_generic;
         348                 :        295 :     ht->hash_func = hash_func;
         349                 :        295 :     ht->compare_func = compare_func;
         350                 :        295 :     ht->key_destroy_func = key_destroy_func;
         351                 :        295 :     ht->value_destroy_func = value_destroy_func;
         352                 :        295 :     ht->alloc = alloc;
         353         [ +  + ]:        295 :     if (ht->hash_func == _Py_hashtable_hash_ptr
         354         [ +  - ]:        290 :         && ht->compare_func == _Py_hashtable_compare_direct)
         355                 :            :     {
         356                 :        290 :         ht->get_entry_func = _Py_hashtable_get_entry_ptr;
         357                 :            :     }
         358                 :        295 :     return ht;
         359                 :            : }
         360                 :            :
         361                 :            :
         362                 :            : _Py_hashtable_t *
         363                 :          0 : _Py_hashtable_new(_Py_hashtable_hash_func hash_func,
         364                 :            :                   _Py_hashtable_compare_func compare_func)
         365                 :            : {
         366                 :          0 :     return _Py_hashtable_new_full(hash_func, compare_func,
         367                 :            :                                   NULL, NULL, NULL);
         368                 :            : }
         369                 :            :
         370                 :            :
         371                 :            : static void
         372                 :      45127 : _Py_hashtable_destroy_entry(_Py_hashtable_t *ht, _Py_hashtable_entry_t *entry)
         373                 :            : {
         374         [ +  + ]:      45127 :     if (ht->key_destroy_func) {
         375                 :      45075 :         ht->key_destroy_func(entry->key);
         376                 :            :     }
         377         [ +  + ]:      45127 :     if (ht->value_destroy_func) {
         378                 :         52 :         ht->value_destroy_func(entry->value);
         379                 :            :     }
         380                 :      45127 :     ht->alloc.free(entry);
         381                 :      45127 : }
         382                 :            :
         383                 :            :
         384                 :            : void
         385                 :          0 : _Py_hashtable_clear(_Py_hashtable_t *ht)
         386                 :            : {
         387         [ #  # ]:          0 :     for (size_t i=0; i < ht->nbuckets; i++) {
         388                 :          0 :         _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i);
         389         [ #  # ]:          0 :         while (entry != NULL) {
         390                 :          0 :             _Py_hashtable_entry_t *next = ENTRY_NEXT(entry);
         391                 :          0 :             _Py_hashtable_destroy_entry(ht, entry);
         392                 :          0 :             entry = next;
         393                 :            :         }
         394                 :          0 :         _Py_slist_init(&ht->buckets[i]);
         395                 :            :     }
         396                 :          0 :     ht->nentries = 0;
         397                 :            :     // Ignore failure: clear function is not expected to fail
         398                 :            :     // because of a memory allocation failure.
         399                 :          0 :     (void)hashtable_rehash(ht);
         400                 :          0 : }
         401                 :            :
         402                 :            :
         403                 :            : void
         404                 :        295 : _Py_hashtable_destroy(_Py_hashtable_t *ht)
         405                 :            : {
         406         [ +  + ]:     135127 :     for (size_t i = 0; i < ht->nbuckets; i++) {
         407                 :     134832 :         _Py_hashtable_entry_t *entry = TABLE_HEAD(ht, i);
         408         [ +  + ]:     179959 :         while (entry) {
         409                 :      45127 :             _Py_hashtable_entry_t *entry_next = ENTRY_NEXT(entry);
         410                 :      45127 :             _Py_hashtable_destroy_entry(ht, entry);
         411                 :      45127 :             entry = entry_next;
         412                 :            :         }
         413                 :            :     }
         414                 :            :
         415                 :        295 :     ht->alloc.free(ht->buckets);
         416                 :        295 :     ht->alloc.free(ht);
         417                 :        295 : }

Generated by: LCOV version 1.14