apps/tagdb/array_buffer.c

   1 #include "malloc.h" // malloc() and free()
   2
   3 #include "array_buffer.h"
   4 #include "unique.h"
   5
   6 static int add_mem(struct array_buffer *b, void *e);
   7 static int add_file(struct array_buffer *b, void *e);
   8
   9 static int update_entry_mem(struct array_buffer *b, const uint32_t index, uint32_t item);
  10 static int update_entry_file(struct array_buffer *b, const uint32_t index, uint32_t item);
  11
  12 static int find_entry_mem(struct array_buffer *b, const void *needle, uint32_t *index);
  13 static int find_entry_file(struct array_buffer *b, const void *needle, uint32_t *index);
  14
  15 static int sort_mem(struct array_buffer *b);
  16 static 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);
  17 static int sort_mem_merge(uint32_t *dest, uint32_t *src, struct array_buffer *b, uint32_t blocksize);
  18 static int sort_file(struct array_buffer *b);
  19
  20 struct 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
  68 int 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
 128 int 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
 179 static 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
 189 static 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
 214 int 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
 268 inline uint32_t array_buffer_get_next_index(struct array_buffer *b) {
 269         assert( b != NULL );
 270         return b->count;
 271 }
 272
 273 static 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
 287 static 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
 366 int 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
 381 static 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
 397 static 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
 457 int 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 /*
 470 static 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) )
 490 static 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
 502 static 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
 522 static int sort_file(struct array_buffer *b) {
 523         printf("TODO: file-sorting\n"); // TODO
 524         return ERR_INVALID;
 525 }
 526
 527 int 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
 556 uint32_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
 591 uint32_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
 608 int 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