commit - 59790a325126d5fa5d7b2a0af2b2db6357d55063
commit + bb7182a5b18165905163dc712f19974358abfe76
blob - c10be9b25f2c42ae51559018bee66d6d981c67f9
blob + 340cb9c6d027478c290e3e6453ed01ae32f4048d
--- lib/object_idcache.c
+++ lib/object_idcache.c
TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element);
struct got_object_idcache {
- struct got_object_idcache_head entries;
- int nelem;
+ /*
+ * The cache is implemented as a collection of 256 lists.
+ * The value of the first byte of an object ID determines
+ * which of these lists an object ID is stored in.
+ */
+ struct got_object_idcache_head entries[0xff + 1];
+ int nelem[0xff + 1];
+ int totelem;
int maxelem;
};
got_object_idcache_alloc(int maxelem)
{
struct got_object_idcache *cache;
+ int i;
cache = calloc(1, sizeof(*cache));
if (cache == NULL)
return NULL;
- TAILQ_INIT(&cache->entries);
+ for (i = 0; i < nitems(cache->entries); i++)
+ TAILQ_INIT(&cache->entries[i]);
cache->maxelem = maxelem;
return cache;
}
got_object_idcache_free(struct got_object_idcache *cache)
{
struct got_object_idcache_element *entry;
+ int i;
- while (!TAILQ_EMPTY(&cache->entries)) {
- entry = TAILQ_FIRST(&cache->entries);
- TAILQ_REMOVE(&cache->entries, entry, entry);
- /* User data should be freed by caller. */
- free(entry);
+ for (i = 0; i < nitems(cache->entries); i++) {
+ while (!TAILQ_EMPTY(&cache->entries[i])) {
+ entry = TAILQ_FIRST(&cache->entries[i]);
+ TAILQ_REMOVE(&cache->entries[i], entry, entry);
+ /* User data should be freed by caller. */
+ free(entry);
+ }
}
free(cache);
}
struct got_object_id *id, void *data)
{
struct got_object_idcache_element *entry;
+ uint8_t i = id->sha1[0];
- if (cache->nelem >= cache->maxelem)
+ if (cache->totelem >= cache->maxelem)
return got_error(GOT_ERR_NO_SPACE);
entry = calloc(1, sizeof(*entry));
memcpy(&entry->id, id, sizeof(entry->id));
entry->data = data;
- TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
- cache->nelem++;
+ TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
+ cache->nelem[i]++;
+ cache->totelem++;
return NULL;
}
got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
{
struct got_object_idcache_element *entry;
+ uint8_t i = id->sha1[0];
- TAILQ_FOREACH(entry, &cache->entries, entry) {
+ TAILQ_FOREACH(entry, &cache->entries[i], entry) {
if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) != 0)
continue;
- if (entry != TAILQ_FIRST(&cache->entries)) {
- TAILQ_REMOVE(&cache->entries, entry, entry);
- TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
+ if (entry != TAILQ_FIRST(&cache->entries[i])) {
+ TAILQ_REMOVE(&cache->entries[i], entry, entry);
+ TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
}
return entry->data;
}
got_object_idcache_remove_least_used(void **data, struct got_object_idcache *cache)
{
struct got_object_idcache_element *entry;
+ int i, idx = 0, maxelem = cache->nelem[0];
if (data)
*data = NULL;
- if (cache->nelem == 0)
+ if (cache->totelem == 0)
return got_error(GOT_ERR_NO_OBJ);
- entry = TAILQ_LAST(&cache->entries, got_object_idcache_head);
- TAILQ_REMOVE(&cache->entries, entry, entry);
+ /* Remove least used element from longest list. */
+ for (i = 0; i < nitems(cache->entries); i++) {
+ if (maxelem < cache->nelem[i]) {
+ idx = i;
+ maxelem = cache->nelem[i];
+ }
+ }
+ entry = TAILQ_LAST(&cache->entries[idx], got_object_idcache_head);
+ TAILQ_REMOVE(&cache->entries[idx], entry, entry);
if (data)
*data = entry->data;
free(entry);
- cache->nelem--;
+ cache->nelem[idx]--;
+ cache->totelem--;
return NULL;
}
struct got_object_id *id)
{
struct got_object_idcache_element *entry;
+ uint8_t i = id->sha1[0];
- TAILQ_FOREACH(entry, &cache->entries, entry) {
+ TAILQ_FOREACH(entry, &cache->entries[i], entry) {
if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) == 0)
return 1;
}
void (*cb)(struct got_object_id *, void *, void *), void *arg)
{
struct got_object_idcache_element *entry;
+ int i;
- TAILQ_FOREACH(entry, &cache->entries, entry)
- cb(&entry->id, entry->data, arg);
+ for (i = 0; i < nitems(cache->entries); i++) {
+ TAILQ_FOREACH(entry, &cache->entries[i], entry)
+ cb(&entry->id, entry->data, arg);
+ }
}
int
-got_object_idcache_num_elements(struct got_object_idcache *set)
+got_object_idcache_num_elements(struct got_object_idcache *cache)
{
- return set->nelem;
+ return cache->totelem;
}