]>
Commit | Line | Data |
---|---|---|
c4034e63 | 1 | /* |
bb742ede | 2 | * Copyright (C) 2009-2011 the libgit2 contributors |
c4034e63 | 3 | * |
bb742ede VM |
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. | |
c4034e63 VM |
6 | */ |
7 | ||
8 | #include "common.h" | |
9 | #include "repository.h" | |
10 | #include "vector.h" | |
11 | ||
12 | static const double resize_factor = 1.75; | |
da7c3c71 | 13 | static const size_t minimum_size = 8; |
c4034e63 VM |
14 | |
15 | static int resize_vector(git_vector *v) | |
16 | { | |
a17777d1 | 17 | v->_alloc_size = ((unsigned int)(v->_alloc_size * resize_factor)) + 1; |
86194b24 | 18 | if (v->_alloc_size < minimum_size) |
c4034e63 VM |
19 | v->_alloc_size = minimum_size; |
20 | ||
3286c408 | 21 | v->contents = git__realloc(v->contents, v->_alloc_size * sizeof(void *)); |
86194b24 | 22 | if (v->contents == NULL) |
c4034e63 VM |
23 | return GIT_ENOMEM; |
24 | ||
c4034e63 VM |
25 | return GIT_SUCCESS; |
26 | } | |
27 | ||
28 | ||
29 | void git_vector_free(git_vector *v) | |
30 | { | |
31 | assert(v); | |
3286c408 | 32 | git__free(v->contents); |
c4034e63 VM |
33 | } |
34 | ||
86d7e1ca | 35 | int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp) |
c4034e63 VM |
36 | { |
37 | assert(v); | |
38 | ||
39 | memset(v, 0x0, sizeof(git_vector)); | |
40 | ||
41 | if (initial_size == 0) | |
42 | initial_size = minimum_size; | |
43 | ||
44 | v->_alloc_size = initial_size; | |
45 | v->_cmp = cmp; | |
932d1baf | 46 | |
c4034e63 | 47 | v->length = 0; |
86d7e1ca | 48 | v->sorted = 1; |
c4034e63 VM |
49 | |
50 | v->contents = git__malloc(v->_alloc_size * sizeof(void *)); | |
51 | if (v->contents == NULL) | |
52 | return GIT_ENOMEM; | |
53 | ||
54 | return GIT_SUCCESS; | |
55 | } | |
56 | ||
57 | int git_vector_insert(git_vector *v, void *element) | |
58 | { | |
59 | assert(v); | |
60 | ||
61 | if (v->length >= v->_alloc_size) { | |
62 | if (resize_vector(v) < 0) | |
63 | return GIT_ENOMEM; | |
64 | } | |
65 | ||
66 | v->contents[v->length++] = element; | |
86d7e1ca | 67 | v->sorted = 0; |
c4034e63 VM |
68 | |
69 | return GIT_SUCCESS; | |
70 | } | |
71 | ||
c4034e63 VM |
72 | void git_vector_sort(git_vector *v) |
73 | { | |
74 | assert(v); | |
75 | ||
86d7e1ca VM |
76 | if (v->sorted || v->_cmp == NULL) |
77 | return; | |
78 | ||
de18f276 | 79 | git__tsort(v->contents, v->length, v->_cmp); |
86d7e1ca | 80 | v->sorted = 1; |
c4034e63 VM |
81 | } |
82 | ||
86d7e1ca | 83 | int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *key) |
c4034e63 VM |
84 | { |
85 | void **find; | |
86 | ||
86d7e1ca VM |
87 | assert(v && key && key_lookup); |
88 | ||
48c27f86 VM |
89 | /* need comparison function to sort the vector */ |
90 | if (v->_cmp == NULL) | |
86f5fa78 | 91 | return git__throw(GIT_ENOTFOUND, "Can't sort vector. No comparison function set"); |
48c27f86 | 92 | |
86d7e1ca VM |
93 | git_vector_sort(v); |
94 | ||
de18f276 | 95 | find = git__bsearch(key, v->contents, v->length, key_lookup); |
86d7e1ca VM |
96 | if (find != NULL) |
97 | return (int)(find - v->contents); | |
98 | ||
86f5fa78 | 99 | return git__throw(GIT_ENOTFOUND, "Can't find element"); |
86d7e1ca VM |
100 | } |
101 | ||
102 | int git_vector_search2(git_vector *v, git_vector_cmp key_lookup, const void *key) | |
103 | { | |
104 | unsigned int i; | |
105 | ||
106 | assert(v && key && key_lookup); | |
107 | ||
108 | for (i = 0; i < v->length; ++i) { | |
109 | if (key_lookup(key, v->contents[i]) == 0) | |
110 | return i; | |
111 | } | |
112 | ||
86f5fa78 | 113 | return git__throw(GIT_ENOTFOUND, "Can't find element"); |
86d7e1ca VM |
114 | } |
115 | ||
48c27f86 | 116 | static int strict_comparison(const void *a, const void *b) |
86d7e1ca | 117 | { |
3c41c635 | 118 | return (a == b) ? 0 : -1; |
48c27f86 | 119 | } |
c4034e63 | 120 | |
48c27f86 VM |
121 | int git_vector_search(git_vector *v, const void *entry) |
122 | { | |
123 | return git_vector_search2(v, v->_cmp ? v->_cmp : strict_comparison, entry); | |
86d7e1ca VM |
124 | } |
125 | ||
126 | int git_vector_bsearch(git_vector *v, const void *key) | |
127 | { | |
86d7e1ca | 128 | return git_vector_bsearch2(v, v->_cmp, key); |
c4034e63 VM |
129 | } |
130 | ||
131 | int git_vector_remove(git_vector *v, unsigned int idx) | |
132 | { | |
133 | unsigned int i; | |
134 | ||
135 | assert(v); | |
136 | ||
137 | if (idx >= v->length || v->length == 0) | |
86f5fa78 | 138 | return git__throw(GIT_ENOTFOUND, "Can't remove element. Index out of bounds"); |
c4034e63 | 139 | |
a17777d1 | 140 | for (i = idx; i < v->length - 1; ++i) |
c4034e63 VM |
141 | v->contents[i] = v->contents[i + 1]; |
142 | ||
143 | v->length--; | |
144 | return GIT_SUCCESS; | |
145 | } | |
146 | ||
476c42ac KS |
147 | void git_vector_uniq(git_vector *v) |
148 | { | |
149 | git_vector_cmp cmp; | |
150 | unsigned int i, j; | |
151 | ||
152 | if (v->length <= 1) | |
153 | return; | |
154 | ||
155 | git_vector_sort(v); | |
156 | cmp = v->_cmp ? v->_cmp : strict_comparison; | |
157 | ||
158 | for (i = 0, j = 1 ; j < v->length; ++j) | |
de18f276 | 159 | if (!cmp(v->contents[i], v->contents[j])) |
476c42ac KS |
160 | v->contents[i] = v->contents[j]; |
161 | else | |
162 | v->contents[++i] = v->contents[j]; | |
163 | ||
164 | v->length -= j - i - 1; | |
165 | } | |
166 | ||
c4034e63 VM |
167 | void git_vector_clear(git_vector *v) |
168 | { | |
169 | assert(v); | |
170 | v->length = 0; | |
86d7e1ca | 171 | v->sorted = 1; |
c4034e63 VM |
172 | } |
173 | ||
174 |