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