From b64acd496028fb582d052f9e7fccfe6d542f85ca Mon Sep 17 00:00:00 2001 From: giraffedata Date: Sun, 27 Jun 2010 19:52:28 +0000 Subject: Add MALLOCARRAY2 git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@1249 9d0c8265-081b-0410-96cb-a4ca84ce46f8 --- lib/Makefile | 1 + lib/libpm.c | 149 ++++------------------------------------- lib/util/Makefile | 1 + lib/util/mallocvar.c | 185 +++++++++++++++++++++++++++++++++++++++++++++++++++ lib/util/mallocvar.h | 21 ++++++ 5 files changed, 222 insertions(+), 135 deletions(-) create mode 100644 lib/util/mallocvar.c (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index ecb3a035..505aef6d 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -40,6 +40,7 @@ LIBOBJECTS = libpm.o pmfileio.o fileio.o bitio.o colorname.o \ LIBOBJECTS_X = \ util/filename.o \ util/io.o \ + util/mallocvar.o \ util/nsleep.o \ util/nstring.o \ util/shhopt.o \ diff --git a/lib/libpm.c b/lib/libpm.c index b8a322a1..6c01148c 100644 --- a/lib/libpm.c +++ b/lib/libpm.c @@ -311,140 +311,26 @@ pm_freerow(void * const itrow) { -static void -allocarrayNoHeap(unsigned char ** const rowIndex, - unsigned int const cols, - unsigned int const rows, - unsigned int const size, - const char ** const errorP) { - - if (cols != 0 && UINT_MAX / cols < size) - asprintfN(errorP, - "Arithmetic overflow multiplying %u by %u to get the " - "size of a row to allocate.", cols, size); - else { - unsigned int rowsDone; - - rowsDone = 0; - *errorP = NULL; - - while (rowsDone < rows && !*errorP) { - unsigned char * const rowSpace = mallocz(cols * size); - if (rowSpace == NULL) - asprintfN(errorP, - "Unable to allocate a %u-column by %u byte row", - cols, size); - else - rowIndex[rowsDone++] = rowSpace; - } - if (*errorP) { - unsigned int row; - for (row = 0; row < rowsDone; ++row) - free(rowIndex[row]); - } - } -} - - - -static unsigned char * -allocRowHeap(unsigned int const cols, - unsigned int const rows, - unsigned int const size) { -/*---------------------------------------------------------------------------- - Allocate a row heap. That's a chunk of memory for use in a - pm_allocarray two-dimensional array to contain the rows. - - The heap must fit 'rows' rows of 'cols' columns each of elements - 'size' bytes in size. - - Return NULL if we can't get the memory. ------------------------------------------------------------------------------*/ - unsigned char * retval; - - if (cols != 0 && rows != 0 && UINT_MAX / cols / rows < size) - /* Too big even to request the memory ! */ - retval = NULL; - else - retval = mallocz(rows * cols * size); - - return retval; -} - - - char ** pm_allocarray(int const cols, int const rows, - int const size ) { + int const elementSize ) { /*---------------------------------------------------------------------------- - Allocate an array of 'rows' rows of 'cols' columns each, with each - element 'size' bytes. - - We use the C multidimensional array paradigm: The array is a row - index (array of pointers to rows) plus an array of elements for each - of those rows. So a[row][col] gives you the element of the two - dimensional array at Row 'row', Column 'col'. - - But we use a special variation on that where we tack on an extra element to - the row index to indicate the format of the array. - - We do NOT TAKE CARE OF ALIGNMENT. Alignment of the elements is only one - byte even if 'size' indicates elements are 4 bytes each. Normally, it - would be a good idea to align such elements to 4 byte boundaries (address - is a multiple of 4). But we don't, so watch out. - - We have two ways of allocating the space: fragmented and - unfragmented. In both, the row index (plus the extra element) is - in one block of memory. In the fragmented format, each row is - also in an independent memory block, and the extra row pointer is - NULL. In the unfragmented format, all the rows are in a single - block of memory called the row heap and the extra row pointer is - the address of that block. - - We use unfragmented format if possible, but if the allocation of the - row heap fails, we fall back to fragmented. ------------------------------------------------------------------------------*/ - unsigned char ** rowIndex; - const char * error; - - MALLOCARRAY(rowIndex, rows + 1); - if (rowIndex == NULL) - asprintfN(&error, - "out of memory allocating row index (%u rows) for an array", - rows); - else { - unsigned char * rowheap; + This is for backward compatibility. MALLOCARRAY2 is usually better. - rowheap = allocRowHeap(cols, rows, size); + A problem with pm_allocarray() is that its return type is char ** + even though 'elementSize' can be other than 1. So users have + traditionally type cast the result. In the old days, that was just + messy; modern compilers can produce the wrong code if you do that. +-----------------------------------------------------------------------------*/ + char ** retval; + void * result; - if (rowheap) { - /* It's unfragmented format */ + pm_mallocarray2(&result, rows, cols, elementSize); - rowIndex[rows] = rowheap; /* Declare it unfragmented format */ + retval = result; - if (rowheap) { - unsigned int row; - - for (row = 0; row < rows; ++row) - rowIndex[row] = &(rowheap[row * cols * size]); - } - error = NULL; - } else { - /* We couldn't get the whole heap in one block, so try fragmented - format. - */ - rowIndex[rows] = NULL; /* Declare it fragmented format */ - - allocarrayNoHeap(rowIndex, cols, rows, size, &error); - } - } - if (error) { - pm_errormsg("Couldn't allocate %u-row array. %s", rows, error); - strfree(error); - pm_longjmp(); - } - return (char **)rowIndex; + return retval; } @@ -453,16 +339,9 @@ void pm_freearray(char ** const rowIndex, int const rows) { - void * const rowheap = rowIndex[rows]; + void * const rowIndexVoid = rowIndex; - if (rowheap != NULL) - free(rowheap); - else { - unsigned int row; - for (row = 0; row < rows; ++row) - pm_freerow(rowIndex[row]); - } - free(rowIndex); + pm_freearray2(rowIndexVoid); } diff --git a/lib/util/Makefile b/lib/util/Makefile index 8d93731e..0cb23449 100644 --- a/lib/util/Makefile +++ b/lib/util/Makefile @@ -12,6 +12,7 @@ include $(BUILDDIR)/config.mk UTILOBJECTS = \ filename.o \ io.o \ + mallocvar.o \ nsleep.o \ nstring.o \ shhopt.o \ diff --git a/lib/util/mallocvar.c b/lib/util/mallocvar.c new file mode 100644 index 00000000..554030ad --- /dev/null +++ b/lib/util/mallocvar.c @@ -0,0 +1,185 @@ +#include +#include + +#include "pm_c_util.h" +#include "nstring.h" + +#include "mallocvar.h" + + +static void * +mallocz(size_t const size) { +/*---------------------------------------------------------------------------- + Same as malloc(), except it is legal to allocate zero bytes. +-----------------------------------------------------------------------------*/ + return malloc(MAX(1, size)); +} + + + +static void +allocarrayNoHeap(void ** const rowIndex, + unsigned int const rows, + unsigned int const cols, + unsigned int const elementSize, + bool * const failedP) { + + unsigned int rowsDone; + + for (rowsDone = 0, *failedP = false; rowsDone < rows && !*failedP; ) { + void * rowSpace; + + mallocProduct(&rowSpace, cols, elementSize); + + if (rowSpace == NULL) { + unsigned int row; + + *failedP = true; + + /* unwind partially completed job */ + for (row = 0; row < rowsDone; ++row) + free(rowIndex[row]); + } else + rowIndex[rowsDone++] = rowSpace; + } +} + + + +static unsigned char * +allocRowHeap(unsigned int const rows, + unsigned int const cols, + unsigned int const size) { +/*---------------------------------------------------------------------------- + Allocate a row heap. That's a chunk of memory for use in a + pm_mallocarray2 two-dimensional array to contain the rows. + + The heap must fit 'rows' rows of 'cols' columns each of elements + 'size' bytes in size. + + Return NULL if we can't get the memory. +-----------------------------------------------------------------------------*/ + unsigned char * retval; + + if (cols != 0 && rows != 0 && UINT_MAX / cols / rows < size) + /* Too big even to request the memory ! */ + retval = NULL; + else + retval = mallocz(rows * cols * size); + + return retval; +} + + + +void +pm_mallocarray2(void ** const resultP, + unsigned int const rows, + unsigned int const cols, + unsigned int const elementSize) { +/*---------------------------------------------------------------------------- + Allocate an array of 'rows' rows of 'cols' columns each, with each + element 'size' bytes. + + We use the C multidimensional array paradigm: The array is a row + index (array of pointers to rows) plus an array of elements for each + of those rows. So a[row][col] gives you the element of the two + dimensional array at Row 'row', Column 'col'. + + Each array element is ideally aligned to an 'elementSize' boundary. + But we guarantee this only for 1, 2, 4, 8, and 16, due to limitations of + libc malloc() (which we use to allocate all the memory). + + We tack on two extra elements to the end of the row index, transparent to + the user, for use in memory management (in particular, in destroying the + array). The first is a NULL pointer, so you can tell the vertical + dimension of the array. The second points to the row heap (see below). + + We have two ways of allocating the space: fragmented and unfragmented. In + both, the row index (plus the extra elements) is in one block of memory. + In the fragmented format, each row is also in an independent memory block, + and the row heap pointer (see above) is NULL. In the unfragmented format, + all the rows are in a single block of memory called the row heap and the + row heap pointer points to that. + + We use unfragmented format if possible, but if the allocation of the + row heap fails, we fall back to fragmented. +-----------------------------------------------------------------------------*/ + void ** rowIndex; + bool failed; + + MALLOCARRAY(rowIndex, rows + 1 + 1); + if (rowIndex == NULL) + failed = true; + else { + unsigned char * rowheap; + + rowheap = allocRowHeap(cols, rows, elementSize); + + if (rowheap) { + /* It's unfragmented format */ + + rowIndex[rows+1] = rowheap; /* Declare it unfragmented format */ + + if (rowheap) { + unsigned int row; + + for (row = 0; row < rows; ++row) + rowIndex[row] = &(rowheap[row * cols * elementSize]); + } + failed = false; + } else { + /* We couldn't get the whole heap in one block, so try fragmented + format. + */ + rowIndex[rows+1] = NULL; /* Declare it fragmented format */ + + allocarrayNoHeap(rowIndex, cols, rows, elementSize, &failed); + } + rowIndex[rows+0] = NULL; /* mark end of rows */ + } + if (failed) + *resultP = NULL; + else + *resultP = rowIndex; +} + + + +static unsigned int +array2RowCount(void ** const rowIndex) { +/*---------------------------------------------------------------------------- + Return the number of rows in the 2-dimensional array. +-----------------------------------------------------------------------------*/ + /* The end of the rows is marked by a null pointer where a row + pointer otherwise would be. + */ + + unsigned int row; + + for (row = 0; rowIndex[row]; ++row); + + return row; +} + + + +void +pm_freearray2(void ** const rowIndex) { + + unsigned int const rows = array2RowCount(rowIndex); + + void * const rowheap = rowIndex[rows+1]; + + if (rowheap != NULL) + free(rowheap); + else { + /* Free each individually malloced row */ + unsigned int row; + for (row = 0; row < rows; ++row) + pm_freerow(rowIndex[row]); + } + free(rowIndex); +} + + diff --git a/lib/util/mallocvar.h b/lib/util/mallocvar.h index 1f2be127..a97b5a00 100644 --- a/lib/util/mallocvar.h +++ b/lib/util/mallocvar.h @@ -107,6 +107,21 @@ do { \ abort(); \ } while(0) +#define MALLOCARRAY2(arrayName, nRows, nCols, elementSz) do { \ + void * array; \ + mallocarray2(&array, nRows, nCols, sizeof(arrayName[0][0])); \ + arrayName = array; \ +} while (0) + +#define MALLOCARRAY2_NOFAIL(arrayName, nRows, nCols, elementSz) do { \ + MALLOCARRAY_NOFAIL(arrayName, nRows, nCols, elementSz); \ + if ((arrayName) == NULL) \ + abort(); \ +} while (0) + +void +pm_freearray2(void ** const rowIndex); + #define MALLOCVAR(varName) \ varName = malloc(sizeof(*varName)) @@ -114,6 +129,12 @@ do { \ #define MALLOCVAR_NOFAIL(varName) \ do {if ((varName = malloc(sizeof(*varName))) == NULL) abort();} while(0) +void +pm_mallocarray2(void ** const resultP, + unsigned int const cols, + unsigned int const rows, + unsigned int const elementSize); + #ifdef __cplusplus } #endif -- cgit 1.4.1