src/cp-hash.c

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