aboutsummaryrefslogtreecommitdiff
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
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.
-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
@@ -341,6 +341,40 @@ push_avail_block (GDBM_FILE dbf)
341 341
342 return 0; 342 return 0;
343} 343}
344
345/* Return index of an item from AV_TABLE whose AV_SIZE member is greater
346 than or equal to SIZE. Start search from index START.
347 AV_TABLE contains COUNT entries ordered by ascending AV_SIZE. */
348static int
349avail_lookup (int size, int start, avail_elem *av_table, int count)
350{
351 if (count == 0)
352 return 0;
353
354 while (count > 0)
355 {
356 int pivot = start + (count >> 1);
357 if (size == av_table[pivot].av_size)
358 return pivot;
359 if (size > av_table[pivot].av_size)
360 {
361 start = pivot + 1;
362 count--;
363 }
364 count >>= 1;
365 }
366 return start;
367}
368
369/* In array AV_TABLE of COUNT items, move all items from
370 position SRC to DST.
371*/
372static inline void
373avail_move (avail_elem *av_table, int count, int src, int dst)
374{
375 memmove (av_table + dst, av_table + src,
376 (count - src) * sizeof av_table[0]);
377}
344 378
345/* 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
346 larger than SIZE. AV_COUNT is the number of elements in the 380 larger than SIZE. AV_COUNT is the number of elements in the
@@ -360,11 +394,7 @@ get_elem (int size, avail_elem av_table[], int *av_count)
360 val.av_size = 0; 394 val.av_size = 0;
361 395
362 /* Search for element. List is sorted by size. */ 396 /* Search for element. List is sorted by size. */
363 index = 0; 397 index = avail_lookup (size, 0, av_table, *av_count);
364 while (index < *av_count && av_table[index].av_size < size)
365 {
366 index++;
367 }
368 398
369 /* Did we find one of the right size? */ 399 /* Did we find one of the right size? */
370 if (index >= *av_count) 400 if (index >= *av_count)
@@ -372,17 +402,11 @@ get_elem (int size, avail_elem av_table[], int *av_count)
372 402
373 /* Ok, save that element and move all others up one. */ 403 /* Ok, save that element and move all others up one. */
374 val = av_table[index]; 404 val = av_table[index];
375 *av_count -= 1; 405 avail_move (av_table, *av_count, index + 1, index);
376 while (index < *av_count) 406 --*av_count;
377 {
378 av_table[index] = av_table[index+1];
379 index++;
380 }
381
382 return val; 407 return val;
383} 408}
384 409
385
386/* This routine inserts a single NEW_EL into the AV_TABLE block. 410/* This routine inserts a single NEW_EL into the AV_TABLE block.
387 This routine does no I/O. */ 411 This routine does no I/O. */
388 412
@@ -390,73 +414,64 @@ void
390_gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count, 414_gdbm_put_av_elem (avail_elem new_el, avail_elem av_table[], int *av_count,
391 int can_merge) 415 int can_merge)
392{ 416{
393 int index; /* For searching through the avail block. */ 417 int index = -1; /* For searching through the avail block. */
394 int index1;
395 418
396 /* Is it too small to deal with? */ 419 /* Is it too small to deal with? */
397 if (new_el.av_size <= IGNORE_SIZE) 420 if (new_el.av_size <= IGNORE_SIZE)
398 return; 421 return;
399 422
400 if (can_merge == TRUE) 423 if (*av_count == 0)
424 index = 0;
425 else if (can_merge == TRUE)
401 { 426 {
402 /* Search for blocks to coalesce with this one. */ 427 /* Search for blocks to coalesce with this one. */
403 index = 0; 428 int i = 0;
404 429
405 while (index < *av_count) 430 while (i < *av_count)
406 { 431 {
407 /* Can we merge with the previous block? */ 432 /* Can we merge with the previous block? */
408 if ((av_table[index].av_adr 433 if ((av_table[i].av_adr + av_table[i].av_size) == new_el.av_adr)
409 + av_table[index].av_size) == new_el.av_adr)
410 { 434 {
411 /* Simply expand the entry. */ 435 /* Simply expand the entry. */
412 av_table[index].av_size += new_el.av_size; 436 av_table[i].av_size += new_el.av_size;
413 } 437 }
414 /* Can we merge with the next block? */ 438 /* Can we merge with the next block? */
415 else if ((new_el.av_adr 439 else if ((new_el.av_adr + new_el.av_size) == av_table[i].av_adr)
416 + new_el.av_size) == av_table[index].av_adr)
417 {
418 /* Update this entry. */
419 av_table[index].av_adr = new_el.av_adr;
420 av_table[index].av_size += new_el.av_size;
421 }
422 /* Not contiguous */
423 else
424 {
425 index++;
426 continue;
427 }
428
429 /* Coalescing breaks the sorting order, so we need to
430 restore it */
431 while (index + 1 < *av_count
432 && av_table[index].av_size > av_table[index + 1].av_size)
433 { 440 {
434 avail_elem t = av_table[index]; 441 /* Update this entry. */
435 av_table[index] = av_table[index + 1]; 442 av_table[i].av_adr = new_el.av_adr;
436 av_table[index + 1] = t; 443 av_table[i].av_size += new_el.av_size;
437 index++; 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 }
453
454 /* Coalescing breaks the sorting order, so we need to restore it */
455 if (i + 1 < *av_count
456 && av_table[i].av_size > av_table[i + 1].av_size)
457 {
458 avail_elem t = av_table[i];
459 int idx = avail_lookup (t.av_size, i + 1, av_table, *av_count);
460 avail_move (av_table, idx, i + 1, i);
461 av_table[idx-1] = t;
438 } 462 }
439
440 /* we're done. */ 463 /* we're done. */
441 return; 464 return;
442 } 465 }
443 } 466 }
444 467
445 /* Search for place to put element. List is sorted by size. */ 468 if (index == -1)
446 index = 0;
447 while (index < *av_count && av_table[index].av_size < new_el.av_size)
448 { 469 {
449 index++; 470 /* Search for place to put element. List is sorted by size. */
471 index = avail_lookup (new_el.av_size, 0, av_table, *av_count);
472 /* Move all others up one. */
473 avail_move (av_table, *av_count, index, index + 1);
450 } 474 }
451
452 /* Move all others up one. */
453 index1 = *av_count-1;
454 while (index1 >= index)
455 {
456 av_table[index1+1] = av_table[index1];
457 index1--;
458 }
459
460 /* Add the new element. */ 475 /* Add the new element. */
461 av_table[index] = new_el; 476 av_table[index] = new_el;
462 477

Return to:

Send suggestions and report system problems to the System administrator.