diff options
author | Sergey Poznyakoff <gray@gnu.org> | 2018-06-27 17:19:06 +0300 |
---|---|---|
committer | Sergey Poznyakoff <gray@gnu.org> | 2018-06-27 17:19:06 +0300 |
commit | 3bf70df01fc591e10b204b69074e1ff4074f143b (patch) | |
tree | 9098295c6fdc92f9530aa4827e896a281a50d389 /src | |
parent | b0560e7bfb6e19b061b926c506f3ee4b04f77ecf (diff) | |
download | gdbm-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')
-rw-r--r-- | src/falloc.c | 86 |
1 files changed, 28 insertions, 58 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. */ |
348 | static int | 348 | static int |
349 | avail_lookup (int size, int start, avail_elem *av_table, int count) | 349 | avail_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 | */ |
372 | static inline void | 371 | static inline void |
373 | avail_move (avail_elem *av_table, int count, int src, int dst) | 372 | avail_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) | ||
469 | { | ||
470 | /* Search for place to put element. List is sorted by size. */ | 448 | /* Search for place to put element. List is sorted by size. */ |
471 | index = avail_lookup (new_el.av_size, 0, av_table, *av_count); | 449 | index = avail_lookup (new_el.av_size, av_table, *av_count); |
472 | /* Move all others up one. */ | 450 | /* Move all others up one. */ |
473 | avail_move (av_table, *av_count, index, index + 1); | 451 | 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 |