source: trunk/src/allmydata/util/spans.py

Last change on this file was 1cfe843d, checked in by Alexandre Detiste <alexandre.detiste@…>, at 2024-02-22T23:40:25Z

more python2 removal

  • Property mode set to 100644
File size: 17.4 KB
Line 
1
2
3class Spans(object):
4    """I represent a compressed list of booleans, one per index (an integer).
5    Typically, each index represents an offset into a large string, pointing
6    to a specific byte of a share. In this context, True means that byte has
7    been received, or has been requested.
8
9    Another way to look at this is maintaining a set of integers, optimized
10    for operations on spans like 'add range to set' and 'is range in set?'.
11
12    This is a python equivalent of perl's Set::IntSpan module, frequently
13    used to represent .newsrc contents.
14
15    Rather than storing an actual (large) list or dictionary, I represent my
16    internal state as a sorted list of spans, each with a start and a length.
17    My API is presented in terms of start+length pairs. I provide set
18    arithmetic operators, to efficiently answer questions like 'I want bytes
19    XYZ, I already requested bytes ABC, and I've already received bytes DEF:
20    what bytes should I request now?'.
21
22    The new downloader will use it to keep track of which bytes we've requested
23    or received already.
24    """
25
26    def __init__(self, _span_or_start=None, length=None):
27        self._spans = list()
28        if length is not None:
29            self._spans.append( (_span_or_start, length) )
30        elif _span_or_start:
31            for (start,length) in _span_or_start:
32                self.add(start, length)
33        self._check()
34
35    def _check(self):
36        assert sorted(self._spans) == self._spans
37        prev_end = None
38        try:
39            for (start,length) in self._spans:
40                if prev_end is not None:
41                    assert start > prev_end
42                prev_end = start+length
43        except AssertionError:
44            print("BAD:", self.dump())
45            raise
46
47    def add(self, start, length):
48        assert start >= 0
49        assert length > 0
50        #print(" ADD [%d+%d -%d) to %s" % (start, length, start+length, self.dump()))
51        first_overlap = last_overlap = None
52        for i,(s_start,s_length) in enumerate(self._spans):
53            #print("  (%d+%d)-> overlap=%s adjacent=%s" % (s_start,s_length, overlap(s_start, s_length, start, length), adjacent(s_start, s_length, start, length)))
54            if (overlap(s_start, s_length, start, length)
55                or adjacent(s_start, s_length, start, length)):
56                last_overlap = i
57                if first_overlap is None:
58                    first_overlap = i
59                continue
60            # no overlap
61            if first_overlap is not None:
62                break
63        #print("  first_overlap", first_overlap, last_overlap)
64        if first_overlap is None:
65            # no overlap, so just insert the span and sort by starting
66            # position.
67            self._spans.insert(0, (start,length))
68            self._spans.sort()
69        else:
70            # everything from [first_overlap] to [last_overlap] overlapped
71            first_start,first_length = self._spans[first_overlap]
72            last_start,last_length = self._spans[last_overlap]
73            newspan_start = min(start, first_start)
74            newspan_end = max(start+length, last_start+last_length)
75            newspan_length = newspan_end - newspan_start
76            newspan = (newspan_start, newspan_length)
77            self._spans[first_overlap:last_overlap+1] = [newspan]
78        #print("  ADD done: %s" % self.dump())
79        self._check()
80
81        return self
82
83    def remove(self, start, length):
84        assert start >= 0
85        assert length > 0
86        #print(" REMOVE [%d+%d -%d) from %s" % (start, length, start+length, self.dump()))
87        first_complete_overlap = last_complete_overlap = None
88        for i,(s_start,s_length) in enumerate(self._spans):
89            s_end = s_start + s_length
90            o = overlap(s_start, s_length, start, length)
91            if o:
92                o_start, o_length = o
93                o_end = o_start+o_length
94                if o_start == s_start and o_end == s_end:
95                    # delete this span altogether
96                    if first_complete_overlap is None:
97                        first_complete_overlap = i
98                    last_complete_overlap = i
99                elif o_start == s_start:
100                    # we only overlap the left side, so trim the start
101                    #    1111
102                    #  rrrr
103                    #    oo
104                    # ->   11
105                    new_start = o_end
106                    new_end = s_end
107                    assert new_start > s_start
108                    new_length = new_end - new_start
109                    self._spans[i] = (new_start, new_length)
110                elif o_end == s_end:
111                    # we only overlap the right side
112                    #    1111
113                    #      rrrr
114                    #      oo
115                    # -> 11
116                    new_start = s_start
117                    new_end = o_start
118                    assert new_end < s_end
119                    new_length = new_end - new_start
120                    self._spans[i] = (new_start, new_length)
121                else:
122                    # we overlap the middle, so create a new span. No need to
123                    # examine any other spans.
124                    #    111111
125                    #      rr
126                    #    LL  RR
127                    left_start = s_start
128                    left_end = o_start
129                    left_length = left_end - left_start
130                    right_start = o_end
131                    right_end = s_end
132                    right_length = right_end - right_start
133                    self._spans[i] = (left_start, left_length)
134                    self._spans.append( (right_start, right_length) )
135                    self._spans.sort()
136                    break
137        if first_complete_overlap is not None:
138            del self._spans[first_complete_overlap:last_complete_overlap+1]
139        #print("  REMOVE done: %s" % self.dump())
140        self._check()
141        return self
142
143    def dump(self):
144        return "len=%d: %s" % (self.len(),
145                               ",".join(["[%d-%d]" % (start,start+l-1)
146                                         for (start,l) in self._spans]) )
147
148    def each(self):
149        for start, length in self._spans:
150            for i in range(start, start+length):
151                yield i
152
153    def __iter__(self):
154        for s in self._spans:
155            yield s
156
157    def __bool__(self): # this gets us bool()
158        return bool(self.len())
159
160    #__nonzero__ = __bool__  # Python 2 backwards compatibility
161
162    def len(self):
163        # guess what! python doesn't allow __len__ to return a long, only an
164        # int. So we stop using len(spans), use spans.len() instead.
165        return sum([length for start,length in self._spans])
166
167    def __add__(self, other):
168        s = self.__class__(self)
169        for (start, length) in other:
170            s.add(start, length)
171        return s
172
173    def __sub__(self, other):
174        s = self.__class__(self)
175        for (start, length) in other:
176            s.remove(start, length)
177        return s
178
179    def __iadd__(self, other):
180        for (start, length) in other:
181            self.add(start, length)
182        return self
183
184    def __isub__(self, other):
185        for (start, length) in other:
186            self.remove(start, length)
187        return self
188
189    def __and__(self, other):
190        if not self._spans:
191            return self.__class__()
192        bounds = self.__class__(self._spans[0][0],
193                                self._spans[-1][0]+self._spans[-1][1])
194        not_other = bounds - other
195        return self - not_other
196
197    def __contains__(self, start_and_length):
198        (start, length) = start_and_length
199        for span_start,span_length in self._spans:
200            o = overlap(start, length, span_start, span_length)
201            if o:
202                o_start,o_length = o
203                if o_start == start and o_length == length:
204                    return True
205        return False
206
207def overlap(start0, length0, start1, length1):
208    # return start2,length2 of the overlapping region, or None
209    #  00      00   000   0000  00  00 000  00   00  00      00
210    #     11    11   11    11   111 11 11  1111 111 11    11
211    left = max(start0, start1)
212    right = min(start0+length0, start1+length1)
213    # if there is overlap, 'left' will be its start, and right-1 will
214    # be the end'
215    if left < right:
216        return (left, right-left)
217    return None
218
219def adjacent(start0, length0, start1, length1):
220    if (start0 < start1) and start0+length0 == start1:
221        return True
222    elif (start1 < start0) and start1+length1 == start0:
223        return True
224    return False
225
226class DataSpans(object):
227    """I represent portions of a large string. Equivalently, I can be said to
228    maintain a large array of characters (with gaps of empty elements). I can
229    be used to manage access to a remote share, where some pieces have been
230    retrieved, some have been requested, and others have not been read.
231    """
232
233    def __init__(self, other=None):
234        self.spans = [] # (start, data) tuples, non-overlapping, merged
235        if other:
236            for (start, data) in other.get_chunks():
237                self.add(start, data)
238
239    def __bool__(self): # this gets us bool()
240        return bool(self.len())
241
242    def len(self):
243        # return number of bytes we're holding
244        return sum([len(data) for (start,data) in self.spans])
245
246    def _dump(self):
247        # return iterator of sorted list of offsets, one per byte
248        for (start,data) in self.spans:
249            for i in range(start, start+len(data)):
250                yield i
251
252    def dump(self):
253        return "len=%d: %s" % (self.len(),
254                               ",".join(["[%d-%d]" % (start,start+len(data)-1)
255                                         for (start,data) in self.spans]) )
256
257    def get_chunks(self):
258        return list(self.spans)
259
260    def get_spans(self):
261        """Return a Spans object with a bit set for each byte I hold"""
262        return Spans([(start, len(data)) for (start,data) in self.spans])
263
264    def assert_invariants(self):
265        if not self.spans:
266            return
267        prev_start = self.spans[0][0]
268        prev_end = prev_start + len(self.spans[0][1])
269        for start, data in self.spans[1:]:
270            if not start > prev_end:
271                # adjacent or overlapping: bad
272                print("ASSERTION FAILED", self.spans)
273                raise AssertionError
274
275    def get(self, start, length):
276        # returns a string of LENGTH, or None
277        #print("get", start, length, self.spans)
278        end = start+length
279        for (s_start,s_data) in self.spans:
280            s_end = s_start+len(s_data)
281            #print(" ",s_start,s_end)
282            if s_start <= start < s_end:
283                # we want some data from this span. Because we maintain
284                # strictly merged and non-overlapping spans, everything we
285                # want must be in this span.
286                offset = start - s_start
287                if offset + length > len(s_data):
288                    #print(" None, span falls short")
289                    return None # span falls short
290                #print(" some", s_data[offset:offset+length])
291                return s_data[offset:offset+length]
292            if s_start >= end:
293                # we've gone too far: no further spans will overlap
294                #print(" None, gone too far")
295                return None
296        #print(" None, ran out of spans")
297        return None
298
299    def add(self, start, data):
300        # first: walk through existing spans, find overlap, modify-in-place
301        #  create list of new spans
302        #  add new spans
303        #  sort
304        #  merge adjacent spans
305        #print("add", start, data, self.spans)
306        end = start + len(data)
307        i = 0
308        while len(data):
309            #print(" loop", start, data, i, len(self.spans), self.spans)
310            if i >= len(self.spans):
311                #print(" append and done")
312                # append a last span
313                self.spans.append( (start, data) )
314                break
315            (s_start,s_data) = self.spans[i]
316            # five basic cases:
317            #  a: OLD  b:OLDD  c1:OLD  c2:OLD   d1:OLDD  d2:OLD  e: OLLDD
318            #    NEW     NEW      NEW     NEWW      NEW      NEW     NEW
319            #
320            # we handle A by inserting a new segment (with "N") and looping,
321            # turning it into B or C. We handle B by replacing a prefix and
322            # terminating. We handle C (both c1 and c2) by replacing the
323            # segment (and, for c2, looping, turning it into A). We handle D
324            # by replacing a suffix (and, for d2, looping, turning it into
325            # A). We handle E by replacing the middle and terminating.
326            if start < s_start:
327                # case A: insert a new span, then loop with the remainder
328                #print(" insert new span")
329                s_len = s_start-start
330                self.spans.insert(i, (start, data[:s_len]))
331                i += 1
332                start = s_start
333                data = data[s_len:]
334                continue
335            s_len = len(s_data)
336            s_end = s_start+s_len
337            if s_start <= start < s_end:
338                #print(" modify this span", s_start, start, s_end)
339                # we want to modify some data in this span: a prefix, a
340                # suffix, or the whole thing
341                if s_start == start:
342                    if s_end <= end:
343                        #print(" replace whole segment")
344                        # case C: replace this segment
345                        self.spans[i] = (s_start, data[:s_len])
346                        i += 1
347                        start += s_len
348                        data = data[s_len:]
349                        # C2 is where len(data)>0
350                        continue
351                    # case B: modify the prefix, retain the suffix
352                    #print(" modify prefix")
353                    self.spans[i] = (s_start, data + s_data[len(data):])
354                    break
355                if start > s_start and end < s_end:
356                    # case E: modify the middle
357                    #print(" modify middle")
358                    prefix_len = start - s_start # we retain this much
359                    suffix_len = s_end - end # and retain this much
360                    newdata = s_data[:prefix_len] + data + s_data[-suffix_len:]
361                    self.spans[i] = (s_start, newdata)
362                    break
363                # case D: retain the prefix, modify the suffix
364                #print(" modify suffix")
365                prefix_len = start - s_start # we retain this much
366                suffix_len = s_len - prefix_len # we replace this much
367                #print("  ", s_data, prefix_len, suffix_len, s_len, data)
368                self.spans[i] = (s_start,
369                                 s_data[:prefix_len] + data[:suffix_len])
370                i += 1
371                start += suffix_len
372                data = data[suffix_len:]
373                #print("  now", start, data)
374                # D2 is where len(data)>0
375                continue
376            # else we're not there yet
377            #print(" still looking")
378            i += 1
379            continue
380        # now merge adjacent spans
381        #print(" merging", self.spans)
382        newspans = []
383        for (s_start,s_data) in self.spans:
384            if newspans and adjacent(newspans[-1][0], len(newspans[-1][1]),
385                                     s_start, len(s_data)):
386                newspans[-1] = (newspans[-1][0], newspans[-1][1] + s_data)
387            else:
388                newspans.append( (s_start, s_data) )
389        self.spans = newspans
390        self.assert_invariants()
391        #print(" done", self.spans)
392
393    def remove(self, start, length):
394        i = 0
395        end = start + length
396        #print("remove", start, length, self.spans)
397        while i < len(self.spans):
398            (s_start,s_data) = self.spans[i]
399            if s_start >= end:
400                # this segment is entirely right of the removed region, and
401                # all further segments are even further right. We're done.
402                break
403            s_len = len(s_data)
404            s_end = s_start + s_len
405            o = overlap(start, length, s_start, s_len)
406            if not o:
407                i += 1
408                continue
409            o_start, o_len = o
410            o_end = o_start + o_len
411            if o_len == s_len:
412                # remove the whole segment
413                del self.spans[i]
414                continue
415            if o_start == s_start:
416                # remove a prefix, leaving the suffix from o_end to s_end
417                prefix_len = o_end - o_start
418                self.spans[i] = (o_end, s_data[prefix_len:])
419                i += 1
420                continue
421            elif o_end == s_end:
422                # remove a suffix, leaving the prefix from s_start to o_start
423                prefix_len = o_start - s_start
424                self.spans[i] = (s_start, s_data[:prefix_len])
425                i += 1
426                continue
427            # remove the middle, creating a new segment
428            # left is s_start:o_start, right is o_end:s_end
429            left_len = o_start - s_start
430            left = s_data[:left_len]
431            right_len = s_end - o_end
432            right = s_data[-right_len:]
433            self.spans[i] = (s_start, left)
434            self.spans.insert(i+1, (o_end, right))
435            break
436        #print(" done", self.spans)
437
438    def pop(self, start, length):
439        data = self.get(start, length)
440        if data:
441            self.remove(start, length)
442        return data
Note: See TracBrowser for help on using the repository browser.