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.
7 #ifndef INCLUDE_util_h__
8 #define INCLUDE_util_h__
10 #if defined(GIT_MSVC_CRTDBG)
11 /* Enable MSVC CRTDBG memory leak reporting.
13 * We DO NOT use the "_CRTDBG_MAP_ALLOC" macro described in the MSVC
14 * documentation because all allocs/frees in libgit2 already go through
15 * the "git__" routines defined in this file. Simply using the normal
16 * reporting mechanism causes all leaks to be attributed to a routine
17 * here in util.h (ie, the actual call to calloc()) rather than the
18 * caller of git__calloc().
20 * Therefore, we declare a set of "git__crtdbg__" routines to replace
21 * the corresponding "git__" routines and re-define the "git__" symbols
22 * as macros. This allows us to get and report the file:line info of
25 * We DO NOT replace the "git__free" routine because it needs to remain
26 * a function pointer because it is used as a function argument when
27 * setting up various structure "destructors".
29 * We also DO NOT use the "_CRTDBG_MAP_ALLOC" macro because it causes
30 * "free" to be remapped to "_free_dbg" and this causes problems for
31 * structures which define a field named "free".
33 * Finally, CRTDBG must be explicitly enabled and configured at program
34 * startup. See tests/main.c for an example.
43 #define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))
44 #define bitsizeof(x) (CHAR_BIT * sizeof(x))
45 #define MSB(x, bits) ((x) & (~0ULL << (bitsizeof(x) - (bits))))
47 # define min(a,b) ((a) < (b) ? (a) : (b))
50 # define max(a,b) ((a) > (b) ? (a) : (b))
53 #define GIT_DATE_RFC2822_SZ 32
56 * Return the length of a constant string.
57 * We are aware that `strlen` performs the same task and is usually
58 * optimized away by the compiler, whilst being safer because it returns
59 * valid values when passed a pointer instead of a constant string; however
60 * this macro will transparently work with wide-char and single-char strings.
62 #define CONST_STRLEN(x) ((sizeof(x)/sizeof(x[0])) - 1)
64 #if defined(GIT_MSVC_CRTDBG)
65 GIT_INLINE(void *) git__crtdbg__malloc(size_t len
, const char *file
, int line
)
67 void *ptr
= _malloc_dbg(len
, _NORMAL_BLOCK
, file
, line
);
68 if (!ptr
) giterr_set_oom();
72 GIT_INLINE(void *) git__crtdbg__calloc(size_t nelem
, size_t elsize
, const char *file
, int line
)
74 void *ptr
= _calloc_dbg(nelem
, elsize
, _NORMAL_BLOCK
, file
, line
);
75 if (!ptr
) giterr_set_oom();
79 GIT_INLINE(char *) git__crtdbg__strdup(const char *str
, const char *file
, int line
)
81 char *ptr
= _strdup_dbg(str
, _NORMAL_BLOCK
, file
, line
);
82 if (!ptr
) giterr_set_oom();
86 GIT_INLINE(char *) git__crtdbg__strndup(const char *str
, size_t n
, const char *file
, int line
)
88 size_t length
= 0, alloclength
;
91 length
= p_strnlen(str
, n
);
93 if (GIT_ADD_SIZET_OVERFLOW(&alloclength
, length
, 1) ||
94 !(ptr
= git__crtdbg__malloc(alloclength
, file
, line
)))
98 memcpy(ptr
, str
, length
);
105 GIT_INLINE(char *) git__crtdbg__substrdup(const char *start
, size_t n
, const char *file
, int line
)
110 if (GIT_ADD_SIZET_OVERFLOW(&alloclen
, n
, 1) ||
111 !(ptr
= git__crtdbg__malloc(alloclen
, file
, line
)))
114 memcpy(ptr
, start
, n
);
119 GIT_INLINE(void *) git__crtdbg__realloc(void *ptr
, size_t size
, const char *file
, int line
)
121 void *new_ptr
= _realloc_dbg(ptr
, size
, _NORMAL_BLOCK
, file
, line
);
122 if (!new_ptr
) giterr_set_oom();
126 GIT_INLINE(void *) git__crtdbg__reallocarray(void *ptr
, size_t nelem
, size_t elsize
, const char *file
, int line
)
129 return GIT_MULTIPLY_SIZET_OVERFLOW(&newsize
, nelem
, elsize
) ?
130 NULL
: _realloc_dbg(ptr
, newsize
, _NORMAL_BLOCK
, file
, line
);
133 GIT_INLINE(void *) git__crtdbg__mallocarray(size_t nelem
, size_t elsize
, const char *file
, int line
)
135 return git__crtdbg__reallocarray(NULL
, nelem
, elsize
, file
, line
);
138 #define git__malloc(len) git__crtdbg__malloc(len, __FILE__, __LINE__)
139 #define git__calloc(nelem, elsize) git__crtdbg__calloc(nelem, elsize, __FILE__, __LINE__)
140 #define git__strdup(str) git__crtdbg__strdup(str, __FILE__, __LINE__)
141 #define git__strndup(str, n) git__crtdbg__strndup(str, n, __FILE__, __LINE__)
142 #define git__substrdup(str, n) git__crtdbg__substrdup(str, n, __FILE__, __LINE__)
143 #define git__realloc(ptr, size) git__crtdbg__realloc(ptr, size, __FILE__, __LINE__)
144 #define git__reallocarray(ptr, nelem, elsize) git__crtdbg__reallocarray(ptr, nelem, elsize, __FILE__, __LINE__)
145 #define git__mallocarray(nelem, elsize) git__crtdbg__mallocarray(nelem, elsize, __FILE__, __LINE__)
150 * Custom memory allocation wrappers
151 * that set error code and error message
152 * on allocation failure
154 GIT_INLINE(void *) git__malloc(size_t len
)
156 void *ptr
= malloc(len
);
157 if (!ptr
) giterr_set_oom();
161 GIT_INLINE(void *) git__calloc(size_t nelem
, size_t elsize
)
163 void *ptr
= calloc(nelem
, elsize
);
164 if (!ptr
) giterr_set_oom();
168 GIT_INLINE(char *) git__strdup(const char *str
)
170 char *ptr
= strdup(str
);
171 if (!ptr
) giterr_set_oom();
175 GIT_INLINE(char *) git__strndup(const char *str
, size_t n
)
177 size_t length
= 0, alloclength
;
180 length
= p_strnlen(str
, n
);
182 if (GIT_ADD_SIZET_OVERFLOW(&alloclength
, length
, 1) ||
183 !(ptr
= git__malloc(alloclength
)))
187 memcpy(ptr
, str
, length
);
194 /* NOTE: This doesn't do null or '\0' checking. Watch those boundaries! */
195 GIT_INLINE(char *) git__substrdup(const char *start
, size_t n
)
200 if (GIT_ADD_SIZET_OVERFLOW(&alloclen
, n
, 1) ||
201 !(ptr
= git__malloc(alloclen
)))
204 memcpy(ptr
, start
, n
);
209 GIT_INLINE(void *) git__realloc(void *ptr
, size_t size
)
211 void *new_ptr
= realloc(ptr
, size
);
212 if (!new_ptr
) giterr_set_oom();
217 * Similar to `git__realloc`, except that it is suitable for reallocing an
218 * array to a new number of elements of `nelem`, each of size `elsize`.
219 * The total size calculation is checked for overflow.
221 GIT_INLINE(void *) git__reallocarray(void *ptr
, size_t nelem
, size_t elsize
)
224 return GIT_MULTIPLY_SIZET_OVERFLOW(&newsize
, nelem
, elsize
) ?
225 NULL
: realloc(ptr
, newsize
);
229 * Similar to `git__calloc`, except that it does not zero memory.
231 GIT_INLINE(void *) git__mallocarray(size_t nelem
, size_t elsize
)
233 return git__reallocarray(NULL
, nelem
, elsize
);
236 #endif /* !MSVC_CTRDBG */
238 GIT_INLINE(void) git__free(void *ptr
)
243 #define STRCMP_CASESELECT(IGNORE_CASE, STR1, STR2) \
244 ((IGNORE_CASE) ? strcasecmp((STR1), (STR2)) : strcmp((STR1), (STR2)))
246 #define CASESELECT(IGNORE_CASE, ICASE, CASE) \
247 ((IGNORE_CASE) ? (ICASE) : (CASE))
249 extern int git__prefixcmp(const char *str
, const char *prefix
);
250 extern int git__prefixcmp_icase(const char *str
, const char *prefix
);
251 extern int git__prefixncmp_icase(const char *str
, size_t str_n
, const char *prefix
);
252 extern int git__suffixcmp(const char *str
, const char *suffix
);
254 GIT_INLINE(int) git__signum(int val
)
256 return ((val
> 0) - (val
< 0));
259 extern int git__strtol32(int32_t *n
, const char *buff
, const char **end_buf
, int base
);
260 extern int git__strtol64(int64_t *n
, const char *buff
, const char **end_buf
, int base
);
262 extern void git__hexdump(const char *buffer
, size_t n
);
263 extern uint32_t git__hash(const void *key
, int len
, uint32_t seed
);
265 /* 32-bit cross-platform rotl */
266 #ifdef _MSC_VER /* use built-in method in MSVC */
267 # define git__rotl(v, s) (uint32_t)_rotl(v, s)
268 #else /* use bitops in GCC; with o2 this gets optimized to a rotl instruction */
269 # define git__rotl(v, s) (uint32_t)(((uint32_t)(v) << (s)) | ((uint32_t)(v) >> (32 - (s))))
272 extern char *git__strtok(char **end
, const char *sep
);
273 extern char *git__strsep(char **end
, const char *sep
);
275 extern void git__strntolower(char *str
, size_t len
);
276 extern void git__strtolower(char *str
);
279 GIT_INLINE(int) git__tolower(int c
)
281 return (c
>= 'A' && c
<= 'Z') ? (c
+ 32) : c
;
284 # define git__tolower(a) tolower(a)
287 GIT_INLINE(const char *) git__next_line(const char *s
)
289 while (*s
&& *s
!= '\n') s
++;
290 while (*s
== '\n' || *s
== '\r') s
++;
294 GIT_INLINE(const void *) git__memrchr(const void *s
, int c
, size_t n
)
296 const unsigned char *cp
;
299 cp
= (unsigned char *)s
+ n
;
301 if (*(--cp
) == (unsigned char)c
)
309 typedef int (*git__tsort_cmp
)(const void *a
, const void *b
);
311 extern void git__tsort(void **dst
, size_t size
, git__tsort_cmp cmp
);
313 typedef int (*git__sort_r_cmp
)(const void *a
, const void *b
, void *payload
);
315 extern void git__tsort_r(
316 void **dst
, size_t size
, git__sort_r_cmp cmp
, void *payload
);
318 extern void git__qsort_r(
319 void *els
, size_t nel
, size_t elsize
, git__sort_r_cmp cmp
, void *payload
);
321 extern void git__insertsort_r(
322 void *els
, size_t nel
, size_t elsize
, void *swapel
,
323 git__sort_r_cmp cmp
, void *payload
);
326 * @param position If non-NULL, this will be set to the position where the
327 * element is or would be inserted if not found.
328 * @return 0 if found; GIT_ENOTFOUND if not found
330 extern int git__bsearch(
334 int (*compare
)(const void *key
, const void *element
),
337 extern int git__bsearch_r(
341 int (*compare_r
)(const void *key
, const void *element
, void *payload
),
345 extern int git__strcmp_cb(const void *a
, const void *b
);
346 extern int git__strcasecmp_cb(const void *a
, const void *b
);
348 extern int git__strcmp(const char *a
, const char *b
);
349 extern int git__strcasecmp(const char *a
, const char *b
);
350 extern int git__strncmp(const char *a
, const char *b
, size_t sz
);
351 extern int git__strncasecmp(const char *a
, const char *b
, size_t sz
);
353 extern int git__strcasesort_cmp(const char *a
, const char *b
);
355 #include "thread-utils.h"
362 typedef void (*git_refcount_freeptr
)(void *r
);
364 #define GIT_REFCOUNT_INC(r) { \
365 git_atomic_inc(&((git_refcount *)(r))->refcount); \
368 #define GIT_REFCOUNT_DEC(_r, do_free) { \
369 git_refcount *r = (git_refcount *)(_r); \
370 int val = git_atomic_dec(&r->refcount); \
371 if (val <= 0 && r->owner == NULL) { do_free(_r); } \
374 #define GIT_REFCOUNT_OWN(r, o) { \
375 ((git_refcount *)(r))->owner = o; \
378 #define GIT_REFCOUNT_OWNER(r) (((git_refcount *)(r))->owner)
380 #define GIT_REFCOUNT_VAL(r) git_atomic_get(&((git_refcount *)(r))->refcount)
383 static signed char from_hex
[] = {
384 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 00 */
385 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 10 */
386 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 20 */
387 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, /* 30 */
388 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 40 */
389 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 50 */
390 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 60 */
391 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 70 */
392 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 80 */
393 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 90 */
394 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a0 */
395 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* b0 */
396 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* c0 */
397 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* d0 */
398 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* e0 */
399 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* f0 */
402 GIT_INLINE(int) git__fromhex(char h
)
404 return from_hex
[(unsigned char) h
];
407 GIT_INLINE(int) git__ishex(const char *str
)
410 for (i
=0; str
[i
] != '\0'; i
++)
411 if (git__fromhex(str
[i
]) < 0)
416 GIT_INLINE(size_t) git__size_t_bitmask(size_t v
)
428 GIT_INLINE(size_t) git__size_t_powerof2(size_t v
)
430 return git__size_t_bitmask(v
) + 1;
433 GIT_INLINE(bool) git__isupper(int c
)
435 return (c
>= 'A' && c
<= 'Z');
438 GIT_INLINE(bool) git__isalpha(int c
)
440 return ((c
>= 'A' && c
<= 'Z') || (c
>= 'a' && c
<= 'z'));
443 GIT_INLINE(bool) git__isdigit(int c
)
445 return (c
>= '0' && c
<= '9');
448 GIT_INLINE(bool) git__isspace(int c
)
450 return (c
== ' ' || c
== '\t' || c
== '\n' || c
== '\f' || c
== '\r' || c
== '\v');
453 GIT_INLINE(bool) git__isspace_nonlf(int c
)
455 return (c
== ' ' || c
== '\t' || c
== '\f' || c
== '\r' || c
== '\v');
458 GIT_INLINE(bool) git__iswildcard(int c
)
460 return (c
== '*' || c
== '?' || c
== '[');
464 * Parse a string value as a boolean, just like Core Git does.
466 * Valid values for true are: 'true', 'yes', 'on'
467 * Valid values for false are: 'false', 'no', 'off'
469 extern int git__parse_bool(int *out
, const char *value
);
472 * Parse a string into a value as a git_time_t.
474 * Sample valid input:
477 * - "2003-7-17 08:23"
479 extern int git__date_parse(git_time_t
*out
, const char *date
);
482 * Format a git_time as a RFC2822 string
484 * @param out buffer to store formatted date; a '\\0' terminator will automatically be added.
485 * @param len size of the buffer; should be atleast `GIT_DATE_RFC2822_SZ` in size;
486 * @param date the date to be formatted
487 * @return 0 if successful; -1 on error
489 extern int git__date_rfc2822_fmt(char *out
, size_t len
, const git_time
*date
);
492 * Unescapes a string in-place.
494 * Edge cases behavior:
495 * - "jackie\" -> "jacky\"
496 * - "chan\\" -> "chan\"
498 extern size_t git__unescape(char *str
);
501 * Iterate through an UTF-8 string, yielding one
502 * codepoint at a time.
504 * @param str current position in the string
505 * @param str_len size left in the string; -1 if the string is NULL-terminated
506 * @param dst pointer where to store the current codepoint
507 * @return length in bytes of the read codepoint; -1 if the codepoint was invalid
509 extern int git__utf8_iterate(const uint8_t *str
, int str_len
, int32_t *dst
);
512 * Safely zero-out memory, making sure that the compiler
513 * doesn't optimize away the operation.
515 GIT_INLINE(void) git__memzero(void *data
, size_t size
)
518 SecureZeroMemory((PVOID
)data
, size
);
520 volatile uint8_t *scan
= (volatile uint8_t *)data
;
529 GIT_INLINE(double) git__timer(void)
531 /* We need the initial tick count to detect if the tick
532 * count has rolled over. */
533 static DWORD initial_tick_count
= 0;
535 /* GetTickCount returns the number of milliseconds that have
536 * elapsed since the system was started. */
537 DWORD count
= GetTickCount();
539 if(initial_tick_count
== 0) {
540 initial_tick_count
= count
;
541 } else if (count
< initial_tick_count
) {
542 /* The tick count has rolled over - adjust for it. */
543 count
= (0xFFFFFFFF - initial_tick_count
) + count
;
546 return (double) count
/ (double) 1000;
551 #include <mach/mach_time.h>
553 GIT_INLINE(double) git__timer(void)
555 uint64_t time
= mach_absolute_time();
556 static double scaling_factor
= 0;
558 if (scaling_factor
== 0) {
559 mach_timebase_info_data_t info
;
560 (void)mach_timebase_info(&info
);
561 scaling_factor
= (double)info
.numer
/ (double)info
.denom
;
564 return (double)time
* scaling_factor
/ 1.0E9
;
569 #include <proto/timer.h>
571 GIT_INLINE(double) git__timer(void)
574 ITimer
->GetUpTime(&tv
);
575 return (double)tv
.Seconds
+ (double)tv
.Microseconds
/ 1.0E6
;
580 #include <sys/time.h>
582 GIT_INLINE(double) git__timer(void)
586 if (clock_gettime(CLOCK_MONOTONIC
, &tp
) == 0) {
587 return (double) tp
.tv_sec
+ (double) tp
.tv_nsec
/ 1.0E9
;
589 /* Fall back to using gettimeofday */
592 gettimeofday(&tv
, &tz
);
593 return (double)tv
.tv_sec
+ (double)tv
.tv_usec
/ 1.0E6
;
599 #endif /* INCLUDE_util_h__ */