2 * Copyright (c) 2003-2007 Tim Kientzle
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
26 #include "archive_platform.h"
27 __FBSDID("$FreeBSD$");
29 #ifdef HAVE_SYS_STAT_H
43 #include "archive_entry.h"
45 /* Initial size of link cache. */
46 #define links_cache_initial_size 1024
48 struct archive_entry_linkresolver {
50 unsigned long number_entries;
51 size_t number_buckets;
52 struct links_entry **buckets;
56 struct links_entry *next;
57 struct links_entry *previous;
64 struct archive_entry_linkresolver *
65 archive_entry_linkresolver_new(void)
67 struct archive_entry_linkresolver *links_cache;
70 links_cache = malloc(sizeof(struct archive_entry_linkresolver));
71 if (links_cache == 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) {
81 for (i = 0; i < links_cache->number_buckets; i++)
82 links_cache->buckets[i] = NULL;
87 archive_entry_linkresolver_free(struct archive_entry_linkresolver *links_cache)
91 if (links_cache->buckets == NULL)
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;
103 free(links_cache->buckets);
104 links_cache->buckets = NULL;
108 archive_entry_linkresolve(struct archive_entry_linkresolver *links_cache,
109 struct archive_entry *entry)
111 struct links_entry *le, **new_buckets;
119 /* Free a held name. */
120 free(links_cache->last_name);
121 links_cache->last_name = NULL;
123 /* If the links cache overflowed and got flushed, don't bother. */
124 if (links_cache->buckets == NULL)
127 dev = archive_entry_dev(entry);
128 ino = archive_entry_ino(entry);
129 nlinks = archive_entry_nlink(entry);
131 /* An entry with one link can't be a hard link. */
135 /* If the links cache is getting too full, enlarge the hash table. */
136 if (links_cache->number_entries > links_cache->number_buckets * 2)
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 *));
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;
151 /* Add entry to new bucket. */
152 hash = (le->dev ^ le->ino) % new_size;
154 if (new_buckets[hash] != NULL)
155 new_buckets[hash]->previous =
157 le->next = new_buckets[hash];
159 new_buckets[hash] = le;
162 free(links_cache->buckets);
163 links_cache->buckets = new_buckets;
164 links_cache->number_buckets = new_size;
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) {
173 * Decrement link count each time and release
174 * the entry if it hits zero. This saves
175 * memory and is necessary for detecting
182 * When we release the entry, save the name
183 * until the next call.
185 links_cache->last_name = le->name;
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--;
197 return (links_cache->last_name);
201 /* Add this entry to the links cache. */
202 le = malloc(sizeof(struct links_entry));
205 le->name = strdup(archive_entry_pathname(entry));
206 if (le->name == NULL) {
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];
217 links_cache->buckets[hash] = le;
220 le->links = nlinks - 1;