util.h 14.8 KB
Newer Older
Vicent Marti committed
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
Vicent Marti committed
3 4 5 6
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */
7 8 9
#ifndef INCLUDE_util_h__
#define INCLUDE_util_h__

10 11
#include "common.h"

12 13
#include "git2/buffer.h"
#include "buffer.h"
14
#include "thread-utils.h"
15

16
#include "common.h"
17
#include "strnlen.h"
18

19
#define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))
Vicent Marti committed
20
#define bitsizeof(x) (CHAR_BIT * sizeof(x))
Vicent Marti committed
21
#define MSB(x, bits) ((x) & (~0ULL << (bitsizeof(x) - (bits))))
22 23 24
#ifndef min
# define min(a,b) ((a) < (b) ? (a) : (b))
#endif
25 26 27
#ifndef max
# define max(a,b) ((a) > (b) ? (a) : (b))
#endif
28

29 30
#define GIT_DATE_RFC2822_SZ  32

31 32 33 34 35 36 37 38 39
/**
 * Return the length of a constant string.
 * We are aware that `strlen` performs the same task and is usually
 * optimized away by the compiler, whilst being safer because it returns
 * valid values when passed a pointer instead of a constant string; however
 * this macro will transparently work with wide-char and single-char strings.
 */
#define CONST_STRLEN(x) ((sizeof(x)/sizeof(x[0])) - 1)

40
#if defined(GIT_MSVC_CRTDBG)
41

42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
/* Enable MSVC CRTDBG memory leak reporting.
 *
 * We DO NOT use the "_CRTDBG_MAP_ALLOC" macro described in the MSVC
 * documentation because all allocs/frees in libgit2 already go through
 * the "git__" routines defined in this file.  Simply using the normal
 * reporting mechanism causes all leaks to be attributed to a routine
 * here in util.h (ie, the actual call to calloc()) rather than the
 * caller of git__calloc().
 *
 * Therefore, we declare a set of "git__crtdbg__" routines to replace
 * the corresponding "git__" routines and re-define the "git__" symbols
 * as macros.  This allows us to get and report the file:line info of
 * the real caller.
 *
 * We DO NOT replace the "git__free" routine because it needs to remain
 * a function pointer because it is used as a function argument when
 * setting up various structure "destructors".
 *
 * We also DO NOT use the "_CRTDBG_MAP_ALLOC" macro because it causes
 * "free" to be remapped to "_free_dbg" and this causes problems for
 * structures which define a field named "free".
 *
 * Finally, CRTDBG must be explicitly enabled and configured at program
 * startup.  See tests/main.c for an example.
 */
67

68
#include "win32/w32_crtdbg_stacktrace.h"
69 70 71 72 73 74 75 76 77 78 79 80

#define git__malloc(len)                      git__crtdbg__malloc(len, __FILE__, __LINE__)
#define git__calloc(nelem, elsize)            git__crtdbg__calloc(nelem, elsize, __FILE__, __LINE__)
#define git__strdup(str)                      git__crtdbg__strdup(str, __FILE__, __LINE__)
#define git__strndup(str, n)                  git__crtdbg__strndup(str, n, __FILE__, __LINE__)
#define git__substrdup(str, n)                git__crtdbg__substrdup(str, n, __FILE__, __LINE__)
#define git__realloc(ptr, size)               git__crtdbg__realloc(ptr, size, __FILE__, __LINE__)
#define git__reallocarray(ptr, nelem, elsize) git__crtdbg__reallocarray(ptr, nelem, elsize, __FILE__, __LINE__)
#define git__mallocarray(nelem, elsize)       git__crtdbg__mallocarray(nelem, elsize, __FILE__, __LINE__)

#else

81
/*
82 83 84
 * Custom memory allocation wrappers
 * that set error code and error message
 * on allocation failure
Vicent Marti committed
85
 */
86 87 88
GIT_INLINE(void *) git__malloc(size_t len)
{
	void *ptr = malloc(len);
89
	if (!ptr) giterr_set_oom();
90 91 92 93 94 95
	return ptr;
}

GIT_INLINE(void *) git__calloc(size_t nelem, size_t elsize)
{
	void *ptr = calloc(nelem, elsize);
96
	if (!ptr) giterr_set_oom();
97 98 99 100 101 102
	return ptr;
}

GIT_INLINE(char *) git__strdup(const char *str)
{
	char *ptr = strdup(str);
103
	if (!ptr) giterr_set_oom();
104 105 106
	return ptr;
}

107 108
GIT_INLINE(char *) git__strndup(const char *str, size_t n)
{
109
	size_t length = 0, alloclength;
110 111
	char *ptr;

112
	length = p_strnlen(str, n);
113

114 115
	if (GIT_ADD_SIZET_OVERFLOW(&alloclength, length, 1) ||
		!(ptr = git__malloc(alloclength)))
116 117
		return NULL;

118 119 120
	if (length)
		memcpy(ptr, str, length);

121
	ptr[length] = '\0';
122 123 124 125

	return ptr;
}

Ben Straub committed
126 127 128
/* NOTE: This doesn't do null or '\0' checking.  Watch those boundaries! */
GIT_INLINE(char *) git__substrdup(const char *start, size_t n)
{
129
	char *ptr;
130
	size_t alloclen;
131

132 133
	if (GIT_ADD_SIZET_OVERFLOW(&alloclen, n, 1) ||
		!(ptr = git__malloc(alloclen)))
134 135
		return NULL;

Ben Straub committed
136
	memcpy(ptr, start, n);
137
	ptr[n] = '\0';
Ben Straub committed
138 139 140
	return ptr;
}

141 142 143
GIT_INLINE(void *) git__realloc(void *ptr, size_t size)
{
	void *new_ptr = realloc(ptr, size);
144
	if (!new_ptr) giterr_set_oom();
145 146
	return new_ptr;
}
147

148 149 150 151 152 153 154
/**
 * Similar to `git__realloc`, except that it is suitable for reallocing an
 * array to a new number of elements of `nelem`, each of size `elsize`.
 * The total size calculation is checked for overflow.
 */
GIT_INLINE(void *) git__reallocarray(void *ptr, size_t nelem, size_t elsize)
{
155 156 157
	size_t newsize;
	return GIT_MULTIPLY_SIZET_OVERFLOW(&newsize, nelem, elsize) ?
		NULL : realloc(ptr, newsize);
158 159 160 161 162 163 164 165 166 167
}

/**
 * Similar to `git__calloc`, except that it does not zero memory.
 */
GIT_INLINE(void *) git__mallocarray(size_t nelem, size_t elsize)
{
	return git__reallocarray(NULL, nelem, elsize);
}

168 169
#endif /* !MSVC_CTRDBG */

170 171 172 173
GIT_INLINE(void) git__free(void *ptr)
{
	free(ptr);
}
174

175 176 177 178 179 180
#define STRCMP_CASESELECT(IGNORE_CASE, STR1, STR2) \
	((IGNORE_CASE) ? strcasecmp((STR1), (STR2)) : strcmp((STR1), (STR2)))

#define CASESELECT(IGNORE_CASE, ICASE, CASE) \
	((IGNORE_CASE) ? (ICASE) : (CASE))

181
extern int git__prefixcmp(const char *str, const char *prefix);
182
extern int git__prefixcmp_icase(const char *str, const char *prefix);
183
extern int git__prefixncmp(const char *str, size_t str_n, const char *prefix);
184
extern int git__prefixncmp_icase(const char *str, size_t str_n, const char *prefix);
185
extern int git__suffixcmp(const char *str, const char *suffix);
186

187 188 189 190 191
GIT_INLINE(int) git__signum(int val)
{
	return ((val > 0) - (val < 0));
}

192
extern int git__strtol32(int32_t *n, const char *buff, const char **end_buf, int base);
193
extern int git__strntol32(int32_t *n, const char *buff, size_t buff_len, const char **end_buf, int base);
194
extern int git__strtol64(int64_t *n, const char *buff, const char **end_buf, int base);
195 196
extern int git__strntol64(int64_t *n, const char *buff, size_t buff_len, const char **end_buf, int base);

197

198
extern void git__hexdump(const char *buffer, size_t n);
199 200 201 202 203 204 205 206 207
extern uint32_t git__hash(const void *key, int len, uint32_t seed);

/* 32-bit cross-platform rotl */
#ifdef _MSC_VER /* use built-in method in MSVC */
#	define git__rotl(v, s) (uint32_t)_rotl(v, s)
#else /* use bitops in GCC; with o2 this gets optimized to a rotl instruction */
#	define git__rotl(v, s) (uint32_t)(((uint32_t)(v) << (s)) | ((uint32_t)(v) >> (32 - (s))))
#endif

208
extern char *git__strtok(char **end, const char *sep);
209
extern char *git__strsep(char **end, const char *sep);
210

211
extern void git__strntolower(char *str, size_t len);
212 213
extern void git__strtolower(char *str);

214 215 216 217 218 219 220 221 222
#ifdef GIT_WIN32
GIT_INLINE(int) git__tolower(int c)
{
	return (c >= 'A' && c <= 'Z') ? (c + 32) : c;
}
#else
# define git__tolower(a) tolower(a)
#endif

223 224
extern size_t git__linenlen(const char *buffer, size_t buffer_len);

225 226 227
GIT_INLINE(const char *) git__next_line(const char *s)
{
	while (*s && *s != '\n') s++;
Russell Belfer committed
228
	while (*s == '\n' || *s == '\r') s++;
229 230 231
	return s;
}

232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
GIT_INLINE(const void *) git__memrchr(const void *s, int c, size_t n)
{
	const unsigned char *cp;

	if (n != 0) {
		cp = (unsigned char *)s + n;
		do {
			if (*(--cp) == (unsigned char)c)
				return cp;
		} while (--n != 0);
	}

	return NULL;
}

247 248 249 250
typedef int (*git__tsort_cmp)(const void *a, const void *b);

extern void git__tsort(void **dst, size_t size, git__tsort_cmp cmp);

251
typedef int (*git__sort_r_cmp)(const void *a, const void *b, void *payload);
252 253

extern void git__tsort_r(
254
	void **dst, size_t size, git__sort_r_cmp cmp, void *payload);
255 256

extern void git__qsort_r(
257 258 259 260 261
	void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload);

extern void git__insertsort_r(
	void *els, size_t nel, size_t elsize, void *swapel,
	git__sort_r_cmp cmp, void *payload);
262

263 264 265
/**
 * @param position If non-NULL, this will be set to the position where the
 * 		element is or would be inserted if not found.
266
 * @return 0 if found; GIT_ENOTFOUND if not found
267
 */
268 269 270 271
extern int git__bsearch(
	void **array,
	size_t array_len,
	const void *key,
272 273 274 275 276 277 278 279 280
	int (*compare)(const void *key, const void *element),
	size_t *position);

extern int git__bsearch_r(
	void **array,
	size_t array_len,
	const void *key,
	int (*compare_r)(const void *key, const void *element, void *payload),
	void *payload,
281
	size_t *position);
282

283
extern int git__strcmp_cb(const void *a, const void *b);
284
extern int git__strcasecmp_cb(const void *a, const void *b);
285

286 287 288 289 290
extern int git__strcmp(const char *a, const char *b);
extern int git__strcasecmp(const char *a, const char *b);
extern int git__strncmp(const char *a, const char *b, size_t sz);
extern int git__strncasecmp(const char *a, const char *b, size_t sz);

291 292
extern int git__strcasesort_cmp(const char *a, const char *b);

293
typedef struct {
294
	git_atomic refcount;
295 296 297 298 299 300
	void *owner;
} git_refcount;

typedef void (*git_refcount_freeptr)(void *r);

#define GIT_REFCOUNT_INC(r) { \
301
	git_atomic_inc(&(r)->rc.refcount);	\
302 303 304
}

#define GIT_REFCOUNT_DEC(_r, do_free) { \
305
	git_refcount *r = &(_r)->rc; \
306 307
	int val = git_atomic_dec(&r->refcount); \
	if (val <= 0 && r->owner == NULL) { do_free(_r); } \
308 309 310
}

#define GIT_REFCOUNT_OWN(r, o) { \
311
	(r)->rc.owner = o; \
312 313
}

314
#define GIT_REFCOUNT_OWNER(r) ((r)->rc.owner)
315

316
#define GIT_REFCOUNT_VAL(r) git_atomic_get((r)->rc.refcount)
317 318


nulltoken committed
319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
static signed char from_hex[] = {
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 00 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 10 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 20 */
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, /* 30 */
-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 40 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 50 */
-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 60 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 70 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 80 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 90 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a0 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* b0 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* c0 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* d0 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* e0 */
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* f0 */
};

GIT_INLINE(int) git__fromhex(char h)
{
	return from_hex[(unsigned char) h];
}
342

schu committed
343 344 345
GIT_INLINE(int) git__ishex(const char *str)
{
	unsigned i;
346
	for (i=0; str[i] != '\0'; i++)
schu committed
347 348 349 350 351
		if (git__fromhex(str[i]) < 0)
			return 0;
	return 1;
}

352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368
GIT_INLINE(size_t) git__size_t_bitmask(size_t v)
{
	v--;
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;

	return v;
}

GIT_INLINE(size_t) git__size_t_powerof2(size_t v)
{
	return git__size_t_bitmask(v) + 1;
}

369 370
GIT_INLINE(bool) git__isupper(int c)
{
Linquize committed
371
	return (c >= 'A' && c <= 'Z');
372 373 374 375
}

GIT_INLINE(bool) git__isalpha(int c)
{
Linquize committed
376
	return ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'));
377 378
}

nulltoken committed
379 380
GIT_INLINE(bool) git__isdigit(int c)
{
Linquize committed
381
	return (c >= '0' && c <= '9');
nulltoken committed
382 383
}

384 385
GIT_INLINE(bool) git__isspace(int c)
{
386
	return (c == ' ' || c == '\t' || c == '\n' || c == '\f' || c == '\r' || c == '\v');
387 388
}

389 390
GIT_INLINE(bool) git__isspace_nonlf(int c)
{
391
	return (c == ' ' || c == '\t' || c == '\f' || c == '\r' || c == '\v');
392 393
}

394 395 396 397 398
GIT_INLINE(bool) git__iswildcard(int c)
{
	return (c == '*' || c == '?' || c == '[');
}

399 400 401 402 403
GIT_INLINE(bool) git__isxdigit(int c)
{
	return ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'));
}

404
/*
405
 * Parse a string value as a boolean, just like Core Git does.
406 407 408 409 410 411
 *
 * Valid values for true are: 'true', 'yes', 'on'
 * Valid values for false are: 'false', 'no', 'off'
 */
extern int git__parse_bool(int *out, const char *value);

412 413 414 415 416 417 418 419
/*
 * Parse a string into a value as a git_time_t.
 *
 * Sample valid input:
 * - "yesterday"
 * - "July 17, 2003"
 * - "2003-7-17 08:23"
 */
420
extern int git__date_parse(git_time_t *out, const char *date);
421

422
/*
423 424 425 426 427 428 429 430 431 432
 * Format a git_time as a RFC2822 string
 *
 * @param out buffer to store formatted date; a '\\0' terminator will automatically be added.
 * @param len size of the buffer; should be atleast `GIT_DATE_RFC2822_SZ` in size;
 * @param date the date to be formatted
 * @return 0 if successful; -1 on error
 */
extern int git__date_rfc2822_fmt(char *out, size_t len, const git_time *date);

/*
433
 * Unescapes a string in-place.
Russell Belfer committed
434
 *
435 436 437 438 439 440
 * Edge cases behavior:
 * - "jackie\" -> "jacky\"
 * - "chan\\" -> "chan\"
 */
extern size_t git__unescape(char *str);

441
/*
442 443 444 445 446 447 448 449 450 451 452
 * Iterate through an UTF-8 string, yielding one
 * codepoint at a time.
 *
 * @param str current position in the string
 * @param str_len size left in the string; -1 if the string is NULL-terminated
 * @param dst pointer where to store the current codepoint
 * @return length in bytes of the read codepoint; -1 if the codepoint was invalid
 */
extern int git__utf8_iterate(const uint8_t *str, int str_len, int32_t *dst);

/*
453 454
 * Safely zero-out memory, making sure that the compiler
 * doesn't optimize away the operation.
455
 */
yorah committed
456 457 458 459 460 461 462 463 464 465 466
GIT_INLINE(void) git__memzero(void *data, size_t size)
{
#ifdef _MSC_VER
	SecureZeroMemory((PVOID)data, size);
#else
	volatile uint8_t *scan = (volatile uint8_t *)data;

	while (size--)
		*scan++ = 0x0;
#endif
}
467

468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
#ifdef GIT_WIN32

GIT_INLINE(double) git__timer(void)
{
	/* We need the initial tick count to detect if the tick
	 * count has rolled over. */
	static DWORD initial_tick_count = 0;

	/* GetTickCount returns the number of milliseconds that have
	 * elapsed since the system was started. */
	DWORD count = GetTickCount();

	if(initial_tick_count == 0) {
		initial_tick_count = count;
	} else if (count < initial_tick_count) {
		/* The tick count has rolled over - adjust for it. */
		count = (0xFFFFFFFF - initial_tick_count) + count;
	}

	return (double) count / (double) 1000;
}

#elif __APPLE__

#include <mach/mach_time.h>

494
GIT_INLINE(double) git__timer(void)
495 496 497 498 499 500 501 502 503 504
{
   uint64_t time = mach_absolute_time();
   static double scaling_factor = 0;

   if (scaling_factor == 0) {
       mach_timebase_info_data_t info;
       (void)mach_timebase_info(&info);
       scaling_factor = (double)info.numer / (double)info.denom;
   }

505
   return (double)time * scaling_factor / 1.0E9;
506 507
}

508 509 510 511 512 513 514 515 516 517 518
#elif defined(AMIGA)

#include <proto/timer.h>

GIT_INLINE(double) git__timer(void)
{
	struct TimeVal tv;
	ITimer->GetUpTime(&tv);
	return (double)tv.Seconds + (double)tv.Microseconds / 1.0E6;
}

519 520 521 522 523 524 525 526 527
#else

#include <sys/time.h>

GIT_INLINE(double) git__timer(void)
{
	struct timespec tp;

	if (clock_gettime(CLOCK_MONOTONIC, &tp) == 0) {
528
		return (double) tp.tv_sec + (double) tp.tv_nsec / 1.0E9;
529 530 531 532 533
	} else {
		/* Fall back to using gettimeofday */
		struct timeval tv;
		struct timezone tz;
		gettimeofday(&tv, &tz);
534
		return (double)tv.tv_sec + (double)tv.tv_usec / 1.0E6;
535 536 537 538 539
	}
}

#endif

540 541
extern int git__getenv(git_buf *out, const char *name);

542
#endif /* INCLUDE_util_h__ */