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 char *hash_insert ();
  25 char *hash_insert2 ();
  26
  27 struct htab *htab;
  28 char new_file;
  29
  30 /* Add PATH to the list of files that we have created.
  31    Return 0 if successful, 1 if not. */
  32
  33 int
  34 remember_created (path)
  35      char *path;
  36 {
  37   struct stat sb;
  38
  39   if (stat (path, &sb) < 0)
  40     {
  41       error (0, errno, "%s", path);
  42       return 1;
  43     }
  44
  45   hash_insert (sb.st_ino, sb.st_dev, &new_file);
  46   return 0;
  47 }
  48
  49 /* Add path NODE, copied from inode number INO and device number DEV,
  50    to the list of files we have copied.
  51    Return NULL if inserted, otherwise non-NULL. */
  52
  53 char *
  54 remember_copied (node, ino, dev)
  55      char *node;
  56      ino_t ino;
  57      dev_t dev;
  58 {
  59   return hash_insert (ino, dev, node);
  60 }
  61
  62 /* Allocate space for the hash structures, and set the global
  63    variable `htab' to point to it.  The initial hash module is specified in
  64    MODULUS, and the number of entries are specified in ENTRY_TAB_SIZE.  (The
  65    hash structure will be rebuilt when ENTRY_TAB_SIZE entries have been
  66    inserted, and MODULUS and ENTRY_TAB_SIZE in the global `htab' will be
  67    doubled.)  */
  68
  69 void
  70 hash_init (modulus, entry_tab_size)
  71      unsigned modulus;
  72      unsigned entry_tab_size;
  73 {
  74   struct htab *htab_r;
  75
  76   htab_r = (struct htab *)
  77     xmalloc (sizeof (struct htab) + sizeof (struct entry *) * modulus);
  78
  79   htab_r->entry_tab = (struct entry *)
  80     xmalloc (sizeof (struct entry) * entry_tab_size);
  81
  82   htab_r->modulus = modulus;
  83   htab_r->entry_tab_size = entry_tab_size;
  84   htab = htab_r;
  85
  86   forget_all ();
  87 }
  88
  89 /* Reset the hash structure in the global variable `htab' to
  90    contain no entries.  */
  91
  92 void
  93 forget_all ()
  94 {
  95   int i;
  96   struct entry **p;
  97
  98   htab->first_free_entry = 0;
  99
 100   p = htab->hash;
 101   for (i = htab->modulus; i > 0; i--)
 102     *p++ = NULL;
 103 }
 104 \f
 105 /* Insert path NODE, copied from inode number INO and device number DEV,
 106    into the hash structure in the global variable `htab', if an entry with
 107    the same inode and device was not found already.
 108    Return NULL if inserted, otherwise non-NULL. */
 109
 110 char *
 111 hash_insert (ino, dev, node)
 112      ino_t ino;
 113      dev_t dev;
 114      char *node;
 115 {
 116   struct htab *htab_r = htab;
 117
 118   if (htab_r->first_free_entry >= htab_r->entry_tab_size)
 119     {
 120       int i;
 121       struct entry *ep;
 122       unsigned modulus;
 123       unsigned entry_tab_size;
 124
 125       /* Increase the number of hash entries, and re-hash the data.
 126          The method of shrinking and increasing is made to compactify
 127          the heap.  If twice as much data would be allocated
 128          straightforwardly, we would never re-use a byte of memory.  */
 129
 130       /* Let htab shrink.  Keep only the header, not the pointer vector.  */
 131
 132       htab_r = (struct htab *)
 133         xrealloc ((char *) htab_r, sizeof (struct htab));
 134
 135       modulus = 2 * htab_r->modulus;
 136       entry_tab_size = 2 * htab_r->entry_tab_size;
 137
 138       /* Increase the number of possible entries.  */
 139
 140       htab_r->entry_tab = (struct entry *)
 141         xrealloc ((char *) htab_r->entry_tab,
 142                   sizeof (struct entry) * entry_tab_size);
 143
 144       /* Increase the size of htab again.  */
 145
 146       htab_r = (struct htab *)
 147         xrealloc ((char *) htab_r,
 148                   sizeof (struct htab) + sizeof (struct entry *) * modulus);
 149
 150       htab_r->modulus = modulus;
 151       htab_r->entry_tab_size = entry_tab_size;
 152       htab = htab_r;
 153
 154       i = htab_r->first_free_entry;
 155
 156       /* Make the increased hash table empty.  The entries are still
 157          available in htab->entry_tab.  */
 158
 159       forget_all ();
 160
 161       /* Go through the entries and install them in the pointer vector
 162          htab->hash.  The items are actually inserted in htab->entry_tab at
 163          the position where they already are.  The htab->coll_link need
 164          however be updated.  Could be made a little more efficient.  */
 165
 166       for (ep = htab_r->entry_tab; i > 0; i--)
 167         {
 168           hash_insert2 (htab_r, ep->ino, ep->dev, ep->node);
 169           ep++;
 170         }
 171     }
 172
 173   return hash_insert2 (htab_r, ino, dev, node);
 174 }
 175
 176 /* Insert path NODE, copied from inode number INO and device number DEV,
 177    into the hash structure HTAB, if not already present.
 178    Return NULL if inserted, otherwise non-NULL. */
 179
 180 char *
 181 hash_insert2 (htab, ino, dev, node)
 182      struct htab *htab;
 183      ino_t ino;
 184      dev_t dev;
 185      char *node;
 186 {
 187   struct entry **hp, *ep2, *ep;
 188   hp = &htab->hash[ino % htab->modulus];
 189   ep2 = *hp;
 190
 191   /* Collision?  */
 192
 193   if (ep2 != NULL)
 194     {
 195       ep = ep2;
 196
 197       /* Search for an entry with the same data.  */
 198
 199       do
 200         {
 201           if (ep->ino == ino && ep->dev == dev)
 202             return ep->node;    /* Found an entry with the same data.  */
 203           ep = ep->coll_link;
 204         }
 205       while (ep != NULL);
 206
 207       /* Did not find it.  */
 208
 209     }
 210
 211   ep = *hp = &htab->entry_tab[htab->first_free_entry++];
 212   ep->ino = ino;
 213   ep->dev = dev;
 214   ep->node = node;
 215   ep->coll_link = ep2;          /* ep2 is NULL if not collision.  */
 216
 217   return NULL;
 218 }