1 //
2 //      aegis - project change supervisor
3 //      Copyright (C) 2002-2008, 2011, 2012 Peter Miller
4 //      Copyright (C) 2007 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_timestamp_to_delta(project * pp,time_t when)29 change_history_timestamp_to_delta(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 
36     cp = pp->change_get();
37     cstate_data = cp->cstate_get();
38     if (!cstate_data->branch)
39         return 0;
40     hl = cstate_data->branch->history;
41     if (!hl)
42         return 0;
43 
44     if (hl->length == 0)
45         return 0;
46 
47     assert(hl->list);
48     if (!hl->list)
49         return 0;
50 
51     //
52     // Find the right candidate using an algorithm with a logarithmic
53     // time complexity.
54     //
55 
56     long start = 0;
57     long end = hl->length - 1;
58 
59     cstate_branch_history_ty *bh_start = hl->list[start];
60     assert(bh_start);
61     time_t time_start =
62         pp->change_completion_timestamp(bh_start->change_number);
63 
64     cstate_branch_history_ty *bh_end = hl->list[end];
65     assert(bh_end);
66     time_t time_end =
67         pp->change_completion_timestamp(bh_end->change_number);
68 
69     //
70     // Find the right candidate using an algorithm with a logarithmic
71     // time complexity.
72     //
73     long result = 0;
74     for(;;)
75     {
76         assert (start <= end);
77 
78         trace_long(start);
79         trace_long(end);
80 
81         if (when == time_end)
82         {
83             assert(hl->list[end]);
84             result = hl->list[end]->delta_number;
85             break;
86         }
87 
88         //
89         // This happend only at the 1st iteration if `when' is outside
90         // the interval.
91         //
92         if (when > time_end)
93         {
94             assert(hl->list[end]);
95             result = hl->list[end]->delta_number;
96             break;
97         }
98 
99         if (when == time_start)
100         {
101             assert(hl->list[start]);
102             result = hl->list[start]->delta_number;
103             break;
104         }
105 
106         //
107         // This happend only at the 1st iteration if `when' is outside
108         // the interval.
109         //
110         if (when < time_start)
111         {
112             result = 0;
113             break;
114         }
115 
116         //
117         // If we cannot further reduce the interval and `when' is still
118         // missing we return the oldest change (pointed by start).
119         //
120         if (end - start == 1)
121         {
122             assert (time_end > when);
123             assert (when > time_start);
124             assert(hl->list[start]);
125 
126             result = hl->list[start]->delta_number;
127             break;
128         }
129 
130         long middle = start + (end - start) / 2;
131 
132         cstate_branch_history_ty *bh_middle = hl->list[middle];
133         assert(bh_middle);
134         time_t time_middle =
135             pp->change_completion_timestamp(bh_middle->change_number);
136 
137         if (when < time_middle)
138         {
139             time_end = time_middle;
140             end = middle;
141         }
142         else
143         {
144             time_start = time_middle;
145             start = middle;
146         }
147     }
148 
149     return result;
150 }
151 
152 
153 // vim: set ts=8 sw=4 et :
154