aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorSergey Poznyakoff <gray@gnu.org>2018-06-25 08:44:39 +0300
committerSergey Poznyakoff <gray@gnu.org>2018-06-25 08:44:39 +0300
commitb0560e7bfb6e19b061b926c506f3ee4b04f77ecf (patch)
tree077257f4139fcb297e4f0b52d55075a679659e1b /src
parentc458171c6deaa9a8eb70d2f9c2c21a129daeb32d (diff)
downloadgdbm-b0560e7bfb6e19b061b926c506f3ee4b04f77ecf.tar.gz
gdbm-b0560e7bfb6e19b061b926c506f3ee4b04f77ecf.tar.bz2
Optimize operations on avail lists.
Use binary search for look-ups. * src/falloc.c (avail_lookup, avail_move): New functions. (get_elem): Use avail_lookup to search. (_gdbm_put_av_elem): Use avail_lookup and avail_move to handle the avail table. In coalesce mode, store the index of the greater than or equal entry to avoid extra lookup in case no suitable entry is found.
Diffstat (limited to 'src')
-rw-r--r--src/falloc.c131
1 files changed, 73 insertions, 58 deletions
diff --git a/src/falloc.c b/src/falloc.c
index a2b3fd9..c07e71c 100644
--- a/src/falloc.c
+++ b/src/falloc.c
@@ -338,12 +338,46 @@ 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. */
+static int
+avail_lookup (int size, int start, avail_elem *av_table, int count)
+{
+ if (count == 0)
+ return 0;
+
+ while (count > 0)
+ {
+ int pivot = start + (count >> 1);
+ if (size == av_table[pivot].av_size)
+ return pivot;
+ if (size > av_table[pivot].av_size)
+ {
+ start = pivot + 1;
+ count--;
+ }
+ count >>= 1;
+ }
+ return start;
+}
+
+/* In array AV_TABLE of COUNT items, move all items from
+ position SRC to DST.
+*/
+static inline void
+avail_move (avail_elem *av_table, int count, int src, int dst)
+{
+ memmove (av_table + dst, av_table + src,
+ (count - src) * sizeof av_table[0]);
+}
/* 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
found larger than SIZE, get_elem returns a size of zero. This
@@ -357,109 +391,90 @@ 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 = 0;
- while (index < *av_count && av_table[index].av_size < size)
- {
- index++;
- }
+ index = avail_lookup (size, 0, 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];
- *av_count -= 1;
- while (index < *av_count)
- {
- av_table[index] = av_table[index+1];
- index++;
- }
-
+ avail_move (av_table, *av_count, index + 1, index);
+ --*av_count;
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; /* For searching through the avail block. */
- int index1;
+ int index = -1; /* For searching through the avail block. */
/* Is it too small to deal with? */
if (new_el.av_size <= IGNORE_SIZE)
return;
- if (can_merge == TRUE)
+ if (*av_count == 0)
+ index = 0;
+ else if (can_merge == TRUE)
{
/* Search for blocks to coalesce with this one. */
- index = 0;
+ int i = 0;
- while (index < *av_count)
+ while (i < *av_count)
{
/* Can we merge with the previous block? */
- if ((av_table[index].av_adr
- + av_table[index].av_size) == new_el.av_adr)
+ if ((av_table[i].av_adr + av_table[i].av_size) == new_el.av_adr)
{
/* Simply expand the entry. */
- av_table[index].av_size += new_el.av_size;
+ 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[index].av_adr)
- {
- /* Update this entry. */
- av_table[index].av_adr = new_el.av_adr;
- av_table[index].av_size += new_el.av_size;
- }
- /* Not contiguous */
- else
- {
- index++;
- continue;
- }
-
- /* Coalescing breaks the sorting order, so we need to
- restore it */
- while (index + 1 < *av_count
- && av_table[index].av_size > av_table[index + 1].av_size)
+ /* Can we merge with the next block? */
+ else if ((new_el.av_adr + new_el.av_size) == av_table[i].av_adr)
{
- avail_elem t = av_table[index];
- av_table[index] = av_table[index + 1];
- av_table[index + 1] = t;
- index++;
+ /* 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;
+ }
+
+ /* 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)
+ {
+ 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;
}
-
/* we're done. */
return;
}
}
- /* Search for place to put element. List is sorted by size. */
- index = 0;
- while (index < *av_count && av_table[index].av_size < new_el.av_size)
+ if (index == -1)
{
- index++;
+ /* 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);
}
-
- /* Move all others up one. */
- index1 = *av_count-1;
- while (index1 >= index)
- {
- av_table[index1+1] = av_table[index1];
- index1--;
- }
-
/* Add the new element. */
av_table[index] = new_el;
/* Increment the number of elements. */
++*av_count;
}

Return to:

Send suggestions and report system problems to the System administrator.