src/cp-hash.c

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