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