1 /***************************************************************************
2 begin : Mon Mar 01 2004
3 copyright : (C) 2020 by Martin Preuss
4 email : martin@libchipcard.de
5
6 ***************************************************************************
7 * *
8 * This library is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU Lesser General Public *
10 * License as published by the Free Software Foundation; either *
11 * version 2.1 of the License, or (at your option) any later version. *
12 * *
13 * This library is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16 * Lesser General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU Lesser General Public *
19 * License along with this library; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21 * MA 02111-1307 USA *
22 * *
23 ***************************************************************************/
24
25 #ifdef HAVE_CONFIG_H
26 # include <config.h>
27 #endif
28
29 #define DISABLE_DEBUGLOG
30
31
32 #include "idlist64_p.h"
33
34 #include <gwenhywfar/memory.h>
35 #include <gwenhywfar/debug.h>
36
37
38 #include <stdlib.h>
39 #include <assert.h>
40
41
42
43 /* ------------------------------------------------------------------------------------------------
44 * forward declarations
45 * ------------------------------------------------------------------------------------------------
46 */
47
48 static GWENHYWFAR_CB void _attachToTable(GWEN_SIMPLEPTRLIST *pl, void *p);
49 static GWENHYWFAR_CB void _detachFromTable(GWEN_SIMPLEPTRLIST *pl, void *p);
50
51 static int GWEN_IdList64__Sort(GWEN_IDLIST64 *idl, int ascending);
52 static int __compAscending(const void *pa, const void *pb);
53 static int __compDescending(const void *pa, const void *pb);
54
55 static GWEN_IDTABLE64 *GWEN_IdTable64_new();
56 static void GWEN_IdTable64_free(GWEN_IDTABLE64 *ft);
57 static void GWEN_IdTable64_Attach(GWEN_IDTABLE64 *ft);
58 static GWEN_IDTABLE64 *GWEN_IdTable64_dup(const GWEN_IDTABLE64 *ftOrig);
59 static GWEN_IDTABLE64 *GWEN_IdTable64_Create(uint64_t maxEntries);
60 static uint64_t GWEN_IdTable64_GetMaxEntries(const GWEN_IDTABLE64 *ft);
61 static uint64_t GWEN_IdTable64_GetFreeEntries(const GWEN_IDTABLE64 *ft);
62 static void GWEN_IdTable64_DecFreeEntries(GWEN_IDTABLE64 *ft);
63 static uint64_t GWEN_IdTable64_GetHighestEntry(const GWEN_IDTABLE64 *ft);
64 static void GWEN_IdTable64_CheckAndSetHighestEntry(GWEN_IDTABLE64 *ft, uint64_t i);
65
66 static uint32_t GWEN_IdTable64_GetRuntimeFlags(const GWEN_IDTABLE64 *ft);
67 static void GWEN_IdTable64_AddRuntimeFlags(GWEN_IDTABLE64 *ft, uint32_t i);
68
69 static uint64_t *GWEN_IdTable64_GetPtrEntries(const GWEN_IDTABLE64 *ft);
70 static void GWEN_IdTable64_SetPtrEntries(GWEN_IDTABLE64 *ft, uint64_t *ptr);
71
72 static GWEN_IDTABLE64 *GWEN_IdList64_GetTableAt(const GWEN_IDLIST64 *tl, uint64_t idx);
73 /*static int GWEN_IdList64_SetIdAt(GWEN_IDLIST64 *tl, uint64_t idx, uint64_t entry);*/
74 static int64_t GWEN_IdList64_AddTable(GWEN_IDLIST64 *idl, GWEN_IDTABLE64 *t);
75
76 static uint64_t GWEN_IdList64__GetFirstId(const GWEN_IDLIST64 *idl, uint64_t *pos);
77 static uint64_t GWEN_IdList64__GetNextId(const GWEN_IDLIST64 *idl, uint64_t *pos);
78
79
80
81
82 /* ------------------------------------------------------------------------------------------------
83 * GWEN_IdList64
84 * ------------------------------------------------------------------------------------------------
85 */
86
87
GWEN_IdList64_new()88 GWEN_IDLIST64 *GWEN_IdList64_new()
89 {
90 return GWEN_IdList64_newWithSteps(GWEN_IDLIST64_ENTRIES_PER_TABLE);
91 }
92
93
94
GWEN_IdList64_newWithSteps(uint64_t steps)95 GWEN_IDLIST64 *GWEN_IdList64_newWithSteps(uint64_t steps)
96 {
97 GWEN_IDLIST64 *idl;
98
99 idl=GWEN_SimplePtrList_new(GWEN_IDLIST64_INITIAL_ENTRYCOUNT, GWEN_IDLIST64_STEPS);
100 GWEN_SimplePtrList_SetAttachObjectFn(idl, _attachToTable);
101 GWEN_SimplePtrList_SetFreeObjectFn(idl, _detachFromTable);
102 GWEN_SimplePtrList_AddFlags(idl, GWEN_SIMPLEPTRLIST_FLAGS_ATTACHTOOBJECTS);
103 GWEN_SimplePtrList_AddFlags(idl, GWEN_SIMPLEPTRLIST_FLAGS_DETACHFROMOBJECTS);
104 GWEN_SimplePtrList_SetUserIntData(idl, steps);
105
106 return idl;
107 }
108
109
110
GWEN_IdList64_dup(const GWEN_IDLIST64 * oldList)111 GWEN_IDLIST64 *GWEN_IdList64_dup(const GWEN_IDLIST64 *oldList)
112 {
113 GWEN_IDLIST64 *idl;
114 uint64_t tableCount;
115 uint64_t i;
116
117 idl=GWEN_IdList64_newWithSteps(GWEN_SimplePtrList_GetUserIntData(oldList));
118 tableCount=GWEN_SimplePtrList_GetUsedEntries(oldList);
119
120 for (i=0; i<tableCount; i++) {
121 const GWEN_IDTABLE64 *oldTable;
122
123 oldTable=GWEN_IdList64_GetTableAt(oldList, i);
124 if (oldTable) {
125 GWEN_IDTABLE64 *table;
126 int64_t rv;
127
128 table=GWEN_IdTable64_dup(oldTable);
129 rv=GWEN_IdList64_AddTable(idl, table);
130 if (rv<0) {
131 DBG_INFO(GWEN_LOGDOMAIN, "here (%d)", (int) rv);
132 GWEN_IdTable64_free(table);
133 GWEN_IdList64_free(idl);
134 return NULL;
135 }
136 GWEN_IdTable64_free(table);
137 }
138 } /* for */
139 GWEN_SimplePtrList_SetUserCounter(idl, GWEN_SimplePtrList_GetUserCounter(oldList));
140
141 return idl;
142 }
143
144
145
GWEN_IdList64_Attach(GWEN_IDLIST64 * idl)146 void GWEN_IdList64_Attach(GWEN_IDLIST64 *idl)
147 {
148 GWEN_SimplePtrList_Attach(idl);
149 }
150
151
152
GWEN_IdList64_free(GWEN_IDLIST64 * idl)153 void GWEN_IdList64_free(GWEN_IDLIST64 *idl)
154 {
155 GWEN_SimplePtrList_free(idl);
156 }
157
158
159
GWEN_IdList64_Clear(GWEN_IDLIST64 * idl)160 void GWEN_IdList64_Clear(GWEN_IDLIST64 *idl)
161 {
162 GWEN_SimplePtrList_Clear(idl);
163 GWEN_SimplePtrList_SetUserCounter(idl, 0);
164 }
165
166
167
GWEN_IdList64_IncIdCounter(GWEN_SIMPLEPTRLIST * pl)168 void GWEN_IdList64_IncIdCounter(GWEN_SIMPLEPTRLIST *pl)
169 {
170 GWEN_SimplePtrList_IncUserCounter(pl);
171 }
172
173
174
GWEN_IdList64_DecIdCounter(GWEN_SIMPLEPTRLIST * pl)175 int GWEN_IdList64_DecIdCounter(GWEN_SIMPLEPTRLIST *pl)
176 {
177 return GWEN_SimplePtrList_DecUserCounter(pl);
178 }
179
180
181
GWEN_IdList64_GetEntryCount(const GWEN_SIMPLEPTRLIST * pl)182 uint64_t GWEN_IdList64_GetEntryCount(const GWEN_SIMPLEPTRLIST *pl)
183 {
184 return GWEN_SimplePtrList_GetUserCounter(pl);
185 }
186
187
188
189
GWEN_IdList64_GetTableMaxEntries(const GWEN_IDLIST64 * idl)190 int GWEN_IdList64_GetTableMaxEntries(const GWEN_IDLIST64 *idl)
191 {
192 return GWEN_SimplePtrList_GetUserIntData(idl);
193 }
194
195
196
GWEN_IdList64_LazyCopy(GWEN_IDLIST64 * oldList)197 GWEN_IDLIST64 *GWEN_IdList64_LazyCopy(GWEN_IDLIST64 *oldList)
198 {
199 return GWEN_SimplePtrList_LazyCopy(oldList);
200 }
201
202
203
GWEN_IdList64_GetTableAt(const GWEN_IDLIST64 * idl,uint64_t idx)204 GWEN_IDTABLE64 *GWEN_IdList64_GetTableAt(const GWEN_IDLIST64 *idl, uint64_t idx)
205 {
206 return GWEN_SimplePtrList_GetPtrAt(idl, idx);
207 }
208
209
210
GWEN_IdList64_SetTableAt(GWEN_IDLIST64 * idl,uint64_t idx,GWEN_IDTABLE64 * t)211 int GWEN_IdList64_SetTableAt(GWEN_IDLIST64 *idl, uint64_t idx, GWEN_IDTABLE64 *t)
212 {
213 return GWEN_SimplePtrList_SetPtrAt(idl, idx, t);
214 }
215
216
217
GWEN_IdList64_AddTable(GWEN_IDLIST64 * idl,GWEN_IDTABLE64 * t)218 int64_t GWEN_IdList64_AddTable(GWEN_IDLIST64 *idl, GWEN_IDTABLE64 *t)
219 {
220 return GWEN_SimplePtrList_AddPtr(idl, t);
221 }
222
223
224
GWEN_IdList64_GetUsedTables(const GWEN_IDLIST64 * idl)225 uint64_t GWEN_IdList64_GetUsedTables(const GWEN_IDLIST64 *idl)
226 {
227 return GWEN_SimplePtrList_GetUsedEntries(idl);
228 }
229
230
231
GWEN_IdList64_GetLastTablePos(const GWEN_IDLIST64 * idl)232 int64_t GWEN_IdList64_GetLastTablePos(const GWEN_IDLIST64 *idl)
233 {
234 uint64_t idx;
235
236 idx=GWEN_SimplePtrList_GetUsedEntries(idl);
237 if (idx)
238 return idx-1;
239 return GWEN_ERROR_NO_DATA;
240 }
241
242
243
GWEN_IdList64_GetIdAt(const GWEN_IDLIST64 * idl,uint64_t idx)244 int64_t GWEN_IdList64_GetIdAt(const GWEN_IDLIST64 *idl, uint64_t idx)
245 {
246 int entriesPerTable;
247
248 entriesPerTable=GWEN_SimplePtrList_GetUserIntData(idl);
249 if (entriesPerTable) {
250 uint64_t tablePos;
251 GWEN_IDTABLE64 *t;
252
253 tablePos=idx/entriesPerTable;
254 t=GWEN_IdList64_GetTableAt(idl, tablePos);
255 if (t) {
256 uint64_t *entries;
257
258 entries=GWEN_IdTable64_GetPtrEntries(t);
259 if (entries) {
260 uint64_t entryPos;
261
262 entryPos=idx%entriesPerTable;
263 return entries[entryPos];
264 }
265 }
266 else {
267 DBG_ERROR(GWEN_LOGDOMAIN, "No table at table pos %lu", (unsigned long) tablePos);
268 }
269 }
270 else {
271 DBG_ERROR(GWEN_LOGDOMAIN, "No entriesPerTable");
272 }
273
274 return GWEN_ERROR_BUFFER_OVERFLOW;
275 }
276
277
278 #if 0
279 int GWEN_IdList64_SetIdAt(GWEN_IDLIST64 *idl, uint64_t idx, uint64_t entry)
280 {
281 int rv;
282 int entriesPerTable;
283
284 rv=GWEN_SimplePtrList_EnsureWritability(idl);
285 if (rv<0) {
286 DBG_INFO(GWEN_LOGDOMAIN, "here (%d)", rv);
287 return (int64_t) rv;
288 }
289
290 entriesPerTable=GWEN_SimplePtrList_GetUserIntData(idl);
291 if (entriesPerTable) {
292 uint64_t tablePos;
293 GWEN_IDTABLE64 *t;
294
295 tablePos=idx/entriesPerTable;
296 t=GWEN_IdList64_GetTableAt(idl, tablePos);
297 if (t) {
298 uint64_t *entries;
299
300 /* copy table if necessary (copy-on-write) */
301 if (!(GWEN_IdTable64_GetRuntimeFlags(t) & GWEN_IDTABLE64_RUNTIME_FLAGS_ISCOPY)) {
302 GWEN_IDTABLE64 *pTableCopy;
303
304 pTableCopy=GWEN_IdTable64_dup(t);
305 GWEN_IdList64_SetTableAt(idl, tablePos, pTableCopy);
306 t=pTableCopy;
307 GWEN_IdTable64_AddRuntimeFlags(t, GWEN_IDTABLE64_RUNTIME_FLAGS_ISCOPY);
308 }
309
310 entries=GWEN_IdTable64_GetPtrEntries(t);
311 if (entries) {
312 uint64_t entryPos;
313
314 entryPos=idx%entriesPerTable;
315 entries[entryPos]=entry;
316 return 0;
317 }
318 } /* if (t) */
319 else {
320 DBG_ERROR(GWEN_LOGDOMAIN, "No table at position %lu", (unsigned long int) tablePos);
321 return GWEN_ERROR_INTERNAL;
322 }
323 } /* if (entriesPerTable) */
324 else {
325 DBG_ERROR(GWEN_LOGDOMAIN, "No entriesPerTable, internal error");
326 return GWEN_ERROR_INTERNAL;
327 }
328
329 return GWEN_ERROR_BUFFER_OVERFLOW;
330
331 }
332 #endif
333
334
GWEN_IdList64_AddId(GWEN_IDLIST64 * idl,uint64_t entry)335 int64_t GWEN_IdList64_AddId(GWEN_IDLIST64 *idl, uint64_t entry)
336 {
337 GWEN_IDTABLE64 *pTableCurrent=NULL;
338 int64_t idxTableCurrent=0;
339 int entriesPerTable=GWEN_IdList64_GetTableMaxEntries(idl);
340 int rv;
341
342 if (entry==0) {
343 DBG_ERROR(GWEN_LOGDOMAIN, "id 0 is not allowed");
344 return GWEN_ERROR_INVALID;
345 }
346
347 rv=GWEN_SimplePtrList_EnsureWritability(idl);
348 if (rv<0) {
349 DBG_INFO(GWEN_LOGDOMAIN, "here (%d)", rv);
350 return (int64_t) rv;
351 }
352
353 /* get last table */
354 idxTableCurrent=GWEN_IdList64_GetLastTablePos(idl);
355 DBG_VERBOUS(GWEN_LOGDOMAIN, "Last table pos is %d", (int)idxTableCurrent);
356 if (idxTableCurrent>=0)
357 pTableCurrent=GWEN_IdList64_GetTableAt(idl, idxTableCurrent);
358
359 /* check last table for existence and free entries, possibly create and add new table */
360 if (pTableCurrent==NULL || GWEN_IdTable64_GetFreeEntries(pTableCurrent)==0) {
361 /* create new table */
362 if (pTableCurrent==NULL) {
363 DBG_VERBOUS(GWEN_LOGDOMAIN, "No table, need to create one");
364 }
365 else if (GWEN_IdTable64_GetFreeEntries(pTableCurrent)==0) {
366 DBG_VERBOUS(GWEN_LOGDOMAIN, "Current table has no free entries, need to create new one");
367 }
368
369 DBG_VERBOUS(GWEN_LOGDOMAIN, "Creating table with %d entries", entriesPerTable);
370 pTableCurrent=GWEN_IdTable64_Create(entriesPerTable);
371 GWEN_IdTable64_AddRuntimeFlags(pTableCurrent, GWEN_IDTABLE64_RUNTIME_FLAGS_ISCOPY); /* no need to copy later */
372
373 /* add table to list */
374 idxTableCurrent=GWEN_IdList64_AddTable(idl, pTableCurrent);
375 if (idxTableCurrent<0) {
376 DBG_INFO(GWEN_LOGDOMAIN, "here (%d)", (int) idxTableCurrent);
377 GWEN_IdTable64_free(pTableCurrent);
378 return idxTableCurrent;
379 }
380 GWEN_IdTable64_free(pTableCurrent);
381 } /* if (pTableCurrent || GWEN_IdTable64_GetFreeEntries(pTableCurrent)==0) */
382
383 /* allocate free entry in current table */
384 if (pTableCurrent && GWEN_IdTable64_GetFreeEntries(pTableCurrent)) {
385 uint64_t *ptr;
386 int64_t index=idxTableCurrent*entriesPerTable;
387 int64_t entryPos;
388
389 /* copy table if necessary (copy-on-write) */
390 if (!(GWEN_IdTable64_GetRuntimeFlags(pTableCurrent) & GWEN_IDTABLE64_RUNTIME_FLAGS_ISCOPY)) {
391 GWEN_IDTABLE64 *pTableCopy;
392
393 DBG_VERBOUS(GWEN_LOGDOMAIN, "Copying table at idx %lu", (unsigned long) idxTableCurrent);
394 pTableCopy=GWEN_IdTable64_dup(pTableCurrent);
395 GWEN_IdList64_SetTableAt(idl, idxTableCurrent, pTableCopy);
396 GWEN_IdTable64_free(pTableCopy);
397 pTableCurrent=pTableCopy;
398 GWEN_IdTable64_AddRuntimeFlags(pTableCurrent, GWEN_IDTABLE64_RUNTIME_FLAGS_ISCOPY);
399 }
400
401 ptr=GWEN_IdTable64_GetPtrEntries(pTableCurrent);
402
403 /* find entryPos of free entry in pTableCurrent */
404 DBG_VERBOUS(GWEN_LOGDOMAIN, "Current table (ptr=%p, %d entriesPerTable):", (void *)ptr, entriesPerTable);
405 /*GWEN_IdTable64_Dump(pTableCurrent);*/
406 if (GWEN_IdTable64_GetFreeEntries(pTableCurrent)==GWEN_IdTable64_GetMaxEntries(pTableCurrent)) {
407 /** all entries are free, this is simple */
408 entryPos=0;
409 }
410 else {
411 if (GWEN_IdTable64_GetHighestEntry(pTableCurrent)+1<entriesPerTable) {
412 /* fastest way: Just append to the end */
413 DBG_VERBOUS(GWEN_LOGDOMAIN, "Finding free empty the fast way");
414 entryPos=GWEN_IdTable64_GetHighestEntry(pTableCurrent)+1;
415 if (ptr[entryPos]!=0) {
416 DBG_ERROR(GWEN_LOGDOMAIN, "Entry[highest+1] should be 0 but isnt, SNH!");
417 return GWEN_ERROR_INTERNAL;
418 }
419 }
420 else {
421 /* slower way: find free entry somewhere in the table */
422 DBG_VERBOUS(GWEN_LOGDOMAIN, "Finding free empty the slow way");
423 for (entryPos=0; entryPos<entriesPerTable; entryPos++) {
424 if (ptr[entryPos]==0)
425 break;
426 }
427 }
428 }
429
430 DBG_VERBOUS(GWEN_LOGDOMAIN, "New entry will be at index %lu in table %lu (index=%lu, resulting index: %lu)",
431 (unsigned long) entryPos,
432 (unsigned long) idxTableCurrent,
433 (unsigned long) index,
434 (unsigned long)(index+entryPos));
435
436 if (entryPos<entriesPerTable) {
437 /* store new entry, get index */
438 ptr[entryPos]=entry;
439 index+=entryPos;
440 GWEN_IdList64_IncIdCounter(idl);
441 GWEN_IdTable64_DecFreeEntries(pTableCurrent);
442 GWEN_IdTable64_CheckAndSetHighestEntry(pTableCurrent, entryPos);
443 GWEN_IdTable64_AddRuntimeFlags(pTableCurrent, GWEN_IDTABLE64_RUNTIME_FLAGS_DIRTY);
444 return index;
445 }
446 else {
447 DBG_ERROR(GWEN_LOGDOMAIN, "Free entry not found, internal counter is invalid. SNH!");
448 return GWEN_ERROR_INTERNAL;
449 }
450 }
451 else {
452 DBG_ERROR(GWEN_LOGDOMAIN, "Still no table? SNH!");
453 return GWEN_ERROR_INTERNAL;
454 }
455 }
456
457
458
GWEN_IdList64_HasId(const GWEN_IDLIST64 * idl,uint64_t wantedId)459 int GWEN_IdList64_HasId(const GWEN_IDLIST64 *idl, uint64_t wantedId)
460 {
461 uint32_t idx;
462 int entriesPerTable=GWEN_IdList64_GetTableMaxEntries(idl);
463 int numTables=GWEN_IdList64_GetUsedTables(idl);
464
465 for (idx=0; idx<numTables; idx++) {
466 GWEN_IDTABLE64 *idt;
467
468 idt=GWEN_IdList64_GetTableAt(idl, idx);
469 if (idt) {
470 int i;
471
472 for (i=0; i<entriesPerTable; i++) {
473 if (idt->ptrEntries[i]==wantedId) {
474 return 1;
475 }
476 }
477 }
478 }
479 return 0;
480 }
481
482
483
GWEN_IdList64_DelId(GWEN_IDLIST64 * idl,uint64_t wantedId)484 int GWEN_IdList64_DelId(GWEN_IDLIST64 *idl, uint64_t wantedId)
485 {
486 uint32_t idx;
487 int entriesPerTable=GWEN_IdList64_GetTableMaxEntries(idl);
488 int numTables=GWEN_IdList64_GetUsedTables(idl);
489
490 for (idx=0; idx<numTables; idx++) {
491 GWEN_IDTABLE64 *idt;
492
493 idt=GWEN_IdList64_GetTableAt(idl, idx);
494 if (idt) {
495 int i;
496
497 for (i=0; i<entriesPerTable; i++) {
498 if (idt->ptrEntries[i]==wantedId) {
499 idt->ptrEntries[i]=0;
500 GWEN_IdList64_DecIdCounter(idl);
501 return 1;
502 }
503 }
504 }
505 }
506 return 0;
507 }
508
509
510
511
512
_attachToTable(GWEN_UNUSED GWEN_SIMPLEPTRLIST * pl,void * p)513 static GWENHYWFAR_CB void _attachToTable(GWEN_UNUSED GWEN_SIMPLEPTRLIST *pl, void *p)
514 {
515 GWEN_IDTABLE64 *ft;
516
517 ft=(GWEN_IDTABLE64 *) p;
518 GWEN_IdTable64_Attach(ft);
519 }
520
521
522
_detachFromTable(GWEN_UNUSED GWEN_SIMPLEPTRLIST * pl,void * p)523 static GWENHYWFAR_CB void _detachFromTable(GWEN_UNUSED GWEN_SIMPLEPTRLIST *pl, void *p)
524 {
525 GWEN_IDTABLE64 *ft;
526
527 ft=(GWEN_IDTABLE64 *) p;
528 GWEN_IdTable64_free(ft);
529 }
530
531
532
GWEN_IdList64__GetFirstId(const GWEN_IDLIST64 * idl,uint64_t * pos)533 uint64_t GWEN_IdList64__GetFirstId(const GWEN_IDLIST64 *idl, uint64_t *pos)
534 {
535 uint32_t idx;
536 int idIndex=0;
537 int entriesPerTable=GWEN_IdList64_GetTableMaxEntries(idl);
538 int numTables=GWEN_IdList64_GetUsedTables(idl);
539
540 *pos=0;
541 for (idx=0; idx<numTables; idx++) {
542 GWEN_IDTABLE64 *idt;
543
544 idt=GWEN_IdList64_GetTableAt(idl, idx);
545 if (idt) {
546 int i;
547 uint64_t id;
548
549 for (i=0; i<entriesPerTable; i++) {
550 if (idt->ptrEntries[i]!=0) {
551 id=idt->ptrEntries[i];
552 *pos=idIndex+i+1;
553 return id;
554 }
555 }
556 }
557 idIndex+=entriesPerTable;
558 }
559
560 return 0;
561 }
562
563
564
GWEN_IdList64__GetNextId(const GWEN_IDLIST64 * idl,uint64_t * pos)565 uint64_t GWEN_IdList64__GetNextId(const GWEN_IDLIST64 *idl, uint64_t *pos)
566 {
567 if (*pos) {
568 int entriesPerTable=GWEN_IdList64_GetTableMaxEntries(idl);
569 int numTables=GWEN_IdList64_GetUsedTables(idl);
570 uint64_t tableNum;
571 uint64_t tableIdx;
572 int idIndex=0;
573 uint32_t idx;
574
575 tableNum=*pos / entriesPerTable;
576 tableIdx=*pos % entriesPerTable;
577
578 if (tableNum>numTables) {
579 DBG_ERROR(GWEN_LOGDOMAIN, "Table number out of range");
580 *pos=0;
581 return 0;
582 }
583
584 idIndex=(tableNum*entriesPerTable);
585
586 for (idx=tableNum; idx<numTables; idx++) {
587 GWEN_IDTABLE64 *idt;
588
589 idt=GWEN_IdList64_GetTableAt(idl, idx);
590 if (idt) {
591 int i;
592 uint64_t id;
593
594 if (idx==tableNum) {
595 for (i=tableIdx; i<entriesPerTable; i++) {
596 if (idt->ptrEntries[i]!=0) {
597 id=idt->ptrEntries[i];
598 *pos=idIndex+i+1;
599 return id;
600 }
601 }
602 }
603 else {
604 for (i=0; i<entriesPerTable; i++) {
605 if (idt->ptrEntries[i]!=0) {
606 id=idt->ptrEntries[i];
607 *pos=idIndex+i+1;
608 return id;
609 }
610 }
611 }
612 }
613 idIndex+=entriesPerTable;
614 }
615 *pos=0;
616 }
617
618 return 0;
619 }
620
621
622
GWEN_IdList64__Sort(GWEN_IDLIST64 * idl,int ascending)623 int GWEN_IdList64__Sort(GWEN_IDLIST64 *idl, int ascending)
624 {
625 uint64_t entryCount;
626
627 assert(idl);
628
629 entryCount=GWEN_IdList64_GetEntryCount(idl);
630
631 if (entryCount) {
632 GWEN_IDLIST64_ITERATOR *it;
633 uint64_t *ptr;
634 unsigned int i;
635
636 assert(idl);
637
638 /* move ids to a temporary list */
639 ptr=(uint64_t *)malloc(sizeof(uint64_t)*entryCount);
640 assert(ptr);
641
642 it=GWEN_IdList64_Iterator_new(idl);
643 for (i=0; i<entryCount; i++) {
644 uint64_t id;
645
646 if (i==0)
647 id=GWEN_IdList64_Iterator_GetFirstId(it);
648 else
649 id=GWEN_IdList64_Iterator_GetNextId(it);
650 assert(id);
651 ptr[i]=id;
652 } /* for */
653 GWEN_IdList64_Iterator_free(it);
654
655 /* remove all tables (we will add sorted tables later) */
656 GWEN_IdList64_Clear(idl);
657
658 if (ascending)
659 qsort(ptr, entryCount, sizeof(uint64_t), __compAscending);
660 else
661 qsort(ptr, entryCount, sizeof(uint64_t), __compDescending);
662
663 /* move back sorted list of ids from temporary list */
664 for (i=0; i<entryCount; i++) {
665 GWEN_IdList64_AddId(idl, ptr[i]);
666 }
667 free(ptr);
668 }
669 return 0;
670 }
671
672
673
GWEN_IdList64_Sort(GWEN_IDLIST64 * idl)674 int GWEN_IdList64_Sort(GWEN_IDLIST64 *idl)
675 {
676 return GWEN_IdList64__Sort(idl, 1);
677 }
678
679
680
GWEN_IdList64_ReverseSort(GWEN_IDLIST64 * idl)681 int GWEN_IdList64_ReverseSort(GWEN_IDLIST64 *idl)
682 {
683 return GWEN_IdList64__Sort(idl, 0);
684 }
685
686
687
__compAscending(const void * pa,const void * pb)688 int __compAscending(const void *pa, const void *pb)
689 {
690 uint64_t a=*((const uint64_t *)pa);
691 uint64_t b=*((const uint64_t *)pb);
692
693 if (a<b)
694 return -1;
695 else if (a>b)
696 return 1;
697 else
698 return 0;
699 }
700
701
702
__compDescending(const void * pa,const void * pb)703 int __compDescending(const void *pa, const void *pb)
704 {
705 uint64_t a=*((const uint64_t *)pa);
706 uint64_t b=*((const uint64_t *)pb);
707
708 if (a<b)
709 return 1;
710 else if (a>b)
711 return -1;
712 else
713 return 0;
714 }
715
716
717
718
719
720
721
722 /* ------------------------------------------------------------------------------------------------
723 * GWEN_IdList64_Iterator
724 * ------------------------------------------------------------------------------------------------
725 */
726
727
GWEN_IdList64_Iterator_new(const GWEN_IDLIST64 * idl)728 GWEN_IDLIST64_ITERATOR *GWEN_IdList64_Iterator_new(const GWEN_IDLIST64 *idl)
729 {
730 GWEN_IDLIST64_ITERATOR *it;
731
732 assert(idl);
733 GWEN_NEW_OBJECT(GWEN_IDLIST64_ITERATOR, it);
734
735 it->list=idl;
736
737 return it;
738 }
739
740
741
GWEN_IdList64_Iterator_free(GWEN_IDLIST64_ITERATOR * it)742 void GWEN_IdList64_Iterator_free(GWEN_IDLIST64_ITERATOR *it)
743 {
744 if (it) {
745 GWEN_FREE_OBJECT(it);
746 }
747 }
748
749
750
GWEN_IdList64_Iterator_GetFirstId(GWEN_IDLIST64_ITERATOR * it)751 uint64_t GWEN_IdList64_Iterator_GetFirstId(GWEN_IDLIST64_ITERATOR *it)
752 {
753 return GWEN_IdList64__GetFirstId(it->list, &(it->nextIndex));
754 }
755
756
757
GWEN_IdList64_Iterator_GetNextId(GWEN_IDLIST64_ITERATOR * it)758 uint64_t GWEN_IdList64_Iterator_GetNextId(GWEN_IDLIST64_ITERATOR *it)
759 {
760 return GWEN_IdList64__GetNextId(it->list, &(it->nextIndex));
761 }
762
763
764
765
766
767
768 /* ------------------------------------------------------------------------------------------------
769 * GWEN_IdTable64
770 * ------------------------------------------------------------------------------------------------
771 */
772
773
774
GWEN_IdTable64_new()775 GWEN_IDTABLE64 *GWEN_IdTable64_new()
776 {
777 GWEN_IDTABLE64 *ft;
778
779 GWEN_NEW_OBJECT(GWEN_IDTABLE64, ft);
780 ft->refCount=1;
781
782 return ft;
783 }
784
785
786
GWEN_IdTable64_Attach(GWEN_IDTABLE64 * ft)787 void GWEN_IdTable64_Attach(GWEN_IDTABLE64 *ft)
788 {
789 assert(ft && ft->refCount);
790 if (ft && ft->refCount) {
791 ft->refCount++;
792 }
793 }
794
795
796
GWEN_IdTable64_free(GWEN_IDTABLE64 * ft)797 void GWEN_IdTable64_free(GWEN_IDTABLE64 *ft)
798 {
799 if (ft) {
800 assert(ft->refCount);
801 if (ft->refCount==1) {
802 ft->refCount=0;
803 free(ft->ptrEntries);
804 GWEN_FREE_OBJECT(ft);
805 }
806 else {
807 ft->refCount--;
808 }
809 }
810 }
811
812
813
GWEN_IdTable64_GetRefCounter(const GWEN_IDTABLE64 * ft)814 int GWEN_IdTable64_GetRefCounter(const GWEN_IDTABLE64 *ft)
815 {
816 assert(ft);
817 return ft->refCount;
818 }
819
820
821
GWEN_IdTable64_dup(const GWEN_IDTABLE64 * ftOrig)822 GWEN_IDTABLE64 *GWEN_IdTable64_dup(const GWEN_IDTABLE64 *ftOrig)
823 {
824 GWEN_IDTABLE64 *ft;
825
826 assert(ftOrig);
827 assert(ftOrig->refCount);
828 ft=GWEN_IdTable64_new();
829 ft->maxEntries=ftOrig->maxEntries;
830 ft->freeEntries=ftOrig->freeEntries;
831 ft->highestEntry=ftOrig->highestEntry;
832 ft->runtimeFlags=ftOrig->runtimeFlags;
833
834 /* copy offset entries */
835 if (ftOrig->maxEntries && ftOrig->ptrEntries) {
836 uint64_t offsetArraySize;
837
838 offsetArraySize=ftOrig->maxEntries*sizeof(uint64_t);
839 ft->ptrEntries=(uint64_t *) malloc(offsetArraySize);
840 assert(ft->ptrEntries);
841 memmove(ft->ptrEntries, ftOrig->ptrEntries, offsetArraySize);
842 }
843
844 return ft;
845 }
846
847
848
GWEN_IdTable64_Create(uint64_t maxEntries)849 GWEN_IDTABLE64 *GWEN_IdTable64_Create(uint64_t maxEntries)
850 {
851 GWEN_IDTABLE64 *ft;
852 uint64_t offsetArraySize;
853 uint64_t *ptr;
854
855 ft=GWEN_IdTable64_new();
856 ft->maxEntries=maxEntries;
857 ft->freeEntries=maxEntries;
858
859 offsetArraySize=ft->maxEntries*sizeof(uint64_t);
860
861 ptr=(uint64_t *) malloc(offsetArraySize);
862 assert(ptr);
863 memset(ptr, 0, offsetArraySize);
864 GWEN_IdTable64_SetPtrEntries(ft, ptr);
865
866 return ft;
867 }
868
869
870
GWEN_IdTable64_GetMaxEntries(const GWEN_IDTABLE64 * ft)871 uint64_t GWEN_IdTable64_GetMaxEntries(const GWEN_IDTABLE64 *ft)
872 {
873 assert(ft);
874 assert(ft->refCount);
875 return ft->maxEntries;
876 }
877
878
879
GWEN_IdTable64_GetFreeEntries(const GWEN_IDTABLE64 * ft)880 uint64_t GWEN_IdTable64_GetFreeEntries(const GWEN_IDTABLE64 *ft)
881 {
882 assert(ft);
883 assert(ft->refCount);
884 return ft->freeEntries;
885 }
886
887
888
GWEN_IdTable64_DecFreeEntries(GWEN_IDTABLE64 * ft)889 void GWEN_IdTable64_DecFreeEntries(GWEN_IDTABLE64 *ft)
890 {
891 assert(ft);
892 assert(ft->refCount);
893 if (ft->freeEntries>0)
894 ft->freeEntries--;
895 }
896
897
898
GWEN_IdTable64_GetHighestEntry(const GWEN_IDTABLE64 * ft)899 uint64_t GWEN_IdTable64_GetHighestEntry(const GWEN_IDTABLE64 *ft)
900 {
901 assert(ft);
902 assert(ft->refCount);
903 return ft->highestEntry;
904 }
905
906
907
GWEN_IdTable64_CheckAndSetHighestEntry(GWEN_IDTABLE64 * ft,uint64_t i)908 void GWEN_IdTable64_CheckAndSetHighestEntry(GWEN_IDTABLE64 *ft, uint64_t i)
909 {
910 assert(ft);
911 assert(ft->refCount);
912 if (i>ft->highestEntry)
913 ft->highestEntry=i;
914 }
915
916
917
GWEN_IdTable64_GetPtrEntries(const GWEN_IDTABLE64 * ft)918 uint64_t *GWEN_IdTable64_GetPtrEntries(const GWEN_IDTABLE64 *ft)
919 {
920 assert(ft);
921 assert(ft->refCount);
922 return ft->ptrEntries;
923 }
924
925
926
GWEN_IdTable64_SetPtrEntries(GWEN_IDTABLE64 * ft,uint64_t * ptr)927 void GWEN_IdTable64_SetPtrEntries(GWEN_IDTABLE64 *ft, uint64_t *ptr)
928 {
929 assert(ft);
930 assert(ft->refCount);
931 if (ft->ptrEntries && ft->ptrEntries!=ptr)
932 free(ft->ptrEntries);
933 ft->ptrEntries=ptr;
934 }
935
936
937
GWEN_IdTable64_GetRuntimeFlags(const GWEN_IDTABLE64 * ft)938 uint32_t GWEN_IdTable64_GetRuntimeFlags(const GWEN_IDTABLE64 *ft)
939 {
940 assert(ft);
941 return ft->runtimeFlags;
942 }
943
944
945
GWEN_IdTable64_AddRuntimeFlags(GWEN_IDTABLE64 * ft,uint32_t i)946 void GWEN_IdTable64_AddRuntimeFlags(GWEN_IDTABLE64 *ft, uint32_t i)
947 {
948 assert(ft);
949 ft->runtimeFlags|=i;
950 }
951
952
953
954 /* include tests */
955 #include "idlist64-t.c"
956
957