LCOV - code coverage report
Current view: top level - gdk - gdk_hash.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 38 40 95.0 %
Date: 2020-06-29 20:00:14 Functions: 0 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 - 2020 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 nil;                /* nil representation */
      19             :         BUN nunique;            /* number of unique values */
      20             :         BUN nheads;             /* number of chain heads */
      21             :         void *Bckt;             /* hash buckets, points into .heapbckt */
      22             :         void *Link;             /* collision list, points into .heaplink */
      23             :         Heap heaplink;          /* heap where the hash links are stored */
      24             :         Heap heapbckt;          /* heap where the hash buckets are stored */
      25             : };
      26             : 
      27             : static inline BUN
      28   834192085 : HASHbucket(const Hash *h, BUN v)
      29             : {
      30   766808085 :         return (v &= h->mask2) < h->nbucket ? v : v & h->mask1;
      31             : }
      32             : 
      33             : gdk_export gdk_return BAThash(BAT *b);
      34             : gdk_export void HASHdestroy(BAT *b);
      35             : gdk_export BUN HASHprobe(const Hash *h, const void *v);
      36             : gdk_export BUN HASHlist(Hash *h, BUN i);
      37             : gdk_export gdk_return HASHgrowbucket(BAT *b);
      38             : 
      39             : #define HASHnil(H)      (H)->nil
      40             : 
      41             : #define BUN2 2
      42             : #define BUN4 4
      43             : #if SIZEOF_BUN > 4
      44             : #define BUN8 8
      45             : #endif
      46             : typedef uint16_t BUN2type;
      47             : typedef uint32_t BUN4type;
      48             : #if SIZEOF_BUN > 4
      49             : typedef uint64_t BUN8type;
      50             : #endif
      51             : #define BUN2_NONE ((BUN2type) UINT16_C(0xFFFF))
      52             : #define BUN4_NONE ((BUN4type) UINT32_C(0xFFFFFFFF))
      53             : #if SIZEOF_BUN > 4
      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   284158834 : HASHput(Hash *h, BUN i, BUN v)
      61             : {
      62   284158834 :         switch (h->width) {
      63    31096304 :         default:                /* BUN2 */
      64    31096304 :                 ((BUN2type *) h->Bckt)[i] = (BUN2type) v;
      65    31096304 :                 break;
      66   253052780 :         case BUN4:
      67   253052780 :                 ((BUN4type *) h->Bckt)[i] = (BUN4type) v;
      68   253052780 :                 break;
      69             : #if SIZEOF_BUN == 8
      70       11270 :         case BUN8:
      71       11270 :                 ((BUN8type *) h->Bckt)[i] = (BUN8type) v;
      72       11270 :                 break;
      73             : #endif
      74             :         }
      75             : }
      76             : 
      77             : static inline void
      78   284098134 : HASHputlink(Hash *h, BUN i, BUN v)
      79             : {
      80   284098134 :         switch (h->width) {
      81    31034504 :         default:                /* BUN2 */
      82    31034504 :                 ((BUN2type *) h->Link)[i] = (BUN2type) v;
      83    31034504 :                 break;
      84   253069869 :         case BUN4:
      85   253069869 :                 ((BUN4type *) h->Link)[i] = (BUN4type) v;
      86   253069869 :                 break;
      87             : #if SIZEOF_BUN == 8
      88           1 :         case BUN8:
      89           1 :                 ((BUN8type *) h->Link)[i] = (BUN8type) v;
      90           1 :                 break;
      91             : #endif
      92             :         }
      93             : }
      94             : 
      95             : static inline BUN
      96   975254751 : HASHget(Hash *h, BUN i)
      97             : {
      98   975254751 :         switch (h->width) {
      99   288844832 :         default:                /* BUN2 */
     100   288844832 :                 return (BUN) ((BUN2type *) h->Bckt)[i];
     101   686460159 :         case BUN4:
     102   686460159 :                 return (BUN) ((BUN4type *) h->Bckt)[i];
     103             : #if SIZEOF_BUN == 8
     104          17 :         case BUN8:
     105          17 :                 return (BUN) ((BUN8type *) h->Bckt)[i];
     106             : #endif
     107             :         }
     108             : }
     109             : 
     110             : static inline BUN
     111   323020147 : HASHgetlink(Hash *h, BUN i)
     112             : {
     113   323020147 :         switch (h->width) {
     114   183696769 :         default:                /* BUN2 */
     115   183696769 :                 return (BUN) ((BUN2type *) h->Link)[i];
     116   139333994 :         case BUN4:
     117   139333994 :                 return (BUN) ((BUN4type *) h->Link)[i];
     118             : #if SIZEOF_BUN == 8
     119           0 :         case BUN8:
     120           0 :                 return (BUN) ((BUN8type *) h->Link)[i];
     121             : #endif
     122             :         }
     123             : }
     124             : 
     125             : /* mix_bte(0x80) == 0x80 */
     126             : #define mix_bte(X)      ((unsigned int) (unsigned char) (X))
     127             : /* mix_sht(0x8000) == 0x8000 */
     128             : #define mix_sht(X)      ((unsigned int) (unsigned short) (X))
     129             : /* mix_int(0x81060038) == 0x80000000 */
     130             : #define mix_int(X)      (((unsigned int) (X) >> 7) ^      \
     131             :                          ((unsigned int) (X) >> 13) ^     \
     132             :                          ((unsigned int) (X) >> 21) ^     \
     133             :                          (unsigned int) (X))
     134             : /* mix_lng(0x810600394347424F) == 0x8000000000000000 */
     135             : #define mix_lng(X)      (((ulng) (X) >> 7) ^      \
     136             :                          ((ulng) (X) >> 13) ^     \
     137             :                          ((ulng) (X) >> 21) ^     \
     138             :                          ((ulng) (X) >> 31) ^     \
     139             :                          ((ulng) (X) >> 38) ^     \
     140             :                          ((ulng) (X) >> 46) ^     \
     141             :                          ((ulng) (X) >> 56) ^     \
     142             :                          (ulng) (X))
     143             : #ifdef HAVE_HGE
     144             : /* mix_hge(0x810600394347424F90AC1429D6BFCC57) ==
     145             :  * 0x80000000000000000000000000000000 */
     146             : #define mix_hge(X)      (((uhge) (X) >> 7) ^      \
     147             :                          ((uhge) (X) >> 13) ^     \
     148             :                          ((uhge) (X) >> 21) ^     \
     149             :                          ((uhge) (X) >> 31) ^     \
     150             :                          ((uhge) (X) >> 38) ^     \
     151             :                          ((uhge) (X) >> 46) ^     \
     152             :                          ((uhge) (X) >> 56) ^     \
     153             :                          ((uhge) (X) >> 65) ^     \
     154             :                          ((uhge) (X) >> 70) ^     \
     155             :                          ((uhge) (X) >> 78) ^     \
     156             :                          ((uhge) (X) >> 85) ^     \
     157             :                          ((uhge) (X) >> 90) ^     \
     158             :                          ((uhge) (X) >> 98) ^     \
     159             :                          ((uhge) (X) >> 107) ^    \
     160             :                          ((uhge) (X) >> 116) ^    \
     161             :                          (uhge) (X))
     162             : #endif
     163             : #define hash_loc(H,V)   hash_any(H,V)
     164             : #define hash_var(H,V)   hash_any(H,V)
     165             : #define hash_any(H,V)   HASHbucket(H, ATOMhash((H)->type, (V)))
     166             : #define hash_bte(H,V)   (assert((H)->nbucket >= 256), (BUN) mix_bte(*(const unsigned char*) (V)))
     167             : #define hash_sht(H,V)   (assert((H)->nbucket >= 65536), (BUN) mix_sht(*(const unsigned short*) (V)))
     168             : #define hash_int(H,V)   HASHbucket(H, (BUN) mix_int(*(const unsigned int *) (V)))
     169             : /* XXX return size_t-sized value for 8-byte oid? */
     170             : #define hash_lng(H,V)   HASHbucket(H, (BUN) mix_lng(*(const ulng *) (V)))
     171             : #ifdef HAVE_HGE
     172             : #define hash_hge(H,V)   HASHbucket(H, (BUN) mix_hge(*(const uhge *) (V)))
     173             : #endif
     174             : #if SIZEOF_OID == SIZEOF_INT
     175             : #define hash_oid(H,V)   hash_int(H,V)
     176             : #else
     177             : #define hash_oid(H,V)   hash_lng(H,V)
     178             : #endif
     179             : 
     180             : #define hash_flt(H,V)   hash_int(H,V)
     181             : #define hash_dbl(H,V)   hash_lng(H,V)
     182             : 
     183             : /*
     184             :  * @- hash-table supported loop over BUNs The first parameter `bi' is
     185             :  * a BAT iterator, the second (`h') should point to the Hash
     186             :  * structure, and `v' a pointer to an atomic value (corresponding to
     187             :  * the head column of `b'). The 'hb' is an BUN index, pointing out the
     188             :  * `hb'-th BUN.
     189             :  */
     190             : #define HASHloop(bi, h, hb, v)                                  \
     191             :         for (hb = HASHget(h, HASHprobe(h, v));                  \
     192             :              hb != HASHnil(h);                                  \
     193             :              hb = HASHgetlink(h, hb))                           \
     194             :                 if (ATOMcmp(h->type, v, BUNtail(bi, hb)) == 0)
     195             : #define HASHloop_str_hv(bi, h, hb, v)                           \
     196             :         for (hb = HASHget(h, HASHbucket(h, ((BUN *) (v))[-1])); \
     197             :              hb != HASHnil(h);                                  \
     198             :              hb = HASHgetlink(h, hb))                           \
     199             :                 if (strEQ(v, BUNtvar(bi, hb)))
     200             : #define HASHloop_str(bi, h, hb, v)                              \
     201             :         for (hb = HASHget(h, HASHbucket(h, strHash(v)));        \
     202             :              hb != HASHnil(h);                                  \
     203             :              hb = HASHgetlink(h, hb))                           \
     204             :                 if (strEQ(v, BUNtvar(bi, hb)))
     205             : 
     206             : #define HASHlooploc(bi, h, hb, v)                               \
     207             :         for (hb = HASHget(h, HASHprobe(h, v));                  \
     208             :              hb != HASHnil(h);                                  \
     209             :              hb = HASHgetlink(h, hb))                           \
     210             :                 if (ATOMcmp(h->type, v, BUNtloc(bi, hb)) == 0)
     211             : #define HASHloopvar(bi, h, hb, v)                               \
     212             :         for (hb = HASHget(h, HASHprobe(h, v));                  \
     213             :              hb != HASHnil(h);                                  \
     214             :              hb = HASHgetlink(h, hb))                           \
     215             :                 if (ATOMcmp(h->type, v, BUNtvar(bi, hb)) == 0)
     216             : 
     217             : #define HASHloop_TYPE(bi, h, hb, v, TYPE)                               \
     218             :         for (hb = HASHget(h, hash_##TYPE(h, v));                        \
     219             :              hb != HASHnil(h);                                          \
     220             :              hb = HASHgetlink(h,hb))                                    \
     221             :                 if (* (const TYPE *) (v) == * (const TYPE *) BUNtloc(bi, hb))
     222             : 
     223             : /* need to take special care comparing nil floating point values */
     224             : #define HASHloop_fTYPE(bi, h, hb, v, TYPE)                              \
     225             :         for (hb = HASHget(h, hash_##TYPE(h, v));                        \
     226             :              hb != HASHnil(h);                                          \
     227             :              hb = HASHgetlink(h,hb))                                    \
     228             :                 if (is_##TYPE##_nil(* (const TYPE *) (v))               \
     229             :                     ? is_##TYPE##_nil(* (const TYPE *) BUNtloc(bi, hb)) \
     230             :                     : * (const TYPE *) (v) == * (const TYPE *) BUNtloc(bi, hb))
     231             : 
     232             : #define HASHloop_bte(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, bte)
     233             : #define HASHloop_sht(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, sht)
     234             : #define HASHloop_int(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, int)
     235             : #define HASHloop_lng(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, lng)
     236             : #ifdef HAVE_HGE
     237             : #define HASHloop_hge(bi, h, hb, v)      HASHloop_TYPE(bi, h, hb, v, hge)
     238             : #endif
     239             : #define HASHloop_flt(bi, h, hb, v)      HASHloop_fTYPE(bi, h, hb, v, flt)
     240             : #define HASHloop_dbl(bi, h, hb, v)      HASHloop_fTYPE(bi, h, hb, v, dbl)
     241             : 
     242             : #define HASHfnd_str(x,y,z)                                              \
     243             :         do {                                                            \
     244             :                 BUN _i;                                                 \
     245             :                 (x) = BUN_NONE;                                         \
     246             :                 if (BAThash((y).b) == GDK_SUCCEED) {                    \
     247             :                         HASHloop_str((y), (y).b->thash, _i, (z)) {   \
     248             :                                 (x) = _i;                               \
     249             :                                 break;                                  \
     250             :                         }                                               \
     251             :                 } else                                                  \
     252             :                         goto hashfnd_failed;                            \
     253             :         } while (0)
     254             : #define HASHfnd(x,y,z)                                          \
     255             :         do {                                                    \
     256             :                 BUN _i;                                         \
     257             :                 (x) = BUN_NONE;                                 \
     258             :                 if (BAThash((y).b) == GDK_SUCCEED) {            \
     259             :                         HASHloop((y), (y).b->thash, _i, (z)) {       \
     260             :                                 (x) = _i;                       \
     261             :                                 break;                          \
     262             :                         }                                       \
     263             :                 } else                                          \
     264             :                         goto hashfnd_failed;                    \
     265             :         } while (0)
     266             : #define HASHfnd_TYPE(x,y,z,TYPE)                                        \
     267             :         do {                                                            \
     268             :                 BUN _i;                                                 \
     269             :                 (x) = BUN_NONE;                                         \
     270             :                 if (BAThash((y).b) == GDK_SUCCEED) {                    \
     271             :                         HASHloop_##TYPE((y), (y).b->thash, _i, (z)) {        \
     272             :                                 (x) = _i;                               \
     273             :                                 break;                                  \
     274             :                         }                                               \
     275             :                 } else                                                  \
     276             :                         goto hashfnd_failed;                            \
     277             :         } while (0)
     278             : #define HASHfnd_bte(x,y,z)      HASHfnd_TYPE(x,y,z,bte)
     279             : #define HASHfnd_sht(x,y,z)      HASHfnd_TYPE(x,y,z,sht)
     280             : #define HASHfnd_int(x,y,z)      HASHfnd_TYPE(x,y,z,int)
     281             : #define HASHfnd_lng(x,y,z)      HASHfnd_TYPE(x,y,z,lng)
     282             : #ifdef HAVE_HGE
     283             : #define HASHfnd_hge(x,y,z)      HASHfnd_TYPE(x,y,z,hge)
     284             : #endif
     285             : #define HASHfnd_flt(x,y,z)      HASHfnd_TYPE(x,y,z,flt)
     286             : #define HASHfnd_dbl(x,y,z)      HASHfnd_TYPE(x,y,z,dbl)
     287             : 
     288             : #endif /* _GDK_SEARCH_H_ */

Generated by: LCOV version 1.14