src/cp-hash.c

   1 /* cp-hash.c  -- file copying (hash search routines)
   2    Copyright (C) 1989, 1990, 1991, 1995 Free Software Foundation.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17
  18    Written by Torbjorn Granlund, Sweden (tege@sics.se). */
  19
  20 #include <config.h>
  21 #include <stdio.h>
  22 #include "cp.h"
  23
  24 struct htab *htab;
  25 char new_file;
  26
  27 /* Add PATH to the list of files that we have created.
  28    Return 0 if successful, 1 if not. */
  29
  30 int
  31 remember_created (const char *path)
  32 {
  33   struct stat sb;
  34
  35   if (stat (path, &sb) < 0)
  36     {
  37       error (0, errno, "%s", path);
  38       return 1;
  39     }
  40
  41   hash_insert (sb.st_ino, sb.st_dev, &new_file);
  42   return 0;
  43 }
  44
  45 /* Add path NODE, copied from inode number INO and device number DEV,
  46    to the list of files we have copied.
  47    Return NULL if inserted, otherwise non-NULL. */
  48
  49 char *
  50 remember_copied (const char *node, ino_t ino, dev_t dev)
  51 {
  52   return hash_insert (ino, dev, node);
  53 }
  54
  55 /* Allocate space for the hash structures, and set the global
  56    variable `htab' to point to it.  The initial hash module is specified in
  57    MODULUS, and the number of entries are specified in ENTRY_TAB_SIZE.  (The
  58    hash structure will be rebuilt when ENTRY_TAB_SIZE entries have been
  59    inserted, and MODULUS and ENTRY_TAB_SIZE in the global `htab' will be
  60    doubled.)  */
  61
  62 void
  63 hash_init (unsigned int modulus, unsigned int entry_tab_size)
  64 {
  65   struct htab *htab_r;
  66
  67   htab_r = (struct htab *)
  68     xmalloc (sizeof (struct htab) + sizeof (struct entry *) * modulus);
  69
  70   htab_r->entry_tab = (struct entry *)
  71     xmalloc (sizeof (struct entry) * entry_tab_size);
  72
  73   htab_r->modulus = modulus;
  74   htab_r->entry_tab_size = entry_tab_size;
  75   htab = htab_r;
  76
  77   forget_all ();
  78 }
  79
  80 /* Reset the hash structure in the global variable `htab' to
  81    contain no entries.  */
  82
  83 void
  84 forget_all (void)
  85 {
  86   int i;
  87   struct entry **p;
  88
  89   htab->first_free_entry = 0;
  90
  91   p = htab->hash;
  92   for (i = htab->modulus; i > 0; i--)
  93     *p++ = NULL;
  94 }
  95 \f
  96 /* Insert path NODE, copied from inode number INO and device number DEV,
  97    into the hash structure in the global variable `htab', if an entry with
  98    the same inode and device was not found already.
  99    Return NULL if inserted, otherwise non-NULL. */
 100
 101 char *
 102 hash_insert (ino_t ino, dev_t dev, const char *node)
 103 {
 104   struct htab *htab_r = htab;
 105
 106   if (htab_r->first_free_entry >= htab_r->entry_tab_size)
 107     {
 108       int i;
 109       struct entry *ep;
 110       unsigned modulus;
 111       unsigned entry_tab_size;
 112
 113       /* Increase the number of hash entries, and re-hash the data.
 114          The method of shrinking and increasing is made to compactify
 115          the heap.  If twice as much data would be allocated
 116          straightforwardly, we would never re-use a byte of memory.  */
 117
 118       /* Let htab shrink.  Keep only the header, not the pointer vector.  */
 119
 120       htab_r = (struct htab *)
 121         xrealloc ((char *) htab_r, sizeof (struct htab));
 122
 123       modulus = 2 * htab_r->modulus;
 124       entry_tab_size = 2 * htab_r->entry_tab_size;
 125
 126       /* Increase the number of possible entries.  */
 127
 128       htab_r->entry_tab = (struct entry *)
 129         xrealloc ((char *) htab_r->entry_tab,
 130                   sizeof (struct entry) * entry_tab_size);
 131
 132       /* Increase the size of htab again.  */
 133
 134       htab_r = (struct htab *)
 135         xrealloc ((char *) htab_r,
 136                   sizeof (struct htab) + sizeof (struct entry *) * modulus);
 137
 138       htab_r->modulus = modulus;
 139       htab_r->entry_tab_size = entry_tab_size;
 140       htab = htab_r;
 141
 142       i = htab_r->first_free_entry;
 143
 144       /* Make the increased hash table empty.  The entries are still
 145          available in htab->entry_tab.  */
 146
 147       forget_all ();
 148
 149       /* Go through the entries and install them in the pointer vector
 150          htab->hash.  The items are actually inserted in htab->entry_tab at
 151          the position where they already are.  The htab->coll_link need
 152          however be updated.  Could be made a little more efficient.  */
 153
 154       for (ep = htab_r->entry_tab; i > 0; i--)
 155         {
 156           hash_insert2 (htab_r, ep->ino, ep->dev, ep->node);
 157           ep++;
 158         }
 159     }
 160
 161   return hash_insert2 (htab_r, ino, dev, node);
 162 }
 163
 164 /* Insert path NODE, copied from inode number INO and device number DEV,
 165    into the hash structure HTAB, if not already present.
 166    Return NULL if inserted, otherwise non-NULL. */
 167
 168 char *
 169 hash_insert2 (struct htab *htab, ino_t ino, dev_t dev, const char *node)
 170 {
 171   struct entry **hp, *ep2, *ep;
 172   hp = &htab->hash[ino % htab->modulus];
 173   ep2 = *hp;
 174
 175   /* Collision?  */
 176
 177   if (ep2 != NULL)
 178     {
 179       ep = ep2;
 180
 181       /* Search for an entry with the same data.  */
 182
 183       do
 184         {
 185           if (ep->ino == ino && ep->dev == dev)
 186             return ep->node;    /* Found an entry with the same data.  */
 187           ep = ep->coll_link;
 188         }
 189       while (ep != NULL);
 190
 191       /* Did not find it.  */
 192
 193     }
 194
 195   ep = *hp = &htab->entry_tab[htab->first_free_entry++];
 196   ep->ino = ino;
 197   ep->dev = dev;
 198   ep->node = (char *) node;
 199   ep->coll_link = ep2;          /* ep2 is NULL if not collision.  */
 200
 201   return NULL;
 202 }