asar coverage - build #203

src/asar/
File: src/asar/assocarr.h
Date: 2024-02-07 17:19:12
Lines:
116/119
97.5%
Functions:
87/95
91.6%
Branches:
58/64
90.6%
Line Branch Exec Source
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 477078 void collectgarbage(const char * ifnotmatch=nullptr)
63 {
64
2/2
✓ Branch 0 taken 127988 times.
✓ Branch 1 taken 133750 times.
 477078 if (lastid==-1) return;
65
4/4
✓ Branch 0 taken 198646 times.
✓ Branch 1 taken 256 times.
✓ Branch 2 taken 95826 times.
✓ Branch 3 taken 102820 times.
 374508 if (ifnotmatch && !strcmp(indexes[lastid], ifnotmatch)) return;
66
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 198776 times.
 374256 if (!memcmp(ptr[lastid], lastone, sizeof(right)))
67 {
68 ✗ int tmpid=lastid;
69 ✗ lastid=-1;
70 ✗ remove(indexes[tmpid]);
71 }
72 374256 lastid=-1;
73 }
74
75 433499 right& rawadd(const char * index, bool collect)
76 {
77 433499 collectgarbage(index);
78 224019 int loc=0;
79 433499 int skip= (int)bitround((unsigned int)num);
80
2/2
✓ Branch 0 taken 1368953 times.
✓ Branch 1 taken 235348 times.
 2864639 while (skip)
81 {
82 int dir;
83
2/2
✓ Branch 0 taken 676454 times.
✓ Branch 1 taken 692499 times.
 2450302 if (loc>=num) dir=1;
84 1742133 else dir=strcmp(indexes[loc], index);
85
2/2
✓ Branch 0 taken 12939 times.
✓ Branch 1 taken 1174912 times.
 2109681 if (!dir) return ptr[loc][0];
86 2433307 skip/=2;
87
2/2
✓ Branch 0 taken 489385 times.
✓ Branch 1 taken 866629 times.
 2433307 if (dir>0) loc-=skip;
88 1560355 else loc+=skip;
89
2/2
✓ Branch 0 taken 656413 times.
✓ Branch 1 taken 699601 times.
 2433307 if (loc<0)
90 {
91 1102 loc=0;
92 1102 break;
93 }
94 }
95
4/4
✓ Branch 0 taken 137437 times.
✓ Branch 1 taken 99237 times.
✓ Branch 2 taken 115539 times.
✓ Branch 3 taken 21898 times.
 416504 if (loc<num && strcmp(indexes[loc], index)<0) loc++;
96
2/2
✓ Branch 0 taken 41794 times.
✓ Branch 1 taken 194880 times.
 416504 if (num==bufferlen)
97 {
98
2/2
✓ Branch 0 taken 8297 times.
✓ Branch 1 taken 33497 times.
 65106 if (!num) bufferlen=1;
99 52914 else bufferlen*=2;
100 65106 ptr=(right**)realloc(ptr, sizeof(right*)*(size_t)bufferlen);
101 65106 indexes=(const char**)realloc(indexes, sizeof(const char *)*(size_t)bufferlen);
102 }
103 416504 num++;
104 416504 memmove(indexes+loc+1, indexes+loc, sizeof(const char *)*(size_t)(num-loc-1));
105 416504 memmove(ptr+loc+1, ptr+loc, sizeof(right*)*(size_t)(num-loc-1));
106 416504 indexes[loc]= duplicate_string(index);
107 416504 ptr[loc]=(right*)malloc(sizeof(right));
108 416504 memset(ptr[loc], 0, sizeof(right));
109
1/4
✓ Branch 0 taken 108 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 416504 new(ptr[loc]) right;
110
2/2
✓ Branch 0 taken 201176 times.
✓ Branch 1 taken 35498 times.
 416504 if (collect)
111 {
112 378800 lastid=loc;
113 378800 memcpy(lastone, ptr[loc], sizeof(right));
114 }
115 416504 return ptr[loc][0];
116 }
117
118 339558 int find_i(const char * index) const
119 {
120 154631 int loc=0;
121 339558 int skip=(int)bitround((unsigned int)num);
122
2/2
✓ Branch 0 taken 1089708 times.
✓ Branch 1 taken 123611 times.
 1393062 while (skip)
123 {
124 int dir;
125
2/2
✓ Branch 0 taken 571014 times.
✓ Branch 1 taken 518694 times.
 1266238 if (loc>=num) dir=1;
126 1224397 else dir=strcmp(indexes[loc], index);
127
2/2
✓ Branch 0 taken 140135 times.
✓ Branch 1 taken 929247 times.
 1245372 if (!dir) return loc;
128 1056049 skip/=2;
129
2/2
✓ Branch 0 taken 411220 times.
✓ Branch 1 taken 538353 times.
 1056049 if (dir>0) loc-=skip;
130 601600 else loc+=skip;
131
2/2
✓ Branch 0 taken 495797 times.
✓ Branch 1 taken 453776 times.
 1056049 if (loc<0) return -1;
132 }
133 58527 return -1;
134 }
135
136 public:
137
138 265545 bool exists(const char * index) const
139 {
140 265545 return find_i(index)>=0;
141 }
142
143 116475 right& find(const char * index) const
144 {
145 116475 return ptr[find_i(index)][0];
146 }
147
148 60134 right& create(const char * index)
149 {
150 60134 return rawadd(index, false);
151 }
152
153 1122 void remove(const char * index)
154 {
155 1122 collectgarbage();
156 578 int loc=0;
157 1122 int skip= (int)bitround((unsigned int)num);
158
2/2
✓ Branch 0 taken 2216 times.
✓ Branch 1 taken 281 times.
 3787 while (skip)
159 {
160 int dir;
161
2/2
✓ Branch 0 taken 1104 times.
✓ Branch 1 taken 1112 times.
 3506 if (loc>=num) dir=1;
162 3500 else dir=strcmp(indexes[loc], index);
163
2/2
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 1709 times.
 3503 if (!dir)
164 {
165 840 free((void*)indexes[loc]);
166 840 ptr[loc]->~right();
167 840 free(ptr[loc]);
168 840 memmove(indexes+loc, indexes+loc+1, sizeof(const char *)*(size_t)(num-loc-1));
169 840 memmove(ptr+loc, ptr+loc+1, sizeof(right*)*(size_t)(num-loc-1));
170 840 num--;
171
2/2
✓ Branch 0 taken 66 times.
✓ Branch 1 taken 438 times.
 840 if (num==bufferlen/2)
172 {
173 132 bufferlen/=2;
174 132 ptr=(right**)realloc(ptr, sizeof(right*)*(size_t)bufferlen);
175 132 indexes=(const char**)realloc(indexes, sizeof(const char *)*(size_t)bufferlen);
176 }
177 840 return;
178 }
179 2666 skip/=2;
180
2/2
✓ Branch 0 taken 632 times.
✓ Branch 1 taken 1080 times.
 2666 if (dir>0) loc-=skip;
181 1680 else loc+=skip;
182
2/2
✓ Branch 0 taken 853 times.
✓ Branch 1 taken 859 times.
 2666 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 28576 void reset()
233 {
234
2/2
✓ Branch 0 taken 204698 times.
✓ Branch 1 taken 14992 times.
 425803 for (int i=0;i<num;i++)
235 {
236 397227 free((void*)indexes[i]);
237 397227 ptr[i]->~right();
238 397227 free(ptr[i]);
239 }
240 28576 free(indexes);
241 28576 free(ptr);
242 28576 indexes=nullptr;
243 28576 ptr= nullptr;
244 28576 num=0;
245 28576 bufferlen=0;
246 28576 lastid=-1;
247 28576 }
248
249 5121 assocarr()
250 {
251 5121 indexes= nullptr;
252 5121 ptr= nullptr;
253 5121 num=0;
254 5121 bufferlen=0;
255 5121 lastid=-1;
256 5121 }
257
258 512 assocarr(std::initializer_list<pair<const char *, right>> list)
259 {
260 512 indexes= nullptr;
261 512 ptr= nullptr;
262 512 num=0;
263 512 bufferlen=0;
264 512 lastid=-1;
265
266
2/2
✓ Branch 0 taken 40448 times.
✓ Branch 1 taken 512 times.
 40960 for(auto &item : list){
267 40448 rawadd(item.first, true) = item.second;
268 }
269 512 }
270
271 3000 ~assocarr()
272 {
273 3000 reset();
274 3000 }
275
276 326544 right& operator[](const char * index)
277 {
278 326544 return rawadd(index, true);
279 }
280
281 //void(*func)(const char * key, right& value)
282 22678 template<typename t> void each(t func)
283 {
284 22678 collectgarbage();
285
2/2
✓ Branch 0 taken 191517 times.
✓ Branch 1 taken 11339 times.
 405712 for (int i=0;i<num;i++)
286 {
287
2/4
✓ Branch 0 taken 29691 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 15096 times.
✗ Branch 3 not taken.
 383034 func(indexes[i], ptr[i][0]);
288 }
289 22678 }
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 };
327