Line data    Source code

       1             : /*
       2             :  * SPDX-License-Identifier: MPL-2.0
       3             :  *
       4             :  * This Source Code Form is subject to the terms of the Mozilla Public
       5             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       6             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       7             :  *
       8             :  * Copyright 2024 MonetDB Foundation;
       9             :  * Copyright August 2008 - 2023 MonetDB B.V.;
      10             :  * Copyright 1997 - July 2008 CWI.
      11             :  */
      12             : 
      13             : #include "monetdb_config.h"
      14             : #include "sql_mem.h"
      15             : #include "sql_hash.h"
      16             : 
      17             : static unsigned int
      18      720982 : log_base2(unsigned int n)
      19             : {
      20      720982 :         unsigned int l ;
      21             : 
      22     3521227 :         for (l = 0; n; l++)
      23     2800245 :                 n >>= 1 ;
      24      720982 :         return l ;
      25             : }
      26             : 
      27             : sql_hash *
      28      720982 : hash_new(allocator *sa, int size, fkeyvalue key)
      29             : {
      30      720982 :         sql_hash *ht = SA_NEW(sa, sql_hash);
      31             : 
      32      720982 :         if (ht == NULL)
      33             :                 return NULL;
      34      720982 :         ht->sa = sa;
      35      720982 :         ht->entries = 0;
      36      720982 :         ht->size = (1<<log_base2(size-1));
      37      720982 :         ht->key = key;
      38      720982 :         ht->buckets = (ht->sa)?SA_ZNEW_ARRAY(sa, sql_hash_e*, ht->size):ZNEW_ARRAY(sql_hash_e*, ht->size);
      39      720982 :         if (ht->buckets == NULL) {
      40           0 :                 if (!ht->sa)
      41           0 :                         _DELETE(ht);
      42           0 :                 return NULL;
      43             :         }
      44             :         return ht;
      45             : }
      46             : 
      47             : int
      48       59394 : hash_entries(sql_hash *h)
      49             : {
      50       59394 :         if (h)
      51       59394 :                 return h->entries;
      52             :         return 0;
      53             : }
      54             : 
      55             : int
      56       59394 : hash_empty(sql_hash *h)
      57             : {
      58       59394 :         if (h)
      59       59394 :                 return hash_entries(h) == 0;
      60             :         return 1;
      61             : }
      62             : 
      63             : void
      64        1173 : hash_del(sql_hash *h, int key, void *value)
      65             : {
      66        1173 :         sql_hash_e *e = h->buckets[key&(h->size-1)], *p = NULL;
      67             : 
      68        1234 :         while (e && (e->key != key || e->value != value)) {
      69          61 :                 p = e;
      70          61 :                 e = e->chain;
      71             :         }
      72        1173 :         if (e) {
      73        1173 :                 h->entries--;
      74        1173 :                 if (p)
      75          57 :                         p->chain = e->chain;
      76             :                 else
      77        1116 :                         h->buckets[key&(h->size-1)] = e->chain;
      78        1173 :                 if (!h->sa)
      79        1173 :                         _DELETE(e);
      80             :         }
      81        1173 : }
      82             : 
      83             : /* clear all hash table entries */
      84             : void
      85           0 : hash_clear(sql_hash *h) /* this code should be called for hash tables created outside SQL allocators only! */
      86             : {
      87           0 :         if (h == NULL || h->sa)
      88             :                 return;
      89           0 :         for (int i = 0; i < h->size; i++) {
      90           0 :                 sql_hash_e *e = h->buckets[i], *c = NULL;
      91             : 
      92           0 :                 if (e)
      93           0 :                         c = e->chain;
      94           0 :                 while (c) {
      95           0 :                         sql_hash_e *next = c->chain;
      96             : 
      97           0 :                         _DELETE(c);
      98           0 :                         c = next;
      99             :                 }
     100           0 :                 _DELETE(e);
     101           0 :                 h->buckets[i] = NULL;
     102             :         }
     103           0 :         h->entries = 0;
     104             : }
     105             : 
     106             : void
     107      298208 : hash_destroy(sql_hash *h) /* this code should be called for hash tables created outside SQL allocators only! */
     108             : {
     109      298208 :         if (h == NULL || h->sa)
     110             :                 return;
     111     5442781 :         for (int i = 0; i < h->size; i++) {
     112     5151104 :                 sql_hash_e *e = h->buckets[i], *c = NULL;
     113             : 
     114     5151104 :                 if (e)
     115      845538 :                         c = e->chain;
     116     5823084 :                 while (c) {
     117      671980 :                         sql_hash_e *next = c->chain;
     118             : 
     119      671980 :                         _DELETE(c);
     120      671980 :                         c = next;
     121             :                 }
     122     5151104 :                 _DELETE(e);
     123             :         }
     124      291677 :         _DELETE(h->buckets);
     125      291677 :         _DELETE(h);
     126             : }