src/vector.c

   1 /*
   2  * This file is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License, version 2,
   4  * as published by the Free Software Foundation.
   5  *
   6  * In addition to the permissions in the GNU General Public License,
   7  * the authors give you unlimited permission to link the compiled
   8  * version of this file into combinations with other programs,
   9  * and to distribute those combinations without any restriction
  10  * coming from the use of this file.  (The General Public License
  11  * restrictions do apply in other respects; for example, they cover
  12  * modification of the file, and distribution when not linked into
  13  * a combined executable.)
  14  *
  15  * This file is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; see the file COPYING.  If not, write to
  22  * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  23  * Boston, MA 02110-1301, USA.
  24  */
  25
  26 #include "common.h"
  27 #include "repository.h"
  28 #include "vector.h"
  29
  30 static const double resize_factor = 1.75;
  31 static const size_t minimum_size = 8;
  32
  33 static int resize_vector(git_vector *v)
  34 {
  35         v->_alloc_size = ((unsigned int)(v->_alloc_size * resize_factor)) + 1;
  36         if (v->_alloc_size < minimum_size)
  37                 v->_alloc_size = minimum_size;
  38
  39         v->contents = realloc(v->contents, v->_alloc_size * sizeof(void *));
  40         if (v->contents == NULL)
  41                 return GIT_ENOMEM;
  42
  43         return GIT_SUCCESS;
  44 }
  45
  46
  47 void git_vector_free(git_vector *v)
  48 {
  49         assert(v);
  50         free(v->contents);
  51 }
  52
  53 int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp)
  54 {
  55         assert(v);
  56
  57         memset(v, 0x0, sizeof(git_vector));
  58
  59         if (initial_size == 0)
  60                 initial_size = minimum_size;
  61
  62         v->_alloc_size = initial_size;
  63         v->_cmp = cmp;
  64
  65         v->length = 0;
  66         v->sorted = 1;
  67
  68         v->contents = git__malloc(v->_alloc_size * sizeof(void *));
  69         if (v->contents == NULL)
  70                 return GIT_ENOMEM;
  71
  72         return GIT_SUCCESS;
  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                 if (resize_vector(v) < 0)
  81                         return GIT_ENOMEM;
  82         }
  83
  84         v->contents[v->length++] = element;
  85         v->sorted = 0;
  86
  87         return GIT_SUCCESS;
  88 }
  89
  90 void git_vector_sort(git_vector *v)
  91 {
  92         assert(v);
  93
  94         if (v->sorted || v->_cmp == NULL)
  95                 return;
  96
  97         qsort(v->contents, v->length, sizeof(void *), v->_cmp);
  98         v->sorted = 1;
  99 }
 100
 101 int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *key)
 102 {
 103         void **find;
 104
 105         assert(v && key && key_lookup);
 106
 107         /* need comparison function to sort the vector */
 108         if (v->_cmp == NULL)
 109                 return git__throw(GIT_ENOTFOUND, "Can't sort vector. No comparison function set");
 110
 111         git_vector_sort(v);
 112
 113         find = bsearch(key, v->contents, v->length, sizeof(void *), key_lookup);
 114         if (find != NULL)
 115                 return (int)(find - v->contents);
 116
 117         return git__throw(GIT_ENOTFOUND, "Can't find element");
 118 }
 119
 120 int git_vector_search2(git_vector *v, git_vector_cmp key_lookup, const void *key)
 121 {
 122         unsigned int i;
 123
 124         assert(v && key && key_lookup);
 125
 126         for (i = 0; i < v->length; ++i) {
 127                 if (key_lookup(key, v->contents[i]) == 0)
 128                         return i;
 129         }
 130
 131         return git__throw(GIT_ENOTFOUND, "Can't find element");
 132 }
 133
 134 static int strict_comparison(const void *a, const void *b)
 135 {
 136         return (a == b) ? 0 : -1;
 137 }
 138
 139 int git_vector_search(git_vector *v, const void *entry)
 140 {
 141         return git_vector_search2(v, v->_cmp ? v->_cmp : strict_comparison, entry);
 142 }
 143
 144 int git_vector_bsearch(git_vector *v, const void *key)
 145 {
 146         return git_vector_bsearch2(v, v->_cmp, key);
 147 }
 148
 149 int git_vector_remove(git_vector *v, unsigned int idx)
 150 {
 151         unsigned int i;
 152
 153         assert(v);
 154
 155         if (idx >= v->length || v->length == 0)
 156                 return git__throw(GIT_ENOTFOUND, "Can't remove element. Index out of bounds");
 157
 158         for (i = idx; i < v->length - 1; ++i)
 159                 v->contents[i] = v->contents[i + 1];
 160
 161         v->length--;
 162         return GIT_SUCCESS;
 163 }
 164
 165 void git_vector_clear(git_vector *v)
 166 {
 167         assert(v);
 168         v->length = 0;
 169         v->sorted = 1;
 170 }
 171
 172