aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorSergey Poznyakoff <gray@gnu.org>2018-06-27 17:19:06 +0300
committerSergey Poznyakoff <gray@gnu.org>2018-06-27 17:19:06 +0300
commit3bf70df01fc591e10b204b69074e1ff4074f143b (patch)
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')
-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
@@ -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

Return to:

Send suggestions and report system problems to the System administrator.