Branch data Line data Source code
1 : : //API for assocarr<mytype> myarr:
2 : : //myarr.exists("index")
3 : : // Returns a boolean telling whether the entry exists.
4 : : // Complexity: O(log n).
5 : : //myarr.find("index")
6 : : // Returns a mytype& corresponding to the relevant entry. If it doesn't exist, behaviour is undefined.
7 : : // Complexity: O(log n).
8 : : //myarr.create("index")
9 : : // Returns a mytype& corresponding to the relevant entry. If it doesn't exist, it's created.
10 : : // Complexity: Worst case O(n), reduced to amortized O(log n) if the element should be at the end (strict weak ordering), or O(log n) if the element
11 : : // exists.
12 : : //myarr.remove("index")
13 : : // Removes the element corresponding to the relevant entry. If it doesn't exist, this structure is left untouched.
14 : : // Complexity: Worst case O(n), reduced to amortized O(log n) if the element is at the end.
15 : : //myarr.reset()
16 : : // Clears the data structure, calling all destructors. It is safe to call this function on an empty structure.
17 : : // Complexity: O(n).
18 : : //myarr.move("from", "to")
19 : : // Moves an element from index "from" to "to". If the source doesn't exist, behaviour is undefined. If the target exists, no action is performed.
20 : : // Complexity: O(n).
21 : : //myarr["index"]
22 : : // Similar to myarr.create("index"), but if the returned entry isn't changed by the next call to any function in the same structure, it's removed.
23 : : // if (myarr["index"]) is safe if type can cast to a bool, and myarr["index"]=4 is also valid if the assignment is valid for a type&. However, it is
24 : : // not safe to use assocarr<assocarr<int> > myarr; if (myarr["3"]["4"]), since the inner assocarr won't know that it's supposed to be garbage collected,
25 : : // and the outer one sees that the inner one changed, so you get pollution and memory waste. However, if (myarr["3"].exists("4")) is safe.
26 : : // Complexity: Same as myarr.create().
27 : : //myarr.each(func)
28 : : // Calls func() for each entry in the structure. func must match the prototype void func(const char * index, mytype& val), but can be a lambda. No
29 : : // non-const function may be called on this structure from inside func(), but it is safe to call const functions of the structure. The function
30 : : // calls are in the same order as the indexes, in a strict weak ordering.
31 : : // Complexity: O(n).
32 : : //Space usage: O(n).
33 : : //C++ version: C++98 or C++03, not sure which.
34 : : //Serializer support: Yes, if mytype is serializable.
35 : : //"Undefined behaviour" means "segfault" in most cases.
36 : :
37 : : #pragma once
38 : :
39 : : #include <initializer_list>
40 : : #include "std-includes.h"
41 : : #include "libmisc.h"//bitround
42 : :
43 : : //just a helper for initializer list
44 : : template<typename T1, typename T2> struct pair{
45 : : T1 first;
46 : : T2 second;
47 : : };
48 : :
49 : : template<typename right> class assocarr {
50 : : public:
51 : : int num;
52 : :
53 : : private:
54 : :
55 : : const char ** indexes;
56 : : right ** ptr;
57 : : int bufferlen;
58 : :
59 : : char lastone[sizeof(right)];
60 : : int lastid;
61 : :
62 : 40820 : void collectgarbage(const char * ifnotmatch=nullptr)
63 : : {
64 [ + + ]: 40820 : if (lastid==-1) return;
65 [ + + + + ]: 29002 : if (ifnotmatch && !strcmp(indexes[lastid], ifnotmatch)) return;
66 [ - + ]: 28981 : if (!memcmp(ptr[lastid], lastone, sizeof(right)))
67 : : {
68 : : int tmpid=lastid;
69 : 0 : lastid=-1;
70 : 0 : remove(indexes[tmpid]);
71 : : }
72 : 28981 : lastid=-1;
73 : : }
74 : :
75 : 39156 : right& rawadd(const char * index, bool collect)
76 : : {
77 : 39156 : collectgarbage(index);
78 : : int loc=0;
79 : 39156 : int skip= (int)bitround((unsigned int)num);
80 [ + + ]: 243969 : while (skip)
81 : : {
82 : : int dir;
83 [ + + ]: 207053 : if (loc>=num) dir=1;
84 : 155695 : else dir=strcmp(indexes[loc], index);
85 [ + + ]: 155695 : if (!dir) return ptr[loc][0];
86 : 205203 : skip/=2;
87 [ + + ]: 205203 : if (dir>0) loc-=skip;
88 : 131531 : else loc+=skip;
89 [ + + ]: 205203 : if (loc<0)
90 : : {
91 : : loc=0;
92 : : break;
93 : : }
94 : : }
95 [ + + + + ]: 37306 : if (loc<num && strcmp(indexes[loc], index)<0) loc++;
96 [ + + ]: 37306 : if (num==bufferlen)
97 : : {
98 [ + + ]: 7090 : if (!num) bufferlen=1;
99 : 5761 : else bufferlen*=2;
100 : 7090 : ptr=(right**)realloc(ptr, sizeof(right*)*(size_t)bufferlen);
101 : 7090 : indexes=(const char**)realloc(indexes, sizeof(const char *)*(size_t)bufferlen);
102 : : }
103 : 37306 : num++;
104 : 37306 : memmove(indexes+loc+1, indexes+loc, sizeof(const char *)*(size_t)(num-loc-1));
105 : 37306 : memmove(ptr+loc+1, ptr+loc, sizeof(right*)*(size_t)(num-loc-1));
106 : 37306 : indexes[loc]= duplicate_string(index);
107 : 37306 : ptr[loc]=(right*)malloc(sizeof(right));
108 : 37306 : memset(ptr[loc], 0, sizeof(right));
109 : 37306 : new(ptr[loc]) right;
110 [ + + ]: 37306 : if (collect)
111 : : {
112 : 29286 : lastid=loc;
113 : 29286 : memcpy(lastone, ptr[loc], sizeof(right));
114 : : }
115 : 37306 : return ptr[loc][0];
116 : : }
117 : :
118 : 21324 : int find_i(const char * index) const
119 : : {
120 : : int loc=0;
121 : 21324 : int skip=(int)bitround((unsigned int)num);
122 [ + + ]: 82914 : while (skip)
123 : : {
124 : : int dir;
125 [ + + ]: 73252 : if (loc>=num) dir=1;
126 : 65069 : else dir=strcmp(indexes[loc], index);
127 [ + + ]: 65069 : if (!dir) return loc;
128 : 61700 : skip/=2;
129 [ + + ]: 61700 : if (dir>0) loc-=skip;
130 : 38445 : else loc+=skip;
131 [ + + ]: 61700 : if (loc<0) return -1;
132 : : }
133 : : return -1;
134 : : }
135 : :
136 : : public:
137 : :
138 : 15807 : bool exists(const char * index) const
139 : : {
140 : 15807 : return find_i(index)>=0;
141 : : }
142 : :
143 : 5517 : right& find(const char * index) const
144 : : {
145 : 5517 : return ptr[find_i(index)][0];
146 : : }
147 : :
148 : 9465 : right& create(const char * index)
149 : : {
150 : 9465 : return rawadd(index, false);
151 : : }
152 : :
153 : 84 : void remove(const char * index)
154 : : {
155 : 84 : collectgarbage();
156 : : int loc=0;
157 : 84 : int skip= (int)bitround((unsigned int)num);
158 [ + - ]: 459 : while (skip)
159 : : {
160 : : int dir;
161 [ + + ]: 459 : if (loc>=num) dir=1;
162 : 456 : else dir=strcmp(indexes[loc], index);
163 [ + + ]: 456 : if (!dir)
164 : : {
165 : 84 : free((void*)indexes[loc]);
166 : 84 : ptr[loc]->~right();
167 : 84 : free(ptr[loc]);
168 : 84 : memmove(indexes+loc, indexes+loc+1, sizeof(const char *)*(size_t)(num-loc-1));
169 : 84 : memmove(ptr+loc, ptr+loc+1, sizeof(right*)*(size_t)(num-loc-1));
170 : 84 : num--;
171 [ - + ]: 84 : if (num==bufferlen/2)
172 : : {
173 : 0 : bufferlen/=2;
174 : 0 : ptr=(right**)realloc(ptr, sizeof(right*)*(size_t)bufferlen);
175 : 0 : indexes=(const char**)realloc(indexes, sizeof(const char *)*(size_t)bufferlen);
176 : : }
177 : 84 : return;
178 : : }
179 : 375 : skip/=2;
180 [ + + ]: 375 : if (dir>0) loc-=skip;
181 : 237 : else loc+=skip;
182 [ + - ]: 375 : if (loc<0) return;
183 : : }
184 : : }
185 : :
186 : : void move(const char * from, const char * to)
187 : : {
188 : : collectgarbage();
189 : : int frompos=find_i(from);
190 : : int topos=0;
191 : : int skip=bitround(num);
192 : : while (skip)
193 : : {
194 : : int dir;
195 : : if (topos>=num) dir=1;
196 : : else dir=strcmp(indexes[topos], to);
197 : : if (!dir) return;
198 : : skip/=2;
199 : : if (dir>0) topos-=skip;
200 : : else topos+=skip;
201 : : if (topos<0)
202 : : {
203 : : topos=0;
204 : : break;
205 : : }
206 : : }
207 : : if (topos<num && strcmp(indexes[topos], to)<0) topos++;
208 : : right * tmp=ptr[frompos];
209 : : if (topos==frompos || topos==frompos+1)
210 : : {
211 : : free((void*)indexes[frompos]);
212 : : indexes[frompos]= duplicate_string(to);
213 : : }
214 : : else if (topos>frompos)
215 : : {
216 : : free((void*)indexes[frompos]);
217 : : memmove(indexes+frompos, indexes+frompos+1, sizeof(const char *)*(topos-frompos-1));
218 : : memmove(ptr+frompos, ptr+frompos+1, sizeof(right*)*(topos-frompos-1));
219 : : ptr[topos-1]=tmp;
220 : : indexes[topos-1]= duplicate_string(to);//I wonder what the fuck I'm doing.
221 : : }
222 : : else
223 : : {
224 : : free((void*)indexes[frompos]);
225 : : memmove(indexes+topos+1, indexes+topos, sizeof(const char *)*(frompos-topos));
226 : : memmove(ptr+topos+1, ptr+topos, sizeof(right*)*(frompos-topos));
227 : : ptr[topos]=tmp;
228 : : indexes[topos]= duplicate_string(to);
229 : : }
230 : : }
231 : :
232 : 2960 : void reset()
233 : : {
234 [ + + ]: 40182 : for (int i=0;i<num;i++)
235 : : {
236 : 37222 : free((void*)indexes[i]);
237 : 37222 : ptr[i]->~right();
238 : 37222 : free(ptr[i]);
239 : : }
240 : 2960 : free(indexes);
241 : 2960 : free(ptr);
242 : 2960 : indexes=nullptr;
243 : 2960 : ptr= nullptr;
244 : 2960 : num=0;
245 : 2960 : bufferlen=0;
246 : 2960 : lastid=-1;
247 : 2960 : }
248 : :
249 : 1150 : assocarr()
250 : : {
251 : 1150 : indexes= nullptr;
252 : 1150 : ptr= nullptr;
253 : 1150 : num=0;
254 : 1150 : bufferlen=0;
255 : 1150 : lastid=-1;
256 : 1150 : }
257 : :
258 : 115 : assocarr(std::initializer_list<pair<const char *, right>> list)
259 : : {
260 : 115 : indexes= nullptr;
261 : 115 : ptr= nullptr;
262 : 115 : num=0;
263 : 115 : bufferlen=0;
264 : 115 : lastid=-1;
265 : :
266 [ + + ]: 7590 : for(auto &item : list){
267 : 7475 : rawadd(item.first, true) = item.second;
268 : : }
269 : 115 : }
270 : :
271 : 1150 : ~assocarr()
272 : : {
273 : 1150 : reset();
274 : 1150 : }
275 : :
276 : 22216 : right& operator[](const char * index)
277 : : {
278 : 22216 : return rawadd(index, true);
279 : : }
280 : :
281 : : //void(*func)(const char * key, right& value)
282 : 1580 : template<typename t> void each(t func)
283 : : {
284 : 1580 : collectgarbage();
285 [ + + ]: 29601 : for (int i=0;i<num;i++)
286 : : {
287 : 28021 : func(indexes[i], ptr[i][0]);
288 : : }
289 : 1580 : }
290 : :
291 : : //void debug(){puts("");for(int i=0;i<num;i++)puts(indexes[i]);}
292 : :
293 : : #ifdef SERIALIZER
294 : : void serialize(serializer & s)
295 : : {
296 : : collectgarbage();
297 : : if (s.serializing)
298 : : {
299 : : s(num);
300 : : s(bufferlen);
301 : : for (int i=0;i<num;i++)
302 : : {
303 : : s(ptr[i][0]);
304 : : s(indexes[i]);
305 : : }
306 : : }
307 : : else
308 : : {
309 : : reset();
310 : : s(num);
311 : : s(bufferlen);
312 : : ptr=(right**)malloc(sizeof(right*)*bufferlen);
313 : : indexes=(const char**)malloc(sizeof(const char *)*bufferlen);
314 : : for (int i=0;i<num;i++)
315 : : {
316 : : ptr[i]=(right*)malloc(sizeof(right));
317 : : memset(ptr[i], 0, sizeof(right));
318 : : new(ptr[i]) right;
319 : : s(ptr[i][0]);
320 : : s(indexes[i]);
321 : : }
322 : : }
323 : : }
324 : : #endif
325 : : #define SERIALIZER_BANNED
326 : : };
|
