sortedcache.c 8.42 KB
Newer Older
1 2
#include "sortedcache.h"

3
GIT__USE_STRMAP
4 5 6 7 8 9 10 11 12 13

int git_sortedcache_new(
	git_sortedcache **out,
	size_t item_path_offset,
	git_sortedcache_free_item_fn free_item,
	void *free_item_payload,
	git_vector_cmp item_cmp,
	const char *path)
{
	git_sortedcache *sc;
14
	size_t pathlen, alloclen;
15 16 17

	pathlen = path ? strlen(path) : 0;

18 19 20
	GITERR_CHECK_ALLOC_ADD(&alloclen, sizeof(git_sortedcache), pathlen);
	GITERR_CHECK_ALLOC_ADD(&alloclen, alloclen, 1);
	sc = git__calloc(1, alloclen);
21 22
	GITERR_CHECK_ALLOC(sc);

23 24 25
	git_pool_init(&sc->pool, 1);

	if (git_vector_init(&sc->items, 4, item_cmp) < 0 ||
26
		git_strmap_alloc(&sc->map) < 0)
27 28
		goto fail;

29 30
	if (git_rwlock_init(&sc->lock)) {
		giterr_set(GITERR_OS, "Failed to initialize lock");
31 32 33
		goto fail;
	}

34 35
	sc->item_path_offset  = item_path_offset;
	sc->free_item         = free_item;
36 37 38 39 40 41 42 43 44
	sc->free_item_payload = free_item_payload;
	GIT_REFCOUNT_INC(sc);
	if (pathlen)
		memcpy(sc->path, path, pathlen);

	*out = sc;
	return 0;

fail:
45
	git_strmap_free(sc->map);
46 47 48 49 50 51 52 53 54 55 56
	git_vector_free(&sc->items);
	git_pool_clear(&sc->pool);
	git__free(sc);
	return -1;
}

void git_sortedcache_incref(git_sortedcache *sc)
{
	GIT_REFCOUNT_INC(sc);
}

57 58 59 60 61
const char *git_sortedcache_path(git_sortedcache *sc)
{
	return sc->path;
}

62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
static void sortedcache_clear(git_sortedcache *sc)
{
	git_strmap_clear(sc->map);

	if (sc->free_item) {
		size_t i;
		void *item;

		git_vector_foreach(&sc->items, i, item) {
			sc->free_item(sc->free_item_payload, item);
		}
	}

	git_vector_clear(&sc->items);

	git_pool_clear(&sc->pool);
}

static void sortedcache_free(git_sortedcache *sc)
{
82 83
	/* acquire write lock to make sure everyone else is done */
	if (git_sortedcache_wlock(sc) < 0)
84 85 86 87 88 89
		return;

	sortedcache_clear(sc);
	git_vector_free(&sc->items);
	git_strmap_free(sc->map);

90
	git_sortedcache_wunlock(sc);
91

92
	git_rwlock_free(&sc->lock);
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
	git__free(sc);
}

void git_sortedcache_free(git_sortedcache *sc)
{
	if (!sc)
		return;
	GIT_REFCOUNT_DEC(sc, sortedcache_free);
}

static int sortedcache_copy_item(void *payload, void *tgt_item, void *src_item)
{
	git_sortedcache *sc = payload;
	/* path will already have been copied by upsert */
	memcpy(tgt_item, src_item, sc->item_path_offset);
	return 0;
}

/* copy a sorted cache */
int git_sortedcache_copy(
	git_sortedcache **out,
	git_sortedcache *src,
115
	bool lock,
116 117 118
	int (*copy_item)(void *payload, void *tgt_item, void *src_item),
	void *payload)
{
119
	int error = 0;
120 121 122 123
	git_sortedcache *tgt;
	size_t i;
	void *src_item, *tgt_item;

124
	/* just use memcpy if no special copy fn is passed in */
125 126 127 128 129
	if (!copy_item) {
		copy_item = sortedcache_copy_item;
		payload   = src;
	}

130
	if ((error = git_sortedcache_new(
131 132
			&tgt, src->item_path_offset,
			src->free_item, src->free_item_payload,
133 134
			src->items._cmp, src->path)) < 0)
		return error;
135

136
	if (lock && git_sortedcache_rlock(src) < 0) {
137 138 139 140 141
		git_sortedcache_free(tgt);
		return -1;
	}

	git_vector_foreach(&src->items, i, src_item) {
142 143 144 145 146
		char *path = ((char *)src_item) + src->item_path_offset;

		if ((error = git_sortedcache_upsert(&tgt_item, tgt, path)) < 0 ||
			(error = copy_item(payload, tgt_item, src_item)) < 0)
			break;
147 148
	}

149 150
	if (lock)
		git_sortedcache_runlock(src);
151 152
	if (error)
		git_sortedcache_free(tgt);
153

154
	*out = !error ? tgt : NULL;
155

156
	return error;
157 158
}

159 160
/* lock sortedcache while making modifications */
int git_sortedcache_wlock(git_sortedcache *sc)
161
{
162
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
163

164 165 166 167 168
	if (git_rwlock_wrlock(&sc->lock) < 0) {
		giterr_set(GITERR_OS, "Unable to acquire write lock on cache");
		return -1;
	}
	return 0;
169 170
}

171 172
/* unlock sorted cache when done with modifications */
void git_sortedcache_wunlock(git_sortedcache *sc)
173
{
174 175
	git_vector_sort(&sc->items);
	git_rwlock_wrunlock(&sc->lock);
176 177
}

178 179
/* lock sortedcache for read */
int git_sortedcache_rlock(git_sortedcache *sc)
180
{
181
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
182

183 184
	if (git_rwlock_rdlock(&sc->lock) < 0) {
		giterr_set(GITERR_OS, "Unable to acquire read lock on cache");
185 186 187 188 189
		return -1;
	}
	return 0;
}

190 191
/* unlock sorted cache when done reading */
void git_sortedcache_runlock(git_sortedcache *sc)
192
{
193 194
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
	git_rwlock_rdunlock(&sc->lock);
195 196 197 198 199 200 201 202 203
}

/* if the file has changed, lock cache and load file contents into buf;
 * returns <0 on error, >0 if file has not changed
 */
int git_sortedcache_lockandload(git_sortedcache *sc, git_buf *buf)
{
	int error, fd;

204
	if ((error = git_sortedcache_wlock(sc)) < 0)
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231
		return error;

	if ((error = git_futils_filestamp_check(&sc->stamp, sc->path)) <= 0)
		goto unlock;

	if (!git__is_sizet(sc->stamp.size)) {
		giterr_set(GITERR_INVALID, "Unable to load file larger than size_t");
		error = -1;
		goto unlock;
	}

	if ((fd = git_futils_open_ro(sc->path)) < 0) {
		error = fd;
		goto unlock;
	}

	if (buf)
		error = git_futils_readbuffer_fd(buf, fd, (size_t)sc->stamp.size);

	(void)p_close(fd);

	if (error < 0)
		goto unlock;

	return 1; /* return 1 -> file needs reload and was successfully loaded */

unlock:
232
	git_sortedcache_wunlock(sc);
233 234 235
	return error;
}

236 237
void git_sortedcache_updated(git_sortedcache *sc)
{
238 239
	/* update filestamp to latest value */
	git_futils_filestamp_check(&sc->stamp, sc->path);
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
}

/* release all items in sorted cache */
int git_sortedcache_clear(git_sortedcache *sc, bool wlock)
{
	if (wlock && git_sortedcache_wlock(sc) < 0)
		return -1;

	sortedcache_clear(sc);

	if (wlock)
		git_sortedcache_wunlock(sc);

	return 0;
}

256
/* find and/or insert item, returning pointer to item data */
257
int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
258 259 260 261
{
	int error = 0;
	khiter_t pos;
	void *item;
262
	size_t keylen, itemlen;
263 264 265 266 267 268 269 270
	char *item_key;

	pos = git_strmap_lookup_index(sc->map, key);
	if (git_strmap_valid_index(sc->map, pos)) {
		item = git_strmap_value_at(sc->map, pos);
		goto done;
	}

271 272 273 274
	keylen  = strlen(key);
	itemlen = sc->item_path_offset + keylen + 1;
	itemlen = (itemlen + 7) & ~7;

275
	if ((item = git_pool_mallocz(&sc->pool, (uint32_t)itemlen)) == NULL) {
276
		/* don't use GITERR_CHECK_ALLOC b/c of lock */
277 278 279
		error = -1;
		goto done;
	}
280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321

	/* one strange thing is that even if the vector or hash table insert
	 * fail, there is no way to free the pool item so we just abandon it
	 */

	item_key = ((char *)item) + sc->item_path_offset;
	memcpy(item_key, key, keylen);

	pos = kh_put(str, sc->map, item_key, &error);
	if (error < 0)
		goto done;

	if (!error)
		kh_key(sc->map, pos) = item_key;
	kh_val(sc->map, pos) = item;

	error = git_vector_insert(&sc->items, item);
	if (error < 0)
		git_strmap_delete_at(sc->map, pos);

done:
	if (out)
		*out = !error ? item : NULL;
	return error;
}

/* lookup item by key */
void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key)
{
	khiter_t pos = git_strmap_lookup_index(sc->map, key);
	if (git_strmap_valid_index(sc->map, pos))
		return git_strmap_value_at(sc->map, pos);
	return NULL;
}

/* find out how many items are in the cache */
size_t git_sortedcache_entrycount(const git_sortedcache *sc)
{
	return git_vector_length(&sc->items);
}

/* lookup item by index */
322
void *git_sortedcache_entry(git_sortedcache *sc, size_t pos)
323
{
324
	/* make sure the items are sorted so this gets the correct item */
325
	if (!git_vector_is_sorted(&sc->items))
326 327
		git_vector_sort(&sc->items);

328 329
	return git_vector_get(&sc->items, pos);
}
330

331
/* helper struct so bsearch callback can know offset + key value for cmp */
332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356
struct sortedcache_magic_key {
	size_t offset;
	const char *key;
};

static int sortedcache_magic_cmp(const void *key, const void *value)
{
	const struct sortedcache_magic_key *magic = key;
	const char *value_key = ((const char *)value) + magic->offset;
	return strcmp(magic->key, value_key);
}

/* lookup index of item by key */
int git_sortedcache_lookup_index(
	size_t *out, git_sortedcache *sc, const char *key)
{
	struct sortedcache_magic_key magic;

	magic.offset = sc->item_path_offset;
	magic.key    = key;

	return git_vector_bsearch2(out, &sc->items, sortedcache_magic_cmp, &magic);
}

/* remove entry from cache */
357
int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
358 359 360 361 362 363 364 365 366 367
{
	char *item;
	khiter_t mappos;

	/* because of pool allocation, this can't actually remove the item,
	 * but we can remove it from the items vector and the hash table.
	 */

	if ((item = git_vector_get(&sc->items, pos)) == NULL) {
		giterr_set(GITERR_INVALID, "Removing item out of range");
368
		return GIT_ENOTFOUND;
369 370 371 372 373 374 375 376 377 378
	}

	(void)git_vector_remove(&sc->items, pos);

	mappos = git_strmap_lookup_index(sc->map, item + sc->item_path_offset);
	git_strmap_delete_at(sc->map, mappos);

	if (sc->free_item)
		sc->free_item(sc->free_item_payload, item);

379
	return 0;
380 381
}