1 // MyMap.cpp
2
3 #include "StdAfx.h"
4
5 #include "MyMap.h"
6
7 static const unsigned kNumBitsMax = sizeof(UInt32) * 8;
8
GetSubBits(UInt32 value,unsigned startPos,unsigned numBits)9 static UInt32 GetSubBits(UInt32 value, unsigned startPos, unsigned numBits) throw()
10 {
11 if (startPos == sizeof(value) * 8)
12 return 0;
13 value >>= startPos;
14 if (numBits == sizeof(value) * 8)
15 return value;
16 return value & (((UInt32)1 << numBits) - 1);
17 }
18
GetSubBit(UInt32 v,unsigned n)19 static inline unsigned GetSubBit(UInt32 v, unsigned n) { return (unsigned)(v >> n) & 1; }
20
Find(UInt32 key,UInt32 & valueRes) const21 bool CMap32::Find(UInt32 key, UInt32 &valueRes) const throw()
22 {
23 valueRes = (UInt32)(Int32)-1;
24 if (Nodes.Size() == 0)
25 return false;
26 if (Nodes.Size() == 1)
27 {
28 const CNode &n = Nodes[0];
29 if (n.Len == kNumBitsMax)
30 {
31 valueRes = n.Values[0];
32 return (key == n.Key);
33 }
34 }
35
36 unsigned cur = 0;
37 unsigned bitPos = kNumBitsMax;
38 for (;;)
39 {
40 const CNode &n = Nodes[cur];
41 bitPos -= n.Len;
42 if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
43 return false;
44 unsigned bit = GetSubBit(key, --bitPos);
45 if (n.IsLeaf[bit])
46 {
47 valueRes = n.Values[bit];
48 return (key == n.Keys[bit]);
49 }
50 cur = (unsigned)n.Keys[bit];
51 }
52 }
53
Set(UInt32 key,UInt32 value)54 bool CMap32::Set(UInt32 key, UInt32 value)
55 {
56 if (Nodes.Size() == 0)
57 {
58 CNode n;
59 n.Key = n.Keys[0] = n.Keys[1] = key;
60 n.Values[0] = n.Values[1] = value;
61 n.IsLeaf[0] = n.IsLeaf[1] = 1;
62 n.Len = kNumBitsMax;
63 Nodes.Add(n);
64 return false;
65 }
66 if (Nodes.Size() == 1)
67 {
68 CNode &n = Nodes[0];
69 if (n.Len == kNumBitsMax)
70 {
71 if (key == n.Key)
72 {
73 n.Values[0] = n.Values[1] = value;
74 return true;
75 }
76 unsigned i = kNumBitsMax - 1;
77 for (; GetSubBit(key, i) == GetSubBit(n.Key, i); i--);
78 n.Len = (UInt16)(kNumBitsMax - (1 + i));
79 unsigned newBit = GetSubBit(key, i);
80 n.Values[newBit] = value;
81 n.Keys[newBit] = key;
82 return false;
83 }
84 }
85
86 unsigned cur = 0;
87 unsigned bitPos = kNumBitsMax;
88 for (;;)
89 {
90 CNode &n = Nodes[cur];
91 bitPos -= n.Len;
92 if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
93 {
94 unsigned i = n.Len - 1;
95 for (; GetSubBit(key, bitPos + i) == GetSubBit(n.Key, bitPos + i); i--);
96
97 CNode e2(n);
98 e2.Len = (UInt16)i;
99
100 n.Len = (UInt16)(n.Len - (1 + i));
101 unsigned newBit = GetSubBit(key, bitPos + i);
102 n.Values[newBit] = value;
103 n.IsLeaf[newBit] = 1;
104 n.IsLeaf[1 - newBit] = 0;
105 n.Keys[newBit] = key;
106 n.Keys[1 - newBit] = Nodes.Size();
107 Nodes.Add(e2);
108 return false;
109 }
110 unsigned bit = GetSubBit(key, --bitPos);
111
112 if (n.IsLeaf[bit])
113 {
114 if (key == n.Keys[bit])
115 {
116 n.Values[bit] = value;
117 return true;
118 }
119 unsigned i = bitPos - 1;
120 for (; GetSubBit(key, i) == GetSubBit(n.Keys[bit], i); i--);
121
122 CNode e2;
123
124 unsigned newBit = GetSubBit(key, i);
125 e2.Values[newBit] = value;
126 e2.Values[1 - newBit] = n.Values[bit];
127 e2.IsLeaf[newBit] = e2.IsLeaf[1 - newBit] = 1;
128 e2.Keys[newBit] = key;
129 e2.Keys[1 - newBit] = e2.Key = n.Keys[bit];
130 e2.Len = (UInt16)(bitPos - (1 + i));
131
132 n.IsLeaf[bit] = 0;
133 n.Keys[bit] = Nodes.Size();
134
135 Nodes.Add(e2);
136 return false;
137 }
138 cur = (unsigned)n.Keys[bit];
139 }
140 }
141