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 int minimum_size = 8;
  32
  33 static int resize_vector(git_vector *v)
  34 {
  35         void **new_contents;
  36
  37         v->_alloc_size = ((unsigned int)(v->_alloc_size * resize_factor)) + 1;
  38         if (v->_alloc_size < minimum_size)
  39                 v->_alloc_size = minimum_size;
  40
  41         v->contents = realloc(v->contents, v->_alloc_size * sizeof(void *));
  42         if (v->contents == NULL)
  43                 return GIT_ENOMEM;
  44
  45         return GIT_SUCCESS;
  46 }
  47
  48
  49 void git_vector_free(git_vector *v)
  50 {
  51         assert(v);
  52         free(v->contents);
  53 }
  54
  55 int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp, git_vector_srch srch)
  56 {
  57         assert(v);
  58
  59         memset(v, 0x0, sizeof(git_vector));
  60
  61         if (initial_size == 0)
  62                 initial_size = minimum_size;
  63
  64         v->_alloc_size = initial_size;
  65         v->_cmp = cmp;
  66         v->_srch = srch;
  67
  68         v->length = 0;
  69
  70         v->contents = git__malloc(v->_alloc_size * sizeof(void *));
  71         if (v->contents == NULL)
  72                 return GIT_ENOMEM;
  73
  74         return GIT_SUCCESS;
  75 }
  76
  77 int git_vector_insert(git_vector *v, void *element)
  78 {
  79         assert(v);
  80
  81         if (v->length >= v->_alloc_size) {
  82                 if (resize_vector(v) < 0)
  83                         return GIT_ENOMEM;
  84         }
  85
  86         v->contents[v->length++] = element;
  87
  88         return GIT_SUCCESS;
  89 }
  90
  91 void git_vector_sort(git_vector *v)
  92 {
  93         assert(v);
  94
  95         if (v->_cmp != NULL)
  96                 qsort(v->contents, v->length, sizeof(void *), v->_cmp);
  97 }
  98
  99 int git_vector_search(git_vector *v, const void *key)
 100 {
 101         void **find;
 102
 103         if (v->_srch == NULL)
 104                 return GIT_ENOTFOUND;
 105
 106         find = bsearch(key, v->contents, v->length, sizeof(void *), v->_srch);
 107         if (find == NULL)
 108                 return GIT_ENOTFOUND;
 109
 110         return (int)(find - v->contents);
 111 }
 112
 113 int git_vector_remove(git_vector *v, unsigned int idx)
 114 {
 115         unsigned int i;
 116
 117         assert(v);
 118
 119         if (idx >= v->length || v->length == 0)
 120                 return GIT_ENOTFOUND;
 121
 122         for (i = idx; i < v->length - 1; ++i)
 123                 v->contents[i] = v->contents[i + 1];
 124
 125         v->length--;
 126         return GIT_SUCCESS;
 127 }
 128
 129 void git_vector_clear(git_vector *v)
 130 {
 131         assert(v);
 132         v->length = 0;
 133 }
 134
 135