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)29change_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