"Fossies" - the Fresh Open Source Software Archive

Member "zsync-0.6.2/librcksum/hash.c" (16 Sep 2010, 4147 Bytes) of package /linux/privat/old/zsync-0.6.2.tar.gz:

    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 /* Functions to manage the rsum and checksum values per block and set up the
   19  * hash tables of the rsum values. */
   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 /* rcksum_add_target_block(self, blockid, rsum, checksum)
   35  * Sets the stored hash values for the given blockid to the given values.
   36  */
   37 void rcksum_add_target_block(struct rcksum_state *z, zs_blockid b,
   38                              struct rsum r, void *checksum) {
   39     if (b < z->blocks) {
   40         /* Get hash entry with checksums for this block */
   41         struct hash_entry *e = &(z->blockhashes[b]);
   42 
   43         /* Enter checksums */
   44         memcpy(e->checksum, checksum, z->checksum_bytes);
   45         e->r.a = r.a & z->rsum_a_mask;
   46         e->r.b = r.b;
   47 
   48         /* New checksums invalidate any existing checksum hash tables */
   49         if (z->rsum_hash) {
   50             free(z->rsum_hash);
   51             z->rsum_hash = NULL;
   52             free(z->bithash);
   53             z->bithash = NULL;
   54         }
   55     }
   56 }
   57 
   58 /* build_hash(self)
   59  * Build hash tables to quickly lookup a block based on its rsum value.
   60  * Returns non-zero if successful.
   61  */
   62 int build_hash(struct rcksum_state *z) {
   63     zs_blockid id;
   64     int i = 16;
   65 
   66     /* Try hash size of 2^i; step down the value of i until we find a good size
   67      */
   68     while ((2 << (i - 1)) > z->blocks && i > 4)
   69         i--;
   70 
   71     /* Allocate hash based on rsum */
   72     z->hashmask = (2 << i) - 1;
   73     z->rsum_hash = calloc(z->hashmask + 1, sizeof *(z->rsum_hash));
   74     if (!z->rsum_hash)
   75         return 0;
   76 
   77     /* Allocate bit-table based on rsum */
   78     z->bithashmask = (2 << (i + BITHASHBITS)) - 1;
   79     z->bithash = calloc(z->bithashmask + 1, 1);
   80     if (!z->bithash) {
   81         free(z->rsum_hash);
   82         z->rsum_hash = NULL;
   83         return 0;
   84     }
   85 
   86     /* Now fill in the hash tables.
   87      * Minor point: We do this in reverse order, because we're adding entries
   88      * to the hash chains by prepending, so if we iterate over the data in
   89      * reverse then the resulting hash chains have the blocks in normal order.
   90      * That's improves our pattern of I/O when writing out identical blocks
   91      * once we are processing data; we will write them in order. */
   92     for (id = z->blocks; id > 0;) {
   93         /* Decrement the loop variable here, and get the hash entry. */
   94         struct hash_entry *e = z->blockhashes + (--id);
   95 
   96         /* Prepend to linked list for this hash entry */
   97         unsigned h = calc_rhash(z, e);
   98         e->next = z->rsum_hash[h & z->hashmask];
   99         z->rsum_hash[h & z->hashmask] = e;
  100 
  101         /* And set relevant bit in the bithash to 1 */
  102         z->bithash[(h & z->bithashmask) >> 3] |= 1 << (h & 7);
  103     }
  104     return 1;
  105 }
  106 
  107 /* remove_block_from_hash(self, block_id)
  108  * Remove the given data block from the rsum hash table, so it won't be
  109  * returned in a hash lookup again (e.g. because we now have the data)
  110  */
  111 void remove_block_from_hash(struct rcksum_state *z, zs_blockid id) {
  112     struct hash_entry *t = &(z->blockhashes[id]);
  113 
  114     struct hash_entry **p = &(z->rsum_hash[calc_rhash(z, t) & z->hashmask]);
  115 
  116     while (*p != NULL) {
  117         if (*p == t) {
  118             if (t == z->rover) {
  119                 z->rover = t->next;
  120             }
  121             *p = (*p)->next;
  122             return;
  123         }
  124         else {
  125             p = &((*p)->next);
  126         }
  127     }
  128 }
  129