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
135
136
137
138
139
140
|
// MyMap.cpp
#include "StdAfx.h"
#include "MyMap.h"
static const unsigned kNumBitsMax = sizeof(UInt32) * 8;
static UInt32 GetSubBits(UInt32 value, unsigned startPos, unsigned numBits) throw()
{
if (startPos == sizeof(value) * 8)
return 0;
value >>= startPos;
if (numBits == sizeof(value) * 8)
return value;
return value & (((UInt32)1 << numBits) - 1);
}
static inline unsigned GetSubBit(UInt32 v, unsigned n) { return (unsigned)(v >> n) & 1; }
bool CMap32::Find(UInt32 key, UInt32 &valueRes) const throw()
{
valueRes = (UInt32)(Int32)-1;
if (Nodes.Size() == 0)
return false;
if (Nodes.Size() == 1)
{
const CNode &n = Nodes[0];
if (n.Len == kNumBitsMax)
{
valueRes = n.Values[0];
return (key == n.Key);
}
}
unsigned cur = 0;
unsigned bitPos = kNumBitsMax;
for (;;)
{
const CNode &n = Nodes[cur];
bitPos -= n.Len;
if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
return false;
unsigned bit = GetSubBit(key, --bitPos);
if (n.IsLeaf[bit])
{
valueRes = n.Values[bit];
return (key == n.Keys[bit]);
}
cur = (unsigned)n.Keys[bit];
}
}
bool CMap32::Set(UInt32 key, UInt32 value)
{
if (Nodes.Size() == 0)
{
CNode n;
n.Key = n.Keys[0] = n.Keys[1] = key;
n.Values[0] = n.Values[1] = value;
n.IsLeaf[0] = n.IsLeaf[1] = 1;
n.Len = kNumBitsMax;
Nodes.Add(n);
return false;
}
if (Nodes.Size() == 1)
{
CNode &n = Nodes[0];
if (n.Len == kNumBitsMax)
{
if (key == n.Key)
{
n.Values[0] = n.Values[1] = value;
return true;
}
unsigned i = kNumBitsMax - 1;
for (; GetSubBit(key, i) == GetSubBit(n.Key, i); i--);
n.Len = (UInt16)(kNumBitsMax - (1 + i));
const unsigned newBit = GetSubBit(key, i);
n.Values[newBit] = value;
n.Keys[newBit] = key;
return false;
}
}
unsigned cur = 0;
unsigned bitPos = kNumBitsMax;
for (;;)
{
CNode &n = Nodes[cur];
bitPos -= n.Len;
if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
{
unsigned i = (unsigned)n.Len - 1;
for (; GetSubBit(key, bitPos + i) == GetSubBit(n.Key, bitPos + i); i--);
CNode e2(n);
e2.Len = (UInt16)i;
n.Len = (UInt16)(n.Len - (1 + i));
unsigned newBit = GetSubBit(key, bitPos + i);
n.Values[newBit] = value;
n.IsLeaf[newBit] = 1;
n.IsLeaf[1 - newBit] = 0;
n.Keys[newBit] = key;
n.Keys[1 - newBit] = (UInt32)Nodes.Size();
Nodes.Add(e2);
return false;
}
const unsigned bit = GetSubBit(key, --bitPos);
if (n.IsLeaf[bit])
{
if (key == n.Keys[bit])
{
n.Values[bit] = value;
return true;
}
unsigned i = bitPos - 1;
for (; GetSubBit(key, i) == GetSubBit(n.Keys[bit], i); i--);
CNode e2;
const unsigned newBit = GetSubBit(key, i);
e2.Values[newBit] = value;
e2.Values[1 - newBit] = n.Values[bit];
e2.IsLeaf[newBit] = e2.IsLeaf[1 - newBit] = 1;
e2.Keys[newBit] = key;
e2.Keys[1 - newBit] = e2.Key = n.Keys[bit];
e2.Len = (UInt16)(bitPos - (1 + i));
n.IsLeaf[bit] = 0;
n.Keys[bit] = (UInt32)Nodes.Size();
Nodes.Add(e2);
return false;
}
cur = (unsigned)n.Keys[bit];
}
}
|
