"Fossies" - the Fresh Open Source Software Archive 
Member "zsync-0.6.2/librcksum/range.c" (16 Sep 2010, 7233 Bytes) of package /linux/privat/old/zsync-0.6.2.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "range.c" see the
Fossies "Dox" file reference documentation.
1
2 /*
3 * rcksum/lib - library for using the rsync algorithm to determine
4 * which parts of a file you have and which you need.
5 * Copyright (C) 2004,2005,2007,2009 Colin Phipps <cph@moria.org.uk>
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the Artistic License v2 (see the accompanying
9 * file COPYING for the full license terms), or, at your option, any later
10 * version of the same license.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * COPYING file for details.
16 */
17
18 /* Manage storage of the set of ranges in the target file that we have so far
19 * got data for. */
20
21 #include "zsglobal.h"
22
23 #include <stdlib.h>
24 #include <string.h>
25 #include <sys/types.h>
26
27 #ifdef WITH_DMALLOC
28 # include <dmalloc.h>
29 #endif
30
31 #include "rcksum.h"
32 #include "internal.h"
33
34 /* r = range_before_block(self, x)
35 * This determines which of the existing known ranges x falls in.
36 * It returns -1 if it is inside an existing range (it doesn't tell you which
37 * one; if you already have it, that usually is enough to know).
38 * Or it returns 0 if x is before the 1st range;
39 * 1 if it is between ranges 1 and 2 (array indexes 0 and 1)
40 * ...
41 * numranges if it is after the last range
42 */
43 static int range_before_block(const struct rcksum_state* rs, zs_blockid x) {
44 /* Lowest number and highest number block that it could be inside (0 based) */
45 register int min = 0, max = rs->numranges-1;
46
47 /* By bisection */
48 for (; min<=max;) {
49 /* Range number to compare against */
50 register int r = (max+min)/2;
51
52 if (x > rs->ranges[2*r+1]) min = r+1; /* After range r */
53 else if (x < rs->ranges[2*r]) max = r-1;/* Before range r */
54 else return -1; /* In range r */
55 }
56
57 /* If we reach here, we know min = max + 1 and we were below range max+1
58 * and above range min-1.
59 * So we're between range max and max + 1
60 * So we return max + 1 (return value is 1 based) ( = min )
61 */
62 return min;
63 }
64
65 /* add_to_ranges(rs, blockid)
66 * Mark the given blockid as known, updating the stored known ranges
67 * appropriately */
68 void add_to_ranges(struct rcksum_state *rs, zs_blockid x) {
69 int r = range_before_block(rs, x);
70
71 if (r == -1) {
72 /* Already have this block */
73 }
74 else {
75 rs->gotblocks++;
76
77 /* If between two ranges and exactly filling the hole between them,
78 * merge them */
79 if (r > 0 && r < rs->numranges
80 && rs->ranges[2 * (r - 1) + 1] == x - 1
81 && rs->ranges[2 * r] == x + 1) {
82
83 // This block fills the gap between two areas that we have got completely. Merge the adjacent ranges
84 rs->ranges[2 * (r - 1) + 1] = rs->ranges[2 * r + 1];
85 memmove(&rs->ranges[2 * r], &rs->ranges[2 * r + 2],
86 (rs->numranges - r - 1) * sizeof(rs->ranges[0]) * 2);
87 rs->numranges--;
88 }
89
90 /* If adjoining a range below, add to it */
91 else if (r > 0 && rs->numranges && rs->ranges[2 * (r - 1) + 1] == x - 1) {
92 rs->ranges[2 * (r - 1) + 1] = x;
93 }
94
95 /* If adjoining a range above, add to it */
96 else if (r < rs->numranges && rs->ranges[2 * r] == x + 1) {
97 rs->ranges[2 * r] = x;
98 }
99
100 else { /* New range for this block alone */
101 rs->ranges =
102 realloc(rs->ranges,
103 (rs->numranges + 1) * 2 * sizeof(rs->ranges[0]));
104 memmove(&rs->ranges[2 * r + 2], &rs->ranges[2 * r],
105 (rs->numranges - r) * 2 * sizeof(rs->ranges[0]));
106 rs->ranges[2 * r] = rs->ranges[2 * r + 1] = x;
107 rs->numranges++;
108 }
109 }
110 #if 0
111 {
112 int i;
113 for (i = 0; i < rs->numranges; i++)
114 fprintf(stderr, "%d-%d,", rs->ranges[i * 2], rs->ranges[i * 2 + 1]);
115 fprintf(stderr, " are the current ranges got (added %d, %d)\n\n", x, r);
116 }
117 #endif
118 }
119
120 /* already_got_block
121 * Return true iff blockid x of the target file is already known */
122 int already_got_block(struct rcksum_state *rs, zs_blockid x) {
123 return (range_before_block(rs, x) == -1);
124 }
125
126 /* next_blockid = next_known_block(rs, blockid)
127 * Returns the blockid of the next block which we already have data for.
128 * If we know the requested block, it returns the blockid given; otherwise it
129 * will return a later blockid.
130 * If no later blocks are known, it returns rs->numblocks (i.e. the block after
131 * the end of the file).
132 */
133 zs_blockid next_known_block(struct rcksum_state *rs, zs_blockid x) {
134 int r = range_before_block(rs, x);
135 if (r == -1)
136 return x;
137 if (r == rs->numranges) {
138 return rs->blocks;
139 }
140 /* Else return first block of next known range. */
141 return rs->ranges[2*r];
142 }
143
144 /* rcksum_needed_block_ranges
145 * Return the block ranges needed to complete the target file */
146 zs_blockid *rcksum_needed_block_ranges(const struct rcksum_state * rs, int *num,
147 zs_blockid from, zs_blockid to) {
148 int i, n;
149 int alloc_n = 100;
150 zs_blockid *r = malloc(2 * alloc_n * sizeof(zs_blockid));
151
152 if (!r)
153 return NULL;
154
155 if (to >= rs->blocks)
156 to = rs->blocks;
157 r[0] = from;
158 r[1] = to;
159 n = 1;
160 /* Note r[2*n-1] is the last range in our prospective list */
161
162 for (i = 0; i < rs->numranges; i++) {
163 if (rs->ranges[2 * i] > r[2 * n - 1])
164 continue;
165 if (rs->ranges[2 * i + 1] < from)
166 continue;
167
168 /* Okay, they intersect */
169 if (n == 1 && rs->ranges[2 * i] <= from) { /* Overlaps the start of our window */
170 r[0] = rs->ranges[2 * i + 1] + 1;
171 }
172 else {
173 /* If the last block that we still (which is the last window end -1, due
174 * to half-openness) then this range just cuts the end of our window */
175 if (rs->ranges[2 * i + 1] >= r[2 * n - 1] - 1) {
176 r[2 * n - 1] = rs->ranges[2 * i];
177 }
178 else {
179 /* In the middle of our range, split it */
180 r[2 * n] = rs->ranges[2 * i + 1] + 1;
181 r[2 * n + 1] = r[2 * n - 1];
182 r[2 * n - 1] = rs->ranges[2 * i];
183 n++;
184 if (n == alloc_n) {
185 zs_blockid *r2;
186 alloc_n += 100;
187 r2 = realloc(r, 2 * alloc_n * sizeof *r);
188 if (!r2) {
189 free(r);
190 return NULL;
191 }
192 r = r2;
193 }
194 }
195 }
196 }
197 r = realloc(r, 2 * n * sizeof *r);
198 if (n == 1 && r[0] >= r[1])
199 n = 0;
200
201 *num = n;
202 return r;
203 }
204
205 /* rcksum_blocks_todo
206 * Return the number of blocks still needed to complete the target file */
207 int rcksum_blocks_todo(const struct rcksum_state *rs) {
208 int i, n = rs->blocks;
209 for (i = 0; i < rs->numranges; i++) {
210 n -= 1 + rs->ranges[2 * i + 1] - rs->ranges[2 * i];
211 }
212 return n;
213 }