LCOV - code coverage report
Current view: top level - gdk - gdk_hash.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 47 60 78.3 %
Date: 2021-09-14 19:48:19 Functions: 5 5 100.0 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : #ifndef _GDK_SEARCH_H_
      10             : #define _GDK_SEARCH_H_
      11             : 
      12             : struct Hash {
      13             :         int type;               /* type of index entity */
      14             :         uint8_t width;          /* width of hash entries */
      15             :         BUN mask1;              /* .mask1 < .nbucket <= .mask2 */
      16             :         BUN mask2;              /* ... both are power-of-two minus one */
      17             :         BUN nbucket;            /* number of valid hash buckets */
      18             :         BUN nunique;            /* number of unique values */
      19             :         BUN nheads;             /* number of chain heads */
      20             :         void *Bckt;             /* hash buckets, points into .heapbckt */
      21             :         void *Link;             /* collision list, points into .heaplink */
      22             :         Heap heaplink;          /* heap where the hash links are stored */
      23             :         Heap heapbckt;          /* heap where the hash buckets are stored */
      24             : };
      25             : 
      26             : static inline BUN
      27             : HASHbucket(const Hash *h, BUN v)
      28             : {
      29   827034388 :         return (v &= h->mask2) < h->nbucket ? v : v & h->mask1;
      30             : }
      31             : 
      32             : gdk_export gdk_return BAThash(BAT *b);
      33             : gdk_export void HASHdestroy(BAT *b);
      34             : gdk_export BUN HASHprobe(const Hash *h, const void *v);
      35             : gdk_export BUN HASHlist(Hash *h, BUN i);
      36             : 
      37             : #define BUN2 2
      38             : #define BUN4 4
      39             : #if SIZEOF_BUN == 8
      40             : #define BUN8 8
      41             : #endif
      42             : #ifdef BUN2
      43             : typedef uint16_t BUN2type;
      44             : #endif
      45             : typedef uint32_t BUN4type;
      46             : #if SIZEOF_BUN > 4
      47             : typedef uint64_t BUN8type;
      48             : #endif
      49             : #ifdef BUN2
      50             : #define BUN2_NONE ((BUN2type) UINT16_C(0xFFFF))
      51             : #endif
      52             : #define BUN4_NONE ((BUN4type) UINT32_C(0xFFFFFFFF))
      53             : #ifdef BUN8
      54             : #define BUN8_NONE ((BUN8type) UINT64_C(0xFFFFFFFFFFFFFFFF))
      55             : #endif
      56             : 
      57             : /* play around with h->Bckt[i] and h->Link[j] */
      58             : 
      59             : static inline void
      60   379937570 : HASHput(Hash *h, BUN i, BUN v)
      61             : {
      62             :         /* if v == BUN_NONE, assigning the value to a BUN2type
      63             :          * etc. automatically converts to BUN2_NONE etc. */
      64   379937570 :         switch (h->width) {
      65             : #ifdef BUN2
      66   167245937 :         case BUN2:
      67   167245937 :                 ((BUN2type *) h->Bckt)[i] = (BUN2type) v;
      68   167245937 :                 break;
      69             : #endif
      70   212691633 :         default:                /* BUN4 */
      71   212691633 :                 ((BUN4type *) h->Bckt)[i] = (BUN4type) v;
      72   212691633 :                 break;
      73             : #ifdef BUN8
      74           0 :         case BUN8:
      75           0 :                 ((BUN8type *) h->Bckt)[i] = (BUN8type) v;
      76           0 :                 break;
      77             : #endif
      78             :         }
      79   379937570 : }
      80             : 
      81             : static inline void
      82   381035500 : HASHputlink(Hash *h, BUN i, BUN v)
      83             : {
      84             :         /* if v == BUN_NONE, assigning the value to a BUN2type
      85             :          * etc. automatically converts to BUN2_NONE etc. */
      86   381035500 :         switch (h->width) {
      87             : #ifdef BUN2
      88   167994279 :         case BUN2:
      89   167994279 :                 assert(v == BUN_NONE || v == BUN2_NONE || v < i);
      90   167994279 :                 ((BUN2type *) h->Link)[i] = (BUN2type) v;
      91   167994279 :                 break;
      92             : #endif
      93   213041221 :         default:                /* BUN4 */
      94   213041221 :                 assert(v == BUN_NONE || v == BUN4_NONE || v < i);
      95   213041221 :                 ((BUN4type *) h->Link)[i] = (BUN4type) v;
      96   213041221 :                 break;
      97             : #ifdef BUN8
      98           0 :         case BUN8:
      99           0 :                 assert(v == BUN_NONE || v == BUN8_NONE || v < i);
     100           0 :                 ((BUN8type *) h->Link)[i] = (BUN8type) v;
     101           0 :                 break;
     102             : #endif
     103             :         }
     104   381035500 : }
     105             : 
     106             : static inline BUN __attribute__((__pure__))
     107   906302608 : HASHget(const Hash *h, BUN i)
     108             : {
     109   906302608 :         switch (h->width) {
     110             : #ifdef BUN2
     111   282876989 :         case BUN2:
     112   282876989 :                 i = (BUN) ((BUN2type *) h->Bckt)[i];
     113   282876989 :                 return i == BUN2_NONE ? BUN_NONE : i;
     114             : #endif
     115   623425619 :         default:                /* BUN4 */
     116   623425619 :                 i = (BUN) ((BUN4type *) h->Bckt)[i];
     117   623425619 :                 return i == BUN4_NONE ? BUN_NONE : i;
     118             : #ifdef BUN8
     119           0 :         case BUN8:
     120           0 :                 i = (BUN) ((BUN8type *) h->Bckt)[i];
     121           0 :                 return i == BUN8_NONE ? BUN_NONE : i;
     122             : #endif
     123             :         }
     124             : }
     125             : 
     126             : static inline BUN __attribute__((__pure__))
     127   510559551 : HASHgetlink(const Hash *h, BUN i)
     128             : {
     129   510559551 :         switch (h->width) {
     130             : #ifdef BUN2
     131   299512174 :         case BUN2:
     132   299512174 :                 i = (BUN) ((BUN2type *) h->Link)[i];
     133   299512174 :                 return i == BUN2_NONE ? BUN_NONE : i;
     134             : #endif
     135   211047377 :         default:                /* BUN4 */
     136   211047377 :                 i = (BUN) ((BUN4type *) h->Link)[i];
     137   211047377 :                 return i == BUN4_NONE ? BUN_NONE : i;
     138             : #ifdef BUN8
     139           0 :         case BUN8:
     140           0 :                 i = (BUN) ((BUN8type *) h->Link)[i];
     141           0 :                 return i == BUN8_NONE ? BUN_NONE : i;
     142             : #endif
     143             :         }
     144             : }
     145             : 
     146             : /* mix_bte(0x80) == 0x80 */
     147             : #define mix_bte(X)      ((unsigned int) (unsigned char) (X))
     148             : /* mix_sht(0x8000) == 0x8000 */
     149             : #define mix_sht(X)      ((unsigned int) (unsigned short) (X))
     150             : /* mix_int(0x81060038) == 0x80000000 */
     151             : #define mix_int(X)      (((unsigned int) (X) >> 7) ^      \
     152             :                          ((unsigned int) (X) >> 13) ^     \
     153             :                          ((unsigned int) (X) >> 21) ^     \
     154             :                          (unsigned int) (X))
     155             : /* mix_lng(0x810600394347424F) == 0x8000000000000000 */
     156             : #define mix_lng(X)      (((ulng) (X) >> 7) ^      \
     157             :                          ((ulng) (X) >> 13) ^     \
     158             :                          ((ulng) (X) >> 21) ^     \
     159             :                          ((ulng) (X) >> 31) ^     \
     160             :                          ((ulng) (X) >> 38) ^     \
     161             :                          ((ulng) (X) >> 46) ^     \
     162             :                          ((ulng) (X) >> 56) ^     \
     163             :                          (ulng) (X))
     164             : #ifdef HAVE_HGE
     165             : /* mix_hge(0x810600394347424F90AC1429D6BFCC57) ==
     166             :  * 0x80000000000000000000000000000000 */
     167             : #define mix_hge(X)      (((uhge) (X) >> 7) ^      \
     168             :                          ((uhge) (X) >> 13) ^     \
     169             :                          ((uhge) (X) >> 21) ^     \
     170             :                          ((uhge) (X) >> 31) ^     \
     171             :                          ((uhge) (X) >> 38) ^     \
     172             :                          ((uhge) (X) >> 46) ^     \
     173             :                          ((uhge) (X) >> 56) ^     \
     174             :                          ((uhge) (X) >> 65) ^     \
     175             :                          ((uhge) (X) >> 70) ^     \
     176             :                          ((uhge) (X) >> 78) ^     \
     177             :                          ((uhge) (X) >> 85) ^     \
     178             :                          ((uhge) (X) >> 90) ^     \
     179             :                          ((uhge) (X) >> 98) ^     \
     180             :                          ((uhge) (X) >> 107) ^    \
     181             :                          ((uhge) (X) >> 116) ^    \
     182             :                          (uhge) (X))
     183             : #endif
     184             : #define hash_loc(H,V)   hash_any(H,V)
     185             : #define hash_var(H,V)   hash_any(H,V)
     186             : #define hash_any(H,V)   HASHbucket(H, ATOMhash((H)->type, (V)))
     187             : #define hash_bte(H,V)   (assert((H)->nbucket >= 256), (BUN) mix_bte(*(const unsigned char*) (V)))
     188             : #define hash_sht(H,V)   (assert((H)->nbucket >= 65536), (BUN) mix_sht(*(const unsigned short*) (V)))
     189             : #define hash_int(H,V)   HASHbucket(H, (BUN) mix_int(*(const unsigned int *) (V)))
     190             : /* XXX return size_t-sized value for 8-byte oid? */
     191             : #define hash_lng(H,V)   HASHbucket(H, (BUN) mix_lng(*(const ulng *) (V)))
     192             : #ifdef HAVE_HGE
     193             : #define hash_hge(H,V)   HASHbucket(H, (BUN) mix_hge(*(const uhge *) (V)))
     194             : #endif
     195             : #if SIZEOF_OID == SIZEOF_INT
     196             : #define hash_oid(H,V)   hash_int(H,V)
     197             : #else
     198             : #define hash_oid(H,V)   hash_lng(H,V)
     199             : #endif
     200             : 
     201             : #define hash_flt(H,V)   hash_int(H,V)
     202             : #define hash_dbl(H,V)   hash_lng(H,V)
     203             : 
     204             : static inline BUN __attribute__((__const__))
     205          49 : mix_uuid(uuid u)
     206             : {
     207             :         ulng u1, u2;
     208             : 
     209          49 :         u1 = (ulng) (uint8_t) u.u[0] << 56 | (ulng) (uint8_t) u.u[1] << 48 |
     210          49 :                 (ulng) (uint8_t) u.u[2] << 40 | (ulng) (uint8_t) u.u[3] << 32 |
     211          49 :                 (ulng) (uint8_t) u.u[4] << 24 | (ulng) (uint8_t) u.u[5] << 16 |
     212          49 :                 (ulng) (uint8_t) u.u[6] << 8 | (ulng) (uint8_t) u.u[7];
     213          49 :         u2 = (ulng) (uint8_t) u.u[8] << 56 | (ulng) (uint8_t) u.u[9] << 48 |
     214          49 :                 (ulng) (uint8_t) u.u[10] << 40 | (ulng) (uint8_t) u.u[11] << 32 |
     215          49 :                 (ulng) (uint8_t) u.u[12] << 24 | (ulng) (uint8_t) u.u[13] << 16 |
     216          49 :                 (ulng) (uint8_t) u.u[14] << 8 | (ulng) (uint8_t) u.u[15];
     217             :         /* we're not using mix_hge since this way we get the same result
     218             :          * on systems with and without 128 bit integer support */
     219          49 :         return (BUN) (mix_lng(u1) ^ mix_lng(u2));
     220             : }
     221             : #define hash_uuid(H,V)  HASHbucket(H, mix_uuid(*(const uuid *) (V)))
     222             : 
     223             : /*
     224             :  * @- hash-table supported loop over BUNs The first parameter `bi' is
     225             :  * a BAT iterator, the second (`h') should point to the Hash
     226             :  * structure, and `v' a pointer to an atomic value (corresponding to
     227             :  * the head column of `b'). The 'hb' is an BUN index, pointing out the
     228             :  * `hb'-th BUN.
     229             :  */
     230             : #define HASHloop(bi, h, hb, v)                                  \
     231             :         for (hb = HASHget(h, HASHprobe(h, v));                  \
     232             :              hb != BUN_NONE;                                    \
     233             :              hb = HASHgetlink(h, hb))                           \
     234             :                 if (ATOMcmp(h->type, v, BUNtail(bi, hb)) == 0)
     235             : #define HASHloop_str_hv(bi, h, hb, v)                           \
     236             :         for (hb = HASHget(h, HASHbucket(h, ((BUN *) (v))[-1])); \
     237             :              hb != BUN_NONE;                                    \
     238             :              hb = HASHgetlink(h, hb))                           \
     239             :                 if (strEQ(v, BUNtvar(bi, hb)))
     240             : #define HASHloop_str(bi, h, hb, v)                              \
     241             :         for (hb = HASHget(h, HASHbucket(h, strHash(v)));        \
     242             :              hb != BUN_NONE;                                    \
     243             :              hb = HASHgetlink(h, hb))                           \
     244             :                 if (strEQ(v, BUNtvar(bi, hb)))
     245             : 
     246             : #define HASHlooploc(bi, h, hb, v)                               \
     247             :         for (hb = HASHget(h, HASHprobe(h, v));                  \
     248             :              hb != BUN_NONE;                                    \
     249             :              hb = HASHgetlink(h, hb))                           \
     250             :                 if (ATOMcmp(h->type, v, BUNtloc(bi, hb)) == 0)
     251             : #define HASHloopvar(bi, h, hb, v)                               \
     252             :         for (hb = HASHget(h, HASHprobe(h, v));                  \
     253             :              hb != BUN_NONE;                                    \
     254             :              hb = HASHgetlink(h, hb))                           \
     255             :                 if (ATOMcmp(h->type, v, BUNtvar(bi, hb)) == 0)
     256             : 
     257             : #define HASHloop_TYPE(bi, h, hb, v, TYPE)                               \
     258             :         for (hb = HASHget(h, hash_##TYPE(h, v));                        \
     259             :              hb != BUN_NONE;                                            \
     260             :              hb = HASHgetlink(h,hb))                                    \
     261             :                 if (* (const TYPE *) (v) == * (const TYPE *) BUNtloc(bi, hb))
     262             : 
     263             : /* need to take special care comparing nil floating point values */
     264             : #define HASHloop_fTYPE(bi, h, hb, v, TYPE)                              \
     265             :         for (hb = HASHget(h, hash_##TYPE(h, v));                        \
     266             :              hb != BUN_NONE;                                            \
     267             :              hb = HASHgetlink(h,hb))                                    \
     268             :                 if (is_##TYPE##_nil(* (const TYPE *) (v))               \
     269             :                     ? is_##TYPE##_nil(* (const TYPE *) BUNtloc(bi, hb)) \
     270             :                     : * (const TYPE *) (v) == * (const TYPE *) BUNtloc(bi, hb))
     271             : 
     272             : #define HASHloop_bte(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, bte)
     273             : #define HASHloop_sht(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, sht)
     274             : #define HASHloop_int(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, int)
     275             : #define HASHloop_lng(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, lng)
     276             : #ifdef HAVE_HGE
     277             : #define HASHloop_hge(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, hge)
     278             : #endif
     279             : #define HASHloop_flt(bi, h, hb, v)      HASHloop_fTYPE(bi, h, hb, v, flt)
     280             : #define HASHloop_dbl(bi, h, hb, v)      HASHloop_fTYPE(bi, h, hb, v, dbl)
     281             : #ifdef HAVE_HGE
     282             : #define HASHloop_uuid(bi, hsh, hb, v)                                   \
     283             :         for (hb = HASHget(hsh, hash_uuid(hsh, v));                      \
     284             :              hb != BUN_NONE;                                            \
     285             :              hb = HASHgetlink(hsh,hb))                                  \
     286             :                 if (((const uuid *) (v))->h == ((const uuid *) BUNtloc(bi, hb))->h)
     287             : #else
     288             : #define HASHloop_uuid(bi, h, hb, v)                                     \
     289             :         for (hb = HASHget(h, hash_uuid(h, v));                          \
     290             :              hb != BUN_NONE;                                            \
     291             :              hb = HASHgetlink(h,hb))                                    \
     292             :                 if (memcmp((const uuid *) (v), (const uuid *) BUNtloc(bi, hb), 16) == 0)
     293             : //              if (((const uuid *) (v))->l[0] == ((const uuid *) BUNtloc(bi, hb))->l[0] && ((const uuid *) (v))->l[1] == ((const uuid *) BUNtloc(bi, hb))->l[1])
     294             : #endif
     295             : 
     296             : #endif /* _GDK_SEARCH_H_ */

Generated by: LCOV version 1.14