src/vector.c

   1 /*
   2  * Copyright (C) 2009-2012 the libgit2 contributors
   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 "common.h"
   9 #include "repository.h"
  10 #include "vector.h"
  11
  12 static const double git_vector_resize_factor = 1.75;
  13 static const size_t git_vector_minimum_size = 8;
  14
  15 static int resize_vector(git_vector *v)
  16 {
  17         v->_alloc_size = (size_t)(v->_alloc_size * git_vector_resize_factor) + 1;
  18         if (v->_alloc_size < git_vector_minimum_size)
  19                 v->_alloc_size = git_vector_minimum_size;
  20
  21         v->contents = git__realloc(v->contents, v->_alloc_size * sizeof(void *));
  22         GITERR_CHECK_ALLOC(v->contents);
  23
  24         return 0;
  25 }
  26
  27 int git_vector_dup(git_vector *v, const git_vector *src, git_vector_cmp cmp)
  28 {
  29         assert(v && src);
  30
  31         v->_alloc_size = src->length;
  32         v->_cmp = cmp;
  33         v->length = src->length;
  34         v->sorted = src->sorted && cmp == src->_cmp;
  35         v->contents = git__malloc(src->length * sizeof(void *));
  36         GITERR_CHECK_ALLOC(v->contents);
  37
  38         memcpy(v->contents, src->contents, src->length * sizeof(void *));
  39
  40         return 0;
  41 }
  42
  43 void git_vector_free(git_vector *v)
  44 {
  45         assert(v);
  46
  47         git__free(v->contents);
  48         v->contents = NULL;
  49
  50         v->length = 0;
  51         v->_alloc_size = 0;
  52 }
  53
  54 int git_vector_init(git_vector *v, size_t initial_size, git_vector_cmp cmp)
  55 {
  56         assert(v);
  57
  58         memset(v, 0x0, sizeof(git_vector));
  59
  60         if (initial_size == 0)
  61                 initial_size = git_vector_minimum_size;
  62
  63         v->_alloc_size = initial_size;
  64         v->_cmp = cmp;
  65
  66         v->length = 0;
  67         v->sorted = 1;
  68
  69         v->contents = git__malloc(v->_alloc_size * sizeof(void *));
  70         GITERR_CHECK_ALLOC(v->contents);
  71
  72         return 0;
  73 }
  74
  75 int git_vector_insert(git_vector *v, void *element)
  76 {
  77         assert(v);
  78
  79         if (v->length >= v->_alloc_size &&
  80                 resize_vector(v) < 0)
  81                 return -1;
  82
  83         v->contents[v->length++] = element;
  84         v->sorted = 0;
  85
  86         return 0;
  87 }
  88
  89 int git_vector_insert_sorted(
  90         git_vector *v, void *element, int (*on_dup)(void **old, void *new))
  91 {
  92         int result;
  93         size_t pos;
  94
  95         assert(v && v->_cmp);
  96
  97         if (!v->sorted)
  98                 git_vector_sort(v);
  99
 100         if (v->length >= v->_alloc_size &&
 101                 resize_vector(v) < 0)
 102                 return -1;
 103
 104         /* If we find the element and have a duplicate handler callback,
 105          * invoke it.  If it returns non-zero, then cancel insert, otherwise
 106          * proceed with normal insert.
 107          */
 108         if (git__bsearch(v->contents, v->length, element, v->_cmp, &pos) >= 0 &&
 109                 on_dup != NULL &&
 110                 (result = on_dup(&v->contents[pos], element)) < 0)
 111                 return result;
 112
 113         /* shift elements to the right */
 114         if (pos < v->length) {
 115                 memmove(v->contents + pos + 1, v->contents + pos,
 116                         (v->length - pos) * sizeof(void *));
 117         }
 118
 119         v->contents[pos] = element;
 120         v->length++;
 121         return 0;
 122 }
 123
 124 void git_vector_sort(git_vector *v)
 125 {
 126         assert(v);
 127
 128         if (v->sorted || v->_cmp == NULL)
 129                 return;
 130
 131         git__tsort(v->contents, v->length, v->_cmp);
 132         v->sorted = 1;
 133 }
 134
 135 int git_vector_bsearch3(
 136         size_t *at_pos,
 137         git_vector *v,
 138         git_vector_cmp key_lookup,
 139         const void *key)
 140 {
 141         int rval;
 142         size_t pos;
 143
 144         assert(v && key && key_lookup);
 145
 146         /* need comparison function to sort the vector */
 147         assert(v->_cmp != NULL);
 148
 149         git_vector_sort(v);
 150
 151         rval = git__bsearch(v->contents, v->length, key, key_lookup, &pos);
 152
 153         if (at_pos != NULL)
 154                 *at_pos = pos;
 155
 156         return (rval >= 0) ? (int)pos : GIT_ENOTFOUND;
 157 }
 158
 159 int git_vector_search2(
 160         const git_vector *v, git_vector_cmp key_lookup, const void *key)
 161 {
 162         size_t i;
 163
 164         assert(v && key && key_lookup);
 165
 166         for (i = 0; i < v->length; ++i) {
 167                 if (key_lookup(key, v->contents[i]) == 0)
 168                         return (int)i;
 169         }
 170
 171         return GIT_ENOTFOUND;
 172 }
 173
 174 static int strict_comparison(const void *a, const void *b)
 175 {
 176         return (a == b) ? 0 : -1;
 177 }
 178
 179 int git_vector_search(const git_vector *v, const void *entry)
 180 {
 181         return git_vector_search2(v, v->_cmp ? v->_cmp : strict_comparison, entry);
 182 }
 183
 184 int git_vector_remove(git_vector *v, size_t idx)
 185 {
 186         size_t i;
 187
 188         assert(v);
 189
 190         if (idx >= v->length || v->length == 0)
 191                 return GIT_ENOTFOUND;
 192
 193         for (i = idx; i < v->length - 1; ++i)
 194                 v->contents[i] = v->contents[i + 1];
 195
 196         v->length--;
 197         return 0;
 198 }
 199
 200 void git_vector_pop(git_vector *v)
 201 {
 202         if (v->length > 0)
 203                 v->length--;
 204 }
 205
 206 void git_vector_uniq(git_vector *v)
 207 {
 208         git_vector_cmp cmp;
 209         size_t i, j;
 210
 211         if (v->length <= 1)
 212                 return;
 213
 214         git_vector_sort(v);
 215         cmp = v->_cmp ? v->_cmp : strict_comparison;
 216
 217         for (i = 0, j = 1 ; j < v->length; ++j)
 218                 if (!cmp(v->contents[i], v->contents[j]))
 219                         v->contents[i] = v->contents[j];
 220                 else
 221                         v->contents[++i] = v->contents[j];
 222
 223         v->length -= j - i - 1;
 224 }
 225
 226 void git_vector_remove_matching(
 227         git_vector *v, int (*match)(const git_vector *v, size_t idx))
 228 {
 229         size_t i, j;
 230
 231         for (i = 0, j = 0; j < v->length; ++j) {
 232                 v->contents[i] = v->contents[j];
 233
 234                 if (!match(v, i))
 235                         i++;
 236         }
 237
 238         v->length = i;
 239 }
 240
 241 void git_vector_clear(git_vector *v)
 242 {
 243         assert(v);
 244         v->length = 0;
 245         v->sorted = 1;
 246 }
 247
 248 void git_vector_swap(git_vector *a, git_vector *b)
 249 {
 250         git_vector t;
 251
 252         if (!a || !b || a == b)
 253                 return;
 254
 255         memcpy(&t, a, sizeof(t));
 256         memcpy(a, b, sizeof(t));
 257         memcpy(b, &t, sizeof(t));
 258 }
 259
 260 int git_vector_resize_to(git_vector *v, size_t new_length)
 261 {
 262         if (new_length <= v->length)
 263                 return 0;
 264
 265         while (new_length >= v->_alloc_size)
 266                 if (resize_vector(v) < 0)
 267                         return -1;
 268
 269         memset(&v->contents[v->length], 0,
 270                 sizeof(void *) * (new_length - v->length));
 271
 272         v->length = new_length;
 273
 274         return 0;
 275 }
 276
 277 int git_vector_set(void **old, git_vector *v, size_t position, void *value)
 278 {
 279         if (git_vector_resize_to(v, position + 1) < 0)
 280                 return -1;
 281
 282         if (old != NULL)
 283                 *old = v->contents[position];
 284
 285         v->contents[position] = value;
 286
 287         return 0;
 288 }