src/util/sortedcache.c

   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
   8 #include "sortedcache.h"
   9
  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;
  19         size_t pathlen, alloclen;
  20
  21         pathlen = path ? strlen(path) : 0;
  22
  23         GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, sizeof(git_sortedcache), pathlen);
  24         GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, alloclen, 1);
  25         sc = git__calloc(1, alloclen);
  26         GIT_ERROR_CHECK_ALLOC(sc);
  27
  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)
  31                 goto fail;
  32
  33         if (git_rwlock_init(&sc->lock)) {
  34                 git_error_set(GIT_ERROR_OS, "failed to initialize lock");
  35                 goto fail;
  36         }
  37
  38         sc->item_path_offset  = item_path_offset;
  39         sc->free_item         = free_item;
  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:
  49         git_strmap_free(sc->map);
  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
  61 const char *git_sortedcache_path(git_sortedcache *sc)
  62 {
  63         return sc->path;
  64 }
  65
  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 {
  86         /* acquire write lock to make sure everyone else is done */
  87         if (git_sortedcache_wlock(sc) < 0)
  88                 return;
  89
  90         sortedcache_clear(sc);
  91         git_vector_free(&sc->items);
  92         git_strmap_free(sc->map);
  93
  94         git_sortedcache_wunlock(sc);
  95
  96         git_rwlock_free(&sc->lock);
  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,
 119         bool lock,
 120         int (*copy_item)(void *payload, void *tgt_item, void *src_item),
 121         void *payload)
 122 {
 123         int error = 0;
 124         git_sortedcache *tgt;
 125         size_t i;
 126         void *src_item, *tgt_item;
 127
 128         /* just use memcpy if no special copy fn is passed in */
 129         if (!copy_item) {
 130                 copy_item = sortedcache_copy_item;
 131                 payload   = src;
 132         }
 133
 134         if ((error = git_sortedcache_new(
 135                         &tgt, src->item_path_offset,
 136                         src->free_item, src->free_item_payload,
 137                         src->items._cmp, src->path)) < 0)
 138                 return error;
 139
 140         if (lock && git_sortedcache_rlock(src) < 0) {
 141                 git_sortedcache_free(tgt);
 142                 return -1;
 143         }
 144
 145         git_vector_foreach(&src->items, i, src_item) {
 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;
 151         }
 152
 153         if (lock)
 154                 git_sortedcache_runlock(src);
 155         if (error)
 156                 git_sortedcache_free(tgt);
 157
 158         *out = !error ? tgt : NULL;
 159
 160         return error;
 161 }
 162
 163 /* lock sortedcache while making modifications */
 164 int git_sortedcache_wlock(git_sortedcache *sc)
 165 {
 166         GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
 167
 168         if (git_rwlock_wrlock(&sc->lock) < 0) {
 169                 git_error_set(GIT_ERROR_OS, "unable to acquire write lock on cache");
 170                 return -1;
 171         }
 172         return 0;
 173 }
 174
 175 /* unlock sorted cache when done with modifications */
 176 void git_sortedcache_wunlock(git_sortedcache *sc)
 177 {
 178         git_vector_sort(&sc->items);
 179         git_rwlock_wrunlock(&sc->lock);
 180 }
 181
 182 /* lock sortedcache for read */
 183 int git_sortedcache_rlock(git_sortedcache *sc)
 184 {
 185         GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
 186
 187         if (git_rwlock_rdlock(&sc->lock) < 0) {
 188                 git_error_set(GIT_ERROR_OS, "unable to acquire read lock on cache");
 189                 return -1;
 190         }
 191         return 0;
 192 }
 193
 194 /* unlock sorted cache when done reading */
 195 void git_sortedcache_runlock(git_sortedcache *sc)
 196 {
 197         GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
 198         git_rwlock_rdunlock(&sc->lock);
 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  */
 204 int git_sortedcache_lockandload(git_sortedcache *sc, git_str *buf)
 205 {
 206         int error, fd;
 207         struct stat st;
 208
 209         if ((error = git_sortedcache_wlock(sc)) < 0)
 210                 return error;
 211
 212         if ((error = git_futils_filestamp_check(&sc->stamp, sc->path)) <= 0)
 213                 goto unlock;
 214
 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) {
 221                 git_error_set(GIT_ERROR_OS, "failed to stat file");
 222                 error = -1;
 223                 (void)p_close(fd);
 224                 goto unlock;
 225         }
 226
 227         if (!git__is_sizet(st.st_size)) {
 228                 git_error_set(GIT_ERROR_INVALID, "unable to load file larger than size_t");
 229                 error = -1;
 230                 (void)p_close(fd);
 231                 goto unlock;
 232         }
 233
 234         if (buf)
 235                 error = git_futils_readbuffer_fd(buf, fd, (size_t)st.st_size);
 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:
 245         git_sortedcache_wunlock(sc);
 246         return error;
 247 }
 248
 249 void git_sortedcache_updated(git_sortedcache *sc)
 250 {
 251         /* update filestamp to latest value */
 252         git_futils_filestamp_check(&sc->stamp, sc->path);
 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
 269 /* find and/or insert item, returning pointer to item data */
 270 int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
 271 {
 272         size_t keylen, itemlen;
 273         int error = 0;
 274         char *item_key;
 275         void *item;
 276
 277         if ((item = git_strmap_get(sc->map, key)) != NULL)
 278                 goto done;
 279
 280         keylen  = strlen(key);
 281         itemlen = sc->item_path_offset + keylen + 1;
 282         itemlen = (itemlen + 7) & ~7;
 283
 284         if ((item = git_pool_mallocz(&sc->pool, itemlen)) == NULL) {
 285                 /* don't use GIT_ERROR_CHECK_ALLOC b/c of lock */
 286                 error = -1;
 287                 goto done;
 288         }
 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
 297         if ((error = git_strmap_set(sc->map, item_key, item)) < 0)
 298                 goto done;
 299
 300         if ((error = git_vector_insert(&sc->items, item)) < 0)
 301                 git_strmap_delete(sc->map, item_key);
 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 {
 312         return git_strmap_get(sc->map, key);
 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 */
 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                 git_vector_sort(&sc->items);
 327
 328         return git_vector_get(&sc->items, pos);
 329 }
 330
 331 /* helper struct so bsearch callback can know offset + key value for cmp */
 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 */
 357 int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
 358 {
 359         char *item;
 360
 361         /*
 362          * Because of pool allocation, this can't actually remove the item,
 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) {
 367                 git_error_set(GIT_ERROR_INVALID, "removing item out of range");
 368                 return GIT_ENOTFOUND;
 369         }
 370
 371         (void)git_vector_remove(&sc->items, pos);
 372
 373         git_strmap_delete(sc->map, item + sc->item_path_offset);
 374
 375         if (sc->free_item)
 376                 sc->free_item(sc->free_item_payload, item);
 377
 378         return 0;
 379 }
 380