summaryrefslogtreecommitdiff
path: root/apps/tagdb/array_buffer.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/tagdb/array_buffer.c')
-rw-r--r--apps/tagdb/array_buffer.c667
1 files changed, 667 insertions, 0 deletions
diff --git a/apps/tagdb/array_buffer.c b/apps/tagdb/array_buffer.c
new file mode 100644
index 0000000000..24772d6bc9
--- /dev/null
+++ b/apps/tagdb/array_buffer.c
@@ -0,0 +1,667 @@
1#include "malloc.h" // malloc() and free()
2
3#include "array_buffer.h"
4#include "unique.h"
5
6static int add_mem(struct array_buffer *b, void *e);
7static int add_file(struct array_buffer *b, void *e);
8
9static int update_entry_mem(struct array_buffer *b, const uint32_t index, uint32_t item);
10static int update_entry_file(struct array_buffer *b, const uint32_t index, uint32_t item);
11
12static int find_entry_mem(struct array_buffer *b, const void *needle, uint32_t *index);
13static int find_entry_file(struct array_buffer *b, const void *needle, uint32_t *index);
14
15static int sort_mem(struct array_buffer *b);
16static int sort_mem_merge_blocks(uint32_t *dest, uint32_t *s1, uint32_t s1_l, uint32_t *s2, uint32_t s2_l, struct array_buffer *b);
17static int sort_mem_merge(uint32_t *dest, uint32_t *src, struct array_buffer *b, uint32_t blocksize);
18static int sort_file(struct array_buffer *b);
19
20struct array_buffer* new_array_buffer( int (*cmp)(const void *a, const void *b),
21 int (*serialize)(FILE *fd, const void *e),
22 int (*unserialize)(void **e, FILE *fd),
23 uint32_t (*get_length)(const void *size),
24 int (*write)(FILE *fd, void *e, const void *size),
25 int (*destruct)(void *e),
26 char* file_name,
27 void* max_size,
28 int (*max_size_update)(void *max_size, const void *e),
29 int (*max_size_destruct)(void *max_size),
30 int (*add_item_mem)(void *e, void *s, uint32_t item),
31 int (*add_item_file)(FILE *fd, void *e, void *s, uint32_t item),
32 int (*pre_write)(void *e, void *s)
33 ) {
34 struct array_buffer *b;
35 b = (struct array_buffer*)malloc(sizeof(struct array_buffer));
36 if( b == NULL ) {
37 DEBUGF("new_array_buffer: failed to allocate memory\n");
38 return NULL;
39 }
40
41 b->count = 0;
42 b->array = NULL;
43 b->sort = NULL;
44
45 b->file_name = file_name;
46
47 b->fd = NULL;
48
49 b->cmp = cmp;
50 b->serialize = serialize;
51 b->unserialize = unserialize;
52 b->get_length = get_length;
53 b->write = write;
54 b->destruct = destruct;
55
56 b->max_size = max_size;
57 b->max_size_update = max_size_update;
58 b->max_size_destruct = max_size_destruct;
59
60 b->add_item_mem = add_item_mem;
61 b->add_item_file = add_item_file;
62
63 b->pre_write = pre_write;
64
65 return b;
66}
67
68int array_buffer_destruct(struct array_buffer *b, const int free_file_name) {
69 assert(b != NULL);
70
71 if( b->fd == NULL ) {
72 if( b->destruct == NULL ) {
73 DEBUGF("array_buffer_destruct: no destruct() function registered\n");
74 return ERR_MALLOC;
75 }
76 //we have memory to clean up
77 // iterate over all stored objects:
78 for(; b->count > 0; b->count--) {
79 if( b->destruct(b->array[b->count-1].mem) ) {
80 DEBUGF("array_buffer_destruct: failed to destruct item[%u]\n", b->count-1);
81 return ERR_MALLOC;
82 }
83 }
84 }
85 free(b->array);
86
87 if( b->fd != NULL ) {
88 // we have a file to clean up
89 if( fclose(b->fd) != 0 ) {
90 DEBUGF("array_buffer_destruct: fclose() failed\n");
91 return ERR_FILE;
92 }
93 b->fd = NULL;
94
95 // remove that file
96 if( remove(b->file_name) != 0 ) {
97 DEBUGF("array_buffer_destruct: remove() failed\n");
98 return ERR_FILE;
99 }
100 }
101 if( free_file_name ) {
102 free(b->file_name);
103 b->file_name = NULL;
104 }
105
106 free(b->sort);
107 b->sort = NULL;
108
109 // free the max_size
110 if( b->max_size != NULL ) {
111 if( b->max_size_destruct == NULL ) {
112 DEBUGF("array_buffer_destruct: no max_size_destruct() function registered\n");
113 return 1;
114 }
115
116 if( b->max_size_destruct(b->max_size) ) {
117 DEBUGF("array_buffer_destruct: failed to destruct max_size\n");
118 return ERR_MALLOC;
119 }
120 b->max_size = NULL;
121 }
122
123 free(b);
124
125 return ERR_NONE;
126}
127
128int array_buffer_switch_to_file(struct array_buffer *b) {
129 uint32_t i;
130 long offset;
131
132 assert(b != NULL);
133
134 if(b->file_name == NULL) {
135 DEBUGF("array_buffer_switch_to_file: no file_name, failing...\n");
136 return ERR_MALLOC;
137 }
138
139 if( b->fd != NULL ) {
140 DEBUGF("array_buffer_switch_to_file: already in file, failing...\n");
141 return ERR_MALLOC;
142 }
143
144 // function calls exist?
145 if( b->serialize == NULL || b->unserialize == NULL ) {
146 DEBUGF("array_buffer_switch_to_file: serialize() and/or unserialize() function(s) not registered\n");
147 return ERR_INVALID;
148 }
149
150 // since we got here, we are VERY short on memory
151 // We cannot do any memory allocation before free()ing some
152 // The filename is already allocated in the constructor
153
154 // open the file
155 b->fd = fopen(b->file_name, "w+");
156 if( b->fd == NULL ) {
157 DEBUGF("array_buffer_switch_to_file: failed to fopen() file\n");
158 return ERR_FILE;
159 }
160
161 for(i=0; i<b->count; i++) {
162 offset = ftell(b->fd);
163 if( offset == -1 ) {
164 DEBUGF("array_buffer_switch_to_file: ftell() failed\n");
165 return ERR_FILE;
166 }
167
168 if( b->serialize(b->fd, b->array[i].mem) ) {
169 DEBUGF("array_buffer_switch_to_file: serialize() failed on item[%u], ignoring...\n", i);
170 }
171 b->destruct(b->array[i].mem);
172
173 b->array[i].file_offset = offset;
174 }
175
176 return ERR_NONE;
177}
178
179static int add_mem(struct array_buffer *b, void *e) {
180 assert(b != NULL);
181 assert(e != NULL);
182
183 // just copy over the pointer
184 b->array[b->count].mem = e;
185
186 return ERR_NONE;
187}
188
189static int add_file(struct array_buffer *b, void *e) {
190 int rc;
191
192 assert(b != NULL);
193 assert(e != NULL);
194
195 if( fseek(b->fd, 0, SEEK_END) != 0 ) {
196 DEBUGF("add_file: could not seek to end of file\n");
197 return ERR_FILE;
198 }
199 if(( b->array[b->count].file_offset = ftell(b->fd) ) == -1) {
200 DEBUGF("add_file: ftell() failed to get file_offset\n");
201 return ERR_FILE;
202 }
203
204 if(( rc = b->serialize(b->fd, e) )) {
205 DEBUGF("add_file: could not serialize entry\n");
206 return rc;
207 }
208 if( b->destruct(e) ) {
209 DEBUGF("add_file: could not destruct entry, ignoring... (memory leak)\n");
210 }
211 return ERR_NONE;
212}
213
214int array_buffer_add(struct array_buffer *b, void *e, uint32_t *index) {
215 void* temp;
216 int rc;
217
218 assert(b != NULL);
219 assert(e != NULL);
220
221 // allow the object to update the max_size
222 // Do this first, so if it fails we can just return without cleanup to do
223 if( b->max_size_update != NULL ) {
224 if(( rc = b->max_size_update(b->max_size, e) )) {
225 DEBUGF("array_buffer_add: could not update max_size, failing...\n");
226 return rc;
227 }
228 }
229
230 // we need to enlarge the array[]
231 temp = (void*)realloc(b->array, sizeof(*b->array)*(b->count+1));
232 while( temp == NULL ) {
233 DEBUGF("array_buffer_add: failed to enlarge index_map[]. Switching to file\n");
234 if(( rc = array_buffer_switch_to_file(b) )) {
235 DEBUGF("array_buffer_add: failed to switch to file, failing...\n");
236 return rc;
237 }
238 // now retry
239 temp = (void*)realloc(b->array, sizeof(*b->array)*(b->count+1));
240 }
241 b->array = (union entry*)temp;
242
243 if( b->fd == NULL ) { // we are in memory
244 rc = add_mem(b, e);
245 if( rc == ERR_MALLOC ) {
246 DEBUGF("array_buffer_add: failed to add in memory due to malloc() trouble, switching to file\n");
247 if(( rc = array_buffer_switch_to_file(b) )) {
248 DEBUGF("array_buffer_add: failed to switch to file, failing...\n");
249 return rc;
250 }
251 // fall out and catch next if
252 }
253 } // NOT else, so we can catch the fall-through
254 if( b->fd != NULL) {
255 if(( rc = add_file(b, e) )) {
256 DEBUGF("array_buffer_add: failed to add in file, failing...\n");
257 return rc;
258 }
259 }
260
261 // count and index-stuff
262 if(index != NULL) *index = b->count;
263 b->count++;
264
265 return ERR_NONE;
266}
267
268inline uint32_t array_buffer_get_next_index(struct array_buffer *b) {
269 assert( b != NULL );
270 return b->count;
271}
272
273static int update_entry_mem(struct array_buffer *b, const uint32_t index, const uint32_t item) {
274 int rc;
275
276 assert(b != NULL);
277 assert(index < b->count);
278
279 if( (rc = b->add_item_mem(b->array[index].mem, b->max_size, item)) ) {
280 DEBUGF("update_entry_mem: failed to update entry\n");
281 return rc;
282 }
283
284 return ERR_NONE;
285}
286
287static int update_entry_file(struct array_buffer *b, const uint32_t index, uint32_t item) {
288/* uint32_t i, index;
289 void *e;
290 int rc;
291 long prev_file_offset;*/
292
293 assert(b != NULL);
294 assert(index < b->count);
295
296 printf("TODO: update entry in file\n");
297
298 return 10; // TODO
299/*
300 rewind(b->fd);
301
302 rc = ERR_NOTFOUND;
303 for(i=0; i<b->count; i++) {
304 prev_file_offset = ftell(b->fd); // keep this file-position
305 if( prev_file_offset == -1 ) {
306 DEBUGF("file_entry_add_file: ftell() failed\n");
307 return ERR_FILE;
308 }
309
310 if( (rc = b->unserialize(&e, b->fd)) ) {
311 DEBUGF("find_entry_add_file: unserialize failed\n");
312 return rc;
313 }
314
315 if( b->cmp(e, needle) == 0 ) { // found
316 if( fseek(b->fd, prev_file_offset, SEEK_SET) ) {
317 DEBUGF("file_entry_add_file: fseek() to entry[%u] failed\n", i);
318 return ERR_FILE;
319 }
320
321 rc = b->add_item_file(b->fd, e, b->max_size, item);
322 if( !( rc == ERR_NONE || rc == ERR_NO_INPLACE_UPDATE )) {
323 DEBUGF("find_entry_add_mem: failed to add item\n");
324 return rc;
325 }
326
327 break; // stop looping
328 }
329
330 b->destruct(e);
331 }
332
333 // seek to the end
334 if( fseek(b->fd, 0, SEEK_END) != 0) {
335 DEBUGF("find_entry_add_file: fseek(SEEK_END) failed\n");
336 return ERR_FILE;
337 }
338
339 // We either succeded, deleted the entry or didn't find it:
340 if( rc == ERR_NOTFOUND ) {
341 return rc; // quit
342 } else if( rc == ERR_NONE ) {
343 b->destruct(e); // delete the entry and quit
344 return rc;
345 }
346
347 // we could not update inplace
348 // the entry is deleted, update it and add it again
349 if( (rc = b->add_item_mem(e, b->max_size, item)) ) {
350 DEBUGF("find_entry_add_file: failed to add item in mem\n");
351 return rc;
352 }
353
354 if( (rc = array_buffer_add(b, e, &index) ) ) {
355 DEBUGF("find_entry_add_file: failed to re-add item to array");
356 return rc;
357 }
358
359 // the entry is now re-added, but with another index number...
360 // change the index_map to reflect this:
361 b->index_map[i] = index;
362
363 return ERR_NONE;*/
364}
365
366int array_buffer_entry_update(struct array_buffer *b, const uint32_t index, uint32_t item) {
367 assert(b != NULL);
368
369 if(index >= b->count) {
370 DEBUGF("array_buffer_entry_update: index out of bounds\n");
371 return ERR_INVALID;
372 }
373
374 if( b->fd == NULL ) {
375 return update_entry_mem(b, index, item);
376 } else {
377 return update_entry_file(b, index, item);
378 }
379}
380
381static int find_entry_mem(struct array_buffer *b, const void *needle, uint32_t *index) {
382 uint32_t i;
383
384 assert(b != NULL);
385 assert(needle != NULL);
386 assert(index != NULL);
387
388 for(i=0; i<b->count; i++) {
389 if( b->cmp(b->array[i].mem, needle) == 0 ) { // found
390 *index = i;
391 return ERR_NONE;
392 }
393 }
394 return ERR_NOTFOUND;
395}
396
397static int find_entry_file(struct array_buffer *b, const void *needle, uint32_t *index) {
398 uint32_t i;
399 void *e;
400 int rc;
401 long prev_file_offset;
402
403 assert(b != NULL);
404 assert(needle != NULL);
405 assert(index != NULL);
406
407 // We do this search in the order of the entries in file.
408 // After we found one, we look for the index of that offset
409 // (in memory).
410 // This will (PROBABELY: TODO) be faster than random-access the file
411 rewind(b->fd);
412
413 for(i=0; i<b->count; i++) {
414 prev_file_offset = ftell(b->fd); // keep this file-position
415 if( prev_file_offset == -1 ) {
416 DEBUGF("file_entry_add_file: ftell() failed\n");
417 return ERR_FILE;
418 }
419
420 if( (rc = b->unserialize(&e, b->fd)) ) {
421 DEBUGF("find_entry_add_file: unserialize failed\n");
422 return rc;
423 }
424
425 if( b->cmp(e, needle) == 0 ) { // found
426 if( fseek(b->fd, prev_file_offset, SEEK_SET) ) {
427 DEBUGF("file_entry_add_file: fseek() to entry[%u] failed\n", i);
428 return ERR_FILE;
429 }
430
431 b->destruct(e);
432 break; // out of the for() loop
433 }
434
435 b->destruct(e);
436 }
437
438 if( i == b->count ) {
439 // we didn't find anything
440 return ERR_NOTFOUND;
441 }
442
443 // we found an entry, look for the index number of that offset:
444 for(i=0; i<b->count; i++) {
445 if(prev_file_offset == b->array[i].file_offset) {
446 // found
447 *index = i;
448 return ERR_NONE;
449 }
450 }
451
452 // we should never get here
453 DEBUGF("find_entry_file: found entry in file, but doens't match an index\n");
454 return ERR_INVALID;
455}
456
457int array_buffer_find_entry(struct array_buffer *b, const void *needle, uint32_t *index) {
458 assert(b != NULL);
459 assert(needle != NULL);
460 assert(index != NULL); // TODO: if it is null, do the search but trash the index
461
462 if( b->fd == NULL ) {
463 return find_entry_mem(b, needle, index);
464 } else {
465 return find_entry_file(b, needle, index);
466 }
467}
468
469/*
470static int sort_mem_merge_blocks(uint32_t *dest, const uint32_t *s1, const uint32_t s1_l, const uint32_t *s2, const uint32_t s2_l, struct array_buffer *b) {
471// merges the 2 blocks at s1 (with s1_l items) and s2 (with s2_l items)
472// together in dest
473 uint32_t *s1_max, s2_max;
474
475#define CMP(a, b) b->cmp( b->entry[a].mem, b->entry[b].mem )
476
477 s1_max = s1 + s1_l;
478 s2_max = s2 + s2_l;
479 while( s1 < s1_max || s2 < s2_max ) {
480 while( s1 < s1_max && ( s2 == s2_max || CMP(s1, s2) <= 0 ) ) // s1 is smaller than s2 (or s2 is used up)
481 *(dest++) = s1++; // copy and move to next
482 while( s2 < s2_max && ( s1 == s1_max || CMP(s1, s2) > 0 ) ) // s2 smaller
483 *(dest++) = s2++;
484 }
485
486 return ERR_NONE;
487}
488
489#define MIN(a, b) ( (a) <= (b) ? (a) : (b) )
490static int sort_mem_merge(uint32_t *dest, uint32_t *src, struct array_buffer *b, uint32_t blocksize) {
491// does 1 merge from src[] into dest[]
492// asumes there are sorted blocks in src[] of size blocksize
493 assert( dest != NULL);
494 assert( src != NULL );
495
496 assert( b->count > blocksize );
497
498 // TODO
499}
500*/
501
502static int sort_mem(struct array_buffer *b) {
503 uint32_t *tmp, blocksize;
504
505 assert(b != NULL);
506
507 tmp = (uint32_t*)malloc(sizeof(uint32_t)*b->count);
508 if( tmp == NULL ) {
509 DEBUGF("sort_mem: could not malloc() for second sort[] array\n");
510 return ERR_MALLOC;
511 }
512
513 for( blocksize = 1; blocksize < b->count; blocksize++) {
514 b->sort[blocksize] = blocksize; // 1-1 map TODO
515 }
516
517 free(tmp);
518
519 return ERR_NONE;
520}
521
522static int sort_file(struct array_buffer *b) {
523 printf("TODO: file-sorting\n"); // TODO
524 return ERR_INVALID;
525}
526
527int array_buffer_sort(struct array_buffer *b) {
528 int rc;
529
530 assert(b != NULL);
531
532 b->sort = (uint32_t*)malloc(sizeof(uint32_t)*b->count);
533 if( b->sort == NULL ) {
534 DEBUGF("array_buffer_sort: could not malloc() sort[] array\n");
535 return ERR_MALLOC;
536 }
537
538 if( b->fd == NULL ) { // in memory
539 rc = sort_mem(b);
540 if( rc == ERR_MALLOC ) {
541 if(( rc = array_buffer_switch_to_file(b) )) {
542 DEBUGF("array_buffer_sort: could not switch to file mode\n");
543 return rc;
544 }
545 return sort_file(b);
546 } else if( rc ) {
547 DEBUGF("array_buffer_sort: could not sort array\n");
548 return rc;
549 }
550 return ERR_NONE;
551 } else {
552 return sort_file(b);
553 }
554}
555
556uint32_t array_buffer_get_offset(struct array_buffer *b, const uint32_t index) {
557 uint32_t offset;
558
559 assert(b != NULL);
560
561 if( index >= b->count ) {
562 DEBUGF("array_buffer_get_offset: index out of bounds\n");
563 return (uint32_t)0xffffffff;
564 }
565
566 // what is the (max) length of 1 item
567 if( b->get_length == NULL ) {
568 DEBUGF("array_buffer_get_offset: get_length() function not registered\n");
569 return (uint32_t)0xffffffff;
570 }
571 offset = b->get_length(b->max_size);
572
573 // multiply that by the number of items before me
574 if( b->sort == NULL ) { // easy, we are unsorted
575 offset *= index;
576 } else {
577 uint32_t i;
578 for(i=0; i<b->count; i++) {
579 if( b->sort[i] == index )
580 break;
581 }
582 if( i == b->count ) {
583 DEBUGF("array_buffer_get_offset: index does not appeat in sorted list\n");
584 return ERR_INVALID;
585 }
586 offset *= i; // that many items are before me
587 }
588 return offset;
589}
590
591uint32_t array_buffer_get_length(struct array_buffer *b) {
592 uint32_t length;
593
594 assert(b != NULL);
595
596 // what is the (max) length of 1 item
597 if( b->get_length == NULL ) {
598 DEBUGF("array_buffer_get_offset: get_length() function not registered\n");
599 return (uint32_t)0xffffffff;
600 }
601 length = b->get_length(b->max_size);
602
603 // multiply that by the number of items
604 length *= b->count;
605 return length;
606}
607
608int array_buffer_write(FILE *fd, struct array_buffer *b) {
609 uint32_t i;
610 int rc;
611
612 assert(b != NULL);
613 assert(fd != NULL);
614
615 // check if the functions exist
616 if( b->write == NULL ) {
617 DEBUGF("array_buffer_write: write() function not registered\n");
618 return ERR_INVALID;
619 }
620 // if the array is in file
621 // serialize and unserialize will exist, since they're checked
622 // in the array_buffer_switch_to_file()
623
624 if( b->fd != NULL ) {
625 rewind(b->fd); // seek to the beginning
626 }
627
628 for(i=0; i<b->count; i++) { // for each element
629 void* item;
630 uint32_t j;
631
632 // go through the sort-array and see which item should go next
633 if(b->sort != NULL) {
634 j = b->sort[i];
635 } else j = i;
636
637 // get the item in memory
638 if( b->fd == NULL ) { // it already is im memory, fetch the pointer
639 item = b->array[j].mem;
640 } else {
641 // since it's sorted, we shouldn't have to seek
642 if( (rc = b->unserialize(&item, b->fd)) ) {
643 DEBUGF("array_buffer_write: could not unserialize item[%u], failing...\n", i);
644 return rc;
645 }
646 }
647
648 if(b->pre_write != NULL && ( rc = b->pre_write(item, b->max_size) )) {
649 DEBUGF("array_buffer_write: pre_write function failed, failing...\n");
650 return rc;
651 }
652
653 // write item to file
654 if(( rc = b->write(fd, item, b->max_size) )) {
655 DEBUGF("array_buffer_write: could not write item[%u], failing...\n", i);
656 return rc;
657 }
658
659 // put it back where it came from
660 if( b->fd != NULL ) {
661 b->destruct(item);
662 }
663 }
664
665 return ERR_NONE;
666}
667
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-27 23:26:57 +0000