ledit

memory.c (6618B)

---

 #include <stdio.h>
 #include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 
 #include "assert.h"
 #include "memory.h"
 #include "cleanup.h"
 
 static void
 fatal_err(const char *msg) {
 	fprintf(stderr, "%s", msg);
 	/* FIXME: maybe don't cleanup here - it will probably fail anyways */
 	ledit_cleanup();
 	exit(1);
 }
 
 void
 err_overflow_impl(const char *file, int line, const char *func) {
 	(void)fprintf(stderr, "Integer overflow: file \"%s\", line %d, function \"%s\"\n", file, line, func);
 	ledit_emergencydump(file, line, func, "Integer overflow");
 	abort();
 }
 
 /* FIXME: should these perform emergencydump instead of just
    fatal_err? It probably isn't of much use when there isn't
    even any memory left. */
 char *
 ledit_strdup(const char *s) {
 	char *str = strdup(s);
 	ledit_assert(str && "Out of memory.");
 	if (!str)
 		fatal_err("Out of memory.\n");
 	return str;
 }
 
 char *
 ledit_strndup(const char *s, size_t n) {
 	char *str = strndup(s, n);
 	if (!str)
 		fatal_err("Out of memory.\n");
 	return str;
 }
 
 void *
 ledit_malloc(size_t size) {
 	void *ptr = malloc(size);
 	if (!ptr)
 		fatal_err("Out of memory.\n");
 	return ptr;
 }
 
 void *
 ledit_calloc(size_t nmemb, size_t size) {
 	void *ptr = calloc(nmemb, size);
 	if (!ptr)
 		fatal_err("Out of memory.\n");
 	return ptr;
 }
 
 void *
 ledit_realloc(void *ptr, size_t size) {
 	void *new_ptr = realloc(ptr, size);
 	if (!new_ptr)
 		fatal_err("Out of memory.\n");
 	return new_ptr;
 }
 
 /* Concatenate the two given strings and return the result.
    This allocates new memory for the result string, unlike
    the actual strcat. Aborts program on error */
 char *
 ledit_strcat(const char *str1, const char *str2) {
 	size_t len1, len2;
 	char *ret;
 
 	len1 = strlen(str1);
 	len2 = strlen(str2);
 	ret = ledit_malloc(len1 + len2 + 1);
 	strcpy(ret, str1);
 	strcpy(ret + len1, str2);
 
 	return ret;
 }
 
 char *
 print_fmt(char *fmt, ...) {
 	va_list args;
 	va_start(args, fmt);
 	int len = vsnprintf(NULL, 0, fmt, args);
 	/* FIXME: what should be done on error? */
 	if (len < 0)
 		fatal_err("Error in vsnprintf called from print_fmt");
 	/* FIXME: overflow */
 	char *str = ledit_malloc(len + 1);
 	va_end(args);
 	va_start(args, fmt);
 	vsnprintf(str, len + 1, fmt, args);
 	va_end(args);
 	return str;
 }
 
 /*
  * This (reallocarray) is from OpenBSD (adapted to exit on error):
  * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net>
  */
 
 /*
  * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
  * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
  */
 #define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4))
 
 void *
 ledit_reallocarray(void *optr, size_t nmemb, size_t size)
 {
 	if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
 	    nmemb > 0 && SIZE_MAX / nmemb < size) {
 		err_overflow();
 	}
 	return ledit_realloc(optr, size * nmemb);
 }
 
 void
 move_gap(
     void *array, size_t elem_size, size_t index,
     size_t gap, size_t cap, size_t len,
     size_t *new_gap_ret) {
 	ledit_assert(array != NULL);
 	ledit_assert(index <= len);
 	ledit_assert(len <= cap);
 	char *carray = (char *)array; /* cast to char * for pointer arithmetic */
 	/* since the array has size cap * elem_size, it is assumed that no overflow happens */
 	if (index > gap) {
 		/* move piece between end of original gap and
 		   index to beginning of original gap */
 		memmove(
 		    carray + gap * elem_size,
 		    carray + (gap + cap - len) * elem_size,
 		    (index - gap) * elem_size
 		);
 	} else if (index < gap) {
 		/* move piece between index and original gap to
 		   end of original gap */
 		memmove(
 		    carray + (index + cap - len) * elem_size,
 		    carray + index * elem_size,
 		    (gap - index) * elem_size
 		);
 	}
 	if (new_gap_ret)
 		*new_gap_ret = index;
 }
 
 /* FIXME: replace with macro version that takes type parameter in order
    to avoid errors with elem_size */
 /* This is almost certainly premature optimization and maybe
    not optimization at all. */
 void *
 resize_and_move_gap(
     void *array, size_t elem_size,
     size_t old_gap, size_t old_cap, size_t len,
     size_t min_size, size_t index,
     size_t *new_gap_ret, size_t *new_cap_ret) {
 	ledit_assert(array != NULL || (len == 0 && old_cap == 0));
 	ledit_assert(index <= len);
 	ledit_assert(len <= old_cap);
 	ledit_assert(old_gap <= len);
 	size_t gap_size = old_cap - len;
 	size_t new_cap = ideal_array_size(old_cap, min_size);;
 	if (new_cap >= old_cap) {
 		if (new_cap > old_cap)
 			array = ledit_reallocarray(array, new_cap, elem_size);
 		char *carray = (char*)array; /* cast to char to do pointer arithmetic */
 		/* we already know new_cap * elem_size does not wrap around because array
 		   is of that size, so all the other multiplications here should be safe
 		   (at least that's what I think, but I may be wrong) */
 		if (index > old_gap) {
 			/* move piece between end of original gap and index to
 			   beginning of original gap */
 			memmove(
 			    carray + old_gap * elem_size,
 			    carray + (old_gap + gap_size) * elem_size,
 			    (index - old_gap) * elem_size
 			);
 			/* move piece after index to end of buffer */
 			memmove(
 			    carray + (new_cap - (len - index)) * elem_size,
 			    carray + (index + gap_size) * elem_size,
 			    (len - index) * elem_size
 			);
 		} else if (index < old_gap) {
 			/* move piece after original gap to end of buffer */
 			memmove(
 			    carray + (new_cap - (len - old_gap)) * elem_size,
 			    carray + (old_gap + gap_size) * elem_size,
 			    (len - old_gap) * elem_size
 			);
 			/* move piece between index and original gap to end */
 			memmove(
 			    carray + (new_cap - len + index) * elem_size,
 			    carray + index * elem_size,
 			    (old_gap - index) * elem_size
 			);
 		} else {
 			/* move piece after original gap to end of buffer */
 			memmove(
 			    carray + (new_cap - (len - old_gap)) * elem_size,
 			    carray + (old_gap + gap_size) * elem_size,
 			    (len - old_gap) * elem_size
 			);
 		}
 	} else {
 		/* otherwise, parts may be cut off */
 		ledit_assert(min_size >= len);
 		/* FIXME: optimize this */
 		if (array)
 			move_gap(array, elem_size, len, old_gap, old_cap, len, NULL);
 		array = ledit_reallocarray(array, new_cap, elem_size);
 		move_gap(array, elem_size, index, len, new_cap, len, NULL);
 	}
 	if (new_gap_ret)
 		*new_gap_ret = index;
 	if (new_cap_ret)
 		*new_cap_ret = new_cap;
 	return array;
 }
 
 /* FIXME: maybe don't double when already very large? */
 /* FIXME: better start size when old == 0? */
 size_t
 ideal_array_size(size_t old, size_t needed) {
 	size_t ret = old;
 	if (old < needed)
 		ret = old * 2 > needed ? old * 2 : needed;
 	else if (needed * 4 < old)
 		ret = old / 2;
 	if (ret == 0)
 		ret = 1; /* not sure if this is necessary */
 	return ret;
 }