Scippy

SCIP

Solving Constraint Integer Programs

memory.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the library */
4 /* BMS --- Block Memory Shell */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* BMS is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with BMS; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file memory.c
17  * @ingroup OTHER_CFILES
18  * @brief memory allocation routines
19  * @author Tobias Achterberg
20  * @author Gerald Gamrath
21  * @author Marc Pfetsch
22  * @author Jakob Witzig
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #ifdef __cplusplus
28 #define __STDC_LIMIT_MACROS
29 #endif
30 
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <assert.h>
34 #include <string.h>
35 
36 /*
37  * include build configuration flags
38  */
39 #ifndef NO_CONFIG_HEADER
40 #include "scip/config.h"
41 #endif
42 
43 #ifdef WITH_SCIPDEF
44 #include "scip/def.h"
45 #include "scip/pub_message.h"
46 #else
47 #include <stdint.h>
48 #endif
49 
50 #include "blockmemshell/memory.h"
51 #include "scip/rbtree.h"
52 
53 /* uncomment the following to enable the use of a memlist in debug mode
54  * that checks for some memory leaks and allows to add the additional
55  * checks enabled with the defines below.
56  * The maintenance of the memlist, however, is not threadsafe.
57  */
58 #ifdef NPARASCIP
59 /*#define ENABLE_MEMLIST_CHECKS*/
60 #endif
61 
62 #ifdef ENABLE_MEMLIST_CHECKS
63 /* uncomment the following for debugging:
64  * - CHECKMEM: run a thorough test on every memory function call, very slow
65  * - CHECKCHKFREE: check for the presence of a pointer in a chunk block
66  */
67 /*#define CHECKMEM*/
68 /*#define CHECKCHKFREE*/
69 #endif
70 
71 /* Uncomment the following for checks that clean buffer is really clean when being freed. */
72 /* #define CHECKCLEANBUFFER */
73 
74 /* Uncomment the following for a warnings if buffers are not freed in the reverse order of allocation. */
75 /* #define CHECKBUFFERORDER */
76 
77 /* if we are included in SCIP, use SCIP's message output methods */
78 #ifdef SCIPdebugMessage
79 #define debugMessage SCIPdebugMessage
80 #define errorMessage SCIPerrorMessage
81 #else
82 #define debugMessage while( FALSE ) printf
83 #define errorMessage printf
84 #define printErrorHeader(f,l) printf("[%s:%d] ERROR: ", f, l)
85 #define printError printf
86 #endif
87 
88 #ifdef ENABLE_MEMLIST_CHECKS
89 #define warningMessage printf
90 #endif
91 #define printInfo printf
92 
93 /* define some macros (if not already defined) */
94 #ifndef FALSE
95 #define FALSE 0
96 #define TRUE 1
97 #endif
98 #ifndef MAX
99 #define MAX(x,y) ((x) >= (y) ? (x) : (y))
100 #define MIN(x,y) ((x) <= (y) ? (x) : (y))
101 #endif
102 
103 #ifndef SCIP_LONGINT_FORMAT
104 #if defined(_WIN32) || defined(_WIN64)
105 #define LONGINT_FORMAT "I64d"
106 #else
107 #define LONGINT_FORMAT "lld"
108 #endif
109 #else
110 #define LONGINT_FORMAT SCIP_LONGINT_FORMAT
111 #endif
112 
113 #ifndef SCIP_MAXMEMSIZE
114 /* we take SIZE_MAX / 2 to detect negative sizes which got a very large value when casting to (unsigned) size_t */
115 #define MAXMEMSIZE SIZE_MAX / 2
116 #else
117 #define MAXMEMSIZE SCIP_MAXMEMSIZE
118 #endif
119 
120 /* define inline (if not already defined) */
121 #ifndef INLINE
122 #if defined(_WIN32) || defined(_WIN64) || defined(__STDC__)
123 #define INLINE __inline
124 #else
125 #define INLINE inline
126 #endif
127 #endif
128 
129 /*************************************************************************************
130  * Standard Memory Management
131  *
132  * In debug mode, these methods extend malloc() and free() by logging all currently
133  * allocated memory elements in an allocation list. This can be used as a simple leak
134  * detection.
135  *************************************************************************************/
136 #if !defined(NDEBUG) && defined(ENABLE_MEMLIST_CHECKS)
137 
138 typedef struct Memlist MEMLIST; /**< memory list for debugging purposes */
139 
140 /** memory list for debugging purposes */
141 struct Memlist
142 {
143  const void* ptr; /**< pointer to allocated memory */
144  size_t size; /**< size of memory element */
145  char* filename; /**< source file where the allocation was performed */
146  int line; /**< line number in source file where the allocation was performed */
147  MEMLIST* next; /**< next entry in the memory list */
148 };
149 
150 static MEMLIST* memlist = NULL; /**< global memory list for debugging purposes */
151 static size_t memused = 0; /**< number of allocated bytes */
152 
153 #ifdef CHECKMEM
154 /** checks, whether the number of allocated bytes match the entries in the memory list */
155 static
156 void checkMemlist(
157  void
158  )
159 {
160  MEMLIST* list = memlist;
161  size_t used = 0;
162 
163  while( list != NULL )
164  {
165  used += list->size;
166  list = list->next;
167  }
168  assert(used == memused);
169 }
170 #else
171 #define checkMemlist() /**/
172 #endif
173 
174 /** adds entry to list of allocated memory */
175 static
176 void addMemlistEntry(
177  const void* ptr, /**< pointer to allocated memory */
178  size_t size, /**< size of memory element */
179  const char* filename, /**< source file where the allocation was performed */
180  int line /**< line number in source file where the allocation was performed */
181  )
182 {
183  MEMLIST* list;
184 
185  assert(ptr != NULL && size > 0);
186 
187  list = (MEMLIST*)malloc(sizeof(MEMLIST));
188  assert(list != NULL);
189 
190  list->ptr = ptr;
191  list->size = size;
192  list->filename = strdup(filename);
193  assert(list->filename != NULL);
194  list->line = line;
195  list->next = memlist;
196  memlist = list;
197  memused += size;
198  checkMemlist();
199 }
200 
201 /** removes entry from the list of allocated memory */
202 static
203 void removeMemlistEntry(
204  const void* ptr, /**< pointer to allocated memory */
205  const char* filename, /**< source file where the deallocation was performed */
206  int line /**< line number in source file where the deallocation was performed */
207  )
208 {
209  MEMLIST* list;
210  MEMLIST** listptr;
211 
212  assert(ptr != NULL);
213 
214  list = memlist;
215  listptr = &memlist;
216  while( list != NULL && ptr != list->ptr )
217  {
218  listptr = &(list->next);
219  list = list->next;
220  }
221  if( list != NULL )
222  {
223  assert(ptr == list->ptr);
224 
225  *listptr = list->next;
226  assert( list->size <= memused );
227  memused -= list->size;
228  free(list->filename);
229  free(list);
230  }
231  else
232  {
233  printErrorHeader(filename, line);
234  printError("Tried to free unknown pointer <%p>.\n", ptr);
235  }
236  checkMemlist();
237 }
238 
239 /** returns the size of an allocated memory element */
241  const void* ptr /**< pointer to allocated memory */
242  )
243 {
244  MEMLIST* list;
245 
246  list = memlist;
247  while( list != NULL && ptr != list->ptr )
248  list = list->next;
249  if( list != NULL )
250  return list->size;
251  else
252  return 0;
253 }
254 
255 /** outputs information about currently allocated memory to the screen */
257  void
258  )
259 {
260  MEMLIST* list;
261  size_t used = 0;
262 
263  printInfo("Allocated memory:\n");
264  list = memlist;
265  while( list != NULL )
266  {
267  printInfo("%12p %8llu %s:%d\n", list->ptr, (unsigned long long) list->size, list->filename, list->line);
268  used += list->size;
269  list = list->next;
270  }
271  printInfo("Total: %8llu\n", (unsigned long long) memused);
272  if( used != memused )
273  {
274  errorMessage("Used memory in list sums up to %llu instead of %llu\n", (unsigned long long)used, (unsigned long long)memused);
275  }
276  checkMemlist();
277 }
278 
279 /** displays a warning message on the screen, if allocated memory exists */
281  void
282  )
283 {
284  if( memlist != NULL || memused > 0 )
285  {
286  warningMessage("Memory list not empty.\n");
288  }
289 }
290 
291 /** returns total number of allocated bytes */
292 long long BMSgetMemoryUsed_call(
293  void
294  )
295 {
296  return (long long) memused;
297 }
298 
299 #else
300 
301 #define addMemlistEntry(ptr, size, filename, line) do { (void) (ptr); (void) (size); (void) (filename); (void) (line); } while(0)
302 #define removeMemlistEntry(ptr, filename, line) do { (void) (ptr); (void) (filename); (void) (line); } while(0)
303 
304 /* these methods are implemented even in optimized mode, such that a program, that includes memory.h in debug mode
305  * but links the optimized version compiles
306  */
307 
308 /** returns the size of an allocated memory element */
310  const void* ptr /**< pointer to allocated memory */
311  )
312 {
313  (void) ptr;
314  return 0;
315 }
316 
317 /** outputs information about currently allocated memory to the screen */
319  void
320  )
321 {
322  printInfo("Optimized, threadsafe version of memory shell linked - no memory diagnostics available.\n");
323 }
324 
325 /** displays a warning message on the screen, if allocated memory exists */
327  void
328  )
329 {
330 }
331 
332 /** returns total number of allocated bytes */
334  void
335  )
336 {
337  return 0;
338 }
339 
340 #endif
341 
342 /** allocates array and initializes it with 0; returns NULL if memory allocation failed */
344  size_t num, /**< number of memory element to allocate */
345  size_t typesize, /**< size of one memory element to allocate */
346  const char* filename, /**< source file where the allocation is performed */
347  int line /**< line number in source file where the allocation is performed */
348  )
349 {
350  void* ptr;
351 
352  assert(typesize > 0);
353 
354  debugMessage("calloc %llu elements of %llu bytes [%s:%d]\n", (unsigned long long)num, (unsigned long long)typesize,
355  filename, line);
356 
357 #ifndef NDEBUG
358  if ( num > (MAXMEMSIZE / typesize) )
359  {
360  printErrorHeader(filename, line);
361  printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE);
362  return NULL;
363  }
364 #endif
365 
366  num = MAX(num, 1);
367  typesize = MAX(typesize, 1);
368  ptr = calloc(num, typesize);
369 
370  if( ptr == NULL )
371  {
372  printErrorHeader(filename, line);
373  printError("Insufficient memory for allocation of %llu bytes.\n", (unsigned long long)(num) * (typesize));
374  }
375  else
376  addMemlistEntry(ptr, num*typesize, filename, line);
377 
378  return ptr;
379 }
380 
381 /** allocates memory; returns NULL if memory allocation failed */
383  size_t size, /**< size of memory element to allocate */
384  const char* filename, /**< source file where the allocation is performed */
385  int line /**< line number in source file where the allocation is performed */
386  )
387 {
388  void* ptr;
389 
390  debugMessage("malloc %llu bytes [%s:%d]\n", (unsigned long long)size, filename, line);
391 
392 #ifndef NDEBUG
393  if ( size > MAXMEMSIZE )
394  {
395  printErrorHeader(filename, line);
396  printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE);
397  return NULL;
398  }
399 #endif
400 
401  size = MAX(size, 1);
402  ptr = malloc(size);
403 
404  if( ptr == NULL )
405  {
406  printErrorHeader(filename, line);
407  printError("Insufficient memory for allocation of %llu bytes.\n", (unsigned long long)size);
408  }
409  else
410  addMemlistEntry(ptr, size, filename, line);
411 
412  return ptr;
413 }
414 
415 /** allocates array; returns NULL if memory allocation failed */
417  size_t num, /**< number of components of array to allocate */
418  size_t typesize, /**< size of each component */
419  const char* filename, /**< source file where the allocation is performed */
420  int line /**< line number in source file where the allocation is performed */
421  )
422 {
423  void* ptr;
424  size_t size;
425 
426  debugMessage("malloc %llu elements of %llu bytes [%s:%d]\n",
427  (unsigned long long)num, (unsigned long long)typesize, filename, line);
428 
429 #ifndef NDEBUG
430  if ( num > (MAXMEMSIZE / typesize) )
431  {
432  printErrorHeader(filename, line);
433  printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE);
434  return NULL;
435  }
436 #endif
437 
438  size = num * typesize;
439  size = MAX(size, 1);
440  ptr = malloc(size);
441 
442  if( ptr == NULL )
443  {
444  printErrorHeader(filename, line);
445  printError("Insufficient memory for allocation of %llu bytes.\n", (unsigned long long)size);
446  }
447  else
448  addMemlistEntry(ptr, size, filename, line);
449 
450  return ptr;
451 }
452 
453 /** allocates memory; returns NULL if memory allocation failed */
455  void* ptr, /**< pointer to memory to reallocate */
456  size_t size, /**< new size of memory element */
457  const char* filename, /**< source file where the reallocation is performed */
458  int line /**< line number in source file where the reallocation is performed */
459  )
460 {
461  void* newptr;
462 
463  if( ptr != NULL )
464  removeMemlistEntry(ptr, filename, line);
465 
466 #ifndef NDEBUG
467  if ( size > MAXMEMSIZE )
468  {
469  printErrorHeader(filename, line);
470  printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE);
471  return NULL;
472  }
473 #endif
474 
475  size = MAX(size, 1);
476  newptr = realloc(ptr, size);
477 
478  if( newptr == NULL )
479  {
480  printErrorHeader(filename, line);
481  printError("Insufficient memory for reallocation of %llu bytes.\n", (unsigned long long)size);
482  }
483  else
484  addMemlistEntry(newptr, size, filename, line);
485 
486  return newptr;
487 }
488 
489 /** reallocates array; returns NULL if memory allocation failed */
491  void* ptr, /**< pointer to memory to reallocate */
492  size_t num, /**< number of components of array to allocate */
493  size_t typesize, /**< size of each component */
494  const char* filename, /**< source file where the reallocation is performed */
495  int line /**< line number in source file where the reallocation is performed */
496  )
497 {
498  void* newptr;
499  size_t size;
500 
501  if( ptr != NULL )
502  removeMemlistEntry(ptr, filename, line);
503 
504 #ifndef NDEBUG
505  if ( num > (MAXMEMSIZE / typesize) )
506  {
507  printErrorHeader(filename, line);
508  printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE);
509  return NULL;
510  }
511 #endif
512 
513  size = num * typesize;
514  size = MAX(size, 1);
515  newptr = realloc(ptr, size);
516 
517  if( newptr == NULL )
518  {
519  printErrorHeader(filename, line);
520  printError("Insufficient memory for reallocation of %llu bytes.\n", (unsigned long long)size);
521  }
522  else
523  addMemlistEntry(newptr, size, filename, line);
524 
525  return newptr;
526 }
527 
528 /** clears a memory element (i.e. fills it with zeros) */
530  void* ptr, /**< pointer to memory element */
531  size_t size /**< size of memory element */
532  )
533 {
534  if( size > 0 )
535  {
536  assert(ptr != NULL);
537  memset(ptr, 0, size);
538  }
539 }
540 
541 /** copies the contents of one memory element into another memory element */
543  void* ptr, /**< pointer to target memory element */
544  const void* source, /**< pointer to source memory element */
545  size_t size /**< size of memory element to copy */
546  )
547 {
548  if( size > 0 )
549  {
550  assert(ptr != NULL);
551  assert(source != NULL);
552  memcpy(ptr, source, size);
553  }
554 }
555 
556 /** moves the contents of one memory element into another memory element, should be used if both elements overlap,
557  * otherwise BMScopyMemory is faster
558  */
560  void* ptr, /**< pointer to target memory element */
561  const void* source, /**< pointer to source memory element */
562  size_t size /**< size of memory element to copy */
563  )
564 {
565  if( size > 0 )
566  {
567  assert(ptr != NULL);
568  assert(source != NULL);
569  memmove(ptr, source, size);
570  }
571 }
572 
573 /** allocates memory and copies the contents of the given memory element into the new memory element */
575  const void* source, /**< pointer to source memory element */
576  size_t size, /**< size of memory element to copy */
577  const char* filename, /**< source file where the duplication is performed */
578  int line /**< line number in source file where the duplication is performed */
579  )
580 {
581  void* ptr;
582 
583  assert(source != NULL || size == 0);
584 
585  ptr = BMSallocMemory_call(size, filename, line);
586  if( ptr != NULL )
587  BMScopyMemory_call(ptr, source, size);
588 
589  return ptr;
590 }
591 
592 /** allocates array and copies the contents of the given source array into the new array */
594  const void* source, /**< pointer to source memory element */
595  size_t num, /**< number of components of array to allocate */
596  size_t typesize, /**< size of each component */
597  const char* filename, /**< source file where the duplication is performed */
598  int line /**< line number in source file where the duplication is performed */
599  )
600 {
601  void* ptr;
602 
603  assert(source != NULL || num == 0);
604 
605  ptr = BMSallocMemoryArray_call(num, typesize, filename, line);
606  if( ptr != NULL )
607  BMScopyMemory_call(ptr, source, num * typesize);
608 
609  return ptr;
610 }
611 
612 /** frees an allocated memory element and sets pointer to NULL */
614  void** ptr, /**< pointer to pointer to memory element */
615  const char* filename, /**< source file where the deallocation is performed */
616  int line /**< line number in source file where the deallocation is performed */
617  )
618 {
619  assert( ptr != NULL );
620  if( *ptr != NULL )
621  {
622  removeMemlistEntry(*ptr, filename, line);
623 
624  free(*ptr);
625  *ptr = NULL;
626  }
627  else
628  {
629  printErrorHeader(filename, line);
630  printError("Tried to free null pointer.\n");
631  }
632 }
633 
634 /** frees an allocated memory element if pointer is not NULL and sets pointer to NULL */
636  void** ptr, /**< pointer to pointer to memory element */
637  const char* filename, /**< source file where the deallocation is performed */
638  int line /**< line number in source file where the deallocation is performed */
639  )
640 {
641  assert( ptr != NULL );
642  if ( *ptr != NULL )
643  {
644  removeMemlistEntry(*ptr, filename, line);
645 
646  free(*ptr);
647  *ptr = NULL;
648  }
649 }
650 
651 
652 /***********************************************************
653  * Block Memory Management (forward declaration)
654  *
655  * Efficient memory management for objects of varying sizes
656  ***********************************************************/
657 
658 #define CHKHASH_POWER 10 /**< power for size of chunk block hash table */
659 #define CHKHASH_SIZE (1<<CHKHASH_POWER) /**< size of chunk block hash table is 2^CHKHASH_POWER */
660 
661 /** collection of chunk blocks */
662 struct BMS_BlkMem
663 {
664  BMS_CHKMEM* chkmemhash[CHKHASH_SIZE]; /**< hash table with chunk blocks */
665  long long memused; /**< total number of used bytes in the memory header */
666  long long memallocated; /**< total number of allocated bytes in the memory header */
667  long long maxmemused; /**< maximal number of used bytes in the memory header */
668  long long maxmemunused; /**< maximal number of allocated but not used bytes in the memory header */
669  long long maxmemallocated; /**< maximal number of allocated bytes in the memory header */
670  int initchunksize; /**< number of elements in the first chunk of each chunk block */
671  int garbagefactor; /**< garbage collector is called, if at least garbagefactor * avg. chunksize
672  * elements are free (-1: disable garbage collection) */
673 };
674 
675 
676 /********************************************************************
677  * Chunk Memory Management
678  *
679  * Efficient memory management for multiple objects of the same size
680  ********************************************************************/
681 
682 /*
683  * block memory methods for faster memory access
684  */
685 
686 #define CHUNKLENGTH_MIN 1024 /**< minimal size of a chunk (in bytes) */
687 #define CHUNKLENGTH_MAX 1048576 /**< maximal size of a chunk (in bytes) */
688 #define STORESIZE_MAX 8192 /**< maximal number of elements in one chunk */
689 #define GARBAGE_SIZE 256 /**< size of lazy free list to start garbage collection */
690 #define ALIGNMENT (sizeof(FREELIST)) /**< minimal alignment of chunks */
691 
692 typedef struct Freelist FREELIST; /**< linked list of free memory elements */
693 typedef struct Chunk CHUNK; /**< chunk of memory elements */
694 
695 /** linked list of free memory elements */
696 struct Freelist
697 {
698  FREELIST* next; /**< pointer to the next free element */
699 };
700 
701 /** chunk of memory elements */
702 struct Chunk
703 {
704  SCIP_RBTREE_HOOKS; /**< organize chunks in a red black tree */ /*lint !e768 */
705  void* store; /**< data storage */
706  void* storeend; /**< points to the first byte in memory not belonging to the chunk */
707  FREELIST* eagerfree; /**< eager free list */
708  CHUNK* nexteager; /**< next chunk, that has a non-empty eager free list */
709  CHUNK* preveager; /**< previous chunk, that has a non-empty eager free list */
710  BMS_CHKMEM* chkmem; /**< chunk memory collection, this chunk belongs to */
711  int elemsize; /**< size of each element in the chunk */
712  int storesize; /**< number of elements in this chunk */
713  int eagerfreesize; /**< number of elements in the eager free list */
714 }; /* the chunk data structure must be aligned, because the storage is allocated directly behind the chunk header! */
715 
716 /** collection of memory chunks of the same element size */
717 struct BMS_ChkMem
718 {
719  CHUNK* rootchunk; /**< array with the chunks of the chunk header */
720  FREELIST* lazyfree; /**< lazy free list of unused memory elements of all chunks of this chunk block */
721  CHUNK* firsteager; /**< first chunk with a non-empty eager free list */
722  BMS_CHKMEM* nextchkmem; /**< next chunk block in the block memory's hash list */
723  int elemsize; /**< size of each memory element in the chunk memory */
724  int nchunks; /**< number of chunks in this chunk block (used slots of the chunk array) */
725  int lastchunksize; /**< number of elements in the last allocated chunk */
726  int storesize; /**< total number of elements in this chunk block */
727  int lazyfreesize; /**< number of elements in the lazy free list of the chunk block */
728  int eagerfreesize; /**< total number of elements of all eager free lists of the block's chunks */
729  int initchunksize; /**< number of elements in the first chunk */
730  int garbagefactor; /**< garbage collector is called, if at least garbagefactor * avg. chunksize
731  * elements are free (-1: disable garbage collection) */
732 #ifndef NDEBUG
733  char* filename; /**< source file, where this chunk block was created */
734  int line; /**< source line, where this chunk block was created */
735  int ngarbagecalls; /**< number of times, the garbage collector was called */
736  int ngarbagefrees; /**< number of chunks, the garbage collector freed */
737 #endif
738 };
739 
740 /* define a find function to find a chunk in a red black tree of chunks */
741 #define CHUNK_LT(ptr,chunk) ptr < chunk->store
742 #define CHUNK_GT(ptr,chunk) ptr >= chunk->storeend
743 
744 static
745 SCIP_DEF_RBTREE_FIND(rbTreeFindChunk, const void*, CHUNK, CHUNK_LT, CHUNK_GT) /*lint !e123*/
746 
747 
748 /** aligns the given byte size corresponding to the minimal alignment */
749 static
750 void alignSize(
751  size_t* size /**< pointer to the size to align */
752  )
753 {
754  if( *size < ALIGNMENT )
755  *size = ALIGNMENT;
756  else
757  *size = ((*size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT;
758 }
759 
760 /** aligns the given byte size corresponding to the minimal alignment for chunk and block memory */
762  size_t* size /**< pointer to the size to align */
763  )
764 {
765  assert(ALIGNMENT == sizeof(void*)); /*lint !e506*/
766  alignSize(size);
767 }
768 
769 /** checks whether the given size meets the alignment conditions for chunk and block memory */
771  size_t size /**< size to check for alignment */
772  )
773 {
774  assert(ALIGNMENT == sizeof(void*)); /*lint !e506*/
775  return( size >= ALIGNMENT && size % ALIGNMENT == 0 );
776 }
777 
778 #ifndef NDEBUG
779 /** checks, if the given pointer belongs to the given chunk */
780 static
782  const CHUNK* chunk, /**< memory chunk */
783  const void* ptr /**< pointer */
784  )
785 {
786  assert(chunk != NULL);
787  assert(chunk->store <= chunk->storeend);
788 
789  return (ptr >= (void*)(chunk->store) && ptr < (void*)(chunk->storeend));
790 }
791 #endif
792 
793 /** given a pointer, finds the chunk this pointer points to in the chunk array of the given chunk block;
794  * binary search is used;
795  * returns NULL if the pointer does not belong to the chunk block
796  */
797 static
799  const BMS_CHKMEM* chkmem, /**< chunk block */
800  const void* ptr /**< pointer */
801  )
802 {
803  CHUNK* chunk;
804 
805  assert(chkmem != NULL);
806  assert(ptr != NULL);
807 
808  if( rbTreeFindChunk(chkmem->rootchunk, ptr, &chunk) == 0 )
809  return chunk;
810 
811  /* ptr was not found in chunk */
812  return NULL;
813 }
814 
815 /** checks, if a pointer belongs to a chunk of the given chunk block */
816 static
818  const BMS_CHKMEM* chkmem, /**< chunk block */
819  const void* ptr /**< pointer */
820  )
821 {
822  assert(chkmem != NULL);
823 
824  return (findChunk(chkmem, ptr) != NULL);
825 }
826 
827 
828 
829 /*
830  * debugging methods
831  */
832 
833 #ifdef CHECKMEM
834 /** sanity check for a memory chunk */
835 static
836 void checkChunk(
837  const CHUNK* chunk /**< memory chunk */
838  )
839 {
840  FREELIST* eager;
841  int eagerfreesize;
842 
843  assert(chunk != NULL);
844  assert(chunk->store != NULL);
845  assert(chunk->storeend == (void*)((char*)(chunk->store) + chunk->elemsize * chunk->storesize));
846  assert(chunk->chkmem != NULL);
847  assert(chunk->chkmem->elemsize == chunk->elemsize);
848 
849  if( chunk->eagerfree == NULL )
850  assert(chunk->nexteager == NULL && chunk->preveager == NULL);
851  else if( chunk->preveager == NULL )
852  assert(chunk->chkmem->firsteager == chunk);
853 
854  if( chunk->nexteager != NULL )
855  assert(chunk->nexteager->preveager == chunk);
856  if( chunk->preveager != NULL )
857  assert(chunk->preveager->nexteager == chunk);
858 
859  eagerfreesize = 0;
860  eager = chunk->eagerfree;
861  while( eager != NULL )
862  {
863  assert(isPtrInChunk(chunk, eager));
864  eagerfreesize++;
865  eager = eager->next;
866  }
867  assert(chunk->eagerfreesize == eagerfreesize);
868 }
869 
870 /** sanity check for a chunk block */
871 static
872 void checkChkmem(
873  const BMS_CHKMEM* chkmem /**< chunk block */
874  )
875 {
876  FREELIST* lazy;
877  int nchunks;
878  int storesize;
879  int lazyfreesize;
880  int eagerfreesize;
881 
882  assert(chkmem != NULL);
883 
884  nchunks = 0;
885  storesize = 0;
886  lazyfreesize = 0;
887  eagerfreesize = 0;
888 
889  FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk,
890  {
891  checkChunk(chunk);
892  nchunks++;
893  storesize += chunk->storesize;
894  eagerfreesize += chunk->eagerfreesize;
895  })
896 
897  assert(chkmem->nchunks == nchunks);
898  assert(chkmem->storesize == storesize);
899  assert(chkmem->eagerfreesize == eagerfreesize);
900 
901  assert(((unsigned int) (chkmem->eagerfreesize == 0)) ^ ( (unsigned int) (chkmem->firsteager != NULL)));
902 
903  if( chkmem->firsteager != NULL )
904  assert(chkmem->firsteager->preveager == NULL);
905 
906  lazy = chkmem->lazyfree;
907  while( lazy != NULL )
908  {
909  CHUNK* chunk = findChunk(chkmem, lazy);
910  assert(chunk != NULL);
911  assert(chunk->chkmem == chkmem);
912  lazyfreesize++;
913  lazy = lazy->next;
914  }
915  assert(chkmem->lazyfreesize == lazyfreesize);
916 }
917 #else
918 #define checkChunk(chunk) /**/
919 #define checkChkmem(chkmem) /**/
920 #endif
921 
922 
923 /** links chunk to the block's chunk array, sort it by store pointer;
924  * returns TRUE if successful, FALSE otherwise
925  */
926 static
928  BMS_CHKMEM* chkmem, /**< chunk block */
929  CHUNK* chunk /**< memory chunk */
930  )
931 {
932  CHUNK* parent;
933  int pos;
934 
935  assert(chkmem != NULL);
936  assert(chunk != NULL);
937  assert(chunk->store != NULL);
938 
939  debugMessage("linking chunk %p to chunk block %p [elemsize:%d, %d chunks]\n",
940  (void*)chunk, (void*)chkmem, chkmem->elemsize, chkmem->nchunks);
941 
942  pos = rbTreeFindChunk(chkmem->rootchunk, chunk->store, &parent);
943  assert(pos != 0);
944 
945  SCIPrbtreeInsert(&chkmem->rootchunk, parent, pos, chunk);
946 
947  chkmem->nchunks++;
948  chkmem->storesize += chunk->storesize;
949 
950  return TRUE;
951 }
952 
953 /** unlinks chunk from the chunk block's chunk list */
954 static
956  CHUNK* chunk /**< memory chunk */
957  )
958 {
959  BMS_CHKMEM* chkmem;
960 
961  assert(chunk != NULL);
962  assert(chunk->eagerfree == NULL);
963  assert(chunk->nexteager == NULL);
964  assert(chunk->preveager == NULL);
965 
966  chkmem = chunk->chkmem;
967  assert(chkmem != NULL);
968  assert(chkmem->elemsize == chunk->elemsize);
969 
970  debugMessage("unlinking chunk %p from chunk block %p [elemsize:%d, %d chunks]\n",
971  (void*)chunk, (void*)chkmem, chkmem->elemsize, chkmem->nchunks);
972 
973  /* remove the chunk from the chunks of the chunk block */
974  SCIPrbtreeDelete(&chkmem->rootchunk, chunk);
975 
976  chkmem->nchunks--;
977  chkmem->storesize -= chunk->storesize;
978 }
979 
980 /** links chunk to the chunk block's eager chunk list */
981 static
983  BMS_CHKMEM* chkmem, /**< chunk block */
984  CHUNK* chunk /**< memory chunk */
985  )
986 {
987  assert(chunk->chkmem == chkmem);
988  assert(chunk->nexteager == NULL);
989  assert(chunk->preveager == NULL);
990 
991  chunk->nexteager = chkmem->firsteager;
992  chunk->preveager = NULL;
993  if( chkmem->firsteager != NULL )
994  {
995  assert(chkmem->firsteager->preveager == NULL);
996  chkmem->firsteager->preveager = chunk;
997  }
998  chkmem->firsteager = chunk;
999 }
1000 
1001 /** unlinks chunk from the chunk block's eager chunk list */
1002 static
1004  CHUNK* chunk /**< memory chunk */
1005  )
1006 {
1007  assert(chunk != NULL);
1008  assert(chunk->eagerfreesize == 0 || chunk->eagerfreesize == chunk->storesize);
1009 
1010  if( chunk->nexteager != NULL )
1011  chunk->nexteager->preveager = chunk->preveager;
1012  if( chunk->preveager != NULL )
1013  chunk->preveager->nexteager = chunk->nexteager;
1014  else
1015  {
1016  assert(chunk->chkmem->firsteager == chunk);
1017  chunk->chkmem->firsteager = chunk->nexteager;
1018  }
1019  chunk->nexteager = NULL;
1020  chunk->preveager = NULL;
1021  chunk->eagerfree = NULL;
1022 }
1023 
1024 /** creates a new memory chunk in the given chunk block and adds memory elements to the lazy free list;
1025  * returns TRUE if successful, FALSE otherwise
1026  */
1027 static
1029  BMS_CHKMEM* chkmem, /**< chunk block */
1030  long long* memsize /**< pointer to total size of allocated memory (or NULL) */
1031  )
1032 {
1033  CHUNK *newchunk;
1034  FREELIST *freelist;
1035  int i;
1036  int storesize;
1037  int retval;
1038 
1039  assert(chkmem != NULL);
1040 
1041  debugMessage("creating new chunk in chunk block %p [elemsize: %d]\n", (void*)chkmem, chkmem->elemsize);
1042 
1043  /* calculate store size */
1044  if( chkmem->nchunks == 0 )
1045  storesize = chkmem->initchunksize;
1046  else
1047  storesize = 2 * chkmem->lastchunksize;
1048  assert(storesize > 0);
1049  storesize = MAX(storesize, CHUNKLENGTH_MIN / chkmem->elemsize);
1050  storesize = MIN(storesize, CHUNKLENGTH_MAX / chkmem->elemsize);
1051  storesize = MIN(storesize, STORESIZE_MAX);
1052  storesize = MAX(storesize, 1);
1053  chkmem->lastchunksize = storesize;
1054 
1055  /* create new chunk */
1056  assert(BMSisAligned(sizeof(CHUNK)));
1057  assert( chkmem->elemsize < INT_MAX / storesize );
1058  assert( sizeof(CHUNK) < MAXMEMSIZE - (size_t)(storesize * chkmem->elemsize) ); /*lint !e571 !e647*/
1059  BMSallocMemorySize(&newchunk, sizeof(CHUNK) + storesize * chkmem->elemsize);
1060  if( newchunk == NULL )
1061  return FALSE;
1062 
1063  /* the store is allocated directly behind the chunk header */
1064  newchunk->store = (void*) ((char*) newchunk + sizeof(CHUNK));
1065  newchunk->storeend = (void*) ((char*) newchunk->store + (ptrdiff_t)storesize * chkmem->elemsize);
1066  newchunk->eagerfree = NULL;
1067  newchunk->nexteager = NULL;
1068  newchunk->preveager = NULL;
1069  newchunk->chkmem = chkmem;
1070  newchunk->elemsize = chkmem->elemsize;
1071  newchunk->storesize = storesize;
1072  newchunk->eagerfreesize = 0;
1073 
1074  if( memsize != NULL )
1075  (*memsize) += ((long long)((long long)sizeof(CHUNK) + (long long)storesize * chkmem->elemsize));
1076 
1077  debugMessage("allocated new chunk %p: %d elements with size %d\n", (void*)newchunk, newchunk->storesize, newchunk->elemsize);
1078 
1079  /* add new memory to the lazy free list
1080  * (due to the BMSisAligned assert above, we know that elemsize is divisible by the size of pointers)
1081  */
1082  for( i = 0; i < newchunk->storesize - 1; ++i )
1083  {
1084  freelist = (FREELIST*) newchunk->store + (ptrdiff_t)i * chkmem->elemsize / (ptrdiff_t)sizeof(FREELIST*); /*lint !e573 !e647*/
1085  freelist->next = (FREELIST*) newchunk->store + ((ptrdiff_t)i + 1) * chkmem->elemsize / (ptrdiff_t)sizeof(FREELIST*); /*lint !e573 !e647*/
1086  }
1087 
1088  freelist = (FREELIST*) newchunk->store + ((ptrdiff_t) newchunk->storesize - 1) * chkmem->elemsize / (ptrdiff_t)sizeof(FREELIST*); /*lint !e573 !e647*/
1089  freelist->next = chkmem->lazyfree;
1090  chkmem->lazyfree = (FREELIST*) (newchunk->store);
1091  chkmem->lazyfreesize += newchunk->storesize;
1092 
1093  /* link chunk into chunk block */
1094  retval = linkChunk(chkmem, newchunk);
1095 
1096  checkChkmem(chkmem);
1097 
1098  return retval;
1099 }
1100 
1101 /** destroys a chunk without updating the chunk lists */
1102 static
1104  CHUNK** chunk, /**< memory chunk */
1105  long long* memsize /**< pointer to total size of allocated memory (or NULL) */
1106  )
1107 {
1108  assert(chunk != NULL);
1109  assert(*chunk != NULL);
1110 
1111  debugMessage("destroying chunk %p\n", (void*)*chunk);
1112 
1113  if( memsize != NULL )
1114  (*memsize) -= ((long long)sizeof(CHUNK) + (long long)(*chunk)->storesize * (*chunk)->elemsize);
1115 
1116  /* free chunk header and store (allocated in one call) */
1117  BMSfreeMemory(chunk);
1118 }
1119 
1120 /** removes a completely unused chunk, i.e. a chunk with all elements in the eager free list */
1121 static
1123  CHUNK** chunk, /**< memory chunk */
1124  long long* memsize /**< pointer to total size of allocated memory (or NULL) */
1125  )
1126 {
1127  assert(chunk != NULL);
1128  assert(*chunk != NULL);
1129  assert((*chunk)->store != NULL);
1130  assert((*chunk)->eagerfree != NULL);
1131  assert((*chunk)->chkmem != NULL);
1132  assert((*chunk)->chkmem->rootchunk != NULL);
1133  assert((*chunk)->chkmem->firsteager != NULL);
1134  assert((*chunk)->eagerfreesize == (*chunk)->storesize);
1135 
1136  debugMessage("freeing chunk %p of chunk block %p [elemsize: %d]\n", (void*)*chunk, (void*)(*chunk)->chkmem, (*chunk)->chkmem->elemsize);
1137 
1138  /* count the deleted eager free slots */
1139  (*chunk)->chkmem->eagerfreesize -= (*chunk)->eagerfreesize;
1140  assert((*chunk)->chkmem->eagerfreesize >= 0);
1141 
1142  /* remove chunk from eager chunk list */
1143  unlinkEagerChunk(*chunk);
1144 
1145  /* remove chunk from chunk list */
1146  unlinkChunk(*chunk);
1147 
1148  /* destroy the chunk */
1149  destroyChunk(chunk, memsize);
1150 }
1151 
1152 /** returns an element of the eager free list and removes it from the list */
1153 static
1155  CHUNK* chunk /**< memory chunk */
1156  )
1157 {
1158  FREELIST* ptr;
1159 
1160  assert(chunk != NULL);
1161  assert(chunk->eagerfree != NULL);
1162  assert(chunk->eagerfreesize > 0);
1163  assert(chunk->chkmem != NULL);
1164 
1165  debugMessage("allocating chunk element in chunk %p [elemsize: %d]\n", (void*)chunk, chunk->chkmem->elemsize);
1166 
1167  /* unlink first element in the eager free list */
1168  ptr = chunk->eagerfree;
1169  chunk->eagerfree = ptr->next;
1170  chunk->eagerfreesize--;
1171  chunk->chkmem->eagerfreesize--;
1172 
1173  assert((chunk->eagerfreesize == 0 && chunk->eagerfree == NULL)
1174  || (chunk->eagerfreesize != 0 && chunk->eagerfree != NULL));
1175  assert(chunk->chkmem->eagerfreesize >= 0);
1176 
1177  /* unlink chunk from eager chunk list if necessary */
1178  if( chunk->eagerfree == NULL )
1179  {
1180  assert(chunk->eagerfreesize == 0);
1181  unlinkEagerChunk(chunk);
1182  }
1183 
1184  checkChunk(chunk);
1185 
1186  return (void*) ptr;
1187 }
1188 
1189 /** puts given pointer into the eager free list and adds the chunk to the eager list of its chunk block, if necessary */
1190 static
1192  CHUNK* chunk, /**< memory chunk */
1193  void* ptr /**< pointer */
1194  )
1195 {
1196  assert(chunk != NULL);
1197  assert(chunk->chkmem != NULL);
1198  assert(isPtrInChunk(chunk, ptr));
1199 
1200  debugMessage("freeing chunk element %p of chunk %p [elemsize: %d]\n", (void*)ptr, (void*)chunk, chunk->chkmem->elemsize);
1201 
1202  /* link chunk to the eager chunk list if necessary */
1203  if( chunk->eagerfree == NULL )
1204  {
1205  assert(chunk->eagerfreesize == 0);
1206  linkEagerChunk(chunk->chkmem, chunk);
1207  }
1208 
1209  /* add ptr to the chunks eager free list */
1210  ((FREELIST*)ptr)->next = chunk->eagerfree;
1211  chunk->eagerfree = (FREELIST*)ptr;
1212  chunk->eagerfreesize++;
1213  chunk->chkmem->eagerfreesize++;
1214 
1215  checkChunk(chunk);
1216 }
1217 
1218 /** creates a new chunk block data structure */
1219 static
1221  int size, /**< element size of the chunk block */
1222  int initchunksize, /**< number of elements in the first chunk of the chunk block */
1223  int garbagefactor, /**< garbage collector is called, if at least garbagefactor * avg. chunksize
1224  * elements are free (-1: disable garbage collection) */
1225  long long* memsize /**< pointer to total size of allocated memory (or NULL) */
1226  )
1227 {
1228  BMS_CHKMEM* chkmem;
1229 
1230  assert(size >= 0);
1231  assert(BMSisAligned((size_t)size)); /*lint !e571*/
1232 
1233  BMSallocMemory(&chkmem);
1234  if( chkmem == NULL )
1235  return NULL;
1236 
1237  chkmem->lazyfree = NULL;
1238  chkmem->rootchunk = NULL;
1239  chkmem->firsteager = NULL;
1240  chkmem->nextchkmem = NULL;
1241  chkmem->elemsize = size;
1242  chkmem->nchunks = 0;
1243  chkmem->lastchunksize = 0;
1244  chkmem->storesize = 0;
1245  chkmem->lazyfreesize = 0;
1246  chkmem->eagerfreesize = 0;
1247  chkmem->initchunksize = initchunksize;
1248  chkmem->garbagefactor = garbagefactor;
1249 #ifndef NDEBUG
1250  chkmem->filename = NULL;
1251  chkmem->line = 0;
1252  chkmem->ngarbagecalls = 0;
1253  chkmem->ngarbagefrees = 0;
1254 #endif
1255 
1256  if( memsize != NULL )
1257  (*memsize) += (long long)sizeof(BMS_CHKMEM);
1258 
1259  return chkmem;
1260 }
1261 
1262 /** destroys all chunks of the chunk block, but keeps the chunk block header structure */
1263 static
1265  BMS_CHKMEM* chkmem, /**< chunk block */
1266  long long* memsize /**< pointer to total size of allocated memory (or NULL) */
1267  )
1268 {
1269  assert(chkmem != NULL);
1270 
1271  /* destroy all chunks of the chunk block */
1272  FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk,
1273  {
1274  SCIPrbtreeDelete(&chkmem->rootchunk, chunk);
1275  destroyChunk(&chunk, memsize);
1276  })
1277 
1278  chkmem->lazyfree = NULL;
1279  chkmem->firsteager = NULL;
1280  chkmem->nchunks = 0;
1281  chkmem->lastchunksize = 0;
1282  chkmem->storesize = 0;
1283  chkmem->lazyfreesize = 0;
1284  chkmem->eagerfreesize = 0;
1285 }
1286 
1287 /** deletes chunk block and frees all associated memory chunks */
1288 static
1290  BMS_CHKMEM** chkmem, /**< pointer to chunk block */
1291  long long* memsize /**< pointer to total size of allocated memory (or NULL) */
1292  )
1293 {
1294  assert(chkmem != NULL);
1295  assert(*chkmem != NULL);
1296 
1297  clearChkmem(*chkmem, memsize);
1298 
1299 #ifndef NDEBUG
1300  BMSfreeMemoryArrayNull(&(*chkmem)->filename);
1301 #endif
1302 
1303  if( memsize != NULL )
1304  (*memsize) -= (long long)(sizeof(BMS_CHKMEM));
1305 
1306  BMSfreeMemory(chkmem);
1307 }
1308 
1309 /** allocates a new memory element from the chunk block */
1310 static
1312  BMS_CHKMEM* chkmem, /**< chunk block */
1313  long long* memsize /**< pointer to total size of allocated memory (or NULL) */
1314  )
1315 {
1316  FREELIST* ptr;
1317 
1318  assert(chkmem != NULL);
1319 
1320  /* if the lazy freelist is empty, we have to find the memory element somewhere else */
1321  if( chkmem->lazyfree == NULL )
1322  {
1323  assert(chkmem->lazyfreesize == 0);
1324 
1325  /* check for a free element in the eager freelists */
1326  if( chkmem->firsteager != NULL )
1327  return allocChunkElement(chkmem->firsteager);
1328 
1329  /* allocate a new chunk */
1330  if( !createChunk(chkmem, memsize) )
1331  return NULL;
1332  }
1333 
1334  /* now the lazy freelist should contain an element */
1335  assert(chkmem->lazyfree != NULL);
1336  assert(chkmem->lazyfreesize > 0);
1337 
1338  ptr = chkmem->lazyfree;
1339  chkmem->lazyfree = ptr->next;
1340  chkmem->lazyfreesize--;
1341 
1342  checkChkmem(chkmem);
1343 
1344  return (void*) ptr;
1345 }
1346 
1347 /** sorts the lazy free list of the chunk block into the eager free lists of the chunks, and removes completely
1348  * unused chunks
1349  */
1350 static
1352  BMS_CHKMEM* chkmem, /**< chunk block */
1353  long long* memsize /**< pointer to total size of allocated memory (or NULL) */
1354  )
1355 {
1356  CHUNK* chunk;
1357  CHUNK* nexteager;
1358  FREELIST* lazyfree;
1359 
1360  assert(chkmem != NULL);
1361 
1362  debugMessage("garbage collection for chunk block %p [elemsize: %d]\n", (void*)chkmem, chkmem->elemsize);
1363 
1364  /* check, if the chunk block is completely unused */
1365  if( chkmem->lazyfreesize + chkmem->eagerfreesize == chkmem->storesize )
1366  {
1367  clearChkmem(chkmem, memsize);
1368  return;
1369  }
1370 
1371 #ifndef NDEBUG
1372  chkmem->ngarbagecalls++;
1373 #endif
1374 
1375  /* put the lazy free elements into the eager free lists */
1376  while( chkmem->lazyfree != NULL )
1377  {
1378  /* unlink first element from the lazy free list */
1379  lazyfree = chkmem->lazyfree;
1380  chkmem->lazyfree = chkmem->lazyfree->next;
1381  chkmem->lazyfreesize--;
1382 
1383  /* identify the chunk of the element */
1384  chunk = findChunk(chkmem, (void*)lazyfree);
1385 #ifndef NDEBUG
1386  if( chunk == NULL )
1387  {
1388  errorMessage("chunk for lazy free chunk %p not found in chunk block %p\n", (void*)lazyfree, (void*)chkmem);
1389  }
1390 #endif
1391  assert(chunk != NULL);
1392 
1393  /* add the element to the chunk's eager free list */
1394  freeChunkElement(chunk, (void*)lazyfree);
1395  assert(chunk->eagerfreesize > 0);
1396  }
1397  assert(chkmem->lazyfreesize == 0);
1398 
1399  /* delete completely unused chunks, but keep at least one */
1400  chunk = chkmem->firsteager;
1401  while( chunk != NULL && chkmem->nchunks > 1 )
1402  {
1403  nexteager = chunk->nexteager;
1404  if( chunk->eagerfreesize == chunk->storesize )
1405  {
1406 #ifndef NDEBUG
1407  chkmem->ngarbagefrees++;
1408 #endif
1409  freeChunk(&chunk, memsize);
1410  }
1411  chunk = nexteager;
1412  }
1413 
1414  checkChkmem(chkmem);
1415 }
1416 
1417 /** frees a memory element and returns it to the lazy freelist of the chunk block */ /*lint -e715*/
1418 static
1420  BMS_CHKMEM* chkmem, /**< chunk block */
1421  void* ptr, /**< memory element */
1422  long long* memsize, /**< pointer to total size of allocated memory (or NULL) */
1423  const char* filename, /**< source file of the function call */
1424  int line /**< line number in source file of the function call */
1425  )
1426 { /*lint --e{715}*/
1427  assert(chkmem != NULL);
1428  assert(ptr != NULL);
1429 
1430 #if ( defined(CHECKMEM) || defined(CHECKCHKFREE) )
1431  /* check, if ptr belongs to the chunk block */
1432  if( !isPtrInChkmem(chkmem, ptr) )
1433  {
1434  printErrorHeader(filename, line);
1435  printError("Pointer %p does not belong to chunk block %p (size: %d).\n", ptr, chkmem, chkmem->elemsize);
1436  }
1437 #endif
1438 
1439  /* put ptr in lazy free list */
1440  ((FREELIST*)ptr)->next = chkmem->lazyfree;
1441  chkmem->lazyfree = (FREELIST*)ptr;
1442  chkmem->lazyfreesize++;
1443 
1444  /* check if we want to apply garbage collection */
1445  if( chkmem->garbagefactor >= 0 && chkmem->nchunks > 0 && chkmem->lazyfreesize >= GARBAGE_SIZE
1446  && chkmem->lazyfreesize + chkmem->eagerfreesize
1447  > chkmem->garbagefactor * (double)(chkmem->storesize) / (double)(chkmem->nchunks) )
1448  {
1449  garbagecollectChkmem(chkmem, memsize);
1450  }
1451 
1452  checkChkmem(chkmem);
1453 }
1454 
1455 /** creates a new chunk block data structure */
1457  size_t size, /**< element size of the chunk block */
1458  int initchunksize, /**< number of elements in the first chunk of the chunk block */
1459  int garbagefactor, /**< garbage collector is called, if at least garbagefactor * avg. chunksize
1460  * elements are free (-1: disable garbage collection) */
1461  const char* filename, /**< source file of the function call */
1462  int line /**< line number in source file of the function call */
1463  )
1464 {
1465  BMS_CHKMEM* chkmem;
1466 
1467  alignSize(&size);
1468  chkmem = createChkmem((int) size, initchunksize, garbagefactor, NULL);
1469  if( chkmem == NULL )
1470  {
1471  printErrorHeader(filename, line);
1472  printError("Insufficient memory for chunk block.\n");
1473  }
1474  debugMessage("created chunk memory %p [elemsize: %d]\n", (void*)chkmem, (int)size);
1475 
1476  return chkmem;
1477 }
1478 
1479 /** clears a chunk block data structure */
1481  BMS_CHKMEM* chkmem, /**< chunk block */
1482  const char* filename, /**< source file of the function call */
1483  int line /**< line number in source file of the function call */
1484  )
1485 {
1486  debugMessage("clearing chunk memory %p [elemsize: %d]\n", (void*)chkmem, chkmem->elemsize);
1487 
1488  if( chkmem != NULL )
1489  clearChkmem(chkmem, NULL);
1490  else
1491  {
1492  printErrorHeader(filename, line);
1493  printError("Tried to clear null chunk block.\n");
1494  }
1495 }
1496 
1497 /** destroys and frees a chunk block data structure */
1499  BMS_CHKMEM** chkmem, /**< pointer to chunk block */
1500  const char* filename, /**< source file of the function call */
1501  int line /**< line number in source file of the function call */
1502  )
1503 {
1504  assert(chkmem != NULL);
1505 
1506  debugMessage("destroying chunk memory %p [elemsize: %d]\n", (void*)*chkmem, (*chkmem)->elemsize);
1507 
1508  if( *chkmem != NULL )
1509  destroyChkmem(chkmem, NULL);
1510  else
1511  {
1512  printErrorHeader(filename, line);
1513  printError("Tried to destroy null chunk block.\n");
1514  }
1515 }
1516 
1517 /** allocates a memory element of the given chunk block */
1519  BMS_CHKMEM* chkmem, /**< chunk block */
1520  size_t size, /**< size of memory element to allocate (only needed for sanity check) */
1521  const char* filename, /**< source file of the function call */
1522  int line /**< line number in source file of the function call */
1523  )
1524 {
1525  void* ptr;
1526 
1527  assert(chkmem != NULL);
1528  assert((int)size == chkmem->elemsize);
1529 
1530  /* get memory inside the chunk block */
1531  ptr = allocChkmemElement(chkmem, NULL);
1532  if( ptr == NULL )
1533  {
1534  printErrorHeader(filename, line);
1535  printError("Insufficient memory for new chunk.\n");
1536  }
1537  debugMessage("alloced %8llu bytes in %p [%s:%d]\n", (unsigned long long)size, (void*)ptr, filename, line);
1538 
1539  checkChkmem(chkmem);
1540 
1541  return ptr;
1542 }
1543 
1544 /** duplicates a given memory element by allocating a new element of the same chunk block and copying the data */
1546  BMS_CHKMEM* chkmem, /**< chunk block */
1547  const void* source, /**< source memory element */
1548  size_t size, /**< size of memory element to allocate (only needed for sanity check) */
1549  const char* filename, /**< source file of the function call */
1550  int line /**< line number in source file of the function call */
1551  )
1552 {
1553  void* ptr;
1554 
1555  assert(chkmem != NULL);
1556  assert(source != NULL);
1557  assert((int)size == chkmem->elemsize);
1558 
1559  ptr = BMSallocChunkMemory_call(chkmem, size, filename, line);
1560  if( ptr != NULL )
1561  BMScopyMemorySize(ptr, source, chkmem->elemsize);
1562 
1563  return ptr;
1564 }
1565 
1566 /** frees a memory element of the given chunk block and sets pointer to NULL */
1568  BMS_CHKMEM* chkmem, /**< chunk block */
1569  void** ptr, /**< pointer to pointer to memory element to free */
1570  size_t size, /**< size of memory element to allocate (only needed for sanity check) */
1571  const char* filename, /**< source file of the function call */
1572  int line /**< line number in source file of the function call */
1573  )
1574 {
1575  assert(chkmem != NULL);
1576  assert((int)size == chkmem->elemsize);
1577  assert( ptr != NULL );
1578 
1579  if ( *ptr != NULL )
1580  {
1581  debugMessage("free %8d bytes in %p [%s:%d]\n", chkmem->elemsize, *ptr, filename, line);
1582 
1583  /* free memory in chunk block */
1584  freeChkmemElement(chkmem, *ptr, NULL, filename, line);
1585  checkChkmem(chkmem);
1586  *ptr = NULL;
1587  }
1588  else
1589  {
1590  printErrorHeader(filename, line);
1591  printError("Tried to free null chunk pointer.\n");
1592  }
1593 }
1594 
1595 /** frees a memory element of the given chunk block if pointer is not NULL and sets pointer to NULL */
1597  BMS_CHKMEM* chkmem, /**< chunk block */
1598  void** ptr, /**< pointer to pointer to memory element to free */
1599  size_t size, /**< size of memory element to allocate (only needed for sanity check) */
1600  const char* filename, /**< source file of the function call */
1601  int line /**< line number in source file of the function call */
1602  )
1603 {
1604  assert(chkmem != NULL);
1605  assert((int)size == chkmem->elemsize);
1606  assert( ptr != NULL );
1607 
1608  if ( *ptr != NULL )
1609  {
1610  debugMessage("free %8d bytes in %p [%s:%d]\n", chkmem->elemsize, *ptr, filename, line);
1611 
1612  /* free memory in chunk block */
1613  freeChkmemElement(chkmem, *ptr, NULL, filename, line);
1614  checkChkmem(chkmem);
1615  *ptr = NULL;
1616  }
1617 }
1618 
1619 /** calls garbage collection of chunk block and frees chunks without allocated memory elements */
1621  BMS_CHKMEM* chkmem /**< chunk block */
1622  )
1623 {
1624  debugMessage("garbage collection on chunk memory %p [elemsize: %d]\n", (void*)chkmem, chkmem->elemsize);
1625 
1626  garbagecollectChkmem(chkmem, NULL);
1627 }
1628 
1629 /** returns the number of allocated bytes in the chunk block */
1631  const BMS_CHKMEM* chkmem /**< chunk block */
1632  )
1633 {
1634  assert(chkmem != NULL);
1635 
1636  return ((long long)(chkmem->elemsize) * (long long)(chkmem->storesize));
1637 }
1638 
1639 
1640 
1641 
1642 /***********************************************************
1643  * Block Memory Management
1644  *
1645  * Efficient memory management for objects of varying sizes
1646  ***********************************************************/
1647 
1648 /* for a definition of the struct, see above */
1649 
1650 
1651 /*
1652  * debugging methods
1653  */
1654 
1655 #ifdef CHECKMEM
1656 static
1657 void checkBlkmem(
1658  const BMS_BLKMEM* blkmem /**< block memory */
1659  )
1660 {
1661  const BMS_CHKMEM* chkmem;
1662  long long tmpmemalloc = 0LL;
1663  long long tmpmemused = 0LL;
1664  int i;
1665 
1666  assert(blkmem != NULL);
1667  assert(blkmem->chkmemhash != NULL);
1668 
1669  for( i = 0; i < CHKHASH_SIZE; ++i )
1670  {
1671  chkmem = blkmem->chkmemhash[i];
1672  while( chkmem != NULL )
1673  {
1674  checkChkmem(chkmem);
1675  tmpmemalloc += ((chkmem->elemsize * chkmem->storesize) + chkmem->nchunks * sizeof(CHUNK) + sizeof(BMS_CHKMEM));
1676  tmpmemused += (chkmem->elemsize * (chkmem->storesize - chkmem->eagerfreesize - chkmem->lazyfreesize));
1677  chkmem = chkmem->nextchkmem;
1678  }
1679  }
1680  assert(tmpmemalloc == blkmem->memallocated);
1681  assert(tmpmemused == blkmem->memused);
1682 }
1683 #else
1684 #define checkBlkmem(blkmem) /**/
1685 #endif
1686 
1687 
1688 /** finds the chunk block, to whick the given pointer belongs to
1689  *
1690  * This could be done by selecting the chunk block of the corresponding element size, but in a case of an
1691  * error (free gives an incorrect element size), we want to identify and output the correct element size.
1692  */
1693 static
1695  const BMS_BLKMEM* blkmem, /**< block memory */
1696  const void* ptr /**< memory element to search */
1697  )
1698 {
1699  BMS_CHKMEM* chkmem;
1700  int i;
1701 
1702  assert(blkmem != NULL);
1703 
1704  chkmem = NULL;
1705  for( i = 0; chkmem == NULL && i < CHKHASH_SIZE; ++i )
1706  {
1707  chkmem = blkmem->chkmemhash[i];
1708  while( chkmem != NULL && !isPtrInChkmem(chkmem, ptr) )
1709  chkmem = chkmem->nextchkmem;
1710  }
1711 
1712  return chkmem;
1713 }
1714 
1715 /** calculates hash number of memory size */
1716 static
1718  int size /**< element size */
1719  )
1720 {
1721  assert(size >= 0);
1722  assert(BMSisAligned((size_t)size)); /*lint !e571*/
1723 
1724  return (int) (((uint32_t)size * UINT32_C(0x9e3779b9))>>(32-CHKHASH_POWER));
1725 }
1726 
1727 /** creates a block memory allocation data structure */
1729  int initchunksize, /**< number of elements in the first chunk of each chunk block */
1730  int garbagefactor, /**< garbage collector is called, if at least garbagefactor * avg. chunksize
1731  * elements are free (-1: disable garbage collection) */
1732  const char* filename, /**< source file of the function call */
1733  int line /**< line number in source file of the function call */
1734  )
1735 {
1736  BMS_BLKMEM* blkmem;
1737  int i;
1738 
1739  BMSallocMemory(&blkmem);
1740  if( blkmem != NULL )
1741  {
1742  for( i = 0; i < CHKHASH_SIZE; ++i )
1743  blkmem->chkmemhash[i] = NULL;
1744  blkmem->initchunksize = initchunksize;
1745  blkmem->garbagefactor = garbagefactor;
1746  blkmem->memused = 0;
1747  blkmem->memallocated = 0;
1748  blkmem->maxmemused = 0;
1749  blkmem->maxmemunused = 0;
1750  blkmem->maxmemallocated = 0;
1751  }
1752  else
1753  {
1754  printErrorHeader(filename, line);
1755  printError("Insufficient memory for block memory header.\n");
1756  }
1757 
1758  return blkmem;
1759 }
1760 
1761 /** frees all chunk blocks in the block memory */
1763  BMS_BLKMEM* blkmem, /**< block memory */
1764  const char* filename, /**< source file of the function call */
1765  int line /**< line number in source file of the function call */
1766  )
1767 {
1768  BMS_CHKMEM* chkmem;
1769  BMS_CHKMEM* nextchkmem;
1770  int i;
1771 
1772  if( blkmem != NULL )
1773  {
1774  for( i = 0; i < CHKHASH_SIZE; ++i )
1775  {
1776  chkmem = blkmem->chkmemhash[i];
1777  while( chkmem != NULL )
1778  {
1779  nextchkmem = chkmem->nextchkmem;
1780  destroyChkmem(&chkmem, &blkmem->memallocated);
1781  chkmem = nextchkmem;
1782  }
1783  blkmem->chkmemhash[i] = NULL;
1784  }
1785  blkmem->memused = 0;
1786  assert(blkmem->memallocated == 0);
1787  }
1788  else
1789  {
1790  printErrorHeader(filename, line);
1791  printError("Tried to clear null block memory.\n");
1792  }
1793 }
1794 
1795 /** clears and deletes block memory */
1797  BMS_BLKMEM** blkmem, /**< pointer to block memory */
1798  const char* filename, /**< source file of the function call */
1799  int line /**< line number in source file of the function call */
1800  )
1801 {
1802  assert(blkmem != NULL);
1803 
1804  if( *blkmem != NULL )
1805  {
1806  BMSclearBlockMemory_call(*blkmem, filename, line);
1807  BMSfreeMemory(blkmem);
1808  assert(*blkmem == NULL);
1809  }
1810  else
1811  {
1812  printErrorHeader(filename, line);
1813  printError("Tried to destroy null block memory.\n");
1814  }
1815 }
1816 
1817 /** work for allocating memory in the block memory pool */
1818 INLINE static
1820  BMS_BLKMEM* blkmem, /**< block memory */
1821  size_t size, /**< size of memory element to allocate */
1822  const char* filename, /**< source file of the function call */
1823  int line /**< line number in source file of the function call */
1824  )
1825 {
1826  BMS_CHKMEM** chkmemptr;
1827  int hashnumber;
1828  void* ptr;
1829 
1830  assert( blkmem != NULL );
1831 
1832  /* calculate hash number of given size */
1833  alignSize(&size);
1834  hashnumber = getHashNumber((int)size);
1835 
1836  /* find correspoding chunk block */
1837  chkmemptr = &(blkmem->chkmemhash[hashnumber]);
1838  while( *chkmemptr != NULL && (*chkmemptr)->elemsize != (int)size )
1839  chkmemptr = &((*chkmemptr)->nextchkmem);
1840 
1841  /* create new chunk block if necessary */
1842  if( *chkmemptr == NULL )
1843  {
1844  *chkmemptr = createChkmem((int)size, blkmem->initchunksize, blkmem->garbagefactor, &blkmem->memallocated);
1845  if( *chkmemptr == NULL )
1846  {
1847  printErrorHeader(filename, line);
1848  printError("Insufficient memory for chunk block.\n");
1849  return NULL;
1850  }
1851 #ifndef NDEBUG
1852  BMSduplicateMemoryArray(&(*chkmemptr)->filename, filename, strlen(filename) + 1);
1853  (*chkmemptr)->line = line;
1854 #endif
1855  }
1856 
1857  /* get memory inside the chunk block */
1858  ptr = allocChkmemElement(*chkmemptr, &blkmem->memallocated);
1859 
1860  if( ptr == NULL )
1861  {
1862  printErrorHeader(filename, line);
1863  printError("Insufficient memory for new chunk.\n");
1864  }
1865  debugMessage("alloced %8llu bytes in %p [%s:%d]\n", (unsigned long long)size, ptr, filename, line);
1866 
1867  /* add the used memory */
1868  blkmem->memused += (long long) size;
1869  blkmem->maxmemused = MAX(blkmem->maxmemused, blkmem->memused);
1870  blkmem->maxmemunused = MAX(blkmem->maxmemunused, blkmem->memallocated - blkmem->memused);
1871  blkmem->maxmemallocated = MAX(blkmem->maxmemallocated, blkmem->memallocated);
1872 
1873  assert(blkmem->memused >= 0);
1874  assert(blkmem->memallocated >= 0);
1875 
1876  checkBlkmem(blkmem);
1877 
1878  return ptr;
1879 }
1880 
1881 /** allocates memory in the block memory pool */
1883  BMS_BLKMEM* blkmem, /**< block memory */
1884  size_t size, /**< size of memory element to allocate */
1885  const char* filename, /**< source file of the function call */
1886  int line /**< line number in source file of the function call */
1887  )
1888 {
1889 #ifndef NDEBUG
1890  if ( size > MAXMEMSIZE )
1891  {
1892  printErrorHeader(filename, line);
1893  printError("Tried to allocate block of size exceeding %lu.\n", MAXMEMSIZE);
1894  return NULL;
1895  }
1896 #endif
1897 
1898  return BMSallocBlockMemory_work(blkmem, size, filename, line);
1899 }
1900 
1901 /** allocates array in the block memory pool */
1903  BMS_BLKMEM* blkmem, /**< block memory */
1904  size_t num, /**< size of array to be allocated */
1905  size_t typesize, /**< size of each component */
1906  const char* filename, /**< source file of the function call */
1907  int line /**< line number in source file of the function call */
1908  )
1909 {
1910 #ifndef NDEBUG
1911  if ( num > (MAXMEMSIZE / typesize) )
1912  {
1913  printErrorHeader(filename, line);
1914  printError("Tried to allocate block of size exceeding %lu.\n", MAXMEMSIZE);
1915  return NULL;
1916  }
1917 #endif
1918 
1919  return BMSallocBlockMemory_work(blkmem, num * typesize, filename, line);
1920 }
1921 
1922 /** allocates array in the block memory pool and clears it */
1924  BMS_BLKMEM* blkmem, /**< block memory */
1925  size_t num, /**< size of array to be allocated */
1926  size_t typesize, /**< size of each component */
1927  const char* filename, /**< source file of the function call */
1928  int line /**< line number in source file of the function call */
1929  )
1930 {
1931  void* ptr;
1932 
1933  ptr = BMSallocBlockMemoryArray_call(blkmem, num, typesize, filename, line);
1934  if ( ptr != NULL )
1935  BMSclearMemorySize(ptr, num * typesize);
1936 
1937  return ptr;
1938 }
1939 
1940 /** resizes memory element in the block memory pool and copies the data */
1942  BMS_BLKMEM* blkmem, /**< block memory */
1943  void* ptr, /**< memory element to reallocated */
1944  size_t oldsize, /**< old size of memory element */
1945  size_t newsize, /**< new size of memory element */
1946  const char* filename, /**< source file of the function call */
1947  int line /**< line number in source file of the function call */
1948  )
1949 {
1950  void* newptr;
1951 
1952  if( ptr == NULL )
1953  {
1954  assert(oldsize == 0);
1955  return BMSallocBlockMemory_call(blkmem, newsize, filename, line);
1956  }
1957 
1958 #ifndef NDEBUG
1959  if ( newsize > MAXMEMSIZE )
1960  {
1961  printErrorHeader(filename, line);
1962  printError("Tried to allocate block of size exceeding %lu.\n", MAXMEMSIZE);
1963  return NULL;
1964  }
1965 #endif
1966 
1967  alignSize(&oldsize);
1968  alignSize(&newsize);
1969  if( oldsize == newsize )
1970  return ptr;
1971 
1972  newptr = BMSallocBlockMemory_call(blkmem, newsize, filename, line);
1973  if( newptr != NULL )
1974  BMScopyMemorySize(newptr, ptr, MIN(oldsize, newsize));
1975  BMSfreeBlockMemory_call(blkmem, &ptr, oldsize, filename, line);
1976 
1977  return newptr;
1978 }
1979 
1980 /** resizes array in the block memory pool and copies the data */
1982  BMS_BLKMEM* blkmem, /**< block memory */
1983  void* ptr, /**< memory element to reallocated */
1984  size_t oldnum, /**< old size of array */
1985  size_t newnum, /**< new size of array */
1986  size_t typesize, /**< size of each component */
1987  const char* filename, /**< source file of the function call */
1988  int line /**< line number in source file of the function call */
1989  )
1990 {
1991  void* newptr;
1992 
1993  if( ptr == NULL )
1994  {
1995  assert(oldnum == 0);
1996  return BMSallocBlockMemoryArray_call(blkmem, newnum, typesize, filename, line);
1997  }
1998 
1999 #ifndef NDEBUG
2000  if ( newnum > (MAXMEMSIZE / typesize) )
2001  {
2002  printErrorHeader(filename, line);
2003  printError("Tried to allocate array of size exceeding %lu.\n", MAXMEMSIZE);
2004  return NULL;
2005  }
2006 #endif
2007 
2008  if ( oldnum == newnum )
2009  return ptr;
2010 
2011  newptr = BMSallocBlockMemoryArray_call(blkmem, newnum, typesize, filename, line);
2012  if ( newptr != NULL )
2013  BMScopyMemorySize(newptr, ptr, MIN(oldnum, newnum) * typesize);
2014  BMSfreeBlockMemory_call(blkmem, &ptr, oldnum * typesize, filename, line);
2015 
2016  return newptr;
2017 }
2018 
2019 /** duplicates memory element in the block memory pool and copies the data */
2021  BMS_BLKMEM* blkmem, /**< block memory */
2022  const void* source, /**< memory element to duplicate */
2023  size_t size, /**< size of memory elements */
2024  const char* filename, /**< source file of the function call */
2025  int line /**< line number in source file of the function call */
2026  )
2027 {
2028  void* ptr;
2029 
2030  assert(source != NULL);
2031 
2032  ptr = BMSallocBlockMemory_call(blkmem, size, filename, line);
2033  if( ptr != NULL )
2034  BMScopyMemorySize(ptr, source, size);
2035 
2036  return ptr;
2037 }
2038 
2039 /** duplicates array in the block memory pool and copies the data */
2041  BMS_BLKMEM* blkmem, /**< block memory */
2042  const void* source, /**< memory element to duplicate */
2043  size_t num, /**< size of array to be duplicated */
2044  size_t typesize, /**< size of each component */
2045  const char* filename, /**< source file of the function call */
2046  int line /**< line number in source file of the function call */
2047  )
2048 {
2049  void* ptr;
2050 
2051  assert(source != NULL);
2052 
2053  ptr = BMSallocBlockMemoryArray_call(blkmem, num, typesize, filename, line);
2054  if( ptr != NULL )
2055  BMScopyMemorySize(ptr, source, num * typesize);
2056 
2057  return ptr;
2058 }
2059 
2060 /** common work for freeing block memory */
2061 INLINE static
2063  BMS_BLKMEM* blkmem, /**< block memory */
2064  void** ptr, /**< pointer to pointer to memory element to free */
2065  size_t size, /**< size of memory element */
2066  const char* filename, /**< source file of the function call */
2067  int line /**< line number in source file of the function call */
2068  )
2069 {
2070  BMS_CHKMEM* chkmem;
2071  int hashnumber;
2072 
2073  assert(ptr != NULL);
2074  assert(*ptr != NULL);
2075 
2076  /* calculate hash number of given size */
2077  alignSize(&size);
2078  hashnumber = getHashNumber((int)size);
2079 
2080  debugMessage("free %8llu bytes in %p [%s:%d]\n", (unsigned long long)size, *ptr, filename, line);
2081 
2082  /* find correspoding chunk block */
2083  assert( blkmem->chkmemhash != NULL );
2084  chkmem = blkmem->chkmemhash[hashnumber];
2085  while( chkmem != NULL && chkmem->elemsize != (int)size )
2086  chkmem = chkmem->nextchkmem;
2087  if( chkmem == NULL )
2088  {
2089  printErrorHeader(filename, line);
2090  printError("Tried to free pointer <%p> in block memory <%p> of unknown size %llu.\n", *ptr, (void*)blkmem, (unsigned long long)size);
2091  return;
2092  }
2093  assert(chkmem->elemsize == (int)size);
2094 
2095  /* free memory in chunk block */
2096  freeChkmemElement(chkmem, *ptr, &blkmem->memallocated, filename, line);
2097  blkmem->memused -= (long long) size;
2098 
2099  blkmem->maxmemunused = MAX(blkmem->maxmemunused, blkmem->memallocated - blkmem->memused);
2100 
2101  assert(blkmem->memused >= 0);
2102  assert(blkmem->memallocated >= 0);
2103 
2104  checkBlkmem(blkmem);
2105 
2106  *ptr = NULL;
2107 }
2108 
2109 /** frees memory element in the block memory pool and sets pointer to NULL */
2111  BMS_BLKMEM* blkmem, /**< block memory */
2112  void** ptr, /**< pointer to pointer to memory element to free */
2113  size_t size, /**< size of memory element */
2114  const char* filename, /**< source file of the function call */
2115  int line /**< line number in source file of the function call */
2116  )
2117 {
2118  assert( blkmem != NULL );
2119  assert( ptr != NULL );
2120 
2121  if( *ptr != NULL )
2122  BMSfreeBlockMemory_work(blkmem, ptr, size, filename, line);
2123  else if( size != 0 )
2124  {
2125  printErrorHeader(filename, line);
2126  printError("Tried to free null block pointer.\n");
2127  }
2128  checkBlkmem(blkmem);
2129 }
2130 
2131 /** frees memory element in the block memory pool if pointer is not NULL and sets pointer to NULL */
2133  BMS_BLKMEM* blkmem, /**< block memory */
2134  void** ptr, /**< pointer to pointer to memory element to free */
2135  size_t size, /**< size of memory element */
2136  const char* filename, /**< source file of the function call */
2137  int line /**< line number in source file of the function call */
2138  )
2139 {
2140  assert( blkmem != NULL );
2141  assert( ptr != NULL );
2142 
2143  if( *ptr != NULL )
2144  {
2145  BMSfreeBlockMemory_work(blkmem, ptr, size, filename, line);
2146  }
2147  checkBlkmem(blkmem);
2148 }
2149 
2150 /** calls garbage collection of block memory, frees chunks without allocated memory elements, and frees
2151  * chunk blocks without any chunks
2152  */
2154  BMS_BLKMEM* blkmem /**< block memory */
2155  )
2156 {
2157  int i;
2158 
2159  assert(blkmem != NULL);
2160 
2161  for( i = 0; i < CHKHASH_SIZE; ++i )
2162  {
2163  BMS_CHKMEM** chkmemptr;
2164 
2165  chkmemptr = &blkmem->chkmemhash[i];
2166  while( *chkmemptr != NULL )
2167  {
2168  garbagecollectChkmem(*chkmemptr, &blkmem->memallocated);
2169  checkBlkmem(blkmem);
2170  if( (*chkmemptr)->nchunks == 0 )
2171  {
2172  BMS_CHKMEM* nextchkmem;
2173 
2174  assert((*chkmemptr)->lazyfreesize == 0);
2175  nextchkmem = (*chkmemptr)->nextchkmem;
2176  destroyChkmem(chkmemptr, &blkmem->memallocated);
2177  *chkmemptr = nextchkmem;
2178  checkBlkmem(blkmem);
2179  }
2180  else
2181  chkmemptr = &(*chkmemptr)->nextchkmem;
2182  }
2183  }
2184 }
2185 
2186 /** returns the number of allocated bytes in the block memory */
2188  const BMS_BLKMEM* blkmem /**< block memory */
2189  )
2190 {
2191  assert( blkmem != NULL );
2192 
2193  return blkmem->memallocated;
2194 }
2195 
2196 /** returns the number of used bytes in the block memory */
2198  const BMS_BLKMEM* blkmem /**< block memory */
2199  )
2200 {
2201  assert( blkmem != NULL );
2202 
2203  return blkmem->memused;
2204 }
2205 
2206 /** returns the number of allocated but not used bytes in the block memory */
2208  const BMS_BLKMEM* blkmem /**< block memory */
2209  )
2210 {
2211  assert( blkmem != NULL );
2212 
2213  return blkmem->memallocated - blkmem->memused;
2214 }
2215 
2216 /** returns the maximal number of used bytes in the block memory */
2218  const BMS_BLKMEM* blkmem /**< block memory */
2219  )
2220 {
2221  assert( blkmem != NULL );
2222 
2223  return blkmem->maxmemused;
2224 }
2225 
2226 /** returns the maximal number of allocated but not used bytes in the block memory */
2228  const BMS_BLKMEM* blkmem /**< block memory */
2229  )
2230 {
2231  assert( blkmem != NULL );
2232 
2233  return blkmem->maxmemunused;
2234 }
2235 
2236 /** returns the maximal number of allocated bytes in the block memory */
2238  const BMS_BLKMEM* blkmem /**< block memory */
2239  )
2240 {
2241  assert( blkmem != NULL );
2242 
2243  return blkmem->maxmemallocated;
2244 }
2245 
2246 /** returns the size of the given memory element; returns 0, if the element is not member of the block memory */
2248  const BMS_BLKMEM* blkmem, /**< block memory */
2249  const void* ptr /**< memory element */
2250  )
2251 {
2252  const BMS_CHKMEM* chkmem;
2253 
2254  assert(blkmem != NULL);
2255 
2256  if( ptr == NULL )
2257  return 0;
2258 
2259  chkmem = findChkmem(blkmem, ptr);
2260  if( chkmem == NULL )
2261  return 0;
2262 
2263  return (size_t)(chkmem->elemsize); /*lint !e571*/
2264 }
2265 
2266 /** outputs allocation diagnostics of block memory */
2268  const BMS_BLKMEM* blkmem /**< block memory */
2269  )
2270 {
2271  const BMS_CHKMEM* chkmem;
2272  int nblocks = 0;
2273  int nunusedblocks = 0;
2274  int totalnchunks = 0;
2275  int totalneagerchunks = 0;
2276  int totalnelems = 0;
2277  int totalneagerelems = 0;
2278  int totalnlazyelems = 0;
2279 #ifndef NDEBUG
2280  int totalngarbagecalls = 0;
2281  int totalngarbagefrees = 0;
2282 #endif
2283  long long allocedmem = 0;
2284  long long freemem = 0;
2285  int i;
2286 
2287 #ifndef NDEBUG
2288  printInfo(" ElSize #Chunk #Eag #Elems #EagFr #LazFr #GCl #GFr Free MBytes First Allocator\n");
2289 #else
2290  printInfo(" ElSize #Chunk #Eag #Elems #EagFr #LazFr Free MBytes\n");
2291 #endif
2292 
2293  assert(blkmem != NULL);
2294 
2295  for( i = 0; i < CHKHASH_SIZE; ++i )
2296  {
2297  chkmem = blkmem->chkmemhash[i];
2298  while( chkmem != NULL )
2299  {
2300  int nchunks = 0;
2301  int nelems = 0;
2302  int neagerchunks = 0;
2303  int neagerelems = 0;
2304 
2305  FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk,
2306  {
2307  assert(chunk != NULL);
2308  assert(chunk->elemsize == chkmem->elemsize);
2309  assert(chunk->chkmem == chkmem);
2310  nchunks++;
2311  nelems += chunk->storesize;
2312  if( chunk->eagerfree != NULL )
2313  {
2314  neagerchunks++;
2315  neagerelems += chunk->eagerfreesize;
2316  }
2317  })
2318 
2319  assert(nchunks == chkmem->nchunks);
2320  assert(nelems == chkmem->storesize);
2321  assert(neagerelems == chkmem->eagerfreesize);
2322 
2323  if( nelems > 0 )
2324  {
2325  nblocks++;
2326  allocedmem += (long long)chkmem->elemsize * (long long)nelems;
2327  freemem += (long long)chkmem->elemsize * ((long long)neagerelems + (long long)chkmem->lazyfreesize);
2328 
2329 #ifndef NDEBUG
2330  printInfo("%7d %6d %4d %7d %7d %7d %5d %4d %5.1f%% %6.1f %s:%d\n",
2331  chkmem->elemsize, nchunks, neagerchunks, nelems,
2332  neagerelems, chkmem->lazyfreesize, chkmem->ngarbagecalls, chkmem->ngarbagefrees,
2333  100.0 * (double) (neagerelems + chkmem->lazyfreesize) / (double) (nelems),
2334  (double)chkmem->elemsize * nelems / (1024.0*1024.0),
2335  chkmem->filename, chkmem->line);
2336 #else
2337  printInfo("%7d %6d %4d %7d %7d %7d %5.1f%% %6.1f\n",
2338  chkmem->elemsize, nchunks, neagerchunks, nelems,
2339  neagerelems, chkmem->lazyfreesize,
2340  100.0 * (double) (neagerelems + chkmem->lazyfreesize) / (double) (nelems),
2341  (double)chkmem->elemsize * nelems / (1024.0*1024.0));
2342 #endif
2343  }
2344  else
2345  {
2346 #ifndef NDEBUG
2347  printInfo("%7d <unused> %5d %4d %s:%d\n",
2348  chkmem->elemsize, chkmem->ngarbagecalls, chkmem->ngarbagefrees,
2349  chkmem->filename, chkmem->line);
2350 #else
2351  printInfo("%7d <unused>\n", chkmem->elemsize);
2352 #endif
2353  nunusedblocks++;
2354  }
2355  totalnchunks += nchunks;
2356  totalneagerchunks += neagerchunks;
2357  totalnelems += nelems;
2358  totalneagerelems += neagerelems;
2359  totalnlazyelems += chkmem->lazyfreesize;
2360 #ifndef NDEBUG
2361  totalngarbagecalls += chkmem->ngarbagecalls;
2362  totalngarbagefrees += chkmem->ngarbagefrees;
2363 #endif
2364  chkmem = chkmem->nextchkmem;
2365  }
2366  }
2367 #ifndef NDEBUG
2368  printInfo(" Total %6d %4d %7d %7d %7d %5d %4d %5.1f%% %6.1f\n",
2369  totalnchunks, totalneagerchunks, totalnelems, totalneagerelems, totalnlazyelems,
2370  totalngarbagecalls, totalngarbagefrees,
2371  totalnelems > 0 ? 100.0 * (double) (totalneagerelems + totalnlazyelems) / (double) (totalnelems) : 0.0,
2372  (double)allocedmem/(1024.0*1024.0));
2373 #else
2374  printInfo(" Total %6d %4d %7d %7d %7d %5.1f%% %6.1f\n",
2375  totalnchunks, totalneagerchunks, totalnelems, totalneagerelems, totalnlazyelems,
2376  totalnelems > 0 ? 100.0 * (double) (totalneagerelems + totalnlazyelems) / (double) (totalnelems) : 0.0,
2377  (double)allocedmem/(1024.0*1024.0));
2378 #endif
2379  printInfo("%d blocks (%d unused), %" LONGINT_FORMAT " bytes allocated, %" LONGINT_FORMAT " bytes free",
2380  nblocks + nunusedblocks, nunusedblocks, allocedmem, freemem);
2381  if( allocedmem > 0 )
2382  printInfo(" (%.1f%%)", 100.0 * (double) freemem / (double) allocedmem);
2383  printInfo("\n\n");
2384 
2385  printInfo("Memory Peaks: Used Lazy Total\n");
2386  printInfo(" %6.1f %6.1f %6.1f MBytes\n", (double)blkmem->maxmemused / (1024.0 * 1024.0),
2387  (double)blkmem->maxmemunused / (1024.0 * 1024.0), (double)blkmem->maxmemallocated / (1024.0 * 1024.0));
2388 }
2389 
2390 /** outputs error messages, if there are allocated elements in the block memory and returns number of unfreed bytes */
2392  const BMS_BLKMEM* blkmem /**< block memory */
2393  )
2394 {
2395  const BMS_CHKMEM* chkmem;
2396  long long allocedmem = 0;
2397  long long freemem = 0;
2398  int i;
2399 
2400  assert(blkmem != NULL);
2401 
2402  for( i = 0; i < CHKHASH_SIZE; ++i )
2403  {
2404  chkmem = blkmem->chkmemhash[i];
2405  while( chkmem != NULL )
2406  {
2407  int nchunks = 0;
2408  int nelems = 0;
2409  int neagerelems = 0;
2410 
2411  FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk,
2412  {
2413  assert(chunk != NULL);
2414  assert(chunk->elemsize == chkmem->elemsize);
2415  assert(chunk->chkmem == chkmem);
2416  nchunks++;
2417  nelems += chunk->storesize;
2418  if( chunk->eagerfree != NULL )
2419  neagerelems += chunk->eagerfreesize;
2420  })
2421 
2422  assert(nchunks == chkmem->nchunks);
2423  assert(nelems == chkmem->storesize);
2424  assert(neagerelems == chkmem->eagerfreesize);
2425 
2426  if( nelems > 0 )
2427  {
2428  allocedmem += (long long)chkmem->elemsize * (long long)nelems;
2429  freemem += (long long)chkmem->elemsize * ((long long)neagerelems + (long long)chkmem->lazyfreesize);
2430 
2431  if( nelems != neagerelems + chkmem->lazyfreesize )
2432  {
2433 #ifndef NDEBUG
2434  errorMessage("%" LONGINT_FORMAT " bytes (%d elements of size %" LONGINT_FORMAT ") not freed. First Allocator: %s:%d\n",
2435  (((long long)nelems - (long long)neagerelems) - (long long)chkmem->lazyfreesize)
2436  * (long long)(chkmem->elemsize),
2437  (nelems - neagerelems) - chkmem->lazyfreesize, (long long)(chkmem->elemsize),
2438  chkmem->filename, chkmem->line);
2439 #else
2440  errorMessage("%" LONGINT_FORMAT " bytes (%d elements of size %" LONGINT_FORMAT ") not freed.\n",
2441  ((nelems - neagerelems) - chkmem->lazyfreesize) * (long long)(chkmem->elemsize),
2442  (nelems - neagerelems) - chkmem->lazyfreesize, (long long)(chkmem->elemsize));
2443 #endif
2444  }
2445  }
2446  chkmem = chkmem->nextchkmem;
2447  }
2448  }
2449 
2450  if( allocedmem != freemem )
2451  {
2452  errorMessage("%" LONGINT_FORMAT " bytes not freed in total.\n", allocedmem - freemem);
2453  }
2454 
2455  return allocedmem - freemem;
2456 }
2457 
2458 
2459 
2460 
2461 
2462 
2463 /***********************************************************
2464  * Buffer Memory Management
2465  *
2466  * Efficient memory management for temporary objects
2467  ***********************************************************/
2468 
2469 /** memory buffer storage for temporary objects */
2471 {
2472  void** data; /**< allocated memory chunks for arbitrary data */
2473  size_t* size; /**< sizes of buffers in bytes */
2474  unsigned int* used; /**< 1 iff corresponding buffer is in use */
2475  size_t totalmem; /**< total memory consumption of buffer */
2476  unsigned int clean; /**< 1 iff the memory blocks in the buffer should be initialized to zero? */
2477  size_t ndata; /**< number of memory chunks */
2478  size_t firstfree; /**< first unused memory chunk */
2479  double arraygrowfac; /**< memory growing factor for dynamically allocated arrays */
2480  unsigned int arraygrowinit; /**< initial size of dynamically allocated arrays */
2481 };
2482 
2483 
2484 /** creates memory buffer storage */
2486  double arraygrowfac, /**< memory growing factor for dynamically allocated arrays */
2487  int arraygrowinit, /**< initial size of dynamically allocated arrays */
2488  unsigned int clean, /**< should the memory blocks in the buffer be initialized to zero? */
2489  const char* filename, /**< source file of the function call */
2490  int line /**< line number in source file of the function call */
2491  )
2492 {
2493  BMS_BUFMEM* buffer;
2494 
2495  assert( arraygrowinit > 0 );
2496  assert( arraygrowfac > 0.0 );
2497 
2498  BMSallocMemory(&buffer);
2499  if ( buffer != NULL )
2500  {
2501  buffer->data = NULL;
2502  buffer->size = NULL;
2503  buffer->used = NULL;
2504  buffer->totalmem = 0UL;
2505  buffer->clean = clean;
2506  buffer->ndata = 0;
2507  buffer->firstfree = 0;
2508  buffer->arraygrowinit = (unsigned) arraygrowinit;
2509  buffer->arraygrowfac = arraygrowfac;
2510  }
2511  else
2512  {
2513  printErrorHeader(filename, line);
2514  printError("Insufficient memory for buffer memory header.\n");
2515  }
2516 
2517  return buffer;
2518 }
2519 
2520 /** destroys buffer memory */
2522  BMS_BUFMEM** buffer, /**< pointer to memory buffer storage */
2523  const char* filename, /**< source file of the function call */
2524  int line /**< line number in source file of the function call */
2525  )
2526 {
2527  size_t i;
2528 
2529  if ( *buffer != NULL )
2530  {
2531  i = (*buffer)->ndata;
2532  if ( i > 0 ) {
2533  for (--i ; ; i--)
2534  {
2535  assert( ! (*buffer)->used[i] );
2536  BMSfreeMemoryArrayNull(&(*buffer)->data[i]);
2537  if ( i == 0 )
2538  break;
2539  }
2540  }
2541  BMSfreeMemoryArrayNull(&(*buffer)->data);
2542  BMSfreeMemoryArrayNull(&(*buffer)->size);
2543  BMSfreeMemoryArrayNull(&(*buffer)->used);
2544  BMSfreeMemory(buffer);
2545  }
2546  else
2547  {
2548  printErrorHeader(filename, line);
2549  printError("Tried to free null buffer memory.\n");
2550  }
2551 }
2552 
2553 /** set arraygrowfac */
2555  BMS_BUFMEM* buffer, /**< pointer to memory buffer storage */
2556  double arraygrowfac /**< memory growing factor for dynamically allocated arrays */
2557  )
2558 {
2559  assert( buffer != NULL );
2560  assert( arraygrowfac > 0.0 );
2561 
2562  buffer->arraygrowfac = arraygrowfac;
2563 }
2564 
2565 /** set arraygrowinit */
2567  BMS_BUFMEM* buffer, /**< pointer to memory buffer storage */
2568  int arraygrowinit /**< initial size of dynamically allocated arrays */
2569  )
2570 {
2571  assert( buffer != NULL );
2572  assert( arraygrowinit > 0 );
2573 
2574  buffer->arraygrowinit = (unsigned) arraygrowinit;
2575 }
2576 
2577 #ifndef SCIP_NOBUFFERMEM
2578 /** calculate memory size for dynamically allocated arrays
2579  *
2580  * This function is a copy of the function in set.c in order to be able to use memory.? separately.
2581  */
2582 static
2584  size_t initsize, /**< initial size of array */
2585  SCIP_Real growfac, /**< growing factor of array */
2586  size_t num /**< minimum number of entries to store */
2587  )
2588 {
2589  size_t size;
2590 
2591  assert( growfac >= 1.0 );
2592 
2593  if ( growfac == 1.0 )
2594  size = MAX(initsize, num);
2595  else
2596  {
2597  size_t oldsize;
2598 
2599  /* calculate the size with this loop, such that the resulting numbers are always the same */
2600  initsize = MAX(initsize, 4);
2601  size = initsize;
2602  oldsize = size - 1;
2603 
2604  /* second condition checks against overflow */
2605  while ( size < num && size > oldsize )
2606  {
2607  oldsize = size;
2608  size = (size_t)(growfac * size + initsize);
2609  }
2610 
2611  /* if an overflow happened, set the correct value */
2612  if ( size <= oldsize )
2613  size = num;
2614  }
2615 
2616  assert( size >= initsize );
2617  assert( size >= num );
2618 
2619  return size;
2620 }
2621 #endif
2622 
2623 /** work for allocating the next unused buffer */
2624 INLINE static
2626  BMS_BUFMEM* buffer, /**< memory buffer storage */
2627  size_t size, /**< minimal required size of the buffer */
2628  const char* filename, /**< source file of the function call */
2629  int line /**< line number in source file of the function call */
2630  )
2631 {
2632  /* cppcheck-suppress unassignedVariable */
2633  void* ptr;
2634 #ifndef SCIP_NOBUFFERMEM
2635  size_t bufnum;
2636 #endif
2637 
2638 #ifndef SCIP_NOBUFFERMEM
2639  assert( buffer != NULL );
2640  assert( buffer->firstfree <= buffer->ndata );
2641 
2642  /* allocate a minimum of 1 byte */
2643  if ( size == 0 )
2644  size = 1;
2645 
2646  /* check, if we need additional buffers */
2647  if ( buffer->firstfree == buffer->ndata )
2648  {
2649  size_t newsize;
2650  size_t i;
2651 
2652  /* create additional buffers */
2653  newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, buffer->firstfree + 1);
2654  BMSreallocMemoryArray(&buffer->data, newsize);
2655  if ( buffer->data == NULL )
2656  {
2657  printErrorHeader(filename, line);
2658  printError("Insufficient memory for reallocating buffer data storage.\n");
2659  return NULL;
2660  }
2661  BMSreallocMemoryArray(&buffer->size, newsize);
2662  if ( buffer->size == NULL )
2663  {
2664  printErrorHeader(filename, line);
2665  printError("Insufficient memory for reallocating buffer size storage.\n");
2666  return NULL;
2667  }
2668  BMSreallocMemoryArray(&buffer->used, newsize);
2669  if ( buffer->used == NULL )
2670  {
2671  printErrorHeader(filename, line);
2672  printError("Insufficient memory for reallocating buffer used storage.\n");
2673  return NULL;
2674  }
2675 
2676  /* init data */
2677  for (i = buffer->ndata; i < newsize; ++i)
2678  {
2679  buffer->data[i] = NULL;
2680  buffer->size[i] = 0;
2681  buffer->used[i] = FALSE;
2682  }
2683  buffer->ndata = newsize;
2684  }
2685  assert(buffer->firstfree < buffer->ndata);
2686 
2687  /* check, if the current buffer is large enough */
2688  bufnum = buffer->firstfree;
2689  assert( ! buffer->used[bufnum] );
2690  if ( buffer->size[bufnum] < size )
2691  {
2692  size_t newsize;
2693 
2694  /* enlarge buffer */
2695  newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, size);
2696  BMSreallocMemorySize(&buffer->data[bufnum], newsize);
2697 
2698  /* clear new memory */
2699  if( buffer->clean )
2700  {
2701  char* tmpptr = (char*)(buffer->data[bufnum]);
2702  size_t inc = buffer->size[bufnum] / sizeof(*tmpptr);
2703  tmpptr += inc;
2704 
2705  BMSclearMemorySize(tmpptr, newsize - buffer->size[bufnum]);
2706  }
2707  assert( newsize > buffer->size[bufnum] );
2708  buffer->totalmem += newsize - buffer->size[bufnum];
2709  buffer->size[bufnum] = newsize;
2710 
2711  if ( buffer->data[bufnum] == NULL )
2712  {
2713  printErrorHeader(filename, line);
2714  printError("Insufficient memory for reallocating buffer storage.\n");
2715  return NULL;
2716  }
2717  }
2718  assert( buffer->size[bufnum] >= size );
2719 
2720 #ifdef CHECKCLEANBUFFER
2721  /* check that the memory is cleared */
2722  if( buffer->clean )
2723  {
2724  char* tmpptr = (char*)(buffer->data[bufnum]);
2725  unsigned int inc = buffer->size[bufnum] / sizeof(*tmpptr);
2726  tmpptr += inc;
2727 
2728  while( --tmpptr >= (char*)(buffer->data[bufnum]) )
2729  assert(*tmpptr == '\0');
2730  }
2731 #endif
2732 
2733  ptr = buffer->data[bufnum];
2734  buffer->used[bufnum] = TRUE;
2735  buffer->firstfree++;
2736 
2737  debugMessage("Allocated buffer %llu/%llu at %p of size %llu (required size: %llu) for pointer %p.\n",
2738  (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum],
2739  (unsigned long long)(buffer->size[bufnum]), (unsigned long long)size, ptr);
2740 
2741 #else
2742  if( buffer->clean )
2743  {
2744  /* we should allocate at least one byte, otherwise BMSallocMemorySize will fail */
2745  size = MAX(size,1);
2746 
2747  BMSallocClearMemorySize(&ptr, size);
2748  }
2749  else
2750  {
2751  BMSallocMemorySize(&ptr, size);
2752  }
2753 #endif
2754 
2755  return ptr;
2756 }
2757 
2758 /** allocates the next unused buffer */
2760  BMS_BUFMEM* buffer, /**< memory buffer storage */
2761  size_t size, /**< minimal required size of the buffer */
2762  const char* filename, /**< source file of the function call */
2763  int line /**< line number in source file of the function call */
2764  )
2765 {
2766 #ifndef NDEBUG
2767  if ( size > MAXMEMSIZE )
2768  {
2769  printErrorHeader(filename, line);
2770  printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE);
2771  return NULL;
2772  }
2773 #endif
2774 
2775  return BMSallocBufferMemory_work(buffer, size, filename, line);
2776 }
2777 
2778 /** allocates the next unused buffer array */
2780  BMS_BUFMEM* buffer, /**< memory buffer storage */
2781  size_t num, /**< size of array to be allocated */
2782  size_t typesize, /**< size of components */
2783  const char* filename, /**< source file of the function call */
2784  int line /**< line number in source file of the function call */
2785  )
2786 {
2787 #ifndef NDEBUG
2788  if ( num > (MAXMEMSIZE / typesize) )
2789  {
2790  printErrorHeader(filename, line);
2791  printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE);
2792  return NULL;
2793  }
2794 #endif
2795 
2796  return BMSallocBufferMemory_work(buffer, num * typesize, filename, line);
2797 }
2798 
2799 /** allocates the next unused buffer and clears it */
2801  BMS_BUFMEM* buffer, /**< memory buffer storage */
2802  size_t num, /**< size of array to be allocated */
2803  size_t typesize, /**< size of components */
2804  const char* filename, /**< source file of the function call */
2805  int line /**< line number in source file of the function call */
2806  )
2807 {
2808  void* ptr;
2809 
2810  ptr = BMSallocBufferMemoryArray_call(buffer, num, typesize, filename, line);
2811  if ( ptr != NULL )
2812  BMSclearMemorySize(ptr, num * typesize);
2813 
2814  return ptr;
2815 }
2816 
2817 /** work for reallocating the buffer to at least the given size */
2818 INLINE static
2820  BMS_BUFMEM* buffer, /**< memory buffer storage */
2821  void* ptr, /**< pointer to the allocated memory buffer */
2822  size_t size, /**< minimal required size of the buffer */
2823  const char* filename, /**< source file of the function call */
2824  int line /**< line number in source file of the function call */
2825  )
2826 {
2827  void* newptr;
2828 #ifndef SCIP_NOBUFFERMEM
2829  size_t bufnum;
2830 #endif
2831 
2832 #ifndef SCIP_NOBUFFERMEM
2833  assert( buffer != NULL );
2834  assert( buffer->firstfree <= buffer->ndata );
2835  assert(!buffer->clean); /* reallocating clean buffer elements is not supported */
2836 
2837  /* if the pointer doesn't exist yet, allocate it */
2838  if ( ptr == NULL )
2839  return BMSallocBufferMemory_call(buffer, size, filename, line);
2840 
2841  assert( buffer->firstfree >= 1 );
2842 
2843  /* Search the pointer in the buffer list:
2844  * Usually, buffers are allocated and freed like a stack, such that the currently used pointer is
2845  * most likely at the end of the buffer list.
2846  */
2847  bufnum = buffer->firstfree - 1;
2848  while ( bufnum > 0 && buffer->data[bufnum] != ptr )
2849  --bufnum;
2850 
2851  newptr = ptr;
2852  assert( buffer->data[bufnum] == newptr );
2853  assert( buffer->used[bufnum] );
2854  assert( buffer->size[bufnum] >= 1 );
2855 
2856  /* check if the buffer has to be enlarged */
2857  if ( size > buffer->size[bufnum] )
2858  {
2859  size_t newsize;
2860 
2861  /* enlarge buffer */
2862  newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, size);
2863  BMSreallocMemorySize(&buffer->data[bufnum], newsize);
2864  assert( newsize > buffer->size[bufnum] );
2865  buffer->totalmem += newsize - buffer->size[bufnum];
2866  buffer->size[bufnum] = newsize;
2867  if ( buffer->data[bufnum] == NULL )
2868  {
2869  printErrorHeader(filename, line);
2870  printError("Insufficient memory for reallocating buffer storage.\n");
2871  return NULL;
2872  }
2873  newptr = buffer->data[bufnum];
2874  }
2875  assert( buffer->size[bufnum] >= size );
2876  assert( newptr == buffer->data[bufnum] );
2877 
2878  debugMessage("Reallocated buffer %llu/%llu at %p to size %llu (required size: %llu) for pointer %p.\n",
2879  (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum],
2880  (unsigned long long)(buffer->size[bufnum]), (unsigned long long)size, newptr);
2881 
2882 #else
2883  newptr = ptr;
2884  BMSreallocMemorySize(&newptr, size);
2885 #endif
2886 
2887  return newptr;
2888 }
2889 
2890 /** reallocates the buffer to at least the given size */
2892  BMS_BUFMEM* buffer, /**< memory buffer storage */
2893  void* ptr, /**< pointer to the allocated memory buffer */
2894  size_t size, /**< minimal required size of the buffer */
2895  const char* filename, /**< source file of the function call */
2896  int line /**< line number in source file of the function call */
2897  )
2898 {
2899 #ifndef NDEBUG
2900  if ( size > MAXMEMSIZE )
2901  {
2902  printErrorHeader(filename, line);
2903  printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE);
2904  return NULL;
2905  }
2906 #endif
2907 
2908  return BMSreallocBufferMemory_work(buffer, ptr, size, filename, line);
2909 }
2910 
2911 /** reallocates an array in the buffer to at least the given size */
2913  BMS_BUFMEM* buffer, /**< memory buffer storage */
2914  void* ptr, /**< pointer to the allocated memory buffer */
2915  size_t num, /**< size of array to be allocated */
2916  size_t typesize, /**< size of components */
2917  const char* filename, /**< source file of the function call */
2918  int line /**< line number in source file of the function call */
2919  )
2920 {
2921 #ifndef NDEBUG
2922  if ( num > (MAXMEMSIZE / typesize) )
2923  {
2924  printErrorHeader(filename, line);
2925  printError("Tried to allocate array of size exceeding %lu.\n", MAXMEMSIZE);
2926  return NULL;
2927  }
2928 #endif
2929 
2930  return BMSreallocBufferMemory_work(buffer, ptr, num * typesize, filename, line);
2931 }
2932 
2933 /** allocates the next unused buffer and copies the given memory into the buffer */
2935  BMS_BUFMEM* buffer, /**< memory buffer storage */
2936  const void* source, /**< memory block to copy into the buffer */
2937  size_t size, /**< minimal required size of the buffer */
2938  const char* filename, /**< source file of the function call */
2939  int line /**< line number in source file of the function call */
2940  )
2941 {
2942  void* ptr;
2943 
2944  assert( source != NULL );
2945 
2946  /* allocate a buffer of the given size */
2947  ptr = BMSallocBufferMemory_call(buffer, size, filename, line);
2948 
2949  /* copy the source memory into the buffer */
2950  if ( ptr != NULL )
2951  BMScopyMemorySize(ptr, source, size);
2952 
2953  return ptr;
2954 }
2955 
2956 /** allocates an array in the next unused buffer and copies the given memory into the buffer */
2958  BMS_BUFMEM* buffer, /**< memory buffer storage */
2959  const void* source, /**< memory block to copy into the buffer */
2960  size_t num, /**< size of array to be allocated */
2961  size_t typesize, /**< size of components */
2962  const char* filename, /**< source file of the function call */
2963  int line /**< line number in source file of the function call */
2964  )
2965 {
2966  void* ptr;
2967 
2968  assert( source != NULL );
2969 
2970  /* allocate a buffer of the given size */
2971  ptr = BMSallocBufferMemoryArray_call(buffer, num, typesize, filename, line);
2972 
2973  /* copy the source memory into the buffer */
2974  if ( ptr != NULL )
2975  BMScopyMemorySize(ptr, source, num * typesize);
2976 
2977  return ptr;
2978 }
2979 
2980 /** work for freeing a buffer */
2981 INLINE static
2983  BMS_BUFMEM* buffer, /**< memory buffer storage */
2984  void** ptr, /**< pointer to pointer to the allocated memory buffer */
2985  const char* filename, /**< source file of the function call */
2986  int line /**< line number in source file of the function call */
2987  )
2988 { /*lint --e{715}*/
2989  size_t bufnum;
2990 
2991  assert( buffer != NULL );
2992  assert( buffer->firstfree <= buffer->ndata );
2993  assert( buffer->firstfree >= 1 );
2994  assert( ptr != NULL );
2995  assert( *ptr != NULL );
2996 
2997  /* Search the pointer in the buffer list:
2998  * Usually, buffers are allocated and freed like a stack, such that the freed pointer is
2999  * most likely at the end of the buffer list.
3000  */
3001  bufnum = buffer->firstfree-1;
3002  while ( bufnum > 0 && buffer->data[bufnum] != *ptr )
3003  --bufnum;
3004 
3005 #ifdef CHECKBUFFERORDER
3006  if ( bufnum < buffer->firstfree - 1 )
3007  {
3008  warningMessage("[%s:%d]: freeing buffer in wrong order.\n", filename, line);
3009  }
3010 #endif
3011 
3012 #ifndef NDEBUG
3013  if ( bufnum == 0 && buffer->data[bufnum] != *ptr )
3014  {
3015  printErrorHeader(filename, line);
3016  printError("Tried to free unkown buffer pointer.\n");
3017  return;
3018  }
3019  if ( ! buffer->used[bufnum] )
3020  {
3021  printErrorHeader(filename, line);
3022  printError("Tried to free buffer pointer already freed.\n");
3023  return;
3024  }
3025 #endif
3026 
3027 #ifdef CHECKCLEANBUFFER
3028  /* check that the memory is cleared */
3029  if( buffer->clean )
3030  {
3031  size_t i;
3032  uint8_t* tmpptr = (uint8_t*)(buffer->data[bufnum]);
3033 
3034  for( i = 0; i < buffer->size[bufnum]; ++i )
3035  assert(tmpptr[i] == 0);
3036  }
3037 #endif
3038 
3039  assert( buffer->data[bufnum] == *ptr );
3040  buffer->used[bufnum] = FALSE;
3041 
3042  while ( buffer->firstfree > 0 && !buffer->used[buffer->firstfree-1] )
3043  --buffer->firstfree;
3044 
3045  debugMessage("Freed buffer %llu/%llu at %p of size %llu for pointer %p, first free is %llu.\n",
3046  (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum],
3047  (unsigned long long)(buffer->size[bufnum]), *ptr, (unsigned long long)(buffer->firstfree));
3048 
3049  *ptr = NULL;
3050 }
3051 
3052 /** frees a buffer and sets pointer to NULL */
3054  BMS_BUFMEM* buffer, /**< memory buffer storage */
3055  void** ptr, /**< pointer to pointer to the allocated memory buffer */
3056  const char* filename, /**< source file of the function call */
3057  int line /**< line number in source file of the function call */
3058  )
3059 { /*lint --e{715}*/
3060  assert( ptr != NULL );
3061 
3062 #ifndef SCIP_NOBUFFERMEM
3063  if ( *ptr != NULL )
3064  BMSfreeBufferMemory_work(buffer, ptr, filename, line);
3065  else
3066  {
3067  printErrorHeader(filename, line);
3068  printError("Tried to free null buffer pointer.\n");
3069  }
3070 #else
3071  BMSfreeMemory(ptr);
3072 #endif
3073 }
3074 
3075 /** frees a buffer if pointer is not NULL and sets pointer to NULL */
3077  BMS_BUFMEM* buffer, /**< memory buffer storage */
3078  void** ptr, /**< pointer to pointer to the allocated memory buffer */
3079  const char* filename, /**< source file of the function call */
3080  int line /**< line number in source file of the function call */
3081  )
3082 { /*lint --e{715}*/
3083  assert( ptr != NULL );
3084 
3085  if ( *ptr != NULL )
3086  {
3087 #ifndef SCIP_NOBUFFERMEM
3088  BMSfreeBufferMemory_work(buffer, ptr, filename, line);
3089 #else
3090  BMSfreeMemory(ptr);
3091 #endif
3092  }
3093 }
3094 
3095 /** gets number of used buffers */
3097  BMS_BUFMEM* buffer /**< memory buffer storage */
3098  )
3099 {
3100  assert( buffer != NULL );
3101 
3102  return buffer->firstfree;
3103 }
3104 
3105 /** returns the number of allocated bytes in the buffer memory */
3107  const BMS_BUFMEM* buffer /**< buffer memory */
3108  )
3109 {
3110 #ifdef CHECKMEM
3111  size_t totalmem = 0UL;
3112  size_t i;
3113 
3114  assert( buffer != NULL );
3115  for (i = 0; i < buffer->ndata; ++i)
3116  totalmem += buffer->size[i];
3117  assert( totalmem == buffer->totalmem );
3118 #endif
3119 
3120  return (long long) buffer->totalmem;
3121 }
3122 
3123 /** outputs statistics about currently allocated buffers to the screen */
3125  BMS_BUFMEM* buffer /**< memory buffer storage */
3126  )
3127 {
3128  size_t totalmem;
3129  size_t i;
3130 
3131  assert( buffer != NULL );
3132 
3133  totalmem = 0UL;
3134  for (i = 0; i < buffer->ndata; ++i)
3135  {
3136  printf("[%c] %8llu bytes at %p\n", buffer->used[i] ? '*' : ' ', (unsigned long long)(buffer->size[i]), buffer->data[i]);
3137  totalmem += buffer->size[i];
3138  }
3139  printf(" %8llu bytes total in %llu buffers\n", (unsigned long long)totalmem, (unsigned long long)(buffer->ndata));
3140 }
void BMSdestroyBlockMemory_call(BMS_BLKMEM **blkmem, const char *filename, int line)
Definition: memory.c:1796
long long BMSgetMemoryUsed_call(void)
Definition: memory.c:333
#define ALIGNMENT
Definition: memory.c:690
void * BMSallocChunkMemory_call(BMS_CHKMEM *chkmem, size_t size, const char *filename, int line)
Definition: memory.c:1518
#define BMScopyMemorySize(ptr, source, size)
Definition: memory.h:127
struct BMS_ChkMem BMS_CHKMEM
Definition: memory.h:294
int BMSisAligned(size_t size)
Definition: memory.c:770
static INLINE void BMSfreeBlockMemory_work(BMS_BLKMEM *blkmem, void **ptr, size_t size, const char *filename, int line)
Definition: memory.c:2062
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:140
#define SCIP_RBTREE_HOOKS
Definition: rbtree.h:53
static void freeChunk(CHUNK **chunk, long long *memsize)
Definition: memory.c:1122
void * BMSduplicateMemoryArray_call(const void *source, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:593
void BMSdisplayBlockMemory_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2267
void * BMSallocBlockMemoryArray_call(BMS_BLKMEM *blkmem, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:1902
#define checkChunk(chunk)
Definition: memory.c:918
static void freeChkmemElement(BMS_CHKMEM *chkmem, void *ptr, long long *memsize, const char *filename, int line)
Definition: memory.c:1419
double arraygrowfac
Definition: memory.c:2479
void BMSfreeBufferMemoryNull_call(BMS_BUFMEM *buffer, void **ptr, const char *filename, int line)
Definition: memory.c:3076
void * BMSduplicateBufferMemoryArray_call(BMS_BUFMEM *buffer, const void *source, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:2957
#define checkBlkmem(blkmem)
Definition: memory.c:1684
void * BMSallocBufferMemoryArray_call(BMS_BUFMEM *buffer, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:2779
#define INLINE
Definition: def.h:109
size_t * size
Definition: memory.c:2473
#define STORESIZE_MAX
Definition: memory.c:688
void * BMSduplicateChunkMemory_call(BMS_CHKMEM *chkmem, const void *source, size_t size, const char *filename, int line)
Definition: memory.c:1545
void * BMSallocClearBlockMemoryArray_call(BMS_BLKMEM *blkmem, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:1923
#define FALSE
Definition: def.h:73
void BMSdestroyChunkMemory_call(BMS_CHKMEM **chkmem, const char *filename, int line)
Definition: memory.c:1498
#define TRUE
Definition: def.h:72
void * BMSallocBlockMemory_call(BMS_BLKMEM *blkmem, size_t size, const char *filename, int line)
Definition: memory.c:1882
struct Chunk CHUNK
Definition: memory.c:693
size_t BMSgetBlockPointerSize_call(const BMS_BLKMEM *blkmem, const void *ptr)
Definition: memory.c:2247
long long BMScheckEmptyBlockMemory_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2391
#define debugMessage
Definition: memory.c:79
void BMSfreeChunkMemory_call(BMS_CHKMEM *chkmem, void **ptr, size_t size, const char *filename, int line)
Definition: memory.c:1567
#define CHKHASH_SIZE
Definition: memory.c:659
unsigned int * used
Definition: memory.c:2474
static void * allocChunkElement(CHUNK *chunk)
Definition: memory.c:1154
static void * allocChkmemElement(BMS_CHKMEM *chkmem, long long *memsize)
Definition: memory.c:1311
#define GARBAGE_SIZE
Definition: memory.c:689
static SCIP_DEF_RBTREE_FIND(rbTreeFindChunk, const void *, CHUNK, CHUNK_LT, CHUNK_GT)
Definition: memory.c:745
#define SCIPrbtreeDelete(root, node)
Definition: rbtree.h:60
static void unlinkEagerChunk(CHUNK *chunk)
Definition: memory.c:1003
#define CHKHASH_POWER
Definition: memory.c:658
void * BMSreallocBlockMemoryArray_call(BMS_BLKMEM *blkmem, void *ptr, size_t oldnum, size_t newnum, size_t typesize, const char *filename, int line)
Definition: memory.c:1981
#define FOR_EACH_NODE(type, n, r, body)
Definition: rbtree.h:68
void * BMSreallocBlockMemory_call(BMS_BLKMEM *blkmem, void *ptr, size_t oldsize, size_t newsize, const char *filename, int line)
Definition: memory.c:1941
#define BMSfreeMemory(ptr)
Definition: memory.h:137
void ** data
Definition: memory.c:2472
size_t totalmem
Definition: memory.c:2475
static BMS_CHKMEM * findChkmem(const BMS_BLKMEM *blkmem, const void *ptr)
Definition: memory.c:1694
static int linkChunk(BMS_CHKMEM *chkmem, CHUNK *chunk)
Definition: memory.c:927
void * BMSallocClearBufferMemoryArray_call(BMS_BUFMEM *buffer, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:2800
#define CHUNKLENGTH_MIN
Definition: memory.c:686
long long BMSgetBufferMemoryUsed(const BMS_BUFMEM *buffer)
Definition: memory.c:3106
void BMSsetBufferMemoryArraygrowinit(BMS_BUFMEM *buffer, int arraygrowinit)
Definition: memory.c:2566
long long BMSgetBlockMemoryUsedMax_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2217
struct Freelist FREELIST
Definition: memory.c:692
void * BMSreallocMemoryArray_call(void *ptr, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:490
static void clearChkmem(BMS_CHKMEM *chkmem, long long *memsize)
Definition: memory.c:1264
static INLINE void * BMSallocBufferMemory_work(BMS_BUFMEM *buffer, size_t size, const char *filename, int line)
Definition: memory.c:2625
size_t firstfree
Definition: memory.c:2478
static INLINE void BMSfreeBufferMemory_work(BMS_BUFMEM *buffer, void **ptr, const char *filename, int line)
Definition: memory.c:2982
#define LONGINT_FORMAT
Definition: memory.c:110
long long BMSgetBlockMemoryAllocated_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2187
static void destroyChunk(CHUNK **chunk, long long *memsize)
Definition: memory.c:1103
void * BMSallocBufferMemory_call(BMS_BUFMEM *buffer, size_t size, const char *filename, int line)
Definition: memory.c:2759
static void unlinkChunk(CHUNK *chunk)
Definition: memory.c:955
#define NULL
Definition: lpi_spx1.cpp:155
#define addMemlistEntry(ptr, size, filename, line)
Definition: memory.c:301
static INLINE void * BMSallocBlockMemory_work(BMS_BLKMEM *blkmem, size_t size, const char *filename, int line)
Definition: memory.c:1819
void BMSgarbagecollectBlockMemory_call(BMS_BLKMEM *blkmem)
Definition: memory.c:2153
void * BMSduplicateMemory_call(const void *source, size_t size, const char *filename, int line)
Definition: memory.c:574
long long BMSgetBlockMemoryUsed_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2197
void * BMSallocMemoryArray_call(size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:416
long long BMSgetBlockMemoryAllocatedMax_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2237
static int isPtrInChunk(const CHUNK *chunk, const void *ptr)
Definition: memory.c:781
void BMSdestroyBufferMemory_call(BMS_BUFMEM **buffer, const char *filename, int line)
Definition: memory.c:2521
void * BMSduplicateBlockMemoryArray_call(BMS_BLKMEM *blkmem, const void *source, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:2040
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:135
static int isPtrInChkmem(const BMS_CHKMEM *chkmem, const void *ptr)
Definition: memory.c:817
void BMSgarbagecollectChunkMemory_call(BMS_CHKMEM *chkmem)
Definition: memory.c:1620
#define checkChkmem(chkmem)
Definition: memory.c:919
void BMSsetBufferMemoryArraygrowfac(BMS_BUFMEM *buffer, double arraygrowfac)
Definition: memory.c:2554
#define CHUNKLENGTH_MAX
Definition: memory.c:687
void BMSclearMemory_call(void *ptr, size_t size)
Definition: memory.c:529
long long BMSgetChunkMemoryUsed_call(const BMS_CHKMEM *chkmem)
Definition: memory.c:1630
#define MAX(x, y)
Definition: tclique_def.h:83
static void freeChunkElement(CHUNK *chunk, void *ptr)
Definition: memory.c:1191
void BMSdisplayMemory_call(void)
Definition: memory.c:318
#define printInfo
Definition: memory.c:91
void BMSfreeMemory_call(void **ptr, const char *filename, int line)
Definition: memory.c:613
static int getHashNumber(int size)
Definition: memory.c:1717
#define CHUNK_LT(ptr, chunk)
Definition: memory.c:741
void BMScopyMemory_call(void *ptr, const void *source, size_t size)
Definition: memory.c:542
unsigned int arraygrowinit
Definition: memory.c:2480
BMS_BUFMEM * BMScreateBufferMemory_call(double arraygrowfac, int arraygrowinit, unsigned int clean, const char *filename, int line)
Definition: memory.c:2485
void BMSfreeBufferMemory_call(BMS_BUFMEM *buffer, void **ptr, const char *filename, int line)
Definition: memory.c:3053
void BMSfreeBlockMemory_call(BMS_BLKMEM *blkmem, void **ptr, size_t size, const char *filename, int line)
Definition: memory.c:2110
static void garbagecollectChkmem(BMS_CHKMEM *chkmem, long long *memsize)
Definition: memory.c:1351
BMS_BLKMEM * BMScreateBlockMemory_call(int initchunksize, int garbagefactor, const char *filename, int line)
Definition: memory.c:1728
static void linkEagerChunk(BMS_CHKMEM *chkmem, CHUNK *chunk)
Definition: memory.c:982
void BMSmoveMemory_call(void *ptr, const void *source, size_t size)
Definition: memory.c:559
#define errorMessage
Definition: memory.c:80
void * BMSreallocBufferMemoryArray_call(BMS_BUFMEM *buffer, void *ptr, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:2912
#define BMSclearMemorySize(ptr, size)
Definition: memory.h:123
void BMSprintBufferMemory(BMS_BUFMEM *buffer)
Definition: memory.c:3124
void * BMSduplicateBlockMemory_call(BMS_BLKMEM *blkmem, const void *source, size_t size, const char *filename, int line)
Definition: memory.c:2020
static void destroyChkmem(BMS_CHKMEM **chkmem, long long *memsize)
Definition: memory.c:1289
long long BMSgetBlockMemoryUnused_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2207
void * BMSallocClearMemory_call(size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:343
void BMScheckEmptyMemory_call(void)
Definition: memory.c:326
void BMSclearChunkMemory_call(BMS_CHKMEM *chkmem, const char *filename, int line)
Definition: memory.c:1480
size_t BMSgetNUsedBufferMemory(BMS_BUFMEM *buffer)
Definition: memory.c:3096
size_t BMSgetPointerSize_call(const void *ptr)
Definition: memory.c:309
void * BMSreallocMemory_call(void *ptr, size_t size, const char *filename, int line)
Definition: memory.c:454
void * BMSduplicateBufferMemory_call(BMS_BUFMEM *buffer, const void *source, size_t size, const char *filename, int line)
Definition: memory.c:2934
#define BMSallocMemorySize(ptr, size)
Definition: memory.h:112
public methods for message output
#define BMSreallocMemorySize(ptr, size)
Definition: memory.h:118
#define removeMemlistEntry(ptr, filename, line)
Definition: memory.c:302
static int createChunk(BMS_CHKMEM *chkmem, long long *memsize)
Definition: memory.c:1028
void * BMSallocMemory_call(size_t size, const char *filename, int line)
Definition: memory.c:382
#define SCIPrbtreeInsert(r, p, c, n)
Definition: rbtree.h:61
#define printError
Definition: pub_message.h:60
#define SCIP_Real
Definition: def.h:163
void BMSfreeBlockMemoryNull_call(BMS_BLKMEM *blkmem, void **ptr, size_t size, const char *filename, int line)
Definition: memory.c:2132
#define BMSallocClearMemorySize(ptr, size)
Definition: memory.h:114
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:119
static CHUNK * findChunk(const BMS_CHKMEM *chkmem, const void *ptr)
Definition: memory.c:798
static INLINE void * BMSreallocBufferMemory_work(BMS_BUFMEM *buffer, void *ptr, size_t size, const char *filename, int line)
Definition: memory.c:2819
#define MAXMEMSIZE
Definition: memory.c:117
intrusive red black tree datastructure
BMS_CHKMEM * BMScreateChunkMemory_call(size_t size, int initchunksize, int garbagefactor, const char *filename, int line)
Definition: memory.c:1456
void BMSfreeMemoryNull_call(void **ptr, const char *filename, int line)
Definition: memory.c:635
long long BMSgetBlockMemoryUnusedMax_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2227
static BMS_CHKMEM * createChkmem(int size, int initchunksize, int garbagefactor, long long *memsize)
Definition: memory.c:1220
void BMSfreeChunkMemoryNull_call(BMS_CHKMEM *chkmem, void **ptr, size_t size, const char *filename, int line)
Definition: memory.c:1596
static size_t calcMemoryGrowSize(size_t initsize, SCIP_Real growfac, size_t num)
Definition: memory.c:2583
common defines and data types used in all packages of SCIP
#define CHUNK_GT(ptr, chunk)
Definition: memory.c:742
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:429
unsigned int clean
Definition: memory.c:2476
void * BMSreallocBufferMemory_call(BMS_BUFMEM *buffer, void *ptr, size_t size, const char *filename, int line)
Definition: memory.c:2891
void BMSclearBlockMemory_call(BMS_BLKMEM *blkmem, const char *filename, int line)
Definition: memory.c:1762
size_t ndata
Definition: memory.c:2477
void BMSalignMemsize(size_t *size)
Definition: memory.c:761
#define printErrorHeader
Definition: pub_message.h:59
memory allocation routines