Marsyas
0.6.0-alpha
|
00001 /* ----------------------- MODULE vmblock.cpp ----------------------- * 00002 *********************************************************** 00003 * Reference: * 00004 * * 00005 * "Numerical Algorithms with C, by Gisela Engeln-Muellges * 00006 * and Frank Uhlig, Springer-Verlag, 1996". * 00007 **********************************************************/ 00008 00009 #include <marsyas/common_source.h> 00010 #ifndef MARSYAS_MACOSX 00011 #include <malloc.h> 00012 #else 00013 #include <malloc/malloc.h> 00014 #endif 00015 00016 00017 00018 00019 00020 #include <marsyas/basis.h> 00021 #include "vmblock.h" 00022 /*********************************************************************** 00023 * * 00024 * Management of a set of dynamically allocated vectors and matrices * 00025 * ----------------------------------------------------------------- * 00026 * * 00027 * Idea: In many subroutines of this Numerical Library dynamically * 00028 * allocated vectors and matrices are constantly being used. * 00029 * This leads to the recurring problem that there is not enough * 00030 * memory for all of the needed vectors and matrices so that * 00031 * the memory already allocated must be freed and the lack of * 00032 * memory must be dealt with. This is a very laborious task * 00033 * and can lead to recurring errors. * 00034 * This module is designed to simplify the storage management * 00035 * significantly: * 00036 * It can manage all contingent memory allocation for vectors * 00037 * and matrices in one linear list. To handle such a list, the * 00038 * user is provided the following four functions: * 00039 * * 00040 * - vminit() which creates an empty vector/matrix list and * 00041 * returns an untyped list pointer to be used by * 00042 * the following three functions, * 00043 * * 00044 * - vmalloc() which allocates memory for a new vector or a * 00045 * new matrix, inserts its address into the list * 00046 * and returns this address, * 00047 * * 00048 * - vmcomplete() to verify that all prior memory allocations * 00049 * in the list have been successful, and * 00050 * * 00051 * - vmfree() which frees all of the memory taken by the * 00052 * vector/matrix list. * 00053 * * 00054 * Moreover the seven macros * 00055 * * 00056 * - VEKTOR (for REAL vectors), * 00057 * - VVEKTOR (for arbitrary vectors), * 00058 * - MATRIX (for REAL matrices), * 00059 * - IMATRIX (for int matrices), * 00060 * - MMATRIX (for matrices of 4x4 matrices), * 00061 * - UMATRIX (for lower triangular matrices of type REAL) and * 00062 * - PMATRIX (for matrices of points in R3) * 00063 * * 00064 * are exported which allow the user to select the kind of data * 00065 * structure when calling vmalloc(). * 00066 * * 00067 * Attention: 1. The memory taken by a vector/matrix list must * 00068 * only be freed using vmfree()! * 00069 * 2. vmfree() only frees the complete memory * 00070 * belonging to one list and therefore cannot be * 00071 * applied to just one vector or matrix of the * 00072 * list! * 00073 * * 00074 * Usage: The user specifies a void pointer which is initialized * 00075 * by calling vminit() and which gives the only valid entry to * 00076 * the vector/matrix list. * 00077 * Using this pointer vectors and matrices can now be allocated * 00078 * dynamically via vmalloc(). * 00079 * Once all storage needs have been satisfied, one should use * 00080 * vmcomplete() to verify that they all were successful and to * 00081 * react on a possible lack of memory. * 00082 * If the contents of a list is no longer needed, we recommend * 00083 * to free its space by calling vmfree(). * 00084 * Example: * 00085 * ... * 00086 * void *vmblock; /+ start of the vector/matrix list +/ * 00087 * REAL *vektor1; /+ REAL vector with n elements +/ * 00088 * int *vektor2; /+ int vector with n elements +/ * 00089 * REAL **matrix1; /+ Matrix with m rows, n columns +/ * 00090 * int **matrix2; /+ Matrix with m rows, n columns +/ * 00091 * mat4x4 **mmat; /+ matrix with m*n elements of +/ * 00092 * /+ type `mat4x4' (16 REAL values) +/ * 00093 * REAL **umatrix; /+ lower triangular (n,n) matrix +/ * 00094 * REAL ***pmatrix; /+ matrix with m*n points in R3 +/ * 00095 * ... * 00096 * vmblock = vminit(); * 00097 * vektor1 = (REAL *)vmalloc(vmblock, VEKTOR, n, 0); * 00098 * vektor2 = (int *) vmalloc(vmblock, VVEKTOR, n, * 00099 * sizeof(int)); * 00100 * ... * 00101 * matrix1 = (REAL **) vmalloc(vmblock, MATRIX, m, n); * 00102 * matrix2 = (int **) vmalloc(vmblock, IMATRIX, m, n); * 00103 * mmat = (mat4x4 **)vmalloc(vmblock, MMATRIX, m, n); * 00104 * umatrix = (REAL ***) vmalloc(vmblock, UMATRIX, m, 0); * 00105 * pmatrix = (REAL ***) vmalloc(vmblock, PMATRIX, m, n); * 00106 * ... * 00107 * if (! vmcomplete(vmblock)) /+ in parts unsuccessful? +/ * 00108 * { * 00109 * vmfree(vmblock); /+ free memory in list +/ * 00110 * return 99; /+ report error +/ * 00111 * } * 00112 * ... * 00113 * vmfree(vmblock); * 00114 * ... * 00115 * * 00116 * Programming language: ANSI C * 00117 * Compiler: Borland C++ 2.0 * 00118 * Computer: IBM PS/2 70 with 80387 * 00119 * Author: Juergen Dietel, Computer Center, RWTH Aachen * 00120 * Date: 9.10.1992 * 00121 * * 00122 ***********************************************************************/ 00123 00124 00125 /*--------------------------------------------------------------------*/ 00126 00127 typedef struct VML /* Element of a vector/matrix list */ 00128 { 00129 void *vmzeiger; /* pointer to the vector or matrix */ 00130 int typ; /* kind of pointer: vector or matrix */ 00131 /* (possible values: VEKTOR, VVEKTOR, */ 00132 /* MATRIX, IMATRIX, */ 00133 /* MMATRIX, UMATRIX, */ 00134 /* PMATRIX) */ 00135 size_t groesse; /* in the anchor element: the flag that */ 00136 /* indicates failed memory allocations; */ 00137 /* otherwise not used except for matrices */ 00138 /* where `groesse' is "abused" to save */ 00139 /* the number of rows */ 00140 size_t spalten; /* number of columns of matrices of */ 00141 /* points in R3 */ 00142 struct VML *naechst; /* pointer to next element in the list */ 00143 } vmltyp; 00144 /*.IX{vmltyp}*/ 00145 00146 #define VMALLOC (vmltyp *)malloc(sizeof(vmltyp)) /* allocate memory */ 00147 /*.IX{VMALLOC}*/ 00148 /* for a new */ 00149 /* element of the */ 00150 /* list */ 00151 00152 #define LISTE ((vmltyp *)vmblock) /* for abbreviation */ 00153 /*.IX{LISTE}*/ 00154 #define MAGIC 410 /* used to mark a */ 00155 /*.IX{MAGIC}*/ 00156 /* valid anchor */ 00157 /* element */ 00158 00159 00160 00161 /*--------------------------------------------------------------------*/ 00162 00163 void *vminit /* create an empty vector/matrix list ...........*/ 00164 /*.IX{vminit}*/ 00165 ( 00166 void 00167 ) /* address of list ...................*/ 00168 00169 /*********************************************************************** 00170 * Generate an empty vector/matrix list. Such a list consists of a * 00171 * anchor element, which is being used only to hold the `out of memory' * 00172 * flag and a magic number that is used for plausibility checks. * 00173 * The return value here is the address of the anchor element or - in * 00174 * case of error - the value NULL. * 00175 * For subsequent calls of vmalloc(), vmcomplete() and vmfree() we use * 00176 * the component `typ' of the anchor element for the magic value which * 00177 * designates a proper anchor element in order to be able to check * 00178 * whether the supplied untyped pointer in fact points to a * 00179 * vector/matrix list. * 00180 * * 00181 * global names used: * 00182 * ================== * 00183 * vmltyp, VMALLOC, MAGIC, NULL, malloc * 00184 ***********************************************************************/ 00185 00186 { 00187 vmltyp *liste; /* pointer to anchor element of list */ 00188 00189 00190 if ((liste = VMALLOC) == NULL) /* allocate memory for the anchor */ 00191 return NULL; /* unsuccessful? => report error */ 00192 liste->vmzeiger = NULL; /* to make vmfree() error free */ 00193 liste->typ = MAGIC; /* mark a valid anchor element */ 00194 liste->groesse = 0; /* no lack of memory as yet */ 00195 liste->naechst = NULL; /* no next element */ 00196 00197 00198 return (void *)liste; 00199 } 00200 00201 00202 00203 /*--------------------------------------------------------------------*/ 00204 00205 static void matfree /* free memory of a dynamic matrix ..............*/ 00206 /*.IX{matfree}*/ 00207 ( 00208 void **matrix, /* [0..m-1,0..] matrix ...............*/ 00209 size_t m /* number of rows of matrix ..........*/ 00210 ) 00211 00212 /*********************************************************************** 00213 * free the memory of a matrix with m rows as allocated in matmalloc() * 00214 * * 00215 * global names used: * 00216 * ================== * 00217 * size_t, NULL, free * 00218 ***********************************************************************/ 00219 00220 { 00221 #ifdef FAST_ALLOC 00222 void *tmp; /* smallest row address */ 00223 00224 #endif 00225 if (matrix != NULL) /* matrix exists? */ 00226 { 00227 #ifndef FAST_ALLOC /* safe, but expensive allocation? */ 00228 while (m != 0) /* free memory of matrix elements */ 00229 free(matrix[--m]); /* row by row */ 00230 #else /* more economical allocation method? */ 00231 /* (assumes linear address space) */ 00232 for (tmp = matrix[0]; m != 0; ) /* find pointer with smallest */ 00233 if (matrix[--m] < tmp) /* address (necessary because of */ 00234 tmp = matrix[m]; /* possible permutation!) */ 00235 free(tmp); /* free memory of all matrix elements */ 00236 /* at once */ 00237 #endif 00238 free(matrix); /* free all row pointers */ 00239 } 00240 } 00241 00242 00243 00244 /*--------------------------------------------------------------------*/ 00245 00246 /*********************************************************************** 00247 * Allocate memory for a rectangular [0..m-1,0..n-1] matrix with * 00248 * elements of type `typ' and store the starting address of the matrix * 00249 * in `mat', if successful; store NULL else. We form a new pointer to * 00250 * the start of each row of the matrix, which contains n elements. * 00251 * Lack of memory causes the part of the matrix already allocated to be * 00252 * freed. * 00253 * If before compilation of this file the macro FAST_ALLOC was defined, * 00254 * there are still m row pointers used, but (following an idea of * 00255 * Albert Becker) the memory of the m*n matrix elements is allocated in * 00256 * one piece into which the row pointers are directed. * 00257 * According to this, matfree() contains a FAST_ALLOC part as well, * 00258 * where one has to pay attention to the fact that the row pointers * 00259 * could have been permuted since the allocation of the matrix. * 00260 * If a lower triangular matrix is needed (umat != 0), the value n is * 00261 * ignored (because the matrix is quadratic) and memory for only * 00262 * m*(m+1)/2 REAL values is allocated (apart from the row pointers). * 00263 * * 00264 * global names used: * 00265 * ================== * 00266 * size_t, NULL, calloc, matfree * 00267 ***********************************************************************/ 00268 00269 #ifndef FAST_ALLOC /* safe, but expensive allocation? */ 00270 #define matmalloc(mat, m, n, typ, umat) \ 00271 /*.IX{matmalloc}*/ \ 00272 \ 00273 { \ 00274 size_t j, /* current row index */ \ 00275 k; /* elements in row j */ \ 00276 \ 00277 if ((mat = (typ **)calloc((m), sizeof(typ *))) != NULL) \ 00278 for (j = 0; j < (m); j++) \ 00279 { \ 00280 k = (umat) ? (j + 1) : (n); \ 00281 if ((((typ **)mat)[j] = (typ *)calloc(k, sizeof(typ))) == NULL) \ 00282 { \ 00283 matfree((void **)(mat), j); \ 00284 mat = NULL; \ 00285 break; \ 00286 } \ 00287 } \ 00288 } 00289 #else /* more economical allocation method? */ 00290 /* (assumes linear address space) */ 00291 #define matmalloc(mat, m, n, typ, umat) \ 00292 /*.IX{matmalloc}*/ \ 00293 \ 00294 { \ 00295 typ *tmp; /* address of the contingent area of memory where */ \ 00296 /* all memory elements reside */ \ 00297 size_t j, /* current row index */ \ 00298 k, /* index for `tmp' to the j. row (value: j*n) */ \ 00299 l; /* size of memory space: full (m*n elements) or */ \ 00300 /* lower triangular (m*(m+1)/2 elements) matrix */ \ 00301 \ 00302 if ((mat = (typ **)calloc((m), sizeof(typ *))) != NULL) \ 00303 { \ 00304 l = (umat) ? (((m) * ((m) + 1)) / 2) : ((m) * (n)); \ 00305 if ((tmp = (typ *)calloc(l, sizeof(typ))) != NULL) \ 00306 for (j = k = 0; j < (m); j++) \ 00307 ((typ **)mat)[j] = tmp + k, \ 00308 k += (umat) ? (j + 1) : (n); \ 00309 else \ 00310 { \ 00311 free(mat); \ 00312 mat = NULL; \ 00313 } \ 00314 } \ 00315 } 00316 #endif 00317 00318 00319 00320 /*--------------------------------------------------------------------*/ 00321 00322 static void pmatfree /* free memory of a matrix of R3 points ........*/ 00323 /*.IX{pmatfree}*/ 00324 ( 00325 void ***matrix, /* [0..m-1,0..n-1] matrix of points ..*/ 00326 size_t m, /* number of rows of matrix ..........*/ 00327 size_t n /* number of columns of matrix .......*/ 00328 ) 00329 00330 /*********************************************************************** 00331 * free a matrix with m rows and n columns as allocated in pmatmalloc() * 00332 * * 00333 * global names used: * 00334 * ================== * 00335 * size_t, NULL, free, matfree * 00336 ***********************************************************************/ 00337 00338 { 00339 if (matrix != NULL) /* matrix exists? */ 00340 { 00341 while (m != 0) /* free memory of matrix elements */ 00342 matfree(matrix[--m], n); /* row by row */ 00343 free(matrix); /* free row pointers */ 00344 } 00345 } 00346 00347 00348 00349 /*--------------------------------------------------------------------*/ 00350 00351 static REAL ***pmatmalloc /* allocate memory for a matrix of points */ 00352 /*.IX{pmatmalloc}*/ 00353 ( 00354 size_t m, /* number of rows of matrix ..........*/ 00355 size_t n /* number of columns of matrix .......*/ 00356 ) /* address of matrix .................*/ 00357 00358 /*********************************************************************** 00359 * Allocate memory for a [0..m-1,0..n-1,0..2] matrix with REAL elements * 00360 * and return its starting address, if successful; return NULL else. We * 00361 * form a new pointer to the start of each row of the matrix. * 00362 * * 00363 * global names used: * 00364 * ================== * 00365 * size_t, REAL, NULL, calloc, pmatfree, matmalloc * 00366 ***********************************************************************/ 00367 00368 { 00369 REAL ***matrix; /* pointer to row vectors */ 00370 size_t i; /* current row index */ 00371 00372 00373 matrix = (REAL ***) /* one pointer for each */ 00374 calloc(m, sizeof(*matrix)); /* of the m rows */ 00375 00376 if (matrix == NULL) /* lack of memory? */ 00377 return NULL; /* report this lack */ 00378 00379 for (i = 0; i < m; ++i) /* allocate one (n,3) matrix */ 00380 { /* for each row pointer */ 00381 matmalloc(matrix[i], n, 3, REAL, 0); 00382 if (matrix[i] == NULL) /* lack of memory? */ 00383 { 00384 pmatfree((void ***)matrix, i, 3); /* free (n,3) matrices */ 00385 /* already allocated */ 00386 return NULL; /* report lack of memory */ 00387 } 00388 } 00389 00390 00391 return matrix; 00392 } 00393 00394 00395 00396 /*--------------------------------------------------------------------*/ 00397 00398 void *vmalloc /* create a dynamic vector or matrix ............*/ 00399 /*.IX{vmalloc}*/ 00400 ( 00401 void *vmblock, /* address of a vector/matrix list ...*/ 00402 int typ, /* kind of vector or matrix ..........*/ 00403 size_t zeilen, /* length (vector) or number of rows .*/ 00404 size_t spalten /* number of columns or element size .*/ 00405 ) /* address of the created object .....*/ 00406 00407 /*********************************************************************** 00408 * Create an element according to `typ' (vector or matrix), whose size * 00409 * is determined by the parameters `zeilen' and `spalten'. This object * 00410 * is inserted into the linear list starting at `vmblock'. * 00411 * The address of the new vector or matrix is returned. * 00412 * For a REAL vector (kind VEKTOR) the parameter `zeilen' contains its * 00413 * length, `spalten' is not used. For arbitrary vectors (kind VVEKTOR) * 00414 * the parameter `spalten' must contain the size of one vector element. * 00415 * For a full matrix (kind MATRIX, IMATRIX, MMATRIX or PMATRIX) the * 00416 * parameter `zeilen' contains the number of rows, while `spalten' * 00417 * contains the number of columns of the matrix. For a (quadratic) * 00418 * lower triangular matrix (kind UMATRIX) `zeilen' contains the number * 00419 * of rows resp. columns of the matrix. * 00420 * * 00421 * global names used: * 00422 * ================== * 00423 * vmltyp, VMALLOC, LISTE, MAGIC, matmalloc, pmatmalloc, REAL, VEKTOR, * 00424 * VVEKTOR, MATRIX, IMATRIX, MMATRIX, UMATRIX, PMATRIX, NULL, size_t, * 00425 * malloc, calloc, mat4x4, matmalloc * 00426 ***********************************************************************/ 00427 00428 { 00429 vmltyp *element; /* pointer to new element in list */ 00430 00431 00432 if (LISTE == NULL || /* invalid list? */ 00433 LISTE->typ != MAGIC) /* invalid starting element? */ 00434 return NULL; /* report error */ 00435 00436 00437 if ((element = VMALLOC) == NULL) /* ask for a new element */ 00438 { /* no success? => */ 00439 LISTE->groesse = 1; /* indicate lack of memory */ 00440 return NULL; /* report error */ 00441 } 00442 00443 switch (typ) /* allocate memory for the desired data */ 00444 { /* structure (vector or matrix) and record its */ 00445 /* address in the new list element */ 00446 00447 case VEKTOR: /* ---------- REAL vector? ---------- */ 00448 element->vmzeiger = calloc(zeilen, sizeof(REAL)); 00449 break; 00450 00451 case VVEKTOR: /* ---------- arbitrary vector? ---------- */ 00452 element->vmzeiger = calloc(zeilen, spalten); 00453 break; 00454 00455 case MATRIX: /* ---------- REAL matrix? ---------- */ 00456 matmalloc(element->vmzeiger, zeilen, spalten, REAL, 0); 00457 element->groesse = zeilen; /* put row number into */ 00458 break; /* `groesse' for vmfree() */ 00459 00460 case IMATRIX: /* ---------- int matrix? ---------- */ 00461 matmalloc(element->vmzeiger, zeilen, spalten, int, 0); 00462 element->groesse = zeilen; /* put row number into */ 00463 break; /* `groesse' for vmfree() */ 00464 00465 case MMATRIX: /* ---------- mat4x4 matrix? ---------- */ 00466 matmalloc(element->vmzeiger, zeilen, spalten, mat4x4, 0); 00467 element->groesse = zeilen; /* put row number into */ 00468 break; /* `groesse' for vmfree() */ 00469 00470 case UMATRIX: /* ---------- untere Dreiecksmatrix? ------ */ 00471 matmalloc(element->vmzeiger, zeilen, 0, mat4x4, 1); 00472 element->groesse = zeilen; /* put row number into */ 00473 break; /* `groesse' for vmfree() */ 00474 00475 case PMATRIX: /* ---------- matrix with points in R3? --- */ 00476 element->vmzeiger = (void *)pmatmalloc(zeilen, spalten); 00477 element->groesse = zeilen; /* put row number into */ 00478 element->spalten = spalten; /* `groesse' and column number */ 00479 break; /* into `spalten' for vmfree() */ 00480 00481 default: /* ---- invalid data type? ------------- */ 00482 element->vmzeiger = NULL; /* record zero pointer */ 00483 } 00484 00485 if (element->vmzeiger == NULL) /* no memory for the object? */ 00486 LISTE->groesse = 1; /* Let's note that down. */ 00487 00488 element->typ = typ; /* note kind of data structure */ 00489 /* in the list element */ 00490 element->naechst = LISTE->naechst; /* insert new element before */ 00491 /* the first existing element, */ 00492 00493 LISTE->naechst = element; /* but behind the anchor */ 00494 /* element */ 00495 00496 return element->vmzeiger; /* return new vector/matrix */ 00497 } /* address */ 00498 00499 00500 00501 /*--------------------------------------------------------------------*/ 00502 00503 bool vmcomplete /* check vector/matrix list for lack of memory ..*/ 00504 ( 00505 void *vmblock /* address of list ...................*/ 00506 ) /* no lack of memory? ................*/ 00507 /*********************************************************************** 00508 * Here just the negated value of the flag in the anchor element is * 00509 * returned which belongs to the vector/matrix list represented by * 00510 * `vmblock'. Thus this functions reports whether all memory * 00511 * allocations in the list have been successful (TRUE) or not (FALSE). * 00512 * * 00513 * global names used: * 00514 * ================== * 00515 * LISTE * 00516 ***********************************************************************/ 00517 { 00518 return LISTE->groesse ? FALSE : TRUE; 00519 } 00520 00521 00522 00523 /*--------------------------------------------------------------------*/ 00524 00525 void vmfree /* free the memory for a vektor/matrix list .....*/ 00526 /*.IX{vmfree}*/ 00527 ( 00528 void *vmblock /* address of list ...................*/ 00529 ) 00530 00531 /*********************************************************************** 00532 * free all dynamic memory consumed by the list beginning at `vmblock' * 00533 * * 00534 * global names used: * 00535 * ================== * 00536 * vmltyp, LISTE, MAGIC, matfree, pmatfree, VEKTOR, VVEKTOR, MATRIX, * 00537 * IMATRIX, MMATRIX, UMATRIX, PMATRIX, NULL, free * 00538 ***********************************************************************/ 00539 00540 { 00541 vmltyp *hilf; /* aux variable for value of pointer */ 00542 00543 00544 if (LISTE == NULL) /* invalid list? */ 00545 return; /* do nothing */ 00546 00547 if (LISTE->typ != MAGIC) /* invalid anchor element? */ 00548 return; /* do nothing again */ 00549 00550 00551 for ( ; LISTE != NULL; vmblock = (void *)hilf) 00552 { 00553 00554 switch (LISTE->typ) 00555 { 00556 case VEKTOR: 00557 case VVEKTOR: if (LISTE->vmzeiger != NULL) 00558 free(LISTE->vmzeiger); 00559 break; 00560 case MATRIX: 00561 case IMATRIX: 00562 case MMATRIX: 00563 case UMATRIX: matfree((void **)LISTE->vmzeiger, 00564 LISTE->groesse); 00565 break; 00566 case PMATRIX: pmatfree((void ***)LISTE->vmzeiger, 00567 LISTE->groesse, LISTE->spalten); 00568 } 00569 00570 hilf = LISTE->naechst; /* save pointer to successor */ 00571 free(LISTE); /* free list element */ 00572 } 00573 } 00574 00575 /* ------------------------ END vmblock.cpp ------------------------- */