Import libarchive-2.4.8:
[dragonfly.git] / contrib / libarchive-2 / libarchive / archive_entry_link_resolver.c
CommitLineData
a44e961d
PA
1/*-
2 * Copyright (c) 2003-2007 Tim Kientzle
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "archive_platform.h"
27__FBSDID("$FreeBSD$");
28
29#ifdef HAVE_SYS_STAT_H
30#include <sys/stat.h>
31#endif
32#ifdef HAVE_ERRNO_H
33#include <errno.h>
34#endif
35#include <stdio.h>
36#ifdef HAVE_STDLIB_H
37#include <stdlib.h>
38#endif
39#ifdef HAVE_STRING_H
40#include <string.h>
41#endif
42
43#include "archive_entry.h"
44
45/* Initial size of link cache. */
46#define links_cache_initial_size 1024
47
48struct archive_entry_linkresolver {
49 char *last_name;
50 unsigned long number_entries;
51 size_t number_buckets;
52 struct links_entry **buckets;
53};
54
55struct links_entry {
56 struct links_entry *next;
57 struct links_entry *previous;
58 int links;
59 dev_t dev;
60 ino_t ino;
61 char *name;
62};
63
64struct archive_entry_linkresolver *
65archive_entry_linkresolver_new(void)
66{
67 struct archive_entry_linkresolver *links_cache;
68 size_t i;
69
70 links_cache = malloc(sizeof(struct archive_entry_linkresolver));
71 if (links_cache == NULL)
72 return (NULL);
73 memset(links_cache, 0, sizeof(struct archive_entry_linkresolver));
74 links_cache->number_buckets = links_cache_initial_size;
75 links_cache->buckets = malloc(links_cache->number_buckets *
76 sizeof(links_cache->buckets[0]));
77 if (links_cache->buckets == NULL) {
78 free(links_cache);
79 return (NULL);
80 }
81 for (i = 0; i < links_cache->number_buckets; i++)
82 links_cache->buckets[i] = NULL;
83 return (links_cache);
84}
85
86void
87archive_entry_linkresolver_free(struct archive_entry_linkresolver *links_cache)
88{
89 size_t i;
90
91 if (links_cache->buckets == NULL)
92 return;
93
94 for (i = 0; i < links_cache->number_buckets; i++) {
95 while (links_cache->buckets[i] != NULL) {
96 struct links_entry *lp = links_cache->buckets[i]->next;
97 if (links_cache->buckets[i]->name != NULL)
98 free(links_cache->buckets[i]->name);
99 free(links_cache->buckets[i]);
100 links_cache->buckets[i] = lp;
101 }
102 }
103 free(links_cache->buckets);
104 links_cache->buckets = NULL;
105}
106
107const char *
108archive_entry_linkresolve(struct archive_entry_linkresolver *links_cache,
109 struct archive_entry *entry)
110{
111 struct links_entry *le, **new_buckets;
112 int hash;
113 size_t i, new_size;
114 dev_t dev;
115 ino_t ino;
116 int nlinks;
117
118
119 /* Free a held name. */
120 free(links_cache->last_name);
121 links_cache->last_name = NULL;
122
123 /* If the links cache overflowed and got flushed, don't bother. */
124 if (links_cache->buckets == NULL)
125 return (NULL);
126
127 dev = archive_entry_dev(entry);
128 ino = archive_entry_ino(entry);
129 nlinks = archive_entry_nlink(entry);
130
131 /* An entry with one link can't be a hard link. */
132 if (nlinks == 1)
133 return (NULL);
134
135 /* If the links cache is getting too full, enlarge the hash table. */
136 if (links_cache->number_entries > links_cache->number_buckets * 2)
137 {
138 /* Try to enlarge the bucket list. */
139 new_size = links_cache->number_buckets * 2;
140 new_buckets = malloc(new_size * sizeof(struct links_entry *));
141
142 if (new_buckets != NULL) {
143 memset(new_buckets, 0,
144 new_size * sizeof(struct links_entry *));
145 for (i = 0; i < links_cache->number_buckets; i++) {
146 while (links_cache->buckets[i] != NULL) {
147 /* Remove entry from old bucket. */
148 le = links_cache->buckets[i];
149 links_cache->buckets[i] = le->next;
150
151 /* Add entry to new bucket. */
152 hash = (le->dev ^ le->ino) % new_size;
153
154 if (new_buckets[hash] != NULL)
155 new_buckets[hash]->previous =
156 le;
157 le->next = new_buckets[hash];
158 le->previous = NULL;
159 new_buckets[hash] = le;
160 }
161 }
162 free(links_cache->buckets);
163 links_cache->buckets = new_buckets;
164 links_cache->number_buckets = new_size;
165 }
166 }
167
168 /* Try to locate this entry in the links cache. */
169 hash = ( dev ^ ino ) % links_cache->number_buckets;
170 for (le = links_cache->buckets[hash]; le != NULL; le = le->next) {
171 if (le->dev == dev && le->ino == ino) {
172 /*
173 * Decrement link count each time and release
174 * the entry if it hits zero. This saves
175 * memory and is necessary for detecting
176 * missed links.
177 */
178 --le->links;
179 if (le->links > 0)
180 return (le->name);
181 /*
182 * When we release the entry, save the name
183 * until the next call.
184 */
185 links_cache->last_name = le->name;
186 /*
187 * Release the entry.
188 */
189 if (le->previous != NULL)
190 le->previous->next = le->next;
191 if (le->next != NULL)
192 le->next->previous = le->previous;
193 if (links_cache->buckets[hash] == le)
194 links_cache->buckets[hash] = le->next;
195 links_cache->number_entries--;
196 free(le);
197 return (links_cache->last_name);
198 }
199 }
200
201 /* Add this entry to the links cache. */
202 le = malloc(sizeof(struct links_entry));
203 if (le == NULL)
204 return (NULL);
205 le->name = strdup(archive_entry_pathname(entry));
206 if (le->name == NULL) {
207 free(le);
208 return (NULL);
209 }
210
211 /* If we could allocate the entry, record it. */
212 if (links_cache->buckets[hash] != NULL)
213 links_cache->buckets[hash]->previous = le;
214 links_cache->number_entries++;
215 le->next = links_cache->buckets[hash];
216 le->previous = NULL;
217 links_cache->buckets[hash] = le;
218 le->dev = dev;
219 le->ino = ino;
220 le->links = nlinks - 1;
221 return (NULL);
222}