[libgit2.git] / src / sortedcache.c

#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;

	GITERR_CHECK_ALLOC_ADD(&alloclen, sizeof(git_sortedcache), pathlen);
	GITERR_CHECK_ALLOC_ADD(&alloclen, alloclen, 1);
	sc = git__calloc(1, alloclen);
	GITERR_CHECK_ALLOC(sc);

	git_pool_init(&sc->pool, 1);

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

	if (git_rwlock_init(&sc->lock)) {
		giterr_set(GITERR_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) {
		giterr_set(GITERR_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) {
		giterr_set(GITERR_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_buf *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) {
		giterr_set(GITERR_OS, "failed to stat file");
		error = -1;
		(void)p_close(fd);
		goto unlock;
	}

	if (!git__is_sizet(st.st_size)) {
		giterr_set(GITERR_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)
{
	int error = 0;
	khiter_t pos;
	void *item;
	size_t keylen, itemlen;
	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;
	}

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

	if ((item = git_pool_mallocz(&sc->pool, (uint32_t)itemlen)) == NULL) {
		/* don't use GITERR_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);

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

	if (!error)
		git_strmap_set_key_at(sc->map, pos, item_key);
	git_strmap_set_value_at(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 */
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;
	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");
		return GIT_ENOTFOUND;
	}

	(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);

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