2 * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 #include <sys/queue.h>
27 #include "got_object.h"
28 #include "got_error.h"
30 #include "got_lib_delta.h"
31 #include "got_lib_inflate.h"
32 #include "got_lib_object.h"
33 #include "got_lib_object_idcache.h"
36 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
39 struct got_object_idcache_element {
40 TAILQ_ENTRY(got_object_idcache_element) entry;
41 struct got_object_id id;
42 void *data; /* API user data */
45 TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element);
47 struct got_object_idcache {
49 * The cache is implemented as a collection of 256 lists.
50 * The value of the first byte of an object ID determines
51 * which of these lists an object ID is stored in.
53 struct got_object_idcache_head entries[0xff + 1];
59 struct got_object_idcache *
60 got_object_idcache_alloc(int maxelem)
62 struct got_object_idcache *cache;
65 cache = calloc(1, sizeof(*cache));
69 for (i = 0; i < nitems(cache->entries); i++)
70 TAILQ_INIT(&cache->entries[i]);
71 cache->maxelem = maxelem;
76 got_object_idcache_free(struct got_object_idcache *cache)
78 struct got_object_idcache_element *entry;
81 for (i = 0; i < nitems(cache->entries); i++) {
82 while (!TAILQ_EMPTY(&cache->entries[i])) {
83 entry = TAILQ_FIRST(&cache->entries[i]);
84 TAILQ_REMOVE(&cache->entries[i], entry, entry);
85 /* User data should be freed by caller. */
92 const struct got_error *
93 got_object_idcache_add(struct got_object_idcache *cache,
94 struct got_object_id *id, void *data)
96 struct got_object_idcache_element *entry;
97 uint8_t i = id->sha1[0];
99 if (cache->totelem >= cache->maxelem)
100 return got_error(GOT_ERR_NO_SPACE);
102 entry = calloc(1, sizeof(*entry));
104 return got_error_from_errno();
106 memcpy(&entry->id, id, sizeof(entry->id));
109 TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
116 got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
118 struct got_object_idcache_element *entry;
119 uint8_t i = id->sha1[0];
121 TAILQ_FOREACH(entry, &cache->entries[i], entry) {
122 if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) != 0)
124 if (entry != TAILQ_FIRST(&cache->entries[i])) {
125 TAILQ_REMOVE(&cache->entries[i], entry, entry);
126 TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
134 const struct got_error *
135 got_object_idcache_remove_least_used(void **data, struct got_object_idcache *cache)
137 struct got_object_idcache_element *entry;
138 int i, idx = 0, maxelem = cache->nelem[0];
143 if (cache->totelem == 0)
144 return got_error(GOT_ERR_NO_OBJ);
146 /* Remove least used element from longest list. */
147 for (i = 0; i < nitems(cache->entries); i++) {
148 if (maxelem < cache->nelem[i]) {
150 maxelem = cache->nelem[i];
153 entry = TAILQ_LAST(&cache->entries[idx], got_object_idcache_head);
154 TAILQ_REMOVE(&cache->entries[idx], entry, entry);
164 got_object_idcache_contains(struct got_object_idcache *cache,
165 struct got_object_id *id)
167 struct got_object_idcache_element *entry;
168 uint8_t i = id->sha1[0];
170 TAILQ_FOREACH(entry, &cache->entries[i], entry) {
171 if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) == 0)
178 void got_object_idcache_for_each(struct got_object_idcache *cache,
179 void (*cb)(struct got_object_id *, void *, void *), void *arg)
181 struct got_object_idcache_element *entry;
184 for (i = 0; i < nitems(cache->entries); i++) {
185 TAILQ_FOREACH(entry, &cache->entries[i], entry)
186 cb(&entry->id, entry->data, arg);
191 got_object_idcache_num_elements(struct got_object_idcache *cache)
193 return cache->totelem;