aboutsummaryrefslogtreecommitdiff
path: root/time
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2007-03-05 19:32:03 +0000
committerUlrich Drepper <drepper@redhat.com>2007-03-05 19:32:03 +0000
commit132526780a7373d92e1d9b92fc76138beec07a13 (patch)
tree7013ac25f07d7f8f85da364f2a3ff6187dea63b7 /time
parentfe64626c136b3e1be9bd51acb6e4c0714f5815d0 (diff)
downloadglibc-132526780a7373d92e1d9b92fc76138beec07a13.zip
glibc-132526780a7373d92e1d9b92fc76138beec07a13.tar.gz
glibc-132526780a7373d92e1d9b92fc76138beec07a13.tar.bz2
(find_transition): Instead of a linear search try to guess the transition index, use a linear search if the result is at most 10 transitions away from the guess or binary search otherwise.
Diffstat (limited to 'time')
-rw-r--r--time/tzfile.c53
1 files changed, 50 insertions, 3 deletions
diff --git a/time/tzfile.c b/time/tzfile.c
index ea2d7ca..0d48c8c 100644
--- a/time/tzfile.c
+++ b/time/tzfile.c
@@ -548,13 +548,60 @@ find_transition (time_t timer)
if (i == num_types)
i = 0;
}
+ else if (timer >= transitions[num_transitions - 1])
+ i = type_idxs[num_transitions - 1];
else
{
/* Find the first transition after TIMER, and
then pick the type of the transition before it. */
- for (i = 1; i < num_transitions; ++i)
- if (timer < transitions[i])
- break;
+ size_t lo = 0;
+ size_t hi = num_transitions - 1;
+ /* Assume that DST is changing twice a year and guess initial
+ search spot from it.
+ Half of a gregorian year has on average 365.2425 * 86400 / 2
+ = 15778476 seconds. */
+ i = (transitions[num_transitions - 1] - timer) / 15778476;
+ if (i < num_transitions)
+ {
+ i = num_transitions - 1 - i;
+ if (timer < transitions[i])
+ {
+ if (i < 10 || timer >= transitions[i - 10])
+ {
+ /* Linear search. */
+ while (timer < transitions[i - 1])
+ --i;
+ goto found;
+ }
+ hi = i - 10;
+ }
+ else
+ {
+ if (i + 10 >= num_transitions || timer < transitions[i + 10])
+ {
+ /* Linear search. */
+ while (timer >= transitions[i])
+ ++i;
+ goto found;
+ }
+ lo = i + 10;
+ }
+ }
+
+ /* Binary search. */
+ /* assert (timer >= transitions[lo] && timer < transitions[hi]); */
+ while (lo + 1 < hi)
+ {
+ i = (lo + hi) / 2;
+ if (timer < transitions[i])
+ hi = i;
+ else
+ lo = i;
+ }
+ i = hi;
+
+ found:
+ /* assert (timer >= transitions[i - 1] && timer < transitions[i]); */
i = type_idxs[i - 1];
}