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) (side-by-side diff)
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
@@ -339,20 +339,19 @@ push_avail_block (GDBM_FILE dbf)
free (temp);
return 0;
}
-/* 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;
while (count > 0)
{
int pivot = start + (count >> 1);
if (size == av_table[pivot].av_size)
return pivot;
@@ -363,20 +362,21 @@ avail_lookup (int size, int start, avail_elem *av_table, int count)
}
count >>= 1;
}
return start;
}
-/* 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;
}
/* Get_elem returns an element in the AV_TABLE block which is
larger than SIZE. AV_COUNT is the number of elements in the
AV_TABLE. If an item is found, it extracts it from the AV_TABLE
and moves the other elements up to fill the space. If no block is
@@ -391,101 +391,71 @@ get_elem (int size, avail_elem av_table[], int *av_count)
/* Initialize default return value. */
val.av_adr = 0;
val.av_size = 0;
/* 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);
/* Did we find one of the right size? */
if (index >= *av_count)
return val;
/* Ok, save that element and move all others up one. */
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;
}
/* This routine inserts a single NEW_EL into the AV_TABLE block.
This routine does no I/O. */
void
_gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count,
int can_merge)
{
- int index = -1; /* For searching through the avail block. */
+ int index;
/* Is it too small to deal with? */
if (new_el.av_size <= IGNORE_SIZE)
return;
- 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;
}
}
- 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
done in integral block sizes. (This helps ensure that data smaller than
one block size is in a single block.) Enough blocks are allocated to
make sure the number of bytes allocated in the blocks is larger than SIZE.
DBF contains the file header that needs updating. This routine does
no I/O. */

Return to:

Send suggestions and report system problems to the System administrator.