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             : #ifndef SQL_HASH_H
      14             : #define SQL_HASH_H
      15             : 
      16             : /* sql_hash implementation
      17             :  * used to optimize search in expression and statement lists
      18             :  */
      19             : 
      20             : #include "sql_mem.h"
      21             : 
      22             : #define HASH_MIN_SIZE 4
      23             : 
      24             : typedef int (*fkeyvalue) (void *data);
      25             : 
      26             : typedef struct sql_hash_e {
      27             :         int key;
      28             :         void *value;
      29             :         struct sql_hash_e *chain;
      30             : } sql_hash_e;
      31             : 
      32             : typedef struct sql_hash {
      33             :         allocator *sa;
      34             :         int size; /* power of 2 */
      35             :         sql_hash_e **buckets;
      36             :         fkeyvalue key;
      37             :         int entries;
      38             : } sql_hash;
      39             : 
      40             : extern sql_hash *hash_new(allocator *sa, int size, fkeyvalue key);
      41             : extern int hash_entries(sql_hash *h);
      42             : extern int hash_empty(sql_hash *h);
      43             : extern void hash_del(sql_hash *ht, int key, void *value);
      44             : extern void hash_clear(sql_hash *h);
      45             : extern void hash_destroy(sql_hash *h);
      46             : 
      47             : static inline sql_hash_e*
      48    13090265 : hash_add(sql_hash *h, int key, void *value)
      49             : {
      50    13090265 :         sql_hash_e *e = (h->sa)?SA_NEW(h->sa, sql_hash_e):MNEW(sql_hash_e);
      51             : 
      52    13090279 :         if (e == NULL)
      53             :                 return NULL;
      54    13090279 :         e->chain = h->buckets[key&(h->size-1)];
      55    13090279 :         h->buckets[key&(h->size-1)] = e;
      56    13090279 :         e->key = key;
      57    13090279 :         e->value = value;
      58    13090279 :         h->entries++;
      59    13090279 :         return e;
      60             : }
      61             : 
      62             : static inline unsigned int
      63    19397277 : hash_key(const char *restrict k)
      64             : {
      65    19397277 :         unsigned int h = 37; /* prime number */
      66   499922109 :         while (*k) {
      67   427021615 :                 h = (h * 54059) ^ (k[0] * 76963); /* prime numbers */
      68   427021615 :                 k++;
      69             :         }
      70    72230296 :         return h;
      71             : }
      72             : 
      73             : #endif /* SQL_HASH_H */