1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
/**************************************************************************/
/* */
/* OCaml */
/* */
/* Stephen Dolan, University of Cambridge */
/* */
/* Copyright 2015 University of Cambridge */
/* */
/* All rights reserved. This file is distributed under the terms of */
/* the GNU Lesser General Public License version 2.1, with the */
/* special exception on linking described in the file LICENSE. */
/* */
/**************************************************************************/
#define CAML_INTERNALS
#include "caml/config.h"
#include "caml/memory.h"
#include "caml/addrmap.h"
#define MAX_CHAIN 100
Caml_inline uintnat pos_initial(struct addrmap* t, value key)
{
uintnat pos = (uintnat)key;
pos *= 0xcc9e2d51;
pos ^= (pos >> 17);
CAMLassert(Is_power_of_2(t->size));
return pos & (t->size - 1);
}
Caml_inline uintnat pos_next(struct addrmap* t, uintnat pos)
{
return (pos + 1) & (t->size - 1);
}
int caml_addrmap_contains(struct addrmap* t, value key)
{
CAMLassert(Is_block(key));
if (!t->entries) return 0;
for (uintnat i = 0, pos = pos_initial(t, key);
i < MAX_CHAIN;
i++, pos = pos_next(t, pos)) {
if (t->entries[pos].key == ADDRMAP_INVALID_KEY) break;
if (t->entries[pos].key == key) return 1;
}
return 0;
}
value caml_addrmap_lookup(struct addrmap* t, value key)
{
CAMLassert(Is_block(key));
CAMLassert(t->entries);
for (uintnat pos = pos_initial(t, key); ; pos = pos_next(t, pos)) {
CAMLassert(t->entries[pos].key != ADDRMAP_INVALID_KEY);
if (t->entries[pos].key == key)
return t->entries[pos].value;
}
}
static void addrmap_alloc(struct addrmap* t, uintnat sz)
{
CAMLassert(Is_power_of_2(sz));
t->entries = caml_stat_alloc(sizeof(struct addrmap_entry) * sz);
t->size = sz;
for (uintnat i = 0; i < sz; i++) {
t->entries[i].key = ADDRMAP_INVALID_KEY;
t->entries[i].value = ADDRMAP_NOT_PRESENT;
}
}
void caml_addrmap_init(struct addrmap* t) {
t->entries = NULL;
t->size = 0;
}
void caml_addrmap_clear(struct addrmap* t) {
caml_stat_free(t->entries);
t->entries = NULL;
t->size = 0;
}
value* caml_addrmap_insert_pos(struct addrmap* t, value key) {
CAMLassert(Is_block(key));
if (!t->entries) {
/* first call, initialise table with a small initial size */
addrmap_alloc(t, 256);
}
for (uintnat i = 0, pos = pos_initial(t, key);
i < MAX_CHAIN;
i++, pos = pos_next(t, pos)) {
if (t->entries[pos].key == ADDRMAP_INVALID_KEY) {
t->entries[pos].key = key;
}
if (t->entries[pos].key == key) {
return &t->entries[pos].value;
}
}
/* failed to insert, rehash and try again */
{
struct addrmap_entry* old_table = t->entries;
uintnat old_size = t->size;
addrmap_alloc(t, old_size * 2);
for (uintnat i = 0; i < old_size; i++) {
if (old_table[i].key != ADDRMAP_INVALID_KEY) {
value* p = caml_addrmap_insert_pos(t, old_table[i].key);
CAMLassert(*p == ADDRMAP_NOT_PRESENT);
*p = old_table[i].value;
}
}
caml_stat_free(old_table);
}
return caml_addrmap_insert_pos(t, key);
}
void caml_addrmap_insert(struct addrmap* t, value k, value v) {
value* p = caml_addrmap_insert_pos(t, k);
CAMLassert(*p == ADDRMAP_NOT_PRESENT);
*p = v;
}
void caml_addrmap_iter(struct addrmap* t, void (*f)(value, value)) {
for (addrmap_iterator i = caml_addrmap_iterator(t);
caml_addrmap_iter_ok(t, i);
i = caml_addrmap_next(t, i)) {
f(caml_addrmap_iter_key(t, i),
caml_addrmap_iter_value(t, i));
}
}
|
