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
src_to_dest_hash(void const * x,size_t table_size)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
src_to_dest_compare(void const * x,void const * y)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
src_to_dest_free(void * x)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
forget_created(ino_t ino,dev_t dev)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 *
src_to_dest_lookup(ino_t ino,dev_t dev)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 *
remember_copied(char const * name,ino_t ino,dev_t dev)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
hash_init(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 }
156