]>
git.proxmox.com Git - libgit2.git/blob - src/util.c
2 * Copyright (C) the libgit2 contributors. All rights reserved.
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.
13 # include "win32/utf-conv.h"
14 # include "win32/w32_buffer.h"
16 # ifndef WIN32_LEAN_AND_MEAN
17 # define WIN32_LEAN_AND_MEAN
30 #if defined(hpux) || defined(__hpux) || defined(_hpux)
31 # include <sys/pstat.h>
34 int git__strntol64(int64_t *result
, const char *nptr
, size_t nptr_len
, const char **endptr
, int base
)
38 int c
, ovfl
, neg
, ndig
;
49 while (nptr_len
&& git__isspace(*p
))
58 if (*p
== '-' || *p
== '+') {
69 * Automatically detect the base if none was given to us.
70 * Right now, we assume that a number starting with '0x'
71 * is hexadecimal and a number starting with '0' is
77 else if (nptr_len
> 2 && (p
[1] == 'x' || p
[1] == 'X'))
83 if (base
< 0 || 36 < base
)
87 * Skip prefix of '0x'-prefixed hexadecimal numbers. There is no
88 * need to do the same for '0'-prefixed octal numbers as a
89 * leading '0' does not have any impact. Also, if we skip a
90 * leading '0' in such a string, then we may end up with no
91 * digits left and produce an error later on which isn't one.
93 if (base
== 16 && nptr_len
> 2 && p
[0] == '0' && (p
[1] == 'x' || p
[1] == 'X')) {
99 * Non-empty sequence of digits
101 for (; nptr_len
> 0; p
++,ndig
++,nptr_len
--) {
104 if ('0'<=c
&& c
<='9')
106 else if ('a'<=c
&& c
<='z')
108 else if ('A'<=c
&& c
<='Z')
113 if (git__multiply_int64_overflow(&nn
, n
, base
) || git__add_int64_overflow(&n
, nn
, v
)) {
115 /* Keep on iterating until the end of this number */
122 git_error_set(GIT_ERROR_INVALID
, "failed to convert string to long: not a number");
130 git_error_set(GIT_ERROR_INVALID
, "failed to convert string to long: overflow error");
138 int git__strntol32(int32_t *result
, const char *nptr
, size_t nptr_len
, const char **endptr
, int base
)
140 const char *tmp_endptr
;
145 if ((error
= git__strntol64(&tmp_long
, nptr
, nptr_len
, &tmp_endptr
, base
)) < 0)
148 tmp_int
= tmp_long
& 0xFFFFFFFF;
149 if (tmp_int
!= tmp_long
) {
150 int len
= (int)(tmp_endptr
- nptr
);
151 git_error_set(GIT_ERROR_INVALID
, "failed to convert: '%.*s' is too large", len
, nptr
);
157 *endptr
= tmp_endptr
;
162 int git__strcasecmp(const char *a
, const char *b
)
164 while (*a
&& *b
&& git__tolower(*a
) == git__tolower(*b
))
166 return ((unsigned char)git__tolower(*a
) - (unsigned char)git__tolower(*b
));
169 int git__strcasesort_cmp(const char *a
, const char *b
)
175 if (git__tolower(*a
) != git__tolower(*b
))
177 /* use case in sort order even if not in equivalence */
179 cmp
= (int)(*(const uint8_t *)a
) - (int)(*(const uint8_t *)b
);
186 return (unsigned char)git__tolower(*a
) - (unsigned char)git__tolower(*b
);
191 int git__strncasecmp(const char *a
, const char *b
, size_t sz
)
196 al
= (unsigned char)git__tolower(*a
);
197 bl
= (unsigned char)git__tolower(*b
);
199 } while (--sz
&& al
&& al
== bl
);
204 void git__strntolower(char *str
, size_t len
)
208 for (i
= 0; i
< len
; ++i
) {
209 str
[i
] = (char)git__tolower(str
[i
]);
213 void git__strtolower(char *str
)
215 git__strntolower(str
, strlen(str
));
218 GIT_INLINE(int) prefixcmp(const char *str
, size_t str_n
, const char *prefix
, bool icase
)
223 s
= (unsigned char)*str
++;
224 p
= (unsigned char)*prefix
++;
238 return (0 - *prefix
);
241 int git__prefixcmp(const char *str
, const char *prefix
)
257 int git__prefixncmp(const char *str
, size_t str_n
, const char *prefix
)
259 return prefixcmp(str
, str_n
, prefix
, false);
262 int git__prefixcmp_icase(const char *str
, const char *prefix
)
264 return prefixcmp(str
, SIZE_MAX
, prefix
, true);
267 int git__prefixncmp_icase(const char *str
, size_t str_n
, const char *prefix
)
269 return prefixcmp(str
, str_n
, prefix
, true);
272 int git__suffixcmp(const char *str
, const char *suffix
)
274 size_t a
= strlen(str
);
275 size_t b
= strlen(suffix
);
278 return strcmp(str
+ (a
- b
), suffix
);
281 char *git__strtok(char **end
, const char *sep
)
285 while (*ptr
&& strchr(sep
, *ptr
))
292 while (**end
&& !strchr(sep
, **end
))
306 /* Similar to strtok, but does not collapse repeated tokens. */
307 char *git__strsep(char **end
, const char *sep
)
309 char *start
= *end
, *ptr
= *end
;
311 while (*ptr
&& !strchr(sep
, *ptr
))
324 size_t git__linenlen(const char *buffer
, size_t buffer_len
)
326 char *nl
= memchr(buffer
, '\n', buffer_len
);
327 return nl
? (size_t)(nl
- buffer
) + 1 : buffer_len
;
331 * Adapted Not So Naive algorithm from http://www-igm.univ-mlv.fr/~lecroq/string/
333 const void * git__memmem(const void *haystack
, size_t haystacklen
,
334 const void *needle
, size_t needlelen
)
339 if (needlelen
> haystacklen
|| !haystacklen
|| !needlelen
)
342 h
= (const char *) haystack
,
343 n
= (const char *) needle
;
346 return memchr(haystack
, *n
, haystacklen
);
357 while (j
<= haystacklen
- needlelen
) {
358 if (n
[1] != h
[j
+ 1]) {
361 if (memcmp(n
+ 2, h
+ j
+ 2, needlelen
- 2) == 0 &&
371 void git__hexdump(const char *buffer
, size_t len
)
373 static const size_t LINE_WIDTH
= 16;
375 size_t line_count
, last_line
, i
, j
;
378 line_count
= (len
/ LINE_WIDTH
);
379 last_line
= (len
% LINE_WIDTH
);
381 for (i
= 0; i
< line_count
; ++i
) {
382 printf("%08" PRIxZ
" ", (i
* LINE_WIDTH
));
384 line
= buffer
+ (i
* LINE_WIDTH
);
385 for (j
= 0; j
< LINE_WIDTH
; ++j
, ++line
) {
386 printf("%02x ", (unsigned char)*line
& 0xFF);
388 if (j
== (LINE_WIDTH
/ 2))
394 line
= buffer
+ (i
* LINE_WIDTH
);
395 for (j
= 0; j
< LINE_WIDTH
; ++j
, ++line
)
396 printf("%c", (*line
>= 32 && *line
<= 126) ? *line
: '.');
402 printf("%08" PRIxZ
" ", (line_count
* LINE_WIDTH
));
404 line
= buffer
+ (line_count
* LINE_WIDTH
);
405 for (j
= 0; j
< last_line
; ++j
, ++line
) {
406 printf("%02x ", (unsigned char)*line
& 0xFF);
408 if (j
== (LINE_WIDTH
/ 2))
412 if (j
< (LINE_WIDTH
/ 2))
414 for (j
= 0; j
< (LINE_WIDTH
- last_line
); ++j
)
419 line
= buffer
+ (line_count
* LINE_WIDTH
);
420 for (j
= 0; j
< last_line
; ++j
, ++line
)
421 printf("%c", (*line
>= 32 && *line
<= 126) ? *line
: '.');
429 #ifdef GIT_LEGACY_HASH
430 uint32_t git__hash(const void *key
, int len
, unsigned int seed
)
432 const uint32_t m
= 0x5bd1e995;
434 uint32_t h
= seed
^ len
;
436 const unsigned char *data
= (const unsigned char *)key
;
439 uint32_t k
= *(uint32_t *)data
;
453 case 3: h
^= data
[2] << 16;
454 case 2: h
^= data
[1] << 8;
455 case 1: h
^= data
[0];
467 Cross-platform version of Murmurhash3
468 http://code.google.com/p/smhasher/wiki/MurmurHash3
469 by Austin Appleby (aappleby@gmail.com)
471 This code is on the public domain.
473 uint32_t git__hash(const void *key
, int len
, uint32_t seed
)
476 #define MURMUR_BLOCK() {\
478 k1 = git__rotl(k1,11);\
481 h1 = h1*3 + 0x52dce729;\
482 c1 = c1*5 + 0x7b7d159c;\
483 c2 = c2*5 + 0x6bce6396;\
486 const uint8_t *data
= (const uint8_t*)key
;
487 const int nblocks
= len
/ 4;
489 const uint32_t *blocks
= (const uint32_t *)(data
+ nblocks
* 4);
490 const uint8_t *tail
= (const uint8_t *)(data
+ nblocks
* 4);
492 uint32_t h1
= 0x971e137b ^ seed
;
495 uint32_t c1
= 0x95543787;
496 uint32_t c2
= 0x2ad7eb25;
500 for (i
= -nblocks
; i
; i
++) {
508 case 3: k1
^= tail
[2] << 16;
510 case 2: k1
^= tail
[1] << 8;
512 case 1: k1
^= tail
[0];
528 * A modified `bsearch` from the BSD glibc.
530 * Copyright (c) 1990 Regents of the University of California.
531 * All rights reserved.
532 * Redistribution and use in source and binary forms, with or without
533 * modification, are permitted provided that the following conditions
535 * 1. Redistributions of source code must retain the above copyright
536 * notice, this list of conditions and the following disclaimer.
537 * 2. Redistributions in binary form must reproduce the above copyright
538 * notice, this list of conditions and the following disclaimer in the
539 * documentation and/or other materials provided with the distribution.
540 * 3. [rescinded 22 July 1999]
541 * 4. Neither the name of the University nor the names of its contributors
542 * may be used to endorse or promote products derived from this software
543 * without specific prior written permission.
545 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
546 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
547 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
548 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
549 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
550 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
551 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
552 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
553 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
554 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
561 int (*compare
)(const void *, const void *),
566 void **part
, **base
= array
;
568 for (lim
= array_len
; lim
!= 0; lim
>>= 1) {
569 part
= base
+ (lim
>> 1);
570 cmp
= (*compare
)(key
, *part
);
575 if (cmp
> 0) { /* key > p; take right partition */
578 } /* else take left partition */
582 *position
= (base
- array
);
584 return (cmp
== 0) ? 0 : GIT_ENOTFOUND
;
591 int (*compare_r
)(const void *, const void *, void *),
597 void **part
, **base
= array
;
599 for (lim
= array_len
; lim
!= 0; lim
>>= 1) {
600 part
= base
+ (lim
>> 1);
601 cmp
= (*compare_r
)(key
, *part
, payload
);
606 if (cmp
> 0) { /* key > p; take right partition */
609 } /* else take left partition */
613 *position
= (base
- array
);
615 return (cmp
== 0) ? 0 : GIT_ENOTFOUND
;
621 * We don't want direct pointers to the CRT on Windows, we may
622 * get stdcall conflicts.
624 int git__strcmp_cb(const void *a
, const void *b
)
626 return strcmp((const char *)a
, (const char *)b
);
629 int git__strcasecmp_cb(const void *a
, const void *b
)
631 return strcasecmp((const char *)a
, (const char *)b
);
634 int git__parse_bool(int *out
, const char *value
)
636 /* A missing value means true */
638 !strcasecmp(value
, "true") ||
639 !strcasecmp(value
, "yes") ||
640 !strcasecmp(value
, "on")) {
644 if (!strcasecmp(value
, "false") ||
645 !strcasecmp(value
, "no") ||
646 !strcasecmp(value
, "off") ||
655 size_t git__unescape(char *str
)
657 char *scan
, *pos
= str
;
662 for (scan
= str
; *scan
; pos
++, scan
++) {
663 if (*scan
== '\\' && *(scan
+ 1) != '\0')
664 scan
++; /* skip '\' but include next char */
676 #if defined(GIT_QSORT_S) || defined(GIT_QSORT_R_BSD)
682 static int GIT_LIBGIT2_CALL
git__qsort_r_glue_cmp(
683 void *payload
, const void *a
, const void *b
)
685 git__qsort_r_glue
*glue
= payload
;
686 return glue
->cmp(a
, b
, glue
->payload
);
691 #if !defined(GIT_QSORT_R_BSD) && \
692 !defined(GIT_QSORT_R_GNU) && \
693 !defined(GIT_QSORT_S)
694 static void swap(uint8_t *a
, uint8_t *b
, size_t elsize
)
699 size_t n
= elsize
< sizeof(tmp
) ? elsize
: sizeof(tmp
);
700 memcpy(tmp
, a
+ elsize
- n
, n
);
701 memcpy(a
+ elsize
- n
, b
+ elsize
- n
, n
);
702 memcpy(b
+ elsize
- n
, tmp
, n
);
707 static void insertsort(
708 void *els
, size_t nel
, size_t elsize
,
709 git__sort_r_cmp cmp
, void *payload
)
712 uint8_t *end
= base
+ nel
* elsize
;
715 for (i
= base
+ elsize
; i
< end
; i
+= elsize
)
716 for (j
= i
; j
> base
&& cmp(j
, j
- elsize
, payload
) < 0; j
-= elsize
)
717 swap(j
, j
- elsize
, elsize
);
722 void *els
, size_t nel
, size_t elsize
, git__sort_r_cmp cmp
, void *payload
)
724 #if defined(GIT_QSORT_R_BSD)
725 git__qsort_r_glue glue
= { cmp
, payload
};
726 qsort_r(els
, nel
, elsize
, &glue
, git__qsort_r_glue_cmp
);
727 #elif defined(GIT_QSORT_R_GNU)
728 qsort_r(els
, nel
, elsize
, cmp
, payload
);
729 #elif defined(GIT_QSORT_S)
730 git__qsort_r_glue glue
= { cmp
, payload
};
731 qsort_s(els
, nel
, elsize
, git__qsort_r_glue_cmp
, &glue
);
733 insertsort(els
, nel
, elsize
, cmp
, payload
);
738 int git__getenv(git_str
*out
, const char *name
)
740 wchar_t *wide_name
= NULL
, *wide_value
= NULL
;
746 if (git__utf8_to_16_alloc(&wide_name
, name
) < 0)
749 if ((value_len
= GetEnvironmentVariableW(wide_name
, NULL
, 0)) > 0) {
750 wide_value
= git__malloc(value_len
* sizeof(wchar_t));
751 GIT_ERROR_CHECK_ALLOC(wide_value
);
753 value_len
= GetEnvironmentVariableW(wide_name
, wide_value
, value_len
);
757 error
= git_str_put_w(out
, wide_value
, value_len
);
758 else if (GetLastError() == ERROR_SUCCESS
|| GetLastError() == ERROR_ENVVAR_NOT_FOUND
)
759 error
= GIT_ENOTFOUND
;
761 git_error_set(GIT_ERROR_OS
, "could not read environment variable '%s'", name
);
763 git__free(wide_name
);
764 git__free(wide_value
);
768 int git__getenv(git_str
*out
, const char *name
)
770 const char *val
= getenv(name
);
775 return GIT_ENOTFOUND
;
777 return git_str_puts(out
, val
);
782 * By doing this in two steps we can at least get
783 * the function to be somewhat coherent, even
784 * with this disgusting nest of #ifdefs.
786 #ifndef _SC_NPROCESSORS_ONLN
787 # ifdef _SC_NPROC_ONLN
788 # define _SC_NPROCESSORS_ONLN _SC_NPROC_ONLN
789 # elif defined _SC_CRAY_NCPU
790 # define _SC_NPROCESSORS_ONLN _SC_CRAY_NCPU
794 int git__online_cpus(void)
796 #ifdef _SC_NPROCESSORS_ONLN
802 GetSystemInfo(&info
);
804 if ((int)info
.dwNumberOfProcessors
> 0)
805 return (int)info
.dwNumberOfProcessors
;
806 #elif defined(hpux) || defined(__hpux) || defined(_hpux)
807 struct pst_dynamic psd
;
809 if (!pstat_getdynamic(&psd
, sizeof(psd
), (size_t)1, 0))
810 return (int)psd
.psd_proc_cnt
;
813 #ifdef _SC_NPROCESSORS_ONLN
814 if ((ncpus
= (long)sysconf(_SC_NPROCESSORS_ONLN
)) > 0)