1 #include <Core/Core.h>
2
3 namespace Upp {
4
5 int IndexCommon::empty[1] = { -1 };
6
IndexCommon()7 IndexCommon::IndexCommon()
8 {
9 hash = NULL;
10 map = empty;
11 mask = 0;
12 unlinked = -1;
13 }
14
Pick(IndexCommon & b)15 void IndexCommon::Pick(IndexCommon& b)
16 {
17 Free();
18
19 hash = b.hash;
20 map = b.map;
21 mask = b.mask;
22 unlinked = b.unlinked;
23
24 b.hash = NULL;
25 b.map = empty;
26 b.mask = 0;
27 b.unlinked = -1;
28 }
29
Copy(const IndexCommon & b,int count)30 void IndexCommon::Copy(const IndexCommon& b, int count)
31 {
32 memcpy_t(hash, b.hash, count);
33 mask = b.mask;
34 unlinked = b.unlinked;
35
36 FreeMap();
37 map = (int *)MemoryAlloc((mask + 1) * sizeof(int));
38 memcpy_t(map, b.map, mask + 1);
39 }
40
Swap(IndexCommon & b)41 void IndexCommon::Swap(IndexCommon& b)
42 {
43 UPP::Swap(hash, b.hash);
44 UPP::Swap(map, b.map);
45 UPP::Swap(mask, b.mask);
46 UPP::Swap(unlinked, b.unlinked);
47 }
48
~IndexCommon()49 IndexCommon::~IndexCommon()
50 {
51 Free();
52 }
53
FreeMap()54 void IndexCommon::FreeMap()
55 {
56 if(map != empty)
57 MemoryFree(map);
58 }
59
Free()60 void IndexCommon::Free()
61 {
62 if(hash)
63 MemoryFree(hash);
64 FreeMap();
65 }
66
Remap(int count)67 void IndexCommon::Remap(int count)
68 {
69 Fill(map, map + mask + 1, -1);
70 for(int i = 0; i < count; i++) // todo: unlinked
71 if(hash[i].hash)
72 Link(i, hash[i].hash);
73 }
74
Reindex(int count)75 void IndexCommon::Reindex(int count)
76 {
77 FreeMap();
78 map = (int *)MemoryAlloc((mask + 1) * sizeof(int));
79 Remap(count);
80 }
81
Clear()82 void IndexCommon::Clear()
83 {
84 Free();
85 hash = NULL;
86 map = empty;
87 mask = 0;
88 unlinked = -1;
89 }
90
GrowMap(int count)91 void IndexCommon::GrowMap(int count)
92 {
93 mask = (mask << 1) | 3;
94 Reindex(count);
95 }
96
GetUnlinked() const97 Vector<int> IndexCommon::GetUnlinked() const
98 {
99 Vector<int> r;
100 int i = unlinked;
101 if(i >= 0) {
102 do {
103 i = hash[i].prev;
104 r.Add(i);
105 }
106 while(i != unlinked);
107 }
108 return r;
109 }
110
AdjustMap(int count,int alloc)111 void IndexCommon::AdjustMap(int count, int alloc)
112 {
113 if(alloc == 0) {
114 FreeMap();
115 map = empty;
116 mask = 0;
117 return;
118 }
119 dword msk = 0;
120 while(msk < (dword)alloc)
121 msk = (msk << 1) | 3;
122 if(msk != mask) {
123 mask = msk;
124 Reindex(count);
125 }
126 }
127
MakeMap(int count)128 void IndexCommon::MakeMap(int count)
129 {
130 mask = 0;
131 AdjustMap(count, count);
132 }
133
Trim(int n,int count)134 void IndexCommon::Trim(int n, int count)
135 {
136 if(n == 0) {
137 int n = (int)(mask + 1);
138 for(int i = 0; i < n; i++)
139 map[i] = -1;
140 unlinked = -1;
141 return;
142 }
143
144 for(int i = n; i < count; i++) { // remove items in trimmed area from buckets / unlinked
145 Hash& hh = hash[i];
146 if(hh.hash)
147 Del(map[hh.hash & mask], hh, i);
148 else
149 Del(unlinked, hh, i);
150 }
151 }
152
Sweep(int n)153 void IndexCommon::Sweep(int n)
154 {
155 int ti = 0;
156 for(int i = 0; i < n; i++)
157 if(hash[i].hash)
158 hash[ti++].hash = hash[i].hash;
159 Remap(ti);
160 unlinked = -1;
161 }
162
163 }