1 /*
2  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
3  *
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.
7  *
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.
15  */
16 
17 #include <sys/queue.h>
18 
19 #include <stdlib.h>
20 #include <string.h>
21 #include <sha1.h>
22 #include <stdio.h>
23 #include <zlib.h>
24 #include <limits.h>
25 #include <time.h>
26 
27 #include "got_object.h"
28 #include "got_error.h"
29 
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"
34 
35 #ifndef nitems
36 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
37 #endif
38 
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 */
43 };
44 
45 TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element);
46 
47 struct got_object_idcache {
48 	struct got_object_idcache_head entries;
49 	int nelem;
50 	int maxelem;
51 };
52 
53 struct got_object_idcache *
54 got_object_idcache_alloc(int maxelem)
55 {
56 	struct got_object_idcache *cache;
57 
58 	cache = calloc(1, sizeof(*cache));
59 	if (cache == NULL)
60 		return NULL;
61 
62 	TAILQ_INIT(&cache->entries);
63 	cache->maxelem = maxelem;
64 	return cache;
65 }
66 
67 void
68 got_object_idcache_free(struct got_object_idcache *cache)
69 {
70 	struct got_object_idcache_element *entry;
71 
72 	while (!TAILQ_EMPTY(&cache->entries)) {
73 		entry = TAILQ_FIRST(&cache->entries);
74 		TAILQ_REMOVE(&cache->entries, entry, entry);
75 		/* User data should be freed by caller. */
76 		free(entry);
77 	}
78 	free(cache);
79 }
80 
81 const struct got_error *
82 got_object_idcache_add(struct got_object_idcache *cache,
83     struct got_object_id *id, void *data)
84 {
85 	struct got_object_idcache_element *entry;
86 
87 	if (cache->nelem >= cache->maxelem)
88 		return got_error(GOT_ERR_NO_SPACE);
89 
90 	entry = calloc(1, sizeof(*entry));
91 	if (entry == NULL)
92 		return got_error_from_errno();
93 
94 	memcpy(&entry->id, id, sizeof(entry->id));
95 	entry->data = data;
96 
97 	TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
98 	cache->nelem++;
99 	return NULL;
100 }
101 
102 void *
103 got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
104 {
105 	struct got_object_idcache_element *entry;
106 
107 	TAILQ_FOREACH(entry, &cache->entries, entry) {
108 		if (got_object_id_cmp(&entry->id, id) != 0)
109 			continue;
110 		if (entry != TAILQ_FIRST(&cache->entries)) {
111 			TAILQ_REMOVE(&cache->entries, entry, entry);
112 			TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
113 		}
114 		return entry->data;
115 	}
116 
117 	return NULL;
118 }
119 
120 const struct got_error *
121 got_object_idcache_remove_least_used(void **data, struct got_object_idcache *cache)
122 {
123 	struct got_object_idcache_element *entry;
124 
125 	if (data)
126 		*data = NULL;
127 
128 	if (cache->nelem == 0)
129 		return got_error(GOT_ERR_NO_OBJ);
130 
131 	entry = TAILQ_LAST(&cache->entries, got_object_idcache_head);
132 	TAILQ_REMOVE(&cache->entries, entry, entry);
133 	if (data)
134 		*data = entry->data;
135 	free(entry);
136 	cache->nelem--;
137 	return NULL;
138 }
139 
140 int
141 got_object_idcache_contains(struct got_object_idcache *cache,
142     struct got_object_id *id)
143 {
144 	struct got_object_idcache_element *entry;
145 
146 	TAILQ_FOREACH(entry, &cache->entries, entry) {
147 		if (got_object_id_cmp(&entry->id, id) == 0)
148 			return 1;
149 	}
150 
151 	return 0;
152 }
153 
154 void got_object_idcache_for_each(struct got_object_idcache *cache,
155     void (*cb)(struct got_object_id *, void *, void *), void *arg)
156 {
157 	struct got_object_idcache_element *entry;
158 
159 	TAILQ_FOREACH(entry, &cache->entries, entry)
160 		cb(&entry->id, entry->data, arg);
161 }
162 
163 int
164 got_object_idcache_num_elements(struct got_object_idcache *set)
165 {
166 	return set->nelem;
167 }