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     1334512 : log_base2(unsigned int n)
      19             : {
      20     1334512 :         unsigned int l ;
      21             : 
      22     6379785 :         for (l = 0; n; l++)
      23     5045273 :                 n >>= 1 ;
      24     1334512 :         return l ;
      25             : }
      26             : 
      27             : sql_hash *
      28     1334519 : hash_new(sql_allocator *sa, int size, fkeyvalue key)
      29             : {
      30     1334519 :         sql_hash *ht = SA_NEW(sa, sql_hash);
      31             : 
      32     1334512 :         if (ht == NULL)
      33             :                 return NULL;
      34     1334512 :         ht->sa = sa;
      35     1334512 :         ht->entries = 0;
      36     1334512 :         ht->size = (1<<log_base2(size-1));
      37     1334512 :         ht->key = key;
      38     1334512 :         ht->buckets = (ht->sa)?SA_ZNEW_ARRAY(sa, sql_hash_e*, ht->size):ZNEW_ARRAY(sql_hash_e*, ht->size);
      39     1334508 :         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       58439 : hash_entries(sql_hash *h)
      49             : {
      50       58439 :         if (h)
      51       58439 :                 return h->entries;
      52             :         return 0;
      53             : }
      54             : 
      55             : int
      56       58439 : hash_empty(sql_hash *h)
      57             : {
      58       58439 :         if (h)
      59       58439 :                 return hash_entries(h) == 0;
      60             :         return 1;
      61             : }
      62             : 
      63             : void
      64        1172 : hash_del(sql_hash *h, int key, void *value)
      65             : {
      66        1172 :         sql_hash_e *e = h->buckets[key&(h->size-1)], *p = NULL;
      67             : 
      68        1233 :         while (e && (e->key != key || e->value != value)) {
      69          61 :                 p = e;
      70          61 :                 e = e->chain;
      71             :         }
      72        1172 :         if (e) {
      73        1172 :                 h->entries--;
      74        1172 :                 if (p)
      75          57 :                         p->chain = e->chain;
      76             :                 else
      77        1115 :                         h->buckets[key&(h->size-1)] = e->chain;
      78        1172 :                 if (!h->sa)
      79        1172 :                         _DELETE(e);
      80             :         }
      81        1172 : }
      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      299643 : hash_destroy(sql_hash *h) /* this code should be called for hash tables created outside SQL allocators only! */
     108             : {
     109      299643 :         if (h == NULL || h->sa)
     110             :                 return;
     111     5456193 :         for (int i = 0; i < h->size; i++) {
     112     5162960 :                 sql_hash_e *e = h->buckets[i], *c = NULL;
     113             : 
     114     5162960 :                 if (e)
     115      842651 :                         c = e->chain;
     116     5831879 :                 while (c) {
     117      668919 :                         sql_hash_e *next = c->chain;
     118             : 
     119      668919 :                         _DELETE(c);
     120      668919 :                         c = next;
     121             :                 }
     122     5162960 :                 _DELETE(e);
     123             :         }
     124      293233 :         _DELETE(h->buckets);
     125      293233 :         _DELETE(h);
     126             : }