src/vector.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 "vector.h"
   9
  10 #include "integer.h"
  11
  12 /* In elements, not bytes */
  13 #define MIN_ALLOCSIZE   8
  14
  15 GIT_INLINE(size_t) compute_new_size(git_vector *v)
  16 {
  17         size_t new_size = v->_alloc_size;
  18
  19         /* Use a resize factor of 1.5, which is quick to compute using integer
  20          * instructions and less than the golden ratio (1.618...) */
  21         if (new_size < MIN_ALLOCSIZE)
  22                 new_size = MIN_ALLOCSIZE;
  23         else if (new_size <= (SIZE_MAX / 3) * 2)
  24                 new_size += new_size / 2;
  25         else
  26                 new_size = SIZE_MAX;
  27
  28         return new_size;
  29 }
  30
  31 GIT_INLINE(int) resize_vector(git_vector *v, size_t new_size)
  32 {
  33         void *new_contents;
  34
  35         if (new_size == 0)
  36                 return 0;
  37
  38         new_contents = git__reallocarray(v->contents, new_size, sizeof(void *));
  39         GIT_ERROR_CHECK_ALLOC(new_contents);
  40
  41         v->_alloc_size = new_size;
  42         v->contents = new_contents;
  43
  44         return 0;
  45 }
  46
  47 int git_vector_size_hint(git_vector *v, size_t size_hint)
  48 {
  49         if (v->_alloc_size >= size_hint)
  50                 return 0;
  51         return resize_vector(v, size_hint);
  52 }
  53
  54 int git_vector_dup(git_vector *v, const git_vector *src, git_vector_cmp cmp)
  55 {
  56         GIT_ASSERT_ARG(v);
  57         GIT_ASSERT_ARG(src);
  58
  59         v->_alloc_size = 0;
  60         v->contents = NULL;
  61         v->_cmp = cmp ? cmp : src->_cmp;
  62         v->length = src->length;
  63         v->flags  = src->flags;
  64         if (cmp != src->_cmp)
  65                 git_vector_set_sorted(v, 0);
  66
  67         if (src->length) {
  68                 size_t bytes;
  69                 GIT_ERROR_CHECK_ALLOC_MULTIPLY(&bytes, src->length, sizeof(void *));
  70                 v->contents = git__malloc(bytes);
  71                 GIT_ERROR_CHECK_ALLOC(v->contents);
  72                 v->_alloc_size = src->length;
  73                 memcpy(v->contents, src->contents, bytes);
  74         }
  75
  76         return 0;
  77 }
  78
  79 void git_vector_free(git_vector *v)
  80 {
  81         if (!v)
  82                 return;
  83
  84         git__free(v->contents);
  85         v->contents = NULL;
  86
  87         v->length = 0;
  88         v->_alloc_size = 0;
  89 }
  90
  91 void git_vector_free_deep(git_vector *v)
  92 {
  93         size_t i;
  94
  95         if (!v)
  96                 return;
  97
  98         for (i = 0; i < v->length; ++i) {
  99                 git__free(v->contents[i]);
 100                 v->contents[i] = NULL;
 101         }
 102
 103         git_vector_free(v);
 104 }
 105
 106 int git_vector_init(git_vector *v, size_t initial_size, git_vector_cmp cmp)
 107 {
 108         GIT_ASSERT_ARG(v);
 109
 110         v->_alloc_size = 0;
 111         v->_cmp = cmp;
 112         v->length = 0;
 113         v->flags = GIT_VECTOR_SORTED;
 114         v->contents = NULL;
 115
 116         return resize_vector(v, max(initial_size, MIN_ALLOCSIZE));
 117 }
 118
 119 void **git_vector_detach(size_t *size, size_t *asize, git_vector *v)
 120 {
 121         void **data = v->contents;
 122
 123         if (size)
 124                 *size = v->length;
 125         if (asize)
 126                 *asize = v->_alloc_size;
 127
 128         v->_alloc_size = 0;
 129         v->length   = 0;
 130         v->contents = NULL;
 131
 132         return data;
 133 }
 134
 135 int git_vector_insert(git_vector *v, void *element)
 136 {
 137         GIT_ASSERT_ARG(v);
 138
 139         if (v->length >= v->_alloc_size &&
 140                 resize_vector(v, compute_new_size(v)) < 0)
 141                 return -1;
 142
 143         v->contents[v->length++] = element;
 144
 145         git_vector_set_sorted(v, v->length <= 1);
 146
 147         return 0;
 148 }
 149
 150 int git_vector_insert_sorted(
 151         git_vector *v, void *element, int (*on_dup)(void **old, void *new))
 152 {
 153         int result;
 154         size_t pos;
 155
 156         GIT_ASSERT_ARG(v);
 157         GIT_ASSERT(v->_cmp);
 158
 159         if (!git_vector_is_sorted(v))
 160                 git_vector_sort(v);
 161
 162         if (v->length >= v->_alloc_size &&
 163                 resize_vector(v, compute_new_size(v)) < 0)
 164                 return -1;
 165
 166         /* If we find the element and have a duplicate handler callback,
 167          * invoke it.  If it returns non-zero, then cancel insert, otherwise
 168          * proceed with normal insert.
 169          */
 170         if (!git__bsearch(v->contents, v->length, element, v->_cmp, &pos) &&
 171                 on_dup && (result = on_dup(&v->contents[pos], element)) < 0)
 172                 return result;
 173
 174         /* shift elements to the right */
 175         if (pos < v->length)
 176                 memmove(v->contents + pos + 1, v->contents + pos,
 177                         (v->length - pos) * sizeof(void *));
 178
 179         v->contents[pos] = element;
 180         v->length++;
 181
 182         return 0;
 183 }
 184
 185 void git_vector_sort(git_vector *v)
 186 {
 187         if (git_vector_is_sorted(v) || !v->_cmp)
 188                 return;
 189
 190         if (v->length > 1)
 191                 git__tsort(v->contents, v->length, v->_cmp);
 192         git_vector_set_sorted(v, 1);
 193 }
 194
 195 int git_vector_bsearch2(
 196         size_t *at_pos,
 197         git_vector *v,
 198         git_vector_cmp key_lookup,
 199         const void *key)
 200 {
 201         GIT_ASSERT_ARG(v);
 202         GIT_ASSERT_ARG(key);
 203         GIT_ASSERT(key_lookup);
 204
 205         /* need comparison function to sort the vector */
 206         if (!v->_cmp)
 207                 return -1;
 208
 209         git_vector_sort(v);
 210
 211         return git__bsearch(v->contents, v->length, key, key_lookup, at_pos);
 212 }
 213
 214 int git_vector_search2(
 215         size_t *at_pos, const git_vector *v, git_vector_cmp key_lookup, const void *key)
 216 {
 217         size_t i;
 218
 219         GIT_ASSERT_ARG(v);
 220         GIT_ASSERT_ARG(key);
 221         GIT_ASSERT(key_lookup);
 222
 223         for (i = 0; i < v->length; ++i) {
 224                 if (key_lookup(key, v->contents[i]) == 0) {
 225                         if (at_pos)
 226                                 *at_pos = i;
 227
 228                         return 0;
 229                 }
 230         }
 231
 232         return GIT_ENOTFOUND;
 233 }
 234
 235 static int strict_comparison(const void *a, const void *b)
 236 {
 237         return (a == b) ? 0 : -1;
 238 }
 239
 240 int git_vector_search(size_t *at_pos, const git_vector *v, const void *entry)
 241 {
 242         return git_vector_search2(at_pos, v, v->_cmp ? v->_cmp : strict_comparison, entry);
 243 }
 244
 245 int git_vector_remove(git_vector *v, size_t idx)
 246 {
 247         size_t shift_count;
 248
 249         GIT_ASSERT_ARG(v);
 250
 251         if (idx >= v->length)
 252                 return GIT_ENOTFOUND;
 253
 254         shift_count = v->length - idx - 1;
 255
 256         if (shift_count)
 257                 memmove(&v->contents[idx], &v->contents[idx + 1],
 258                         shift_count * sizeof(void *));
 259
 260         v->length--;
 261         return 0;
 262 }
 263
 264 void git_vector_pop(git_vector *v)
 265 {
 266         if (v->length > 0)
 267                 v->length--;
 268 }
 269
 270 void git_vector_uniq(git_vector *v, void  (*git_free_cb)(void *))
 271 {
 272         git_vector_cmp cmp;
 273         size_t i, j;
 274
 275         if (v->length <= 1)
 276                 return;
 277
 278         git_vector_sort(v);
 279         cmp = v->_cmp ? v->_cmp : strict_comparison;
 280
 281         for (i = 0, j = 1 ; j < v->length; ++j)
 282                 if (!cmp(v->contents[i], v->contents[j])) {
 283                         if (git_free_cb)
 284                                 git_free_cb(v->contents[i]);
 285
 286                         v->contents[i] = v->contents[j];
 287                 } else
 288                         v->contents[++i] = v->contents[j];
 289
 290         v->length -= j - i - 1;
 291 }
 292
 293 void git_vector_remove_matching(
 294         git_vector *v,
 295         int (*match)(const git_vector *v, size_t idx, void *payload),
 296         void *payload)
 297 {
 298         size_t i, j;
 299
 300         for (i = 0, j = 0; j < v->length; ++j) {
 301                 v->contents[i] = v->contents[j];
 302
 303                 if (!match(v, i, payload))
 304                         i++;
 305         }
 306
 307         v->length = i;
 308 }
 309
 310 void git_vector_clear(git_vector *v)
 311 {
 312         v->length = 0;
 313         git_vector_set_sorted(v, 1);
 314 }
 315
 316 void git_vector_swap(git_vector *a, git_vector *b)
 317 {
 318         git_vector t;
 319
 320         if (a != b) {
 321                 memcpy(&t, a, sizeof(t));
 322                 memcpy(a, b, sizeof(t));
 323                 memcpy(b, &t, sizeof(t));
 324         }
 325 }
 326
 327 int git_vector_resize_to(git_vector *v, size_t new_length)
 328 {
 329         if (new_length > v->_alloc_size &&
 330                 resize_vector(v, new_length) < 0)
 331                 return -1;
 332
 333         if (new_length > v->length)
 334                 memset(&v->contents[v->length], 0,
 335                         sizeof(void *) * (new_length - v->length));
 336
 337         v->length = new_length;
 338
 339         return 0;
 340 }
 341
 342 int git_vector_insert_null(git_vector *v, size_t idx, size_t insert_len)
 343 {
 344         size_t new_length;
 345
 346         GIT_ASSERT_ARG(insert_len > 0);
 347         GIT_ASSERT_ARG(idx <= v->length);
 348
 349         GIT_ERROR_CHECK_ALLOC_ADD(&new_length, v->length, insert_len);
 350
 351         if (new_length > v->_alloc_size && resize_vector(v, new_length) < 0)
 352                 return -1;
 353
 354         memmove(&v->contents[idx + insert_len], &v->contents[idx],
 355                 sizeof(void *) * (v->length - idx));
 356         memset(&v->contents[idx], 0, sizeof(void *) * insert_len);
 357
 358         v->length = new_length;
 359         return 0;
 360 }
 361
 362 int git_vector_remove_range(git_vector *v, size_t idx, size_t remove_len)
 363 {
 364         size_t new_length = v->length - remove_len;
 365         size_t end_idx = 0;
 366
 367         GIT_ASSERT_ARG(remove_len > 0);
 368
 369         if (git__add_sizet_overflow(&end_idx, idx, remove_len))
 370                 GIT_ASSERT(0);
 371
 372         GIT_ASSERT(end_idx <= v->length);
 373
 374         if (end_idx < v->length)
 375                 memmove(&v->contents[idx], &v->contents[end_idx],
 376                         sizeof(void *) * (v->length - end_idx));
 377
 378         memset(&v->contents[new_length], 0, sizeof(void *) * remove_len);
 379
 380         v->length = new_length;
 381         return 0;
 382 }
 383
 384 int git_vector_set(void **old, git_vector *v, size_t position, void *value)
 385 {
 386         if (position + 1 > v->length) {
 387                 if (git_vector_resize_to(v, position + 1) < 0)
 388                         return -1;
 389         }
 390
 391         if (old != NULL)
 392                 *old = v->contents[position];
 393
 394         v->contents[position] = value;
 395
 396         return 0;
 397 }
 398
 399 int git_vector_verify_sorted(const git_vector *v)
 400 {
 401         size_t i;
 402
 403         if (!git_vector_is_sorted(v))
 404                 return -1;
 405
 406         for (i = 1; i < v->length; ++i) {
 407                 if (v->_cmp(v->contents[i - 1], v->contents[i]) > 0)
 408                         return -1;
 409         }
 410
 411         return 0;
 412 }
 413
 414 void git_vector_reverse(git_vector *v)
 415 {
 416         size_t a, b;
 417
 418         if (v->length == 0)
 419                 return;
 420
 421         a = 0;
 422         b = v->length - 1;
 423
 424         while (a < b) {
 425                 void *tmp = v->contents[a];
 426                 v->contents[a] = v->contents[b];
 427                 v->contents[b] = tmp;
 428                 a++;
 429                 b--;
 430         }
 431 }