diff options
author | Sergey Poznyakoff <gray@gnu.org> | 2018-06-25 08:44:39 +0300 |
---|---|---|
committer | Sergey Poznyakoff <gray@gnu.org> | 2018-06-25 08:44:39 +0300 |
commit | b0560e7bfb6e19b061b926c506f3ee4b04f77ecf (patch) | |
tree | 077257f4139fcb297e4f0b52d55075a679659e1b | |
parent | c458171c6deaa9a8eb70d2f9c2c21a129daeb32d (diff) | |
download | gdbm-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.c | 131 |
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. */ | ||
348 | static int | ||
349 | avail_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 | */ | ||
372 | static inline void | ||
373 | avail_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 | ||