1 //
2 // aegis - project change supervisor
3 // Copyright (C) 2002-2008, 2011, 2012 Peter Miller
4 // Copyright (C) 2007, 2008 Walter Franzini
5 //
6 // This program is free software; you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 3 of the License, or
9 // (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program. If not, see
18 // <http://www.gnu.org/licenses/>.
19 //
20
21 #include <common/ac/assert.h>
22
23 #include <common/trace.h>
24 #include <libaegis/change/branch.h>
25 #include <libaegis/project.h>
26
27
28 long
change_history_change_by_timestamp(project * pp,time_t when)29 change_history_change_by_timestamp(project *pp, time_t when)
30 {
31 trace(("%s\n{\n", __PRETTY_FUNCTION__));
32 cstate_ty *cstate_data;
33 cstate_branch_history_list_ty *hl;
34 change::pointer cp;
35 long result = 0;
36
37 cp = pp->change_get();
38 cstate_data = cp->cstate_get();
39 if (!cstate_data->branch)
40 return 0;
41 hl = cstate_data->branch->history;
42 if (!hl)
43 return 0;
44
45 trace(("hl->length = %ld;\n", (unsigned long)hl->length));
46 if (hl->length == 0)
47 return 0;
48
49 assert(hl->list);
50 if (!hl->list)
51 return 0;
52
53 long start = 0;
54 long end = hl->length - 1;
55
56 cstate_branch_history_ty *bh_start = hl->list[start];
57 assert(bh_start);
58 time_t time_start =
59 pp->change_completion_timestamp(bh_start->change_number);
60
61 cstate_branch_history_ty *bh_end = hl->list[end];
62 assert(bh_end);
63 time_t time_end =
64 pp->change_completion_timestamp(bh_end->change_number);
65
66 //
67 // Find the right candidate using an algorithm with a logarithmic
68 // time complexity.
69 //
70 for (;;)
71 {
72 assert (start <= end);
73
74 trace_long(start);
75 trace_long(end);
76
77 if (when == time_end)
78 {
79 assert(hl->list[end]);
80 result = hl->list[end]->change_number;
81 break;
82 }
83
84 //
85 // This happens only at the first iteration if `when' is outside
86 // the interval.
87 //
88 if (when > time_end)
89 {
90 assert(hl->list[end]);
91 result = hl->list[end]->change_number;
92 break;
93 }
94
95 if (when == time_start)
96 {
97 assert(hl->list[start]);
98 result = hl->list[start]->change_number;
99 break;
100 }
101
102 //
103 // This happens only at the first iteration if `when' is outside
104 // the interval.
105 //
106 if (when < time_start)
107 {
108 result = 0;
109 break;
110 }
111
112 //
113 // If we cannot further reduce the interval and `when' is still
114 // missing we return the oldest change (pointed by start).
115 //
116 if (end - start == 1)
117 {
118 assert (time_end > when);
119 assert (when > time_start);
120 assert(hl->list[start]);
121
122 result = hl->list[start]->change_number;
123 break;
124 }
125
126 long middle = (start + end) / 2;
127
128 cstate_branch_history_ty *bh_middle = hl->list[middle];
129 assert(bh_middle);
130 time_t time_middle =
131 bh_middle->when != TIME_NOT_SET
132 ? bh_middle->when
133 : pp->change_completion_timestamp(bh_middle->change_number);
134 if (when < time_middle)
135 {
136 time_end = time_middle;
137 end = middle;
138 }
139 else
140 {
141 time_start = time_middle;
142 start = middle;
143 }
144 }
145
146 return result;
147 }
148
149
150 // vim: set ts=8 sw=4 et :
151