]>
Commit | Line | Data |
---|---|---|
bb742ede | 1 | /* |
359fc2d2 | 2 | * Copyright (C) the libgit2 contributors. All rights reserved. |
bb742ede VM |
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 | */ | |
eae0bfdc PP |
7 | |
8 | #include "util.h" | |
9 | ||
64a47c01 SP |
10 | #include "common.h" |
11 | ||
e069c621 | 12 | #ifdef GIT_WIN32 |
4b3ec53c | 13 | # include "win32/utf-conv.h" |
eba784d2 | 14 | # include "win32/w32_buffer.h" |
4b3ec53c XL |
15 | |
16 | # ifdef HAVE_QSORT_S | |
17 | # include <search.h> | |
18 | # endif | |
e069c621 ET |
19 | #endif |
20 | ||
ae2e4c6a | 21 | #ifdef _MSC_VER |
63f91e1c | 22 | # include <Shlwapi.h> |
63f91e1c CMN |
23 | #endif |
24 | ||
955f9ae9 VM |
25 | void git_strarray_free(git_strarray *array) |
26 | { | |
27 | size_t i; | |
2fcc0d07 BR |
28 | |
29 | if (array == NULL) | |
30 | return; | |
31 | ||
955f9ae9 | 32 | for (i = 0; i < array->count; ++i) |
3286c408 | 33 | git__free(array->strings[i]); |
955f9ae9 | 34 | |
3286c408 | 35 | git__free(array->strings); |
5540d947 RB |
36 | |
37 | memset(array, 0, sizeof(*array)); | |
955f9ae9 VM |
38 | } |
39 | ||
14a513e0 RB |
40 | int git_strarray_copy(git_strarray *tgt, const git_strarray *src) |
41 | { | |
42 | size_t i; | |
43 | ||
32460251 | 44 | assert(tgt && src); |
14a513e0 RB |
45 | |
46 | memset(tgt, 0, sizeof(*tgt)); | |
47 | ||
32460251 | 48 | if (!src->count) |
14a513e0 RB |
49 | return 0; |
50 | ||
32460251 | 51 | tgt->strings = git__calloc(src->count, sizeof(char *)); |
14a513e0 RB |
52 | GITERR_CHECK_ALLOC(tgt->strings); |
53 | ||
32460251 RB |
54 | for (i = 0; i < src->count; ++i) { |
55 | if (!src->strings[i]) | |
5540d947 | 56 | continue; |
14a513e0 | 57 | |
32460251 | 58 | tgt->strings[tgt->count] = git__strdup(src->strings[i]); |
14a513e0 RB |
59 | if (!tgt->strings[tgt->count]) { |
60 | git_strarray_free(tgt); | |
32460251 | 61 | memset(tgt, 0, sizeof(*tgt)); |
14a513e0 RB |
62 | return -1; |
63 | } | |
64 | ||
65 | tgt->count++; | |
66 | } | |
67 | ||
68 | return 0; | |
69 | } | |
70 | ||
d34f6826 | 71 | int git__strntol64(int64_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base) |
c6e65aca VM |
72 | { |
73 | const char *p; | |
fafd4710 | 74 | int64_t n, nn; |
c6e65aca VM |
75 | int c, ovfl, v, neg, ndig; |
76 | ||
77 | p = nptr; | |
78 | neg = 0; | |
79 | n = 0; | |
80 | ndig = 0; | |
81 | ovfl = 0; | |
82 | ||
83 | /* | |
84 | * White space | |
85 | */ | |
0f49200c | 86 | while (git__isspace(*p)) |
c6e65aca VM |
87 | p++; |
88 | ||
89 | /* | |
90 | * Sign | |
91 | */ | |
92 | if (*p == '-' || *p == '+') | |
93 | if (*p++ == '-') | |
94 | neg = 1; | |
95 | ||
96 | /* | |
97 | * Base | |
98 | */ | |
99 | if (base == 0) { | |
100 | if (*p != '0') | |
101 | base = 10; | |
102 | else { | |
103 | base = 8; | |
104 | if (p[1] == 'x' || p[1] == 'X') { | |
105 | p += 2; | |
106 | base = 16; | |
107 | } | |
108 | } | |
109 | } else if (base == 16 && *p == '0') { | |
110 | if (p[1] == 'x' || p[1] == 'X') | |
111 | p += 2; | |
112 | } else if (base < 0 || 36 < base) | |
113 | goto Return; | |
114 | ||
115 | /* | |
116 | * Non-empty sequence of digits | |
117 | */ | |
d34f6826 | 118 | for (; nptr_len > 0; p++,ndig++,nptr_len--) { |
c6e65aca VM |
119 | c = *p; |
120 | v = base; | |
121 | if ('0'<=c && c<='9') | |
122 | v = c - '0'; | |
123 | else if ('a'<=c && c<='z') | |
124 | v = c - 'a' + 10; | |
125 | else if ('A'<=c && c<='Z') | |
126 | v = c - 'A' + 10; | |
127 | if (v >= base) | |
128 | break; | |
6c7cee42 RD |
129 | v = neg ? -v : v; |
130 | if (n > INT64_MAX / base || n < INT64_MIN / base) { | |
c6e65aca | 131 | ovfl = 1; |
6c7cee42 RD |
132 | /* Keep on iterating until the end of this number */ |
133 | continue; | |
134 | } | |
135 | nn = n * base; | |
136 | if ((v > 0 && nn > INT64_MAX - v) || | |
137 | (v < 0 && nn < INT64_MIN - v)) { | |
138 | ovfl = 1; | |
139 | /* Keep on iterating until the end of this number */ | |
140 | continue; | |
141 | } | |
142 | n = nn + v; | |
c6e65aca VM |
143 | } |
144 | ||
145 | Return: | |
7c7ff7d1 | 146 | if (ndig == 0) { |
909d5494 | 147 | giterr_set(GITERR_INVALID, "failed to convert string to long: not a number"); |
7c7ff7d1 RB |
148 | return -1; |
149 | } | |
c6e65aca VM |
150 | |
151 | if (endptr) | |
152 | *endptr = p; | |
153 | ||
7c7ff7d1 | 154 | if (ovfl) { |
909d5494 | 155 | giterr_set(GITERR_INVALID, "failed to convert string to long: overflow error"); |
7c7ff7d1 RB |
156 | return -1; |
157 | } | |
c6e65aca | 158 | |
70b9b841 | 159 | *result = n; |
7c7ff7d1 | 160 | return 0; |
c6e65aca VM |
161 | } |
162 | ||
d34f6826 | 163 | int git__strntol32(int32_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base) |
ad196c6a | 164 | { |
6c7cee42 | 165 | const char *tmp_endptr; |
fafd4710 VM |
166 | int32_t tmp_int; |
167 | int64_t tmp_long; | |
6c7cee42 | 168 | int error; |
ad196c6a | 169 | |
6c7cee42 | 170 | if ((error = git__strntol64(&tmp_long, nptr, nptr_len, &tmp_endptr, base)) < 0) |
ad196c6a | 171 | return error; |
172 | ||
173 | tmp_int = tmp_long & 0xFFFFFFFF; | |
7c7ff7d1 | 174 | if (tmp_int != tmp_long) { |
6c7cee42 RD |
175 | int len = tmp_endptr - nptr; |
176 | giterr_set(GITERR_INVALID, "failed to convert: '%.*s' is too large", len, nptr); | |
7c7ff7d1 RB |
177 | return -1; |
178 | } | |
ad196c6a | 179 | |
180 | *result = tmp_int; | |
6c7cee42 RD |
181 | if (endptr) |
182 | *endptr = tmp_endptr; | |
7c7ff7d1 | 183 | |
ad196c6a | 184 | return error; |
185 | } | |
186 | ||
a277345e RB |
187 | int git__strcmp(const char *a, const char *b) |
188 | { | |
189 | while (*a && *b && *a == *b) | |
190 | ++a, ++b; | |
191 | return (int)(*(const unsigned char *)a) - (int)(*(const unsigned char *)b); | |
192 | } | |
193 | ||
194 | int git__strcasecmp(const char *a, const char *b) | |
195 | { | |
75a4636f | 196 | while (*a && *b && git__tolower(*a) == git__tolower(*b)) |
a277345e | 197 | ++a, ++b; |
75a4636f | 198 | return ((unsigned char)git__tolower(*a) - (unsigned char)git__tolower(*b)); |
a277345e RB |
199 | } |
200 | ||
e3b4a47c ET |
201 | int git__strcasesort_cmp(const char *a, const char *b) |
202 | { | |
203 | int cmp = 0; | |
204 | ||
e3b4a47c | 205 | while (*a && *b) { |
c9b18018 | 206 | if (*a != *b) { |
75a4636f | 207 | if (git__tolower(*a) != git__tolower(*b)) |
c9b18018 RB |
208 | break; |
209 | /* use case in sort order even if not in equivalence */ | |
e3b4a47c | 210 | if (!cmp) |
c9b18018 RB |
211 | cmp = (int)(*(const uint8_t *)a) - (int)(*(const uint8_t *)b); |
212 | } | |
e3b4a47c ET |
213 | |
214 | ++a, ++b; | |
215 | } | |
216 | ||
217 | if (*a || *b) | |
75a4636f | 218 | return (unsigned char)git__tolower(*a) - (unsigned char)git__tolower(*b); |
e3b4a47c ET |
219 | |
220 | return cmp; | |
221 | } | |
222 | ||
a277345e RB |
223 | int git__strncmp(const char *a, const char *b, size_t sz) |
224 | { | |
225 | while (sz && *a && *b && *a == *b) | |
226 | --sz, ++a, ++b; | |
227 | if (!sz) | |
228 | return 0; | |
229 | return (int)(*(const unsigned char *)a) - (int)(*(const unsigned char *)b); | |
230 | } | |
231 | ||
232 | int git__strncasecmp(const char *a, const char *b, size_t sz) | |
233 | { | |
0db4cd04 | 234 | int al, bl; |
91e7d263 | 235 | |
0db4cd04 | 236 | do { |
75a4636f ET |
237 | al = (unsigned char)git__tolower(*a); |
238 | bl = (unsigned char)git__tolower(*b); | |
0db4cd04 PK |
239 | ++a, ++b; |
240 | } while (--sz && al && al == bl); | |
91e7d263 | 241 | |
0db4cd04 | 242 | return al - bl; |
a277345e RB |
243 | } |
244 | ||
26e74c6a | 245 | void git__strntolower(char *str, size_t len) |
0da2c700 | 246 | { |
26e74c6a | 247 | size_t i; |
0da2c700 VM |
248 | |
249 | for (i = 0; i < len; ++i) { | |
75a4636f | 250 | str[i] = (char)git__tolower(str[i]); |
0da2c700 VM |
251 | } |
252 | } | |
253 | ||
254 | void git__strtolower(char *str) | |
255 | { | |
256 | git__strntolower(str, strlen(str)); | |
257 | } | |
258 | ||
eae0bfdc | 259 | GIT_INLINE(int) prefixcmp(const char *str, size_t str_n, const char *prefix, bool icase) |
9eb79764 | 260 | { |
eae0bfdc PP |
261 | int s, p; |
262 | ||
263 | while (str_n--) { | |
264 | s = (unsigned char)*str++; | |
265 | p = (unsigned char)*prefix++; | |
266 | ||
267 | if (icase) { | |
268 | s = git__tolower(s); | |
269 | p = git__tolower(p); | |
270 | } | |
271 | ||
9eb79764 SP |
272 | if (!p) |
273 | return 0; | |
eae0bfdc PP |
274 | |
275 | if (s != p) | |
9eb79764 SP |
276 | return s - p; |
277 | } | |
eae0bfdc PP |
278 | |
279 | return (0 - *prefix); | |
9eb79764 SP |
280 | } |
281 | ||
eae0bfdc | 282 | int git__prefixcmp(const char *str, const char *prefix) |
ec40b7f9 | 283 | { |
eae0bfdc | 284 | return prefixcmp(str, SIZE_MAX, prefix, false); |
ec40b7f9 PK |
285 | } |
286 | ||
eae0bfdc | 287 | int git__prefixncmp(const char *str, size_t str_n, const char *prefix) |
a64119e3 | 288 | { |
eae0bfdc PP |
289 | return prefixcmp(str, str_n, prefix, false); |
290 | } | |
a64119e3 | 291 | |
eae0bfdc PP |
292 | int git__prefixcmp_icase(const char *str, const char *prefix) |
293 | { | |
294 | return prefixcmp(str, SIZE_MAX, prefix, true); | |
295 | } | |
a64119e3 | 296 | |
eae0bfdc PP |
297 | int git__prefixncmp_icase(const char *str, size_t str_n, const char *prefix) |
298 | { | |
299 | return prefixcmp(str, str_n, prefix, true); | |
a64119e3 ET |
300 | } |
301 | ||
9eb79764 SP |
302 | int git__suffixcmp(const char *str, const char *suffix) |
303 | { | |
304 | size_t a = strlen(str); | |
305 | size_t b = strlen(suffix); | |
306 | if (a < b) | |
307 | return -1; | |
308 | return strcmp(str + (a - b), suffix); | |
309 | } | |
ced645ea | 310 | |
0291b5b7 | 311 | char *git__strtok(char **end, const char *sep) |
f725931b | 312 | { |
0291b5b7 | 313 | char *ptr = *end; |
ced645ea | 314 | |
0291b5b7 VM |
315 | while (*ptr && strchr(sep, *ptr)) |
316 | ++ptr; | |
f725931b | 317 | |
0291b5b7 VM |
318 | if (*ptr) { |
319 | char *start = ptr; | |
320 | *end = start + 1; | |
ced645ea | 321 | |
0291b5b7 VM |
322 | while (**end && !strchr(sep, **end)) |
323 | ++*end; | |
f725931b | 324 | |
0291b5b7 VM |
325 | if (**end) { |
326 | **end = '\0'; | |
327 | ++*end; | |
328 | } | |
329 | ||
330 | return start; | |
331 | } | |
332 | ||
333 | return NULL; | |
ced645ea RJ |
334 | } |
335 | ||
7fcec834 ET |
336 | /* Similar to strtok, but does not collapse repeated tokens. */ |
337 | char *git__strsep(char **end, const char *sep) | |
338 | { | |
339 | char *start = *end, *ptr = *end; | |
340 | ||
341 | while (*ptr && !strchr(sep, *ptr)) | |
342 | ++ptr; | |
343 | ||
344 | if (*ptr) { | |
345 | *end = ptr + 1; | |
346 | *ptr = '\0'; | |
347 | ||
348 | return start; | |
349 | } | |
350 | ||
351 | return NULL; | |
352 | } | |
353 | ||
d34f6826 ET |
354 | size_t git__linenlen(const char *buffer, size_t buffer_len) |
355 | { | |
356 | char *nl = memchr(buffer, '\n', buffer_len); | |
357 | return nl ? (size_t)(nl - buffer) + 1 : buffer_len; | |
358 | } | |
359 | ||
6c7cee42 RD |
360 | /* |
361 | * Adapted Not So Naive algorithm from http://www-igm.univ-mlv.fr/~lecroq/string/ | |
362 | */ | |
363 | const void * git__memmem(const void *haystack, size_t haystacklen, | |
364 | const void *needle, size_t needlelen) | |
365 | { | |
366 | const char *h, *n; | |
367 | size_t j, k, l; | |
368 | ||
369 | if (needlelen > haystacklen || !haystacklen || !needlelen) | |
370 | return NULL; | |
371 | ||
372 | h = (const char *) haystack, | |
373 | n = (const char *) needle; | |
374 | ||
375 | if (needlelen == 1) | |
376 | return memchr(haystack, *n, haystacklen); | |
377 | ||
378 | if (n[0] == n[1]) { | |
379 | k = 2; | |
380 | l = 1; | |
381 | } else { | |
382 | k = 1; | |
383 | l = 2; | |
384 | } | |
385 | ||
386 | j = 0; | |
387 | while (j <= haystacklen - needlelen) { | |
388 | if (n[1] != h[j + 1]) { | |
389 | j += k; | |
390 | } else { | |
391 | if (memcmp(n + 2, h + j + 2, needlelen - 2) == 0 && | |
392 | n[0] == h[j]) | |
393 | return h + j; | |
394 | j += l; | |
395 | } | |
396 | } | |
397 | ||
398 | return NULL; | |
399 | } | |
400 | ||
0e465f97 VM |
401 | void git__hexdump(const char *buffer, size_t len) |
402 | { | |
403 | static const size_t LINE_WIDTH = 16; | |
404 | ||
405 | size_t line_count, last_line, i, j; | |
406 | const char *line; | |
407 | ||
408 | line_count = (len / LINE_WIDTH); | |
409 | last_line = (len % LINE_WIDTH); | |
410 | ||
411 | for (i = 0; i < line_count; ++i) { | |
412 | line = buffer + (i * LINE_WIDTH); | |
413 | for (j = 0; j < LINE_WIDTH; ++j, ++line) | |
414 | printf("%02X ", (unsigned char)*line & 0xFF); | |
415 | ||
416 | printf("| "); | |
417 | ||
418 | line = buffer + (i * LINE_WIDTH); | |
419 | for (j = 0; j < LINE_WIDTH; ++j, ++line) | |
420 | printf("%c", (*line >= 32 && *line <= 126) ? *line : '.'); | |
421 | ||
422 | printf("\n"); | |
423 | } | |
424 | ||
425 | if (last_line > 0) { | |
426 | ||
427 | line = buffer + (line_count * LINE_WIDTH); | |
428 | for (j = 0; j < last_line; ++j, ++line) | |
429 | printf("%02X ", (unsigned char)*line & 0xFF); | |
430 | ||
431 | for (j = 0; j < (LINE_WIDTH - last_line); ++j) | |
87d9869f | 432 | printf(" "); |
0e465f97 VM |
433 | |
434 | printf("| "); | |
435 | ||
436 | line = buffer + (line_count * LINE_WIDTH); | |
437 | for (j = 0; j < last_line; ++j, ++line) | |
438 | printf("%c", (*line >= 32 && *line <= 126) ? *line : '.'); | |
439 | ||
440 | printf("\n"); | |
441 | } | |
442 | ||
443 | printf("\n"); | |
444 | } | |
e0646b38 VM |
445 | |
446 | #ifdef GIT_LEGACY_HASH | |
447 | uint32_t git__hash(const void *key, int len, unsigned int seed) | |
448 | { | |
449 | const uint32_t m = 0x5bd1e995; | |
450 | const int r = 24; | |
451 | uint32_t h = seed ^ len; | |
452 | ||
453 | const unsigned char *data = (const unsigned char *)key; | |
454 | ||
455 | while(len >= 4) { | |
456 | uint32_t k = *(uint32_t *)data; | |
457 | ||
932d1baf KS |
458 | k *= m; |
459 | k ^= k >> r; | |
460 | k *= m; | |
461 | ||
462 | h *= m; | |
e0646b38 VM |
463 | h ^= k; |
464 | ||
465 | data += 4; | |
466 | len -= 4; | |
467 | } | |
932d1baf | 468 | |
e0646b38 VM |
469 | switch(len) { |
470 | case 3: h ^= data[2] << 16; | |
471 | case 2: h ^= data[1] << 8; | |
472 | case 1: h ^= data[0]; | |
87d9869f | 473 | h *= m; |
e0646b38 VM |
474 | }; |
475 | ||
476 | h ^= h >> 13; | |
477 | h *= m; | |
478 | h ^= h >> 15; | |
479 | ||
480 | return h; | |
932d1baf | 481 | } |
e0646b38 VM |
482 | #else |
483 | /* | |
484 | Cross-platform version of Murmurhash3 | |
485 | http://code.google.com/p/smhasher/wiki/MurmurHash3 | |
486 | by Austin Appleby (aappleby@gmail.com) | |
487 | ||
488 | This code is on the public domain. | |
489 | */ | |
490 | uint32_t git__hash(const void *key, int len, uint32_t seed) | |
491 | { | |
492 | ||
493 | #define MURMUR_BLOCK() {\ | |
87d9869f VM |
494 | k1 *= c1; \ |
495 | k1 = git__rotl(k1,11);\ | |
496 | k1 *= c2;\ | |
497 | h1 ^= k1;\ | |
498 | h1 = h1*3 + 0x52dce729;\ | |
499 | c1 = c1*5 + 0x7b7d159c;\ | |
500 | c2 = c2*5 + 0x6bce6396;\ | |
e0646b38 VM |
501 | } |
502 | ||
503 | const uint8_t *data = (const uint8_t*)key; | |
504 | const int nblocks = len / 4; | |
505 | ||
506 | const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4); | |
507 | const uint8_t *tail = (const uint8_t *)(data + nblocks * 4); | |
508 | ||
509 | uint32_t h1 = 0x971e137b ^ seed; | |
510 | uint32_t k1; | |
511 | ||
512 | uint32_t c1 = 0x95543787; | |
513 | uint32_t c2 = 0x2ad7eb25; | |
514 | ||
515 | int i; | |
516 | ||
517 | for (i = -nblocks; i; i++) { | |
518 | k1 = blocks[i]; | |
519 | MURMUR_BLOCK(); | |
520 | } | |
521 | ||
522 | k1 = 0; | |
523 | ||
524 | switch(len & 3) { | |
525 | case 3: k1 ^= tail[2] << 16; | |
eae0bfdc | 526 | /* fall through */ |
e0646b38 | 527 | case 2: k1 ^= tail[1] << 8; |
eae0bfdc | 528 | /* fall through */ |
e0646b38 | 529 | case 1: k1 ^= tail[0]; |
eae0bfdc | 530 | MURMUR_BLOCK(); |
e0646b38 VM |
531 | } |
532 | ||
533 | h1 ^= len; | |
534 | h1 ^= h1 >> 16; | |
535 | h1 *= 0x85ebca6b; | |
536 | h1 ^= h1 >> 13; | |
537 | h1 *= 0xc2b2ae35; | |
538 | h1 ^= h1 >> 16; | |
539 | ||
540 | return h1; | |
932d1baf | 541 | } |
e0646b38 | 542 | #endif |
c20ffa61 | 543 | |
de18f276 VM |
544 | /** |
545 | * A modified `bsearch` from the BSD glibc. | |
546 | * | |
547 | * Copyright (c) 1990 Regents of the University of California. | |
548 | * All rights reserved. | |
0470f8fc MW |
549 | * Redistribution and use in source and binary forms, with or without |
550 | * modification, are permitted provided that the following conditions | |
551 | * are met: | |
552 | * 1. Redistributions of source code must retain the above copyright | |
553 | * notice, this list of conditions and the following disclaimer. | |
554 | * 2. Redistributions in binary form must reproduce the above copyright | |
555 | * notice, this list of conditions and the following disclaimer in the | |
556 | * documentation and/or other materials provided with the distribution. | |
557 | * 3. [rescinded 22 July 1999] | |
558 | * 4. Neither the name of the University nor the names of its contributors | |
559 | * may be used to endorse or promote products derived from this software | |
560 | * without specific prior written permission. | |
561 | * | |
562 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
563 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
564 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
565 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
566 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
567 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
568 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
569 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
570 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
571 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
572 | * SUCH DAMAGE. | |
851ad650 | 573 | */ |
bd370b14 RB |
574 | int git__bsearch( |
575 | void **array, | |
576 | size_t array_len, | |
577 | const void *key, | |
578 | int (*compare)(const void *, const void *), | |
579 | size_t *position) | |
c20ffa61 | 580 | { |
11d9f6b3 | 581 | size_t lim; |
44ef8b1b | 582 | int cmp = -1; |
bd370b14 RB |
583 | void **part, **base = array; |
584 | ||
11d9f6b3 | 585 | for (lim = array_len; lim != 0; lim >>= 1) { |
bd370b14 RB |
586 | part = base + (lim >> 1); |
587 | cmp = (*compare)(key, *part); | |
588 | if (cmp == 0) { | |
ae9e29fd RB |
589 | base = part; |
590 | break; | |
591 | } | |
592 | if (cmp > 0) { /* key > p; take right partition */ | |
bd370b14 RB |
593 | base = part + 1; |
594 | lim--; | |
595 | } /* else take left partition */ | |
596 | } | |
597 | ||
ae9e29fd RB |
598 | if (position) |
599 | *position = (base - array); | |
851ad650 | 600 | |
11d9f6b3 | 601 | return (cmp == 0) ? 0 : GIT_ENOTFOUND; |
851ad650 RB |
602 | } |
603 | ||
604 | int git__bsearch_r( | |
605 | void **array, | |
606 | size_t array_len, | |
607 | const void *key, | |
608 | int (*compare_r)(const void *, const void *, void *), | |
609 | void *payload, | |
610 | size_t *position) | |
611 | { | |
11d9f6b3 | 612 | size_t lim; |
851ad650 RB |
613 | int cmp = -1; |
614 | void **part, **base = array; | |
615 | ||
11d9f6b3 | 616 | for (lim = array_len; lim != 0; lim >>= 1) { |
851ad650 RB |
617 | part = base + (lim >> 1); |
618 | cmp = (*compare_r)(key, *part, payload); | |
619 | if (cmp == 0) { | |
620 | base = part; | |
621 | break; | |
622 | } | |
623 | if (cmp > 0) { /* key > p; take right partition */ | |
624 | base = part + 1; | |
625 | lim--; | |
626 | } /* else take left partition */ | |
627 | } | |
628 | ||
629 | if (position) | |
630 | *position = (base - array); | |
ae9e29fd | 631 | |
11d9f6b3 | 632 | return (cmp == 0) ? 0 : GIT_ENOTFOUND; |
c20ffa61 KS |
633 | } |
634 | ||
d1f34693 | 635 | /** |
636 | * A strcmp wrapper | |
16248ee2 | 637 | * |
d1f34693 | 638 | * We don't want direct pointers to the CRT on Windows, we may |
639 | * get stdcall conflicts. | |
640 | */ | |
641 | int git__strcmp_cb(const void *a, const void *b) | |
642 | { | |
3b4c401a RB |
643 | return strcmp((const char *)a, (const char *)b); |
644 | } | |
d1f34693 | 645 | |
3b4c401a RB |
646 | int git__strcasecmp_cb(const void *a, const void *b) |
647 | { | |
648 | return strcasecmp((const char *)a, (const char *)b); | |
84dd3820 | 649 | } |
29e948de VM |
650 | |
651 | int git__parse_bool(int *out, const char *value) | |
652 | { | |
653 | /* A missing value means true */ | |
47db054d CMN |
654 | if (value == NULL || |
655 | !strcasecmp(value, "true") || | |
29e948de VM |
656 | !strcasecmp(value, "yes") || |
657 | !strcasecmp(value, "on")) { | |
658 | *out = 1; | |
659 | return 0; | |
660 | } | |
661 | if (!strcasecmp(value, "false") || | |
662 | !strcasecmp(value, "no") || | |
47db054d CMN |
663 | !strcasecmp(value, "off") || |
664 | value[0] == '\0') { | |
29e948de VM |
665 | *out = 0; |
666 | return 0; | |
667 | } | |
668 | ||
669 | return -1; | |
670 | } | |
02a0d651 | 671 | |
672 | size_t git__unescape(char *str) | |
673 | { | |
674 | char *scan, *pos = str; | |
675 | ||
a9f51e43 RB |
676 | if (!str) |
677 | return 0; | |
678 | ||
02a0d651 | 679 | for (scan = str; *scan; pos++, scan++) { |
680 | if (*scan == '\\' && *(scan + 1) != '\0') | |
681 | scan++; /* skip '\' but include next char */ | |
682 | if (pos != scan) | |
683 | *pos = *scan; | |
684 | } | |
685 | ||
686 | if (pos != scan) { | |
687 | *pos = '\0'; | |
688 | } | |
689 | ||
690 | return (pos - str); | |
691 | } | |
e40f1c2d | 692 | |
6c7cee42 | 693 | #if defined(HAVE_QSORT_S) || defined(HAVE_QSORT_R_BSD) |
e40f1c2d | 694 | typedef struct { |
62beacd3 | 695 | git__sort_r_cmp cmp; |
e40f1c2d RB |
696 | void *payload; |
697 | } git__qsort_r_glue; | |
698 | ||
699 | static int GIT_STDLIB_CALL git__qsort_r_glue_cmp( | |
700 | void *payload, const void *a, const void *b) | |
701 | { | |
702 | git__qsort_r_glue *glue = payload; | |
703 | return glue->cmp(a, b, glue->payload); | |
704 | } | |
705 | #endif | |
706 | ||
707 | void git__qsort_r( | |
62beacd3 | 708 | void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload) |
e40f1c2d | 709 | { |
6c7cee42 | 710 | #if defined(HAVE_QSORT_R_BSD) |
e40f1c2d RB |
711 | git__qsort_r_glue glue = { cmp, payload }; |
712 | qsort_r(els, nel, elsize, &glue, git__qsort_r_glue_cmp); | |
6c7cee42 | 713 | #elif defined(HAVE_QSORT_R_GNU) |
e40f1c2d | 714 | qsort_r(els, nel, elsize, cmp, payload); |
e683d152 ET |
715 | #elif defined(HAVE_QSORT_S) |
716 | git__qsort_r_glue glue = { cmp, payload }; | |
717 | qsort_s(els, nel, elsize, git__qsort_r_glue_cmp, &glue); | |
718 | #else | |
719 | git__insertsort_r(els, nel, elsize, NULL, cmp, payload); | |
e40f1c2d | 720 | #endif |
62beacd3 RB |
721 | } |
722 | ||
723 | void git__insertsort_r( | |
724 | void *els, size_t nel, size_t elsize, void *swapel, | |
725 | git__sort_r_cmp cmp, void *payload) | |
726 | { | |
ad003763 VM |
727 | uint8_t *base = els; |
728 | uint8_t *end = base + nel * elsize; | |
62beacd3 RB |
729 | uint8_t *i, *j; |
730 | bool freeswap = !swapel; | |
731 | ||
732 | if (freeswap) | |
733 | swapel = git__malloc(elsize); | |
734 | ||
735 | for (i = base + elsize; i < end; i += elsize) | |
736 | for (j = i; j > base && cmp(j, j - elsize, payload) < 0; j -= elsize) { | |
737 | memcpy(swapel, j, elsize); | |
738 | memcpy(j, j - elsize, elsize); | |
739 | memcpy(j - elsize, swapel, elsize); | |
740 | } | |
741 | ||
742 | if (freeswap) | |
743 | git__free(swapel); | |
e40f1c2d | 744 | } |
8e35527d | 745 | |
ec510666 ET |
746 | /* |
747 | * git__utf8_iterate is taken from the utf8proc project, | |
748 | * http://www.public-software-group.org/utf8proc | |
749 | * | |
750 | * Copyright (c) 2009 Public Software Group e. V., Berlin, Germany | |
751 | * | |
752 | * Permission is hereby granted, free of charge, to any person obtaining a | |
753 | * copy of this software and associated documentation files (the ""Software""), | |
754 | * to deal in the Software without restriction, including without limitation | |
755 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, | |
756 | * and/or sell copies of the Software, and to permit persons to whom the | |
757 | * Software is furnished to do so, subject to the following conditions: | |
758 | * | |
759 | * The above copyright notice and this permission notice shall be included in | |
760 | * all copies or substantial portions of the Software. | |
761 | * | |
762 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
763 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
764 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
765 | * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
766 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING | |
767 | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER | |
768 | * DEALINGS IN THE SOFTWARE. | |
769 | */ | |
770 | ||
8e35527d VM |
771 | static const int8_t utf8proc_utf8class[256] = { |
772 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
773 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
774 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
775 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
776 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
777 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
778 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
779 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
780 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
781 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
782 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
783 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
784 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, | |
785 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, | |
786 | 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, | |
787 | 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0 | |
788 | }; | |
789 | ||
790 | int git__utf8_charlen(const uint8_t *str, int str_len) | |
791 | { | |
792 | int length, i; | |
793 | ||
794 | length = utf8proc_utf8class[str[0]]; | |
795 | if (!length) | |
796 | return -1; | |
797 | ||
798 | if (str_len >= 0 && length > str_len) | |
799 | return -str_len; | |
800 | ||
801 | for (i = 1; i < length; i++) { | |
802 | if ((str[i] & 0xC0) != 0x80) | |
803 | return -i; | |
804 | } | |
805 | ||
806 | return length; | |
807 | } | |
808 | ||
809 | int git__utf8_iterate(const uint8_t *str, int str_len, int32_t *dst) | |
810 | { | |
811 | int length; | |
812 | int32_t uc = -1; | |
813 | ||
814 | *dst = -1; | |
815 | length = git__utf8_charlen(str, str_len); | |
816 | if (length < 0) | |
817 | return -1; | |
818 | ||
819 | switch (length) { | |
820 | case 1: | |
821 | uc = str[0]; | |
822 | break; | |
823 | case 2: | |
824 | uc = ((str[0] & 0x1F) << 6) + (str[1] & 0x3F); | |
825 | if (uc < 0x80) uc = -1; | |
826 | break; | |
827 | case 3: | |
828 | uc = ((str[0] & 0x0F) << 12) + ((str[1] & 0x3F) << 6) | |
829 | + (str[2] & 0x3F); | |
830 | if (uc < 0x800 || (uc >= 0xD800 && uc < 0xE000) || | |
831 | (uc >= 0xFDD0 && uc < 0xFDF0)) uc = -1; | |
832 | break; | |
833 | case 4: | |
834 | uc = ((str[0] & 0x07) << 18) + ((str[1] & 0x3F) << 12) | |
835 | + ((str[2] & 0x3F) << 6) + (str[3] & 0x3F); | |
836 | if (uc < 0x10000 || uc >= 0x110000) uc = -1; | |
837 | break; | |
838 | } | |
839 | ||
840 | if (uc < 0 || ((uc & 0xFFFF) >= 0xFFFE)) | |
841 | return -1; | |
842 | ||
843 | *dst = uc; | |
844 | return length; | |
845 | } | |
e069c621 | 846 | |
2749ff46 VM |
847 | double git_time_monotonic(void) |
848 | { | |
849 | return git__timer(); | |
850 | } | |
851 | ||
e069c621 ET |
852 | #ifdef GIT_WIN32 |
853 | int git__getenv(git_buf *out, const char *name) | |
854 | { | |
855 | wchar_t *wide_name = NULL, *wide_value = NULL; | |
856 | DWORD value_len; | |
857 | int error = -1; | |
858 | ||
859 | git_buf_clear(out); | |
860 | ||
861 | if (git__utf8_to_16_alloc(&wide_name, name) < 0) | |
862 | return -1; | |
863 | ||
864 | if ((value_len = GetEnvironmentVariableW(wide_name, NULL, 0)) > 0) { | |
865 | wide_value = git__malloc(value_len * sizeof(wchar_t)); | |
866 | GITERR_CHECK_ALLOC(wide_value); | |
867 | ||
868 | value_len = GetEnvironmentVariableW(wide_name, wide_value, value_len); | |
869 | } | |
870 | ||
871 | if (value_len) | |
872 | error = git_buf_put_w(out, wide_value, value_len); | |
873 | else if (GetLastError() == ERROR_ENVVAR_NOT_FOUND) | |
874 | error = GIT_ENOTFOUND; | |
875 | else | |
876 | giterr_set(GITERR_OS, "could not read environment variable '%s'", name); | |
877 | ||
878 | git__free(wide_name); | |
879 | git__free(wide_value); | |
880 | return error; | |
881 | } | |
882 | #else | |
883 | int git__getenv(git_buf *out, const char *name) | |
884 | { | |
885 | const char *val = getenv(name); | |
886 | ||
887 | git_buf_clear(out); | |
888 | ||
889 | if (!val) | |
890 | return GIT_ENOTFOUND; | |
891 | ||
892 | return git_buf_puts(out, val); | |
893 | } | |
894 | #endif |