src/cp-hash.c

   1 /* cp-hash.c  -- file copying (hash search routines)
   2    Copyright (C) 1989-2023 Free Software Foundation, Inc.
   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 3 of the License, or
   7    (at your option) 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, see <https://www.gnu.org/licenses/>.
  16
  17    Written by Torbjörn Granlund, Sweden (tege@sics.se).
  18    Rewritten to use lib/hash.c by Jim Meyering.  */
  19
  20 #include <config.h>
  21
  22 #include <sys/types.h>
  23 #include "system.h"
  24
  25 #include "hash.h"
  26 #include "cp-hash.h"
  27
  28 /* Use ST_DEV and ST_INO as the key, FILENAME as the value.
  29    These are used e.g., in copy.c to associate the destination name with
  30    the source device/inode pair so that if we encounter a matching dev/ino
  31    pair in the source tree we can arrange to create a hard link between
  32    the corresponding names in the destination tree.  */
  33 struct Src_to_dest
  34 {
  35   ino_t st_ino;
  36   dev_t st_dev;
  37   /* Destination file name (of non-directory or pre-existing directory)
  38      corresponding to the dev/ino of a copied file, or the destination file
  39      name corresponding to a dev/ino pair for a newly-created directory. */
  40   char *name;
  41 };
  42
  43 /* This table maps source dev/ino to destination file name.
  44    We use it to preserve hard links when copying.  */
  45 static Hash_table *src_to_dest;
  46
  47 /* Initial size of the above hash table.  */
  48 #define INITIAL_TABLE_SIZE 103
  49
  50 static size_t
  51 src_to_dest_hash (void const *x, size_t table_size)
  52 {
  53   struct Src_to_dest const *p = x;
  54
  55   /* Ignoring the device number here should be fine.  */
  56   /* The cast to uintmax_t prevents negative remainders
  57      if st_ino is negative.  */
  58   return (uintmax_t) p->st_ino % table_size;
  59 }
  60
  61 /* Compare two Src_to_dest entries.
  62    Return true if their keys are judged 'equal'.  */
  63 static bool
  64 src_to_dest_compare (void const *x, void const *y)
  65 {
  66   struct Src_to_dest const *a = x;
  67   struct Src_to_dest const *b = y;
  68   return PSAME_INODE (a, b);
  69 }
  70
  71 static void
  72 src_to_dest_free (void *x)
  73 {
  74   struct Src_to_dest *a = x;
  75   free (a->name);
  76   free (x);
  77 }
  78
  79 /* Remove the entry matching INO/DEV from the table
  80    that maps source ino/dev to destination file name.  */
  81 extern void
  82 forget_created (ino_t ino, dev_t dev)
  83 {
  84   struct Src_to_dest probe;
  85   struct Src_to_dest *ent;
  86
  87   probe.st_ino = ino;
  88   probe.st_dev = dev;
  89   probe.name = nullptr;
  90
  91   ent = hash_remove (src_to_dest, &probe);
  92   if (ent)
  93     src_to_dest_free (ent);
  94 }
  95
  96 /* If INO/DEV correspond to an already-copied source file, return the
  97    name of the corresponding destination file.  Otherwise, return nullptr.  */
  98
  99 extern char *
 100 src_to_dest_lookup (ino_t ino, dev_t dev)
 101 {
 102   struct Src_to_dest ent;
 103   struct Src_to_dest const *e;
 104   ent.st_ino = ino;
 105   ent.st_dev = dev;
 106   e = hash_lookup (src_to_dest, &ent);
 107   return e ? e->name : nullptr;
 108 }
 109
 110 /* Add file NAME, copied from inode number INO and device number DEV,
 111    to the list of files we have copied.
 112    Return nullptr if inserted, otherwise a non-null pointer. */
 113
 114 extern char *
 115 remember_copied (char const *name, ino_t ino, dev_t dev)
 116 {
 117   struct Src_to_dest *ent;
 118   struct Src_to_dest *ent_from_table;
 119
 120   ent = xmalloc (sizeof *ent);
 121   ent->name = xstrdup (name);
 122   ent->st_ino = ino;
 123   ent->st_dev = dev;
 124
 125   ent_from_table = hash_insert (src_to_dest, ent);
 126   if (ent_from_table == nullptr)
 127     {
 128       /* Insertion failed due to lack of memory.  */
 129       xalloc_die ();
 130     }
 131
 132   /* Determine whether there was already an entry in the table
 133      with a matching key.  If so, free ENT (it wasn't inserted) and
 134      return the 'name' from the table entry.  */
 135   if (ent_from_table != ent)
 136     {
 137       src_to_dest_free (ent);
 138       return (char *) ent_from_table->name;
 139     }
 140
 141   /* New key;  insertion succeeded.  */
 142   return nullptr;
 143 }
 144
 145 /* Initialize the hash table.  */
 146 extern void
 147 hash_init (void)
 148 {
 149   src_to_dest = hash_initialize (INITIAL_TABLE_SIZE, nullptr,
 150                                  src_to_dest_hash,
 151                                  src_to_dest_compare,
 152                                  src_to_dest_free);
 153   if (src_to_dest == nullptr)
 154     xalloc_die ();
 155 }