"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 }