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