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 | 94 |
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 @@ -344,10 +344,9 @@ push_avail_block (GDBM_FILE dbf) -/* Return index of an item from AV_TABLE whose AV_SIZE member is greater - than or equal to SIZE. Start search from index START. - AV_TABLE contains COUNT entries ordered by ascending AV_SIZE. */ +/* AV_TABLE contains COUNT entries sorted by AV_SIZE in ascending order. + Avail_lookup returns index of an item whose AV_SIZE member is greater + than or equal to SIZE. */ static int -avail_lookup (int size, int start, avail_elem *av_table, int count) +avail_lookup (int size, avail_elem *av_table, int count) { - if (count == 0) - return 0; + int start = 0; @@ -368,10 +367,11 @@ avail_lookup (int size, int start, avail_elem *av_table, int count) -/* In array AV_TABLE of COUNT items, move all items from - position SRC to DST. +/* In array AV_TABLE of *AV_COUNT items, move all items from + position SRC to DST and update *AV_COUNT accordingly. */ static inline void -avail_move (avail_elem *av_table, int count, int src, int dst) +avail_move (avail_elem *av_table, int *av_count, int src, int dst) { memmove (av_table + dst, av_table + src, - (count - src) * sizeof av_table[0]); + (*av_count - src) * sizeof av_table[0]); + *av_count += dst - src; } @@ -396,3 +396,3 @@ get_elem (int size, avail_elem av_table[], int *av_count) /* Search for element. List is sorted by size. */ - index = avail_lookup (size, 0, av_table, *av_count); + index = avail_lookup (size, av_table, *av_count); @@ -404,4 +404,3 @@ get_elem (int size, avail_elem av_table[], int *av_count) val = av_table[index]; - avail_move (av_table, *av_count, index + 1, index); - --*av_count; + avail_move (av_table, av_count, index + 1, index); return val; @@ -416,3 +415,3 @@ _gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count, { - int index = -1; /* For searching through the avail block. */ + int index; @@ -422,44 +421,25 @@ _gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count, - if (*av_count == 0) - index = 0; - else if (can_merge == TRUE) + if (can_merge == TRUE) { /* Search for blocks to coalesce with this one. */ - int i = 0; - - while (i < *av_count) + int i; + + for (i = 0; i < *av_count; i++) { - /* Can we merge with the previous block? */ if ((av_table[i].av_adr + av_table[i].av_size) == new_el.av_adr) { - /* Simply expand the entry. */ - av_table[i].av_size += new_el.av_size; - } - /* Can we merge with the next block? */ - else if ((new_el.av_adr + new_el.av_size) == av_table[i].av_adr) - { - /* Update this entry. */ - av_table[i].av_adr = new_el.av_adr; - av_table[i].av_size += new_el.av_size; - } - /* Not contiguous */ - else - { - if (av_table[i].av_size < new_el.av_size) - index = i; - i++; - continue; + /* Right adjacent */ + new_el.av_size += av_table[i].av_size; + new_el.av_adr = av_table[i].av_adr; + avail_move (av_table, av_count, i + 1, i); + --i; } - - /* Coalescing breaks the sorting order, so we need to restore it */ - if (i + 1 < *av_count - && av_table[i].av_size > av_table[i + 1].av_size) + + if ((new_el.av_adr + new_el.av_size) == av_table[i].av_adr) { - avail_elem t = av_table[i]; - int idx = avail_lookup (t.av_size, i + 1, av_table, *av_count); - avail_move (av_table, idx, i + 1, i); - av_table[idx-1] = t; + /* Left adjacent */ + new_el.av_size += av_table[i].av_size; + avail_move (av_table, av_count, i + 1, i); + --i; } - /* we're done. */ - return; } @@ -467,20 +447,10 @@ _gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count, - if (index == -1) - { - /* Search for place to put element. List is sorted by size. */ - index = avail_lookup (new_el.av_size, 0, av_table, *av_count); - /* Move all others up one. */ - avail_move (av_table, *av_count, index, index + 1); - } + /* Search for place to put element. List is sorted by size. */ + index = avail_lookup (new_el.av_size, av_table, *av_count); + /* Move all others up one. */ + avail_move (av_table, av_count, index, index + 1); /* Add the new element. */ av_table[index] = new_el; - - /* Increment the number of elements. */ - ++*av_count; } - - - - /* Get_block "allocates" new file space and the end of the file. This is |