summaryrefslogtreecommitdiffabout
path: root/src
authorSergey Poznyakoff <gray@gnu.org>2018-06-27 14:19:06 (GMT)
committer Sergey Poznyakoff <gray@gnu.org>2018-06-27 14:19:06 (GMT)
commit3bf70df01fc591e10b204b69074e1ff4074f143b (patch) (unidiff)
tree9098295c6fdc92f9530aa4827e896a281a50d389 /src
parentb0560e7bfb6e19b061b926c506f3ee4b04f77ecf (diff)
downloadgdbm-3bf70df01fc591e10b204b69074e1ff4074f143b.tar.gz
gdbm-3bf70df01fc591e10b204b69074e1ff4074f143b.tar.bz2
Coalesce mode: take into account both left- and right-adjacent slots.
* src/falloc.c (avail_lookup): Remove the start parameter. (avail_move): Take pointer to the count of entries in av_table. Update the pointed to value after performing the move. All uses changed. (_gdbm_put_av_elem): Rewrite the "can_merge" loop.
Diffstat (limited to 'src') (more/less context) (ignore whitespace changes)
-rw-r--r--src/falloc.c94
1 files changed, 32 insertions, 62 deletions
diff --git a/src/falloc.c b/src/falloc.c
index c07e71c..09b40d4 100644
--- a/src/falloc.c
+++ b/src/falloc.c
@@ -342,14 +342,13 @@ push_avail_block (GDBM_FILE dbf)
342 return 0; 342 return 0;
343} 343}
344 344
345/* Return index of an item from AV_TABLE whose AV_SIZE member is greater 345/* AV_TABLE contains COUNT entries sorted by AV_SIZE in ascending order.
346 than or equal to SIZE. Start search from index START. 346 Avail_lookup returns index of an item whose AV_SIZE member is greater
347 AV_TABLE contains COUNT entries ordered by ascending AV_SIZE. */ 347 than or equal to SIZE. */
348static int 348static int
349avail_lookup (int size, int start, avail_elem *av_table, int count) 349avail_lookup (int size, avail_elem *av_table, int count)
350{ 350{
351 if (count == 0) 351 int start = 0;
352 return 0;
353 352
354 while (count > 0) 353 while (count > 0)
355 { 354 {
@@ -366,14 +365,15 @@ avail_lookup (int size, int start, avail_elem *av_table, int count)
366 return start; 365 return start;
367} 366}
368 367
369/* In array AV_TABLE of COUNT items, move all items from 368/* In array AV_TABLE of *AV_COUNT items, move all items from
370 position SRC to DST. 369 position SRC to DST and update *AV_COUNT accordingly.
371*/ 370*/
372static inline void 371static inline void
373avail_move (avail_elem *av_table, int count, int src, int dst) 372avail_move (avail_elem *av_table, int *av_count, int src, int dst)
374{ 373{
375 memmove (av_table + dst, av_table + src, 374 memmove (av_table + dst, av_table + src,
376 (count - src) * sizeof av_table[0]); 375 (*av_count - src) * sizeof av_table[0]);
376 *av_count += dst - src;
377} 377}
378 378
379/* Get_elem returns an element in the AV_TABLE block which is 379/* Get_elem returns an element in the AV_TABLE block which is
@@ -394,7 +394,7 @@ get_elem (int size, avail_elem av_table[], int *av_count)
394 val.av_size = 0; 394 val.av_size = 0;
395 395
396 /* Search for element. List is sorted by size. */ 396 /* Search for element. List is sorted by size. */
397 index = avail_lookup (size, 0, av_table, *av_count); 397 index = avail_lookup (size, av_table, *av_count);
398 398
399 /* Did we find one of the right size? */ 399 /* Did we find one of the right size? */
400 if (index >= *av_count) 400 if (index >= *av_count)
@@ -402,8 +402,7 @@ get_elem (int size, avail_elem av_table[], int *av_count)
402 402
403 /* Ok, save that element and move all others up one. */ 403 /* Ok, save that element and move all others up one. */
404 val = av_table[index]; 404 val = av_table[index];
405 avail_move (av_table, *av_count, index + 1, index); 405 avail_move (av_table, av_count, index + 1, index);
406 --*av_count;
407 return val; 406 return val;
408} 407}
409 408
@@ -414,75 +413,46 @@ void
414_gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count, 413_gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count,
415 int can_merge) 414 int can_merge)
416{ 415{
417 int index = -1; /* For searching through the avail block. */ 416 int index;
418 417
419 /* Is it too small to deal with? */ 418 /* Is it too small to deal with? */
420 if (new_el.av_size <= IGNORE_SIZE) 419 if (new_el.av_size <= IGNORE_SIZE)
421 return; 420 return;
422 421
423 if (*av_count == 0) 422 if (can_merge == TRUE)
424 index = 0;
425 else if (can_merge == TRUE)
426 { 423 {
427 /* Search for blocks to coalesce with this one. */ 424 /* Search for blocks to coalesce with this one. */
428 int i = 0; 425 int i;
429 426
430 while (i < *av_count) 427 for (i = 0; i < *av_count; i++)
431 { 428 {
432 /* Can we merge with the previous block? */
433 if ((av_table[i].av_adr + av_table[i].av_size) == new_el.av_adr) 429 if ((av_table[i].av_adr + av_table[i].av_size) == new_el.av_adr)
434 { 430 {
435 /* Simply expand the entry. */ 431 /* Right adjacent */
436 av_table[i].av_size += new_el.av_size; 432 new_el.av_size += av_table[i].av_size;
437 } 433 new_el.av_adr = av_table[i].av_adr;
438 /* Can we merge with the next block? */ 434 avail_move (av_table, av_count, i + 1, i);
439 else if ((new_el.av_adr + new_el.av_size) == av_table[i].av_adr) 435 --i;
440 {
441 /* Update this entry. */
442 av_table[i].av_adr = new_el.av_adr;
443 av_table[i].av_size += new_el.av_size;
444 }
445 /* Not contiguous */
446 else
447 {
448 if (av_table[i].av_size < new_el.av_size)
449 index = i;
450 i++;
451 continue;
452 } 436 }
453 437
454 /* Coalescing breaks the sorting order, so we need to restore it */ 438 if ((new_el.av_adr + new_el.av_size) == av_table[i].av_adr)
455 if (i + 1 < *av_count
456 && av_table[i].av_size > av_table[i + 1].av_size)
457 { 439 {
458 avail_elem t = av_table[i]; 440 /* Left adjacent */
459 int idx = avail_lookup (t.av_size, i + 1, av_table, *av_count); 441 new_el.av_size += av_table[i].av_size;
460 avail_move (av_table, idx, i + 1, i); 442 avail_move (av_table, av_count, i + 1, i);
461 av_table[idx-1] = t; 443 --i;
462 } 444 }
463 /* we're done. */
464 return;
465 } 445 }
466 } 446 }
467 447
468 if (index == -1) 448 /* Search for place to put element. List is sorted by size. */
469 { 449 index = avail_lookup (new_el.av_size, av_table, *av_count);
470 /* Search for place to put element. List is sorted by size. */ 450 /* Move all others up one. */
471 index = avail_lookup (new_el.av_size, 0, av_table, *av_count); 451 avail_move (av_table, av_count, index, index + 1);
472 /* Move all others up one. */
473 avail_move (av_table, *av_count, index, index + 1);
474 }
475 /* Add the new element. */ 452 /* Add the new element. */
476 av_table[index] = new_el; 453 av_table[index] = new_el;
477
478 /* Increment the number of elements. */
479 ++*av_count;
480} 454}
481 455
482
483
484
485
486/* Get_block "allocates" new file space and the end of the file. This is 456/* Get_block "allocates" new file space and the end of the file. This is
487 done in integral block sizes. (This helps ensure that data smaller than 457 done in integral block sizes. (This helps ensure that data smaller than
488 one block size is in a single block.) Enough blocks are allocated to 458 one block size is in a single block.) Enough blocks are allocated to

Return to:

Send suggestions and report system problems to the System administrator.