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
|
* Hash Map
* Linear Probe Set
* Tree
** Implicitly balanced tree (input is hashed)
** Red-Black Tree
** etc.
"Quick Map":
Root structure:
- array[32] of (hash-bits,flag,ptr)
- if flag == 0, then it is an entry (works similar to a hashmap, but without chaining)
- if flag == 1, it is a nested "quick map" structure
- if flag == 2, it is a list with 32 slots for items with the same hash
"Quick Map 2":
(The idea is to reduce fragmentation by re-using, rather than freeing, too
small areas. But will this actually help? Or are we better of just ignoring
the fragmentation?)
Structure:
- node type:
0 = linear probe set, with pointers to leaf entries
(may contain bucket lists areas also, see below)
1 = bucket list, indexed by part of hash (for root node, it is the highest order bits)
- entries array
for type 0: 128 entries: (hash,pointer)
- if hash is 0, then it is a pointer to to another node.
for type 1: 256 entries: (pointer)
"Quick Map 3"
Like 2 but use the smaller areas for caching for commonly looked up items.
"Quick Map 4"
struct { uintptr_t flag; uintptr_t data[64]; }
<= 32 items: Linear Probe Set with 32x (hash,pointer) in data.
>= 33 items: Buckets with pointers to the "first" item in a tree or skiplist.
(can we cache common items? perhaps put the most recently used item as the first one in the bucket)
|
