oceanbase

1
/**
2
 * Copyright (c) 2021 OceanBase
3
 * OceanBase CE is licensed under Mulan PubL v2.
4
 * You can use this software according to the terms and conditions of the Mulan PubL v2.
5
 * You may obtain a copy of Mulan PubL v2 at:
6
 *          http://license.coscl.org.cn/MulanPubL-2.0
7
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
8
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
9
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
10
 * See the Mulan PubL v2 for more details.
11
 */
12

13
#define __ussl_fhmix(h) ({                      \
14
      (h) ^= (h) >> 23;                         \
15
      (h) *= 0x2127599bf4325c37ULL;             \
16
      (h) ^= (h) >> 47; })
17

18
static uint64_t ussl_fasthash64(const void *buf, size_t len, uint64_t seed)
19
{
20
	const uint64_t    m = 0x880355f21e6d1965ULL;
21
	const uint64_t *pos = (const uint64_t *)buf;
22
	const uint64_t *end = pos + (len / 8);
23
	const unsigned char *pos2;
24
	uint64_t h = seed ^ (len * m);
25
	uint64_t v;
26

27
	while (pos != end) {
28
		v  = *pos++;
29
		h ^= __ussl_fhmix(v);
30
		h *= m;
31
	}
32

33
	pos2 = (const unsigned char*)pos;
34
	v = 0;
35

36
	switch (len & 7) {
37
    case 7: v ^= (uint64_t)pos2[6] << 48;
38
      // fall through
39
    case 6: v ^= (uint64_t)pos2[5] << 40;
40
      // fall through
41
    case 5: v ^= (uint64_t)pos2[4] << 32;
42
      // fall through
43
    case 4: v ^= (uint64_t)pos2[3] << 24;
44
      // fall through
45
    case 3: v ^= (uint64_t)pos2[2] << 16;
46
      // fall through
47
    case 2: v ^= (uint64_t)pos2[1] << 8;
48
      // fall through
49
    case 1: v ^= (uint64_t)pos2[0];
50
      h ^= __ussl_fhmix(v);
51
      h *= m;
52
	}
53
	return __ussl_fhmix(h);
54
}
55

56
static uint64_t __ussl_ihash_calc(uint64_t k) { return ussl_fasthash64(&k, sizeof(k), 0); }
57
static ussl_link_t* __ussl_ihash_locate(ussl_hash_t* map, uint64_t k) { return &map->table[__ussl_ihash_calc(k) % map->capacity]; }
58
static uint64_t __ussl_ihash_key(ussl_link_t* l) { return *(uint64_t*)(l + 1); }
59
static ussl_link_t* __ussl_ihash_list_search(ussl_link_t* start, uint64_t k, ussl_link_t** prev) {
60
  ussl_link_t* p = start;
61
  while(p->next != NULL && __ussl_ihash_key(p->next) != k) {
62
    p = p->next;
63
  }
64
  if (NULL != prev) {
65
    *prev = p;
66
  }
67
  return p->next;
68
}
69

70
ussl_link_t* ussl_ihash_insert(ussl_hash_t* map, ussl_link_t* klink) {
71
  ussl_link_t* prev = NULL;
72
  uint64_t k = __ussl_ihash_key(klink);
73
  if(!__ussl_ihash_list_search(__ussl_ihash_locate(map, k), k, &prev)) {
74
    ussl_link_insert(prev, klink);
75
  } else {
76
    klink = NULL;
77
  }
78
  return klink;
79
}
80

81
ussl_link_t* ussl_ihash_del(ussl_hash_t* map, uint64_t k) {
82
  ussl_link_t* ret = NULL;
83
  ussl_link_t* prev = NULL;
84
  if((ret = __ussl_ihash_list_search(__ussl_ihash_locate(map, k), k, &prev))) {
85
    ussl_link_delete(prev);
86
  }
87
  return ret;
88
}
89

90
ussl_link_t* ussl_ihash_get(ussl_hash_t* map, uint64_t k) {
91
  return __ussl_ihash_list_search(__ussl_ihash_locate(map, k), k, NULL);
92
}
93

94
void ussl_hash_init(ussl_hash_t* h, int64_t capacity) {
95
  h->capacity = capacity;
96
  memset(&h->table, 0, sizeof(ussl_link_t) * capacity);
97
}