[libgit2.git] / src / util / sortedcache.c

/*
 * Copyright (C) the libgit2 contributors. All rights reserved.
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

#include "sortedcache.h"

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;
	size_t pathlen, alloclen;

	pathlen = path ? strlen(path) : 0;

	GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, sizeof(git_sortedcache), pathlen);
	GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, alloclen, 1);
	sc = git__calloc(1, alloclen);
	GIT_ERROR_CHECK_ALLOC(sc);

	if (git_pool_init(&sc->pool, 1) < 0 ||
	    git_vector_init(&sc->items, 4, item_cmp) < 0 ||
	    git_strmap_new(&sc->map) < 0)
		goto fail;

	if (git_rwlock_init(&sc->lock)) {
		git_error_set(GIT_ERROR_OS, "failed to initialize lock");
		goto fail;
	}

	sc->item_path_offset  = item_path_offset;
	sc->free_item         = free_item;
	sc->free_item_payload = free_item_payload;
	GIT_REFCOUNT_INC(sc);
	if (pathlen)
		memcpy(sc->path, path, pathlen);

	*out = sc;
	return 0;

fail:
	git_strmap_free(sc->map);
	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);
}

const char *git_sortedcache_path(git_sortedcache *sc)
{
	return sc->path;
}

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)
{
	/* acquire write lock to make sure everyone else is done */
	if (git_sortedcache_wlock(sc) < 0)
		return;

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

	git_sortedcache_wunlock(sc);

	git_rwlock_free(&sc->lock);
	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,
	bool lock,
	int (*copy_item)(void *payload, void *tgt_item, void *src_item),
	void *payload)
{
	int error = 0;
	git_sortedcache *tgt;
	size_t i;
	void *src_item, *tgt_item;

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

	if ((error = git_sortedcache_new(
			&tgt, src->item_path_offset,
			src->free_item, src->free_item_payload,
			src->items._cmp, src->path)) < 0)
		return error;

	if (lock && git_sortedcache_rlock(src) < 0) {
		git_sortedcache_free(tgt);
		return -1;
	}

	git_vector_foreach(&src->items, i, src_item) {
		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;
	}

	if (lock)
		git_sortedcache_runlock(src);
	if (error)
		git_sortedcache_free(tgt);

	*out = !error ? tgt : NULL;

	return error;
}

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

	if (git_rwlock_wrlock(&sc->lock) < 0) {
		git_error_set(GIT_ERROR_OS, "unable to acquire write lock on cache");
		return -1;
	}
	return 0;
}

/* unlock sorted cache when done with modifications */
void git_sortedcache_wunlock(git_sortedcache *sc)
{
	git_vector_sort(&sc->items);
	git_rwlock_wrunlock(&sc->lock);
}

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

	if (git_rwlock_rdlock(&sc->lock) < 0) {
		git_error_set(GIT_ERROR_OS, "unable to acquire read lock on cache");
		return -1;
	}
	return 0;
}

/* unlock sorted cache when done reading */
void git_sortedcache_runlock(git_sortedcache *sc)
{
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
	git_rwlock_rdunlock(&sc->lock);
}

/* 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_str *buf)
{
	int error, fd;
	struct stat st;

	if ((error = git_sortedcache_wlock(sc)) < 0)
		return error;

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

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

	if (p_fstat(fd, &st) < 0) {
		git_error_set(GIT_ERROR_OS, "failed to stat file");
		error = -1;
		(void)p_close(fd);
		goto unlock;
	}

	if (!git__is_sizet(st.st_size)) {
		git_error_set(GIT_ERROR_INVALID, "unable to load file larger than size_t");
		error = -1;
		(void)p_close(fd);
		goto unlock;
	}

	if (buf)
		error = git_futils_readbuffer_fd(buf, fd, (size_t)st.st_size);

	(void)p_close(fd);

	if (error < 0)
		goto unlock;

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

unlock:
	git_sortedcache_wunlock(sc);
	return error;
}

void git_sortedcache_updated(git_sortedcache *sc)
{
	/* update filestamp to latest value */
	git_futils_filestamp_check(&sc->stamp, sc->path);
}

/* 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;
}

/* find and/or insert item, returning pointer to item data */
int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
{
	size_t keylen, itemlen;
	int error = 0;
	char *item_key;
	void *item;

	if ((item = git_strmap_get(sc->map, key)) != NULL)
		goto done;

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

	if ((item = git_pool_mallocz(&sc->pool, itemlen)) == NULL) {
		/* don't use GIT_ERROR_CHECK_ALLOC b/c of lock */
		error = -1;
		goto done;
	}

	/* 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);

	if ((error = git_strmap_set(sc->map, item_key, item)) < 0)
		goto done;

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

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

/* lookup item by key */
void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key)
{
	return git_strmap_get(sc->map, key);
}

/* 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 */
void *git_sortedcache_entry(git_sortedcache *sc, size_t pos)
{
	/* make sure the items are sorted so this gets the correct item */
	if (!git_vector_is_sorted(&sc->items))
		git_vector_sort(&sc->items);

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

/* helper struct so bsearch callback can know offset + key value for cmp */
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 */
int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
{
	char *item;

	/*
	 * 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) {
		git_error_set(GIT_ERROR_INVALID, "removing item out of range");
		return GIT_ENOTFOUND;
	}

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

	git_strmap_delete(sc->map, item + sc->item_path_offset);

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

	return 0;
}
Commit	Line	Data
eae0bfdc PP	1	/*
	2	* Copyright (C) the libgit2 contributors. All rights reserved.
	3	*
	4	* This file is part of libgit2, distributed under the GNU GPL v2 with
	5	* a Linking Exception. For full terms see the included COPYING file.
	6	*/
	7
0b7cdc02 RB	8	#include "sortedcache.h"
0b7cdc02 RB	9
0b7cdc02 RB	10	int git_sortedcache_new(
	11	git_sortedcache **out,
	12	size_t item_path_offset,
	13	git_sortedcache_free_item_fn free_item,
	14	void *free_item_payload,
	15	git_vector_cmp item_cmp,
	16	const char *path)
	17	{
	18	git_sortedcache *sc;
f1453c59	19	size_t pathlen, alloclen;
0b7cdc02 RB	20
	21	pathlen = path ? strlen(path) : 0;
	22
ac3d33df JK	23	GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, sizeof(git_sortedcache), pathlen);
ac3d33df JK	24	GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, alloclen, 1);
f1453c59	25	sc = git__calloc(1, alloclen);
ac3d33df	26	GIT_ERROR_CHECK_ALLOC(sc);
0b7cdc02	27
22a2d3d5 UG	28	if (git_pool_init(&sc->pool, 1) < 0 \|\|
	29	git_vector_init(&sc->items, 4, item_cmp) < 0 \|\|
	30	git_strmap_new(&sc->map) < 0)
0b7cdc02 RB	31	goto fail;
0b7cdc02 RB	32
8d9a85d4	33	if (git_rwlock_init(&sc->lock)) {
ac3d33df	34	git_error_set(GIT_ERROR_OS, "failed to initialize lock");
0b7cdc02 RB	35	goto fail;
	36	}
	37
8d9a85d4 RB	38	sc->item_path_offset = item_path_offset;
8d9a85d4 RB	39	sc->free_item = free_item;
0b7cdc02 RB	40	sc->free_item_payload = free_item_payload;
	41	GIT_REFCOUNT_INC(sc);
	42	if (pathlen)
	43	memcpy(sc->path, path, pathlen);
	44
	45	*out = sc;
	46	return 0;
	47
	48	fail:
40ed4990	49	git_strmap_free(sc->map);
0b7cdc02 RB	50	git_vector_free(&sc->items);
	51	git_pool_clear(&sc->pool);
	52	git__free(sc);
	53	return -1;
	54	}
	55
	56	void git_sortedcache_incref(git_sortedcache *sc)
	57	{
	58	GIT_REFCOUNT_INC(sc);
	59	}
	60
8d9a85d4 RB	61	const char git_sortedcache_path(git_sortedcache sc)
	62	{
	63	return sc->path;
	64	}
	65
0b7cdc02 RB	66	static void sortedcache_clear(git_sortedcache *sc)
	67	{
	68	git_strmap_clear(sc->map);
	69
	70	if (sc->free_item) {
	71	size_t i;
	72	void *item;
	73
	74	git_vector_foreach(&sc->items, i, item) {
	75	sc->free_item(sc->free_item_payload, item);
	76	}
	77	}
	78
	79	git_vector_clear(&sc->items);
	80
	81	git_pool_clear(&sc->pool);
	82	}
	83
	84	static void sortedcache_free(git_sortedcache *sc)
	85	{
8d9a85d4 RB	86	/* acquire write lock to make sure everyone else is done */
8d9a85d4 RB	87	if (git_sortedcache_wlock(sc) < 0)
0b7cdc02	88	return;
0b7cdc02 RB	89
0b7cdc02 RB	90	sortedcache_clear(sc);
0b7cdc02 RB	91	git_vector_free(&sc->items);
	92	git_strmap_free(sc->map);
	93
8d9a85d4	94	git_sortedcache_wunlock(sc);
0b7cdc02	95
8d9a85d4	96	git_rwlock_free(&sc->lock);
0b7cdc02 RB	97	git__free(sc);
	98	}
	99
	100	void git_sortedcache_free(git_sortedcache *sc)
	101	{
	102	if (!sc)
	103	return;
	104	GIT_REFCOUNT_DEC(sc, sortedcache_free);
	105	}
	106
	107	static int sortedcache_copy_item(void payload, void tgt_item, void *src_item)
	108	{
	109	git_sortedcache *sc = payload;
	110	/* path will already have been copied by upsert */
	111	memcpy(tgt_item, src_item, sc->item_path_offset);
	112	return 0;
	113	}
	114
	115	/* copy a sorted cache */
	116	int git_sortedcache_copy(
	117	git_sortedcache **out,
	118	git_sortedcache *src,
805755f4	119	bool lock,
0b7cdc02 RB	120	int (copy_item)(void payload, void tgt_item, void src_item),
	121	void *payload)
	122	{
8d9a85d4	123	int error = 0;
0b7cdc02 RB	124	git_sortedcache *tgt;
	125	size_t i;
	126	void src_item, tgt_item;
	127
8d9a85d4	128	/* just use memcpy if no special copy fn is passed in */
0b7cdc02 RB	129	if (!copy_item) {
	130	copy_item = sortedcache_copy_item;
	131	payload = src;
	132	}
	133
8d9a85d4	134	if ((error = git_sortedcache_new(
0b7cdc02 RB	135	&tgt, src->item_path_offset,
0b7cdc02 RB	136	src->free_item, src->free_item_payload,
8d9a85d4 RB	137	src->items._cmp, src->path)) < 0)
8d9a85d4 RB	138	return error;
0b7cdc02	139
805755f4	140	if (lock && git_sortedcache_rlock(src) < 0) {
0b7cdc02 RB	141	git_sortedcache_free(tgt);
	142	return -1;
	143	}
	144
0b7cdc02	145	git_vector_foreach(&src->items, i, src_item) {
8d9a85d4 RB	146	char path = ((char )src_item) + src->item_path_offset;
	147
	148	if ((error = git_sortedcache_upsert(&tgt_item, tgt, path)) < 0 \|\|
	149	(error = copy_item(payload, tgt_item, src_item)) < 0)
	150	break;
0b7cdc02 RB	151	}
0b7cdc02 RB	152
805755f4 RB	153	if (lock)
805755f4 RB	154	git_sortedcache_runlock(src);
8d9a85d4 RB	155	if (error)
8d9a85d4 RB	156	git_sortedcache_free(tgt);
0b7cdc02	157
8d9a85d4	158	*out = !error ? tgt : NULL;
0b7cdc02	159
8d9a85d4	160	return error;
0b7cdc02 RB	161	}
0b7cdc02 RB	162
8d9a85d4 RB	163	/* lock sortedcache while making modifications */
8d9a85d4 RB	164	int git_sortedcache_wlock(git_sortedcache *sc)
0b7cdc02	165	{
8d9a85d4	166	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
0b7cdc02	167
8d9a85d4	168	if (git_rwlock_wrlock(&sc->lock) < 0) {
ac3d33df	169	git_error_set(GIT_ERROR_OS, "unable to acquire write lock on cache");
8d9a85d4 RB	170	return -1;
	171	}
	172	return 0;
0b7cdc02 RB	173	}
0b7cdc02 RB	174
8d9a85d4 RB	175	/* unlock sorted cache when done with modifications */
8d9a85d4 RB	176	void git_sortedcache_wunlock(git_sortedcache *sc)
0b7cdc02	177	{
8d9a85d4 RB	178	git_vector_sort(&sc->items);
8d9a85d4 RB	179	git_rwlock_wrunlock(&sc->lock);
0b7cdc02 RB	180	}
0b7cdc02 RB	181
8d9a85d4 RB	182	/* lock sortedcache for read */
8d9a85d4 RB	183	int git_sortedcache_rlock(git_sortedcache *sc)
0b7cdc02	184	{
8d9a85d4	185	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
b37359aa	186
8d9a85d4	187	if (git_rwlock_rdlock(&sc->lock) < 0) {
ac3d33df	188	git_error_set(GIT_ERROR_OS, "unable to acquire read lock on cache");
0b7cdc02 RB	189	return -1;
	190	}
	191	return 0;
	192	}
	193
8d9a85d4 RB	194	/* unlock sorted cache when done reading */
8d9a85d4 RB	195	void git_sortedcache_runlock(git_sortedcache *sc)
0b7cdc02	196	{
8d9a85d4 RB	197	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
8d9a85d4 RB	198	git_rwlock_rdunlock(&sc->lock);
0b7cdc02 RB	199	}
	200
	201	/* if the file has changed, lock cache and load file contents into buf;
	202	* returns <0 on error, >0 if file has not changed
	203	*/
e579e0f7	204	int git_sortedcache_lockandload(git_sortedcache sc, git_str buf)
0b7cdc02 RB	205	{
0b7cdc02 RB	206	int error, fd;
40ffa07f	207	struct stat st;
0b7cdc02	208
8d9a85d4	209	if ((error = git_sortedcache_wlock(sc)) < 0)
0b7cdc02 RB	210	return error;
	211
	212	if ((error = git_futils_filestamp_check(&sc->stamp, sc->path)) <= 0)
	213	goto unlock;
	214
40ffa07f CMN	215	if ((fd = git_futils_open_ro(sc->path)) < 0) {
	216	error = fd;
	217	goto unlock;
	218	}
	219
	220	if (p_fstat(fd, &st) < 0) {
ac3d33df	221	git_error_set(GIT_ERROR_OS, "failed to stat file");
0b7cdc02	222	error = -1;
24b2182c	223	(void)p_close(fd);
0b7cdc02 RB	224	goto unlock;
	225	}
	226
40ffa07f	227	if (!git__is_sizet(st.st_size)) {
ac3d33df	228	git_error_set(GIT_ERROR_INVALID, "unable to load file larger than size_t");
40ffa07f CMN	229	error = -1;
40ffa07f CMN	230	(void)p_close(fd);
0b7cdc02 RB	231	goto unlock;
	232	}
	233
	234	if (buf)
40ffa07f	235	error = git_futils_readbuffer_fd(buf, fd, (size_t)st.st_size);
0b7cdc02 RB	236
	237	(void)p_close(fd);
	238
	239	if (error < 0)
	240	goto unlock;
	241
	242	return 1; /* return 1 -> file needs reload and was successfully loaded */
	243
	244	unlock:
8d9a85d4	245	git_sortedcache_wunlock(sc);
0b7cdc02 RB	246	return error;
	247	}
	248
8d9a85d4 RB	249	void git_sortedcache_updated(git_sortedcache *sc)
8d9a85d4 RB	250	{
7d490872 RB	251	/* update filestamp to latest value */
7d490872 RB	252	git_futils_filestamp_check(&sc->stamp, sc->path);
8d9a85d4 RB	253	}
	254
	255	/* release all items in sorted cache */
	256	int git_sortedcache_clear(git_sortedcache *sc, bool wlock)
	257	{
	258	if (wlock && git_sortedcache_wlock(sc) < 0)
	259	return -1;
	260
	261	sortedcache_clear(sc);
	262
	263	if (wlock)
	264	git_sortedcache_wunlock(sc);
	265
	266	return 0;
	267	}
	268
0b7cdc02	269	/* find and/or insert item, returning pointer to item data */
8d9a85d4	270	int git_sortedcache_upsert(void *out, git_sortedcache sc, const char *key)
0b7cdc02	271	{
2b6e1908	272	size_t keylen, itemlen;
22a2d3d5	273	int error = 0;
0b7cdc02	274	char *item_key;
22a2d3d5	275	void *item;
0b7cdc02	276
22a2d3d5	277	if ((item = git_strmap_get(sc->map, key)) != NULL)
0b7cdc02	278	goto done;
0b7cdc02	279
2b6e1908 RB	280	keylen = strlen(key);
	281	itemlen = sc->item_path_offset + keylen + 1;
	282	itemlen = (itemlen + 7) & ~7;
	283
22a2d3d5	284	if ((item = git_pool_mallocz(&sc->pool, itemlen)) == NULL) {
ac3d33df	285	/* don't use GIT_ERROR_CHECK_ALLOC b/c of lock */
8d9a85d4 RB	286	error = -1;
	287	goto done;
	288	}
0b7cdc02 RB	289
	290	/* one strange thing is that even if the vector or hash table insert
	291	* fail, there is no way to free the pool item so we just abandon it
	292	*/
	293
	294	item_key = ((char *)item) + sc->item_path_offset;
	295	memcpy(item_key, key, keylen);
	296
22a2d3d5	297	if ((error = git_strmap_set(sc->map, item_key, item)) < 0)
0b7cdc02 RB	298	goto done;
0b7cdc02 RB	299
22a2d3d5 UG	300	if ((error = git_vector_insert(&sc->items, item)) < 0)
22a2d3d5 UG	301	git_strmap_delete(sc->map, item_key);
0b7cdc02 RB	302
	303	done:
	304	if (out)
	305	*out = !error ? item : NULL;
	306	return error;
	307	}
	308
	309	/* lookup item by key */
	310	void git_sortedcache_lookup(const git_sortedcache sc, const char *key)
	311	{
22a2d3d5	312	return git_strmap_get(sc->map, key);
0b7cdc02 RB	313	}
	314
	315	/* find out how many items are in the cache */
	316	size_t git_sortedcache_entrycount(const git_sortedcache *sc)
	317	{
	318	return git_vector_length(&sc->items);
	319	}
	320
	321	/* lookup item by index */
8d9a85d4	322	void git_sortedcache_entry(git_sortedcache sc, size_t pos)
0b7cdc02	323	{
8d9a85d4	324	/* make sure the items are sorted so this gets the correct item */
882c7742	325	if (!git_vector_is_sorted(&sc->items))
8d9a85d4 RB	326	git_vector_sort(&sc->items);
8d9a85d4 RB	327
0b7cdc02 RB	328	return git_vector_get(&sc->items, pos);
0b7cdc02 RB	329	}
a4977169	330
8d9a85d4	331	/* helper struct so bsearch callback can know offset + key value for cmp */
a4977169 RB	332	struct sortedcache_magic_key {
	333	size_t offset;
	334	const char *key;
	335	};
	336
	337	static int sortedcache_magic_cmp(const void key, const void value)
	338	{
	339	const struct sortedcache_magic_key *magic = key;
	340	const char value_key = ((const char )value) + magic->offset;
	341	return strcmp(magic->key, value_key);
	342	}
	343
	344	/* lookup index of item by key */
	345	int git_sortedcache_lookup_index(
	346	size_t out, git_sortedcache sc, const char *key)
	347	{
	348	struct sortedcache_magic_key magic;
	349
	350	magic.offset = sc->item_path_offset;
	351	magic.key = key;
	352
	353	return git_vector_bsearch2(out, &sc->items, sortedcache_magic_cmp, &magic);
	354	}
	355
	356	/* remove entry from cache */
8d9a85d4	357	int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
a4977169	358	{
a4977169	359	char *item;
a4977169	360
22a2d3d5 UG	361	/*
22a2d3d5 UG	362	* Because of pool allocation, this can't actually remove the item,
a4977169 RB	363	* but we can remove it from the items vector and the hash table.
	364	*/
	365
	366	if ((item = git_vector_get(&sc->items, pos)) == NULL) {
ac3d33df	367	git_error_set(GIT_ERROR_INVALID, "removing item out of range");
8d9a85d4	368	return GIT_ENOTFOUND;
a4977169 RB	369	}
	370
	371	(void)git_vector_remove(&sc->items, pos);
	372
22a2d3d5	373	git_strmap_delete(sc->map, item + sc->item_path_offset);
a4977169 RB	374
	375	if (sc->free_item)
	376	sc->free_item(sc->free_item_payload, item);
	377
8d9a85d4	378	return 0;
a4977169 RB	379	}
a4977169 RB	380