oceanbase

1
#include "util/easy_hash.h"
2

3
#define EASY_KEY_MAX_SIZE 65
4
static uint32_t easy_hash_getm(uint32_t size);
5
static uint32_t         easy_http_hdr_hseed = 5;
6
static int easy_hash_string_tolower(const char *src, int slen, char *dst, int dlen);
7

8
/**
9
 * 创建一easy_hash_t
10
 */
11
easy_hash_t *easy_hash_create(easy_pool_t *pool, uint32_t size, int offset)
12
{
13
    easy_hash_t             *table;
14
    easy_hash_list_t        **buckets;
15
    uint32_t                n = easy_hash_getm(size);
16

17
    // alloc
18
    buckets = (easy_hash_list_t **)easy_pool_calloc(pool, n * sizeof(easy_hash_list_t *));
19
    table = (easy_hash_t *)easy_pool_alloc(pool, sizeof(easy_hash_t));
20

21
    if (table == NULL || buckets == NULL)
22
        return NULL;
23

24
    table->buckets = buckets;
25
    table->size = n;
26
    table->mask = n - 1;
27
    table->count = 0;
28
    table->offset = offset;
29
    table->seqno = 1;
30
    easy_list_init(&table->list);
31

32
    return table;
33
}
34

35
easy_hash_t *easy_hash_create_without_pool(uint32_t size, int offset)
36
{
37
    easy_pool_t* pool = easy_pool_create(4096);
38
    easy_hash_t* table = NULL;
39
    if (pool) {
40
        if (NULL == (table = easy_hash_create(pool, size, offset))) {
41
            easy_pool_destroy(pool);
42
        }
43
    }
44
    return table;
45
}
46

47
int easy_hash_add(easy_hash_t *table, uint64_t key, easy_hash_list_t *list)
48
{
49
    uint64_t                n;
50
    easy_hash_list_t        *first;
51

52
    n = easy_hash_key(key);
53
    n &= table->mask;
54

55
    // init
56
    list->key = key;
57
    table->count ++;
58
    table->seqno ++;
59

60
    // add to list
61
    first = table->buckets[n];
62
    list->next = first;
63

64
    if (first)
65
        first->pprev = &list->next;
66

67
    table->buckets[n] = (easy_hash_list_t *)list;
68
    list->pprev = &(table->buckets[n]);
69

70
    return EASY_OK;
71
}
72

73
void easy_hash_clear(easy_hash_t *table)
74
{
75
    int                     i;
76
    easy_hash_list_t        *node;
77

78
    for (i = 0; i < table->size; i++) {
79
        if ((node = table->buckets[i])) {
80
            node->pprev = NULL;
81
        }
82

83
        table->buckets[i] = NULL;
84
    }
85
}
86

87
void *easy_hash_find(easy_hash_t *table, uint64_t key)
88
{
89
    uint64_t                n;
90
    easy_hash_list_t        *list;
91

92
    n = easy_hash_key(key);
93
    n &= table->mask;
94
    list = table->buckets[n];
95

96
    // foreach
97
    while (list) {
98
        if (list->key == key) {
99
            return ((char *)list - table->offset);
100
        }
101

102
        list = list->next;
103
    }
104

105
    return NULL;
106
}
107

108
void *easy_hash_find_ex(easy_hash_t *table, uint64_t key, easy_hash_cmp_pt cmp, const void *a)
109
{
110
    uint64_t                n;
111
    easy_hash_list_t        *list;
112

113
    n = easy_hash_key(key);
114
    n &= table->mask;
115
    list = table->buckets[n];
116

117
    // foreach
118
    while (list) {
119
        if (list->key == key) {
120
            if (cmp(a, ((char *)list - table->offset)) == 0)
121
                return ((char *)list - table->offset);
122
        }
123

124
        list = list->next;
125
    }
126

127
    return NULL;
128
}
129

130
void *easy_hash_del(easy_hash_t *table, uint64_t key)
131
{
132
    uint64_t                n;
133
    easy_hash_list_t        *list;
134

135
    n = easy_hash_key(key);
136
    n &= table->mask;
137
    list = table->buckets[n];
138

139
    // foreach
140
    while (list) {
141
        if (list->key == key) {
142
            easy_hash_del_node(list);
143
            table->count --;
144

145
            return ((char *)list - table->offset);
146
        }
147

148
        list = list->next;
149
    }
150

151
    return NULL;
152
}
153

154
int easy_hash_del_node(easy_hash_list_t *node)
155
{
156
    easy_hash_list_t        *next, **pprev;
157

158
    if (!node->pprev)
159
        return 0;
160

161
    next = node->next;
162
    pprev = node->pprev;
163
    *pprev = next;
164

165
    if (next) next->pprev = pprev;
166

167
    node->next = NULL;
168
    node->pprev = NULL;
169

170
    return 1;
171
}
172

173
int easy_hash_dlist_add(easy_hash_t *table, uint64_t key, easy_hash_list_t *hash, easy_list_t *list)
174
{
175
    easy_list_add_tail(list, &table->list);
176
    return easy_hash_add(table, key, hash);
177
}
178

179
void *easy_hash_dlist_del(easy_hash_t *table, uint64_t key)
180
{
181
    char                    *object;
182

183
    if ((object = (char *)easy_hash_del(table, key)) != NULL) {
184
        easy_list_del((easy_list_t *)(object + table->offset + sizeof(easy_hash_list_t)));
185
    }
186

187
    return object;
188
}
189

190
/**
191
 * string hash
192
 */
193
easy_hash_string_t *easy_hash_string_create(easy_pool_t *pool, uint32_t size, int ignore_case)
194
{
195
    easy_hash_string_t      *table;
196
    easy_string_pair_t      **buckets;
197
    uint32_t                n = easy_hash_getm(size);
198

199
    // alloc
200
    buckets = (easy_string_pair_t **)easy_pool_calloc(pool, n * sizeof(easy_string_pair_t *));
201
    table = (easy_hash_string_t *)easy_pool_alloc(pool, sizeof(easy_hash_string_t));
202

203
    if (table == NULL || buckets == NULL)
204
        return NULL;
205

206
    table->buckets = buckets;
207
    table->size = n;
208
    table->mask = n - 1;
209
    table->count = 0;
210
    table->ignore_case = ignore_case;
211
    easy_list_init(&table->list);
212

213
    return table;
214
}
215

216
/**
217
 * add string to table
218
 */
219
void easy_hash_string_add(easy_hash_string_t *table, easy_string_pair_t *header)
220
{
221
    uint64_t                n;
222
    int                     len;
223
    char                    *key, buffer[EASY_KEY_MAX_SIZE];
224

225
    key = easy_buf_string_ptr(&header->name);
226
    len = header->name.len;
227

228
    // 转小写
229
    if (table->ignore_case) {
230
        len = easy_hash_string_tolower(key, len, buffer, EASY_KEY_MAX_SIZE - 1);
231
        key = buffer;
232
    }
233

234
    n = easy_fnv_hashcode(key, len, easy_http_hdr_hseed);
235
    n &= table->mask;
236
    header->next = table->buckets[n];
237
    table->buckets[n] = header;
238
    table->count ++;
239
    easy_list_add_tail(&header->list, &table->list);
240
}
241

242
/**
243
 * find string
244
 */
245
easy_string_pair_t *easy_hash_string_get(easy_hash_string_t *table, const char *key, int len)
246
{
247
    uint64_t                n;
248
    easy_string_pair_t      *t;
249
    char                    buffer[EASY_KEY_MAX_SIZE];
250

251
    // 转小写
252
    if (table->ignore_case) {
253
        len = easy_hash_string_tolower(key, len, buffer, EASY_KEY_MAX_SIZE - 1);
254
        key = buffer;
255
    }
256

257
    n = easy_fnv_hashcode(key, len, easy_http_hdr_hseed);
258
    n &= table->mask;
259

260
    // ignore_case
261
    if (table->ignore_case) {
262
        char                    buffer1[EASY_KEY_MAX_SIZE];
263

264
        for (t = table->buckets[n]; t; t = t->next) {
265
            if (t->name.len != len) continue;
266

267
            easy_hash_string_tolower(t->name.data, len, buffer1, EASY_KEY_MAX_SIZE - 1);
268

269
            if (memcmp(key, buffer1, len) == 0)
270
                return t;
271
        }
272
    } else {
273
        for (t = table->buckets[n]; t; t = t->next) {
274
            if (t->name.len != len) continue;
275

276
            if (memcmp(key, t->name.data, len) == 0)
277
                return t;
278
        }
279
    }
280

281
    return NULL;
282
}
283

284
/**
285
 * delete string
286
 */
287
easy_string_pair_t *easy_hash_string_del(easy_hash_string_t *table, const char *key, int len)
288
{
289
    uint64_t                n;
290
    easy_string_pair_t      *t, *prev;
291
    char                    buffer[EASY_KEY_MAX_SIZE], buffer1[EASY_KEY_MAX_SIZE];
292

293
    // 转小写
294
    if (table->ignore_case) {
295
        len = easy_hash_string_tolower(key, len, buffer, EASY_KEY_MAX_SIZE - 1);
296
        key = buffer;
297
    }
298

299
    n = easy_fnv_hashcode(key, len, easy_http_hdr_hseed);
300
    n &= table->mask;
301

302
    // list
303
    for (t = table->buckets[n], prev = NULL; t; prev = t, t = t->next) {
304
        if (t->name.len != len) continue;
305

306
        if (table->ignore_case) {
307
            easy_hash_string_tolower(t->name.data, len, buffer1, EASY_KEY_MAX_SIZE - 1);
308

309
            if (memcmp(key, buffer1, len)) continue;
310
        } else if (memcmp(key, t->name.data, len)) {
311
            continue;
312
        }
313

314
        // delete from list
315
        if (prev)
316
            prev->next = t->next;
317
        else
318
            table->buckets[n] = t->next;
319

320
        t->next = NULL;
321
        table->count --;
322
        easy_list_del(&t->list);
323
        return t;
324
    }
325

326
    return NULL;
327
}
328

329
/**
330
 * delete string
331
 */
332
easy_string_pair_t *easy_hash_pair_del(easy_hash_string_t *table, easy_string_pair_t *pair)
333
{
334
    uint64_t                n;
335
    easy_string_pair_t      *t, *prev;
336
    char                    buffer[EASY_KEY_MAX_SIZE];
337
    char                    *key;
338
    int                     len;
339

340
    // 转小写
341
    if (table->ignore_case) {
342
        len = easy_hash_string_tolower(pair->name.data, pair->name.len, buffer, EASY_KEY_MAX_SIZE - 1);
343
        key = buffer;
344
    } else {
345
        len = pair->name.len;
346
        key = pair->name.data;
347
    }
348

349
    n = easy_fnv_hashcode(key, len, easy_http_hdr_hseed);
350

351
    n &= table->mask;
352

353
    // list
354
    for (t = table->buckets[n], prev = NULL; t; prev = t, t = t->next) {
355
        if (t != pair)
356
            continue;
357

358
        // delete from list
359
        if (prev)
360
            prev->next = t->next;
361
        else
362
            table->buckets[n] = t->next;
363

364
        t->next = NULL;
365
        table->count --;
366
        easy_list_del(&t->list);
367
        return t;
368
    }
369

370
    return NULL;
371
}
372
///////////////////////////////////////////////////////////////////////////////////////////////////
373
// hash 64 bit
374
uint64_t easy_hash_key(volatile uint64_t key)
375
{
376
    void                    *ptr = (void *) &key;
377
    return easy_hash_code(ptr, sizeof(uint64_t), 5);
378
}
379

380
#define ROL64(x, n) (((x) << (n)) | ((x) >> (64-(n))))
381
#define ROL(x, n) (((x) << (n)) | ((x) >> (32-(n))))
382

383
#ifdef _LP64
384
#define BIG_CONSTANT(x) (x##LLU)
385
#define HASH_FMIX(k) { k ^= k >> 33; k *= BIG_CONSTANT(0xff51afd7ed558ccd); k ^= k >> 33; k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53); k ^= k >> 33; }
386

387
uint64_t easy_hash_code(const void *key, int len, unsigned int seed)
388
{
389
    int                     i;
390
    uint64_t                h1, h2, k1, k2;
391

392
    const uint8_t           *data = (const uint8_t *)key;
393
    const int               nblocks = len / 16;
394
    const uint64_t          c1 = BIG_CONSTANT(0x87c37b91114253d5);
395
    const uint64_t          c2 = BIG_CONSTANT(0x4cf5ad432745937f);
396
    const uint64_t          *blocks = (const uint64_t *)(data);
397

398
    h1 = h2 = seed;
399

400
    for (i = 0; i < nblocks; i += 2) {
401
        k1 = blocks[i];
402
        k2 = blocks[i + 1];
403

404
        k1                      *= c1;
405
        k1  = ROL64(k1, 31);
406
        k1                      *= c2;
407
        h1 ^= k1;
408

409
        h1 = ROL64(h1, 27);
410
        h1 += h2;
411
        h1 = h1 * 5 + 0x52dce729;
412

413
        k2                      *= c2;
414
        k2  = ROL64(k2, 33);
415
        k2                      *= c1;
416
        h2 ^= k2;
417

418
        h2 = ROL64(h2, 31);
419
        h2 += h1;
420
        h2 = h2 * 5 + 0x38495ab5;
421
    }
422

423
    if ((i = (len & 15))) {
424
        const uint8_t           *tail = (const uint8_t *)(data + nblocks * 16);
425
        k1 = k2 = 0;
426

427
        switch (i) {
428
        case 15:
429
            k2 ^= ((uint64_t)tail[14]) << 48;
430

431
        case 14:
432
            k2 ^= ((uint64_t)tail[13]) << 40;
433

434
        case 13:
435
            k2 ^= ((uint64_t)tail[12]) << 32;
436

437
        case 12:
438
            k2 ^= ((uint64_t)tail[11]) << 24;
439

440
        case 11:
441
            k2 ^= ((uint64_t)tail[10]) << 16;
442

443
        case 10:
444
            k2 ^= ((uint64_t)tail[ 9]) << 8;
445

446
        case  9:
447
            k2 ^= ((uint64_t)tail[ 8]) << 0;
448
            k2                      *= c2;
449
            k2  = ROL64(k2, 33);
450
            k2                      *= c1;
451
            h2 ^= k2;
452

453
        case  8:
454
            k1 ^= ((uint64_t)tail[ 7]) << 56;
455

456
        case  7:
457
            k1 ^= ((uint64_t)tail[ 6]) << 48;
458

459
        case  6:
460
            k1 ^= ((uint64_t)tail[ 5]) << 40;
461

462
        case  5:
463
            k1 ^= ((uint64_t)tail[ 4]) << 32;
464

465
        case  4:
466
            k1 ^= ((uint64_t)tail[ 3]) << 24;
467

468
        case  3:
469
            k1 ^= ((uint64_t)tail[ 2]) << 16;
470

471
        case  2:
472
            k1 ^= ((uint64_t)tail[ 1]) << 8;
473

474
        case  1:
475
            k1 ^= ((uint64_t)tail[ 0]) << 0;
476
            k1                      *= c1;
477
            k1  = ROL64(k1, 31);
478
            k1                      *= c2;
479
            h1 ^= k1;
480
        };
481
    }
482

483
    h1 ^= len;
484
    h2 ^= len;
485
    h1 += h2;
486
    h2 += h1;
487
    HASH_FMIX(h1);
488
    HASH_FMIX(h2);
489

490
    return (h1 + h2);
491
}
492
#else
493
uint64_t easy_hash_code(const void *key, int len, unsigned int seed)
494
{
495
    const uint64_t          m = __UINT64_C(0xc6a4a7935bd1e995);
496
    const int               r = 47;
497

498
    uint64_t                h = seed ^ (len * m);
499

500
    const uint64_t          *data = (const uint64_t *)key;
501
    const uint64_t          *end = data + (len / 8);
502

503
    while (data != end) {
504
        uint64_t                k = *data++;
505

506
        k                       *= m;
507
        k ^= k >> r;
508
        k                       *= m;
509

510
        h ^= k;
511
        h                       *= m;
512
    }
513

514
    const unsigned char     *data2 = (const unsigned char *)data;
515

516
    switch (len & 7) {
517
    case 7:
518
        h ^= (uint64_t)(data2[6]) << 48;
519

520
    case 6:
521
        h ^= (uint64_t)(data2[5]) << 40;
522

523
    case 5:
524
        h ^= (uint64_t)(data2[4]) << 32;
525

526
    case 4:
527
        h ^= (uint64_t)(data2[3]) << 24;
528

529
    case 3:
530
        h ^= (uint64_t)(data2[2]) << 16;
531

532
    case 2:
533
        h ^= (uint64_t)(data2[1]) << 8;
534

535
    case 1:
536
        h ^= (uint64_t)(data2[0]);
537
        h                       *= m;
538
    };
539

540
    h ^= h >> r;
541

542
    h                       *= m;
543

544
    h ^= h >> r;
545

546
    return h;
547
}
548
#endif
549

550
static uint32_t easy_hash_getm(uint32_t size)
551
{
552
    uint32_t                n = 4;
553
    size &= 0x7fffffff;
554

555
    while (size > n) n <<= 1;
556

557
    return n;
558
}
559

560
// tolower
561
static int easy_hash_string_tolower(const char *src, int slen, char *dst, int dlen)
562
{
563
    dlen = slen = easy_min(slen, dlen);
564

565
    while (slen -- > 0) {
566
        if ((*src) >= 'A' && (*src) <= 'Z')
567
            (*dst) = (*src) + 32;
568
        else
569
            (*dst) = (*src);
570

571
        src ++;
572
        dst ++;
573
    }
574

575
    *dst = '\0';
576
    return dlen;
577
}
578

579
uint64_t easy_fnv_hashcode(const void *key, int wrdlen, unsigned int seed)
580
{
581
    const uint64_t          PRIME = 11400714819323198393ULL;
582
    uint64_t                hash64 = 2166136261U + seed;
583
    uint64_t                hash64B = hash64;
584
    const char              *p = (const char *)key;
585

586
    for (; wrdlen >= 2 * 2 * 2 * sizeof(uint32_t); wrdlen -= 2 * 2 * 2 * sizeof(uint32_t), p += 2 * 2 * 2 * sizeof(uint32_t)) {
587
        hash64 = (hash64 ^ (ROL64(*(unsigned long long *)(p + 0), 5 - 0) ^ * (unsigned long long *)(p + 8))) * PRIME;
588
        hash64B = (hash64B ^ (ROL64(*(unsigned long long *)(p + 8 + 8), 5 - 0) ^ * (unsigned long long *)(p + 8 + 8 + 8))) * PRIME;
589
    }
590

591
    hash64 = (hash64 ^ hash64B); // Some mix, the simplest is given, maybe the B-line should be rolled by 32bits before xoring.
592

593
    // Cases: 0,1,2,3,4,5,6,7,... 15,... 31
594
    if (wrdlen & (2 * 2 * sizeof(uint32_t))) {
595
        hash64 = (hash64 ^ (ROL(*(uint32_t *)(p + 0), 5 - 0) ^ * (uint32_t *)(p + 4))) * PRIME;
596
        hash64 = (hash64 ^ (ROL(*(uint32_t *)(p + 4 + 4), 5 - 0) ^ * (uint32_t *)(p + 4 + 4 + 4))) * PRIME;
597
        p += 2 * 2 * sizeof(uint32_t);
598
    }
599

600
    if (wrdlen & (2 * sizeof(uint32_t))) {
601
        hash64 = (hash64 ^ (ROL(*(uint32_t *)p, 5 - 0) ^ * (uint32_t *)(p + 4))) * PRIME;
602
        p += 2 * sizeof(uint32_t);
603
    }
604

605
    if (wrdlen & sizeof(uint32_t)) {
606
        hash64 = (hash64 ^ * (uint32_t *)p) * PRIME;
607
        p += sizeof(uint32_t);
608
    }
609

610
    if (wrdlen & sizeof(uint16_t)) {
611
        hash64 = (hash64 ^ * (uint16_t *)p) * PRIME;
612
        p += sizeof(uint16_t);
613
    }
614

615
    if (wrdlen & 1)
616
        hash64 = (hash64 ^ *p) * PRIME;
617

618
    return hash64 ^ (hash64 >> 32);
619
}
620