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


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 "hash.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 /* 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