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 #ifndef SCIP_THREADSAFE
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 memory in the block memory pool and clears it */
1903  BMS_BLKMEM* blkmem, /**< block memory */
1904  size_t size, /**< size of memory element to allocate */
1905  const char* filename, /**< source file of the function call */
1906  int line /**< line number in source file of the function call */
1907  )
1908 {
1909  void* ptr;
1910 
1911  ptr = BMSallocBlockMemory_call(blkmem, size, filename, line);
1912  if( ptr != NULL )
1913  BMSclearMemorySize(ptr, size);
1914 
1915  return ptr;
1916 }
1917 
1918 /** allocates array in the block memory pool */
1920  BMS_BLKMEM* blkmem, /**< block memory */
1921  size_t num, /**< size of array to be allocated */
1922  size_t typesize, /**< size of each component */
1923  const char* filename, /**< source file of the function call */
1924  int line /**< line number in source file of the function call */
1925  )
1926 {
1927 #ifndef NDEBUG
1928  if ( num > (MAXMEMSIZE / typesize) )
1929  {
1930  printErrorHeader(filename, line);
1931  printError("Tried to allocate block of size exceeding %lu.\n", MAXMEMSIZE);
1932  return NULL;
1933  }
1934 #endif
1935 
1936  return BMSallocBlockMemory_work(blkmem, num * typesize, filename, line);
1937 }
1938 
1939 /** allocates array in the block memory pool and clears it */
1941  BMS_BLKMEM* blkmem, /**< block memory */
1942  size_t num, /**< size of array to be allocated */
1943  size_t typesize, /**< size of each component */
1944  const char* filename, /**< source file of the function call */
1945  int line /**< line number in source file of the function call */
1946  )
1947 {
1948  void* ptr;
1949 
1950  ptr = BMSallocBlockMemoryArray_call(blkmem, num, typesize, filename, line);
1951  if ( ptr != NULL )
1952  BMSclearMemorySize(ptr, num * typesize);
1953 
1954  return ptr;
1955 }
1956 
1957 /** resizes memory element in the block memory pool and copies the data */
1959  BMS_BLKMEM* blkmem, /**< block memory */
1960  void* ptr, /**< memory element to reallocated */
1961  size_t oldsize, /**< old size of memory element */
1962  size_t newsize, /**< new size of memory element */
1963  const char* filename, /**< source file of the function call */
1964  int line /**< line number in source file of the function call */
1965  )
1966 {
1967  void* newptr;
1968 
1969  if( ptr == NULL )
1970  {
1971  assert(oldsize == 0);
1972  return BMSallocBlockMemory_call(blkmem, newsize, filename, line);
1973  }
1974 
1975 #ifndef NDEBUG
1976  if ( newsize > MAXMEMSIZE )
1977  {
1978  printErrorHeader(filename, line);
1979  printError("Tried to allocate block of size exceeding %lu.\n", MAXMEMSIZE);
1980  return NULL;
1981  }
1982 #endif
1983 
1984  alignSize(&oldsize);
1985  alignSize(&newsize);
1986  if( oldsize == newsize )
1987  return ptr;
1988 
1989  newptr = BMSallocBlockMemory_call(blkmem, newsize, filename, line);
1990  if( newptr != NULL )
1991  BMScopyMemorySize(newptr, ptr, MIN(oldsize, newsize));
1992  BMSfreeBlockMemory_call(blkmem, &ptr, oldsize, filename, line);
1993 
1994  return newptr;
1995 }
1996 
1997 /** resizes array in the block memory pool and copies the data */
1999  BMS_BLKMEM* blkmem, /**< block memory */
2000  void* ptr, /**< memory element to reallocated */
2001  size_t oldnum, /**< old size of array */
2002  size_t newnum, /**< new size of array */
2003  size_t typesize, /**< size of each component */
2004  const char* filename, /**< source file of the function call */
2005  int line /**< line number in source file of the function call */
2006  )
2007 {
2008  void* newptr;
2009 
2010  if( ptr == NULL )
2011  {
2012  assert(oldnum == 0);
2013  return BMSallocBlockMemoryArray_call(blkmem, newnum, typesize, filename, line);
2014  }
2015 
2016 #ifndef NDEBUG
2017  if ( newnum > (MAXMEMSIZE / typesize) )
2018  {
2019  printErrorHeader(filename, line);
2020  printError("Tried to allocate array of size exceeding %lu.\n", MAXMEMSIZE);
2021  return NULL;
2022  }
2023 #endif
2024 
2025  if ( oldnum == newnum )
2026  return ptr;
2027 
2028  newptr = BMSallocBlockMemoryArray_call(blkmem, newnum, typesize, filename, line);
2029  if ( newptr != NULL )
2030  BMScopyMemorySize(newptr, ptr, MIN(oldnum, newnum) * typesize);
2031  BMSfreeBlockMemory_call(blkmem, &ptr, oldnum * typesize, filename, line);
2032 
2033  return newptr;
2034 }
2035 
2036 /** duplicates memory element in the block memory pool and copies the data */
2038  BMS_BLKMEM* blkmem, /**< block memory */
2039  const void* source, /**< memory element to duplicate */
2040  size_t size, /**< size of memory elements */
2041  const char* filename, /**< source file of the function call */
2042  int line /**< line number in source file of the function call */
2043  )
2044 {
2045  void* ptr;
2046 
2047  assert(source != NULL);
2048 
2049  ptr = BMSallocBlockMemory_call(blkmem, size, filename, line);
2050  if( ptr != NULL )
2051  BMScopyMemorySize(ptr, source, size);
2052 
2053  return ptr;
2054 }
2055 
2056 /** duplicates array in the block memory pool and copies the data */
2058  BMS_BLKMEM* blkmem, /**< block memory */
2059  const void* source, /**< memory element to duplicate */
2060  size_t num, /**< size of array to be duplicated */
2061  size_t typesize, /**< size of each component */
2062  const char* filename, /**< source file of the function call */
2063  int line /**< line number in source file of the function call */
2064  )
2065 {
2066  void* ptr;
2067 
2068  assert(source != NULL);
2069 
2070  ptr = BMSallocBlockMemoryArray_call(blkmem, num, typesize, filename, line);
2071  if( ptr != NULL )
2072  BMScopyMemorySize(ptr, source, num * typesize);
2073 
2074  return ptr;
2075 }
2076 
2077 /** common work for freeing block memory */
2078 INLINE static
2080  BMS_BLKMEM* blkmem, /**< block memory */
2081  void** ptr, /**< pointer to pointer to memory element to free */
2082  size_t size, /**< size of memory element */
2083  const char* filename, /**< source file of the function call */
2084  int line /**< line number in source file of the function call */
2085  )
2086 {
2087  BMS_CHKMEM* chkmem;
2088  int hashnumber;
2089 
2090  assert(ptr != NULL);
2091  assert(*ptr != NULL);
2092 
2093  /* calculate hash number of given size */
2094  alignSize(&size);
2095  hashnumber = getHashNumber((int)size);
2096 
2097  debugMessage("free %8llu bytes in %p [%s:%d]\n", (unsigned long long)size, *ptr, filename, line);
2098 
2099  /* find correspoding chunk block */
2100  assert( blkmem->chkmemhash != NULL );
2101  chkmem = blkmem->chkmemhash[hashnumber];
2102  while( chkmem != NULL && chkmem->elemsize != (int)size )
2103  chkmem = chkmem->nextchkmem;
2104  if( chkmem == NULL )
2105  {
2106  printErrorHeader(filename, line);
2107  printError("Tried to free pointer <%p> in block memory <%p> of unknown size %llu.\n", *ptr, (void*)blkmem, (unsigned long long)size);
2108  return;
2109  }
2110  assert(chkmem->elemsize == (int)size);
2111 
2112  /* free memory in chunk block */
2113  freeChkmemElement(chkmem, *ptr, &blkmem->memallocated, filename, line);
2114  blkmem->memused -= (long long) size;
2115 
2116  blkmem->maxmemunused = MAX(blkmem->maxmemunused, blkmem->memallocated - blkmem->memused);
2117 
2118  assert(blkmem->memused >= 0);
2119  assert(blkmem->memallocated >= 0);
2120 
2121  checkBlkmem(blkmem);
2122 
2123  *ptr = NULL;
2124 }
2125 
2126 /** frees memory element in the block memory pool and sets pointer to NULL */
2128  BMS_BLKMEM* blkmem, /**< block memory */
2129  void** ptr, /**< pointer to pointer to memory element to free */
2130  size_t size, /**< size of memory element */
2131  const char* filename, /**< source file of the function call */
2132  int line /**< line number in source file of the function call */
2133  )
2134 {
2135  assert( blkmem != NULL );
2136  assert( ptr != NULL );
2137 
2138  if( *ptr != NULL )
2139  BMSfreeBlockMemory_work(blkmem, ptr, size, filename, line);
2140  else if( size != 0 )
2141  {
2142  printErrorHeader(filename, line);
2143  printError("Tried to free null block pointer.\n");
2144  }
2145  checkBlkmem(blkmem);
2146 }
2147 
2148 /** frees memory element in the block memory pool if pointer is not NULL and sets pointer to NULL */
2150  BMS_BLKMEM* blkmem, /**< block memory */
2151  void** ptr, /**< pointer to pointer to memory element to free */
2152  size_t size, /**< size of memory element */
2153  const char* filename, /**< source file of the function call */
2154  int line /**< line number in source file of the function call */
2155  )
2156 {
2157  assert( blkmem != NULL );
2158  assert( ptr != NULL );
2159 
2160  if( *ptr != NULL )
2161  {
2162  BMSfreeBlockMemory_work(blkmem, ptr, size, filename, line);
2163  }
2164  checkBlkmem(blkmem);
2165 }
2166 
2167 /** calls garbage collection of block memory, frees chunks without allocated memory elements, and frees
2168  * chunk blocks without any chunks
2169  */
2171  BMS_BLKMEM* blkmem /**< block memory */
2172  )
2173 {
2174  int i;
2175 
2176  assert(blkmem != NULL);
2177 
2178  for( i = 0; i < CHKHASH_SIZE; ++i )
2179  {
2180  BMS_CHKMEM** chkmemptr;
2181 
2182  chkmemptr = &blkmem->chkmemhash[i];
2183  while( *chkmemptr != NULL )
2184  {
2185  garbagecollectChkmem(*chkmemptr, &blkmem->memallocated);
2186  checkBlkmem(blkmem);
2187  if( (*chkmemptr)->nchunks == 0 )
2188  {
2189  BMS_CHKMEM* nextchkmem;
2190 
2191  assert((*chkmemptr)->lazyfreesize == 0);
2192  nextchkmem = (*chkmemptr)->nextchkmem;
2193  destroyChkmem(chkmemptr, &blkmem->memallocated);
2194  *chkmemptr = nextchkmem;
2195  checkBlkmem(blkmem);
2196  }
2197  else
2198  chkmemptr = &(*chkmemptr)->nextchkmem;
2199  }
2200  }
2201 }
2202 
2203 /** returns the number of allocated bytes in the block memory */
2205  const BMS_BLKMEM* blkmem /**< block memory */
2206  )
2207 {
2208  assert( blkmem != NULL );
2209 
2210  return blkmem->memallocated;
2211 }
2212 
2213 /** returns the number of used bytes in the block memory */
2215  const BMS_BLKMEM* blkmem /**< block memory */
2216  )
2217 {
2218  assert( blkmem != NULL );
2219 
2220  return blkmem->memused;
2221 }
2222 
2223 /** returns the number of allocated but not used bytes in the block memory */
2225  const BMS_BLKMEM* blkmem /**< block memory */
2226  )
2227 {
2228  assert( blkmem != NULL );
2229 
2230  return blkmem->memallocated - blkmem->memused;
2231 }
2232 
2233 /** returns the maximal number of used bytes in the block memory */
2235  const BMS_BLKMEM* blkmem /**< block memory */
2236  )
2237 {
2238  assert( blkmem != NULL );
2239 
2240  return blkmem->maxmemused;
2241 }
2242 
2243 /** returns the maximal number of allocated but not used bytes in the block memory */
2245  const BMS_BLKMEM* blkmem /**< block memory */
2246  )
2247 {
2248  assert( blkmem != NULL );
2249 
2250  return blkmem->maxmemunused;
2251 }
2252 
2253 /** returns the maximal number of allocated bytes in the block memory */
2255  const BMS_BLKMEM* blkmem /**< block memory */
2256  )
2257 {
2258  assert( blkmem != NULL );
2259 
2260  return blkmem->maxmemallocated;
2261 }
2262 
2263 /** returns the size of the given memory element; returns 0, if the element is not member of the block memory */
2265  const BMS_BLKMEM* blkmem, /**< block memory */
2266  const void* ptr /**< memory element */
2267  )
2268 {
2269  const BMS_CHKMEM* chkmem;
2270 
2271  assert(blkmem != NULL);
2272 
2273  if( ptr == NULL )
2274  return 0;
2275 
2276  chkmem = findChkmem(blkmem, ptr);
2277  if( chkmem == NULL )
2278  return 0;
2279 
2280  return (size_t)(chkmem->elemsize); /*lint !e571*/
2281 }
2282 
2283 /** outputs allocation diagnostics of block memory */
2285  const BMS_BLKMEM* blkmem /**< block memory */
2286  )
2287 {
2288  const BMS_CHKMEM* chkmem;
2289  int nblocks = 0;
2290  int nunusedblocks = 0;
2291  int totalnchunks = 0;
2292  int totalneagerchunks = 0;
2293  int totalnelems = 0;
2294  int totalneagerelems = 0;
2295  int totalnlazyelems = 0;
2296 #ifndef NDEBUG
2297  int totalngarbagecalls = 0;
2298  int totalngarbagefrees = 0;
2299 #endif
2300  long long allocedmem = 0;
2301  long long freemem = 0;
2302  int i;
2303 
2304 #ifndef NDEBUG
2305  printInfo(" ElSize #Chunk #Eag #Elems #EagFr #LazFr #GCl #GFr Free MBytes First Allocator\n");
2306 #else
2307  printInfo(" ElSize #Chunk #Eag #Elems #EagFr #LazFr Free MBytes\n");
2308 #endif
2309 
2310  assert(blkmem != NULL);
2311 
2312  for( i = 0; i < CHKHASH_SIZE; ++i )
2313  {
2314  chkmem = blkmem->chkmemhash[i];
2315  while( chkmem != NULL )
2316  {
2317  int nchunks = 0;
2318  int nelems = 0;
2319  int neagerchunks = 0;
2320  int neagerelems = 0;
2321 
2322  FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk,
2323  {
2324  assert(chunk != NULL);
2325  assert(chunk->elemsize == chkmem->elemsize);
2326  assert(chunk->chkmem == chkmem);
2327  nchunks++;
2328  nelems += chunk->storesize;
2329  if( chunk->eagerfree != NULL )
2330  {
2331  neagerchunks++;
2332  neagerelems += chunk->eagerfreesize;
2333  }
2334  })
2335 
2336  assert(nchunks == chkmem->nchunks);
2337  assert(nelems == chkmem->storesize);
2338  assert(neagerelems == chkmem->eagerfreesize);
2339 
2340  if( nelems > 0 )
2341  {
2342  nblocks++;
2343  allocedmem += (long long)chkmem->elemsize * (long long)nelems;
2344  freemem += (long long)chkmem->elemsize * ((long long)neagerelems + (long long)chkmem->lazyfreesize);
2345 
2346 #ifndef NDEBUG
2347  printInfo("%7d %6d %4d %7d %7d %7d %5d %4d %5.1f%% %6.1f %s:%d\n",
2348  chkmem->elemsize, nchunks, neagerchunks, nelems,
2349  neagerelems, chkmem->lazyfreesize, chkmem->ngarbagecalls, chkmem->ngarbagefrees,
2350  100.0 * (double) (neagerelems + chkmem->lazyfreesize) / (double) (nelems),
2351  (double)chkmem->elemsize * nelems / (1024.0*1024.0),
2352  chkmem->filename, chkmem->line);
2353 #else
2354  printInfo("%7d %6d %4d %7d %7d %7d %5.1f%% %6.1f\n",
2355  chkmem->elemsize, nchunks, neagerchunks, nelems,
2356  neagerelems, chkmem->lazyfreesize,
2357  100.0 * (double) (neagerelems + chkmem->lazyfreesize) / (double) (nelems),
2358  (double)chkmem->elemsize * nelems / (1024.0*1024.0));
2359 #endif
2360  }
2361  else
2362  {
2363 #ifndef NDEBUG
2364  printInfo("%7d <unused> %5d %4d %s:%d\n",
2365  chkmem->elemsize, chkmem->ngarbagecalls, chkmem->ngarbagefrees,
2366  chkmem->filename, chkmem->line);
2367 #else
2368  printInfo("%7d <unused>\n", chkmem->elemsize);
2369 #endif
2370  nunusedblocks++;
2371  }
2372  totalnchunks += nchunks;
2373  totalneagerchunks += neagerchunks;
2374  totalnelems += nelems;
2375  totalneagerelems += neagerelems;
2376  totalnlazyelems += chkmem->lazyfreesize;
2377 #ifndef NDEBUG
2378  totalngarbagecalls += chkmem->ngarbagecalls;
2379  totalngarbagefrees += chkmem->ngarbagefrees;
2380 #endif
2381  chkmem = chkmem->nextchkmem;
2382  }
2383  }
2384 #ifndef NDEBUG
2385  printInfo(" Total %6d %4d %7d %7d %7d %5d %4d %5.1f%% %6.1f\n",
2386  totalnchunks, totalneagerchunks, totalnelems, totalneagerelems, totalnlazyelems,
2387  totalngarbagecalls, totalngarbagefrees,
2388  totalnelems > 0 ? 100.0 * (double) (totalneagerelems + totalnlazyelems) / (double) (totalnelems) : 0.0,
2389  (double)allocedmem/(1024.0*1024.0));
2390 #else
2391  printInfo(" Total %6d %4d %7d %7d %7d %5.1f%% %6.1f\n",
2392  totalnchunks, totalneagerchunks, totalnelems, totalneagerelems, totalnlazyelems,
2393  totalnelems > 0 ? 100.0 * (double) (totalneagerelems + totalnlazyelems) / (double) (totalnelems) : 0.0,
2394  (double)allocedmem/(1024.0*1024.0));
2395 #endif
2396  printInfo("%d blocks (%d unused), %" LONGINT_FORMAT " bytes allocated, %" LONGINT_FORMAT " bytes free",
2397  nblocks + nunusedblocks, nunusedblocks, allocedmem, freemem);
2398  if( allocedmem > 0 )
2399  printInfo(" (%.1f%%)", 100.0 * (double) freemem / (double) allocedmem);
2400  printInfo("\n\n");
2401 
2402  printInfo("Memory Peaks: Used Lazy Total\n");
2403  printInfo(" %6.1f %6.1f %6.1f MBytes\n", (double)blkmem->maxmemused / (1024.0 * 1024.0),
2404  (double)blkmem->maxmemunused / (1024.0 * 1024.0), (double)blkmem->maxmemallocated / (1024.0 * 1024.0));
2405 }
2406 
2407 /** outputs error messages, if there are allocated elements in the block memory and returns number of unfreed bytes */
2409  const BMS_BLKMEM* blkmem /**< block memory */
2410  )
2411 {
2412  const BMS_CHKMEM* chkmem;
2413  long long allocedmem = 0;
2414  long long freemem = 0;
2415  int i;
2416 
2417  assert(blkmem != NULL);
2418 
2419  for( i = 0; i < CHKHASH_SIZE; ++i )
2420  {
2421  chkmem = blkmem->chkmemhash[i];
2422  while( chkmem != NULL )
2423  {
2424  int nchunks = 0;
2425  int nelems = 0;
2426  int neagerelems = 0;
2427 
2428  FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk,
2429  {
2430  assert(chunk != NULL);
2431  assert(chunk->elemsize == chkmem->elemsize);
2432  assert(chunk->chkmem == chkmem);
2433  nchunks++;
2434  nelems += chunk->storesize;
2435  if( chunk->eagerfree != NULL )
2436  neagerelems += chunk->eagerfreesize;
2437  })
2438 
2439  assert(nchunks == chkmem->nchunks);
2440  assert(nelems == chkmem->storesize);
2441  assert(neagerelems == chkmem->eagerfreesize);
2442 
2443  if( nelems > 0 )
2444  {
2445  allocedmem += (long long)chkmem->elemsize * (long long)nelems;
2446  freemem += (long long)chkmem->elemsize * ((long long)neagerelems + (long long)chkmem->lazyfreesize);
2447 
2448  if( nelems != neagerelems + chkmem->lazyfreesize )
2449  {
2450 #ifndef NDEBUG
2451  errorMessage("%" LONGINT_FORMAT " bytes (%d elements of size %" LONGINT_FORMAT ") not freed. First Allocator: %s:%d\n",
2452  (((long long)nelems - (long long)neagerelems) - (long long)chkmem->lazyfreesize)
2453  * (long long)(chkmem->elemsize),
2454  (nelems - neagerelems) - chkmem->lazyfreesize, (long long)(chkmem->elemsize),
2455  chkmem->filename, chkmem->line);
2456 #else
2457  errorMessage("%" LONGINT_FORMAT " bytes (%d elements of size %" LONGINT_FORMAT ") not freed.\n",
2458  ((nelems - neagerelems) - chkmem->lazyfreesize) * (long long)(chkmem->elemsize),
2459  (nelems - neagerelems) - chkmem->lazyfreesize, (long long)(chkmem->elemsize));
2460 #endif
2461  }
2462  }
2463  chkmem = chkmem->nextchkmem;
2464  }
2465  }
2466 
2467  if( allocedmem != freemem )
2468  {
2469  errorMessage("%" LONGINT_FORMAT " bytes not freed in total.\n", allocedmem - freemem);
2470  }
2471 
2472  return allocedmem - freemem;
2473 }
2474 
2475 
2476 
2477 
2478 
2479 
2480 /***********************************************************
2481  * Buffer Memory Management
2482  *
2483  * Efficient memory management for temporary objects
2484  ***********************************************************/
2485 
2486 /** memory buffer storage for temporary objects */
2488 {
2489  void** data; /**< allocated memory chunks for arbitrary data */
2490  size_t* size; /**< sizes of buffers in bytes */
2491  unsigned int* used; /**< 1 iff corresponding buffer is in use */
2492  size_t totalmem; /**< total memory consumption of buffer */
2493  unsigned int clean; /**< 1 iff the memory blocks in the buffer should be initialized to zero? */
2494  size_t ndata; /**< number of memory chunks */
2495  size_t firstfree; /**< first unused memory chunk */
2496  double arraygrowfac; /**< memory growing factor for dynamically allocated arrays */
2497  unsigned int arraygrowinit; /**< initial size of dynamically allocated arrays */
2498 };
2499 
2500 
2501 /** creates memory buffer storage */
2503  double arraygrowfac, /**< memory growing factor for dynamically allocated arrays */
2504  int arraygrowinit, /**< initial size of dynamically allocated arrays */
2505  unsigned int clean, /**< should the memory blocks in the buffer be initialized to zero? */
2506  const char* filename, /**< source file of the function call */
2507  int line /**< line number in source file of the function call */
2508  )
2509 {
2510  BMS_BUFMEM* buffer;
2511 
2512  assert( arraygrowinit > 0 );
2513  assert( arraygrowfac > 0.0 );
2514 
2515  BMSallocMemory(&buffer);
2516  if ( buffer != NULL )
2517  {
2518  buffer->data = NULL;
2519  buffer->size = NULL;
2520  buffer->used = NULL;
2521  buffer->totalmem = 0UL;
2522  buffer->clean = clean;
2523  buffer->ndata = 0;
2524  buffer->firstfree = 0;
2525  buffer->arraygrowinit = (unsigned) arraygrowinit;
2526  buffer->arraygrowfac = arraygrowfac;
2527  }
2528  else
2529  {
2530  printErrorHeader(filename, line);
2531  printError("Insufficient memory for buffer memory header.\n");
2532  }
2533 
2534  return buffer;
2535 }
2536 
2537 /** destroys buffer memory */
2539  BMS_BUFMEM** buffer, /**< pointer to memory buffer storage */
2540  const char* filename, /**< source file of the function call */
2541  int line /**< line number in source file of the function call */
2542  )
2543 {
2544  size_t i;
2545 
2546  if ( *buffer != NULL )
2547  {
2548  i = (*buffer)->ndata;
2549  if ( i > 0 ) {
2550  for (--i ; ; i--)
2551  {
2552  assert( ! (*buffer)->used[i] );
2553  BMSfreeMemoryArrayNull(&(*buffer)->data[i]);
2554  if ( i == 0 )
2555  break;
2556  }
2557  }
2558  BMSfreeMemoryArrayNull(&(*buffer)->data);
2559  BMSfreeMemoryArrayNull(&(*buffer)->size);
2560  BMSfreeMemoryArrayNull(&(*buffer)->used);
2561  BMSfreeMemory(buffer);
2562  }
2563  else
2564  {
2565  printErrorHeader(filename, line);
2566  printError("Tried to free null buffer memory.\n");
2567  }
2568 }
2569 
2570 /** set arraygrowfac */
2572  BMS_BUFMEM* buffer, /**< pointer to memory buffer storage */
2573  double arraygrowfac /**< memory growing factor for dynamically allocated arrays */
2574  )
2575 {
2576  assert( buffer != NULL );
2577  assert( arraygrowfac > 0.0 );
2578 
2579  buffer->arraygrowfac = arraygrowfac;
2580 }
2581 
2582 /** set arraygrowinit */
2584  BMS_BUFMEM* buffer, /**< pointer to memory buffer storage */
2585  int arraygrowinit /**< initial size of dynamically allocated arrays */
2586  )
2587 {
2588  assert( buffer != NULL );
2589  assert( arraygrowinit > 0 );
2590 
2591  buffer->arraygrowinit = (unsigned) arraygrowinit;
2592 }
2593 
2594 #ifndef SCIP_NOBUFFERMEM
2595 /** calculate memory size for dynamically allocated arrays
2596  *
2597  * This function is a copy of the function in set.c in order to be able to use memory.? separately.
2598  */
2599 static
2601  size_t initsize, /**< initial size of array */
2602  SCIP_Real growfac, /**< growing factor of array */
2603  size_t num /**< minimum number of entries to store */
2604  )
2605 {
2606  size_t size;
2607 
2608  assert( growfac >= 1.0 );
2609 
2610  if ( growfac == 1.0 )
2611  size = MAX(initsize, num);
2612  else
2613  {
2614  size_t oldsize;
2615 
2616  /* calculate the size with this loop, such that the resulting numbers are always the same */
2617  initsize = MAX(initsize, 4);
2618  size = initsize;
2619  oldsize = size - 1;
2620 
2621  /* second condition checks against overflow */
2622  while ( size < num && size > oldsize )
2623  {
2624  oldsize = size;
2625  size = (size_t)(growfac * size + initsize);
2626  }
2627 
2628  /* if an overflow happened, set the correct value */
2629  if ( size <= oldsize )
2630  size = num;
2631  }
2632 
2633  assert( size >= initsize );
2634  assert( size >= num );
2635 
2636  return size;
2637 }
2638 #endif
2639 
2640 /** work for allocating the next unused buffer */
2641 INLINE static
2643  BMS_BUFMEM* buffer, /**< memory buffer storage */
2644  size_t size, /**< minimal required size of the buffer */
2645  const char* filename, /**< source file of the function call */
2646  int line /**< line number in source file of the function call */
2647  )
2648 {
2649  /* cppcheck-suppress unassignedVariable */
2650  void* ptr;
2651 #ifndef SCIP_NOBUFFERMEM
2652  size_t bufnum;
2653 #endif
2654 
2655 #ifndef SCIP_NOBUFFERMEM
2656  assert( buffer != NULL );
2657  assert( buffer->firstfree <= buffer->ndata );
2658 
2659  /* allocate a minimum of 1 byte */
2660  if ( size == 0 )
2661  size = 1;
2662 
2663  /* check, if we need additional buffers */
2664  if ( buffer->firstfree == buffer->ndata )
2665  {
2666  size_t newsize;
2667  size_t i;
2668 
2669  /* create additional buffers */
2670  newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, buffer->firstfree + 1);
2671  BMSreallocMemoryArray(&buffer->data, newsize);
2672  if ( buffer->data == NULL )
2673  {
2674  printErrorHeader(filename, line);
2675  printError("Insufficient memory for reallocating buffer data storage.\n");
2676  return NULL;
2677  }
2678  BMSreallocMemoryArray(&buffer->size, newsize);
2679  if ( buffer->size == NULL )
2680  {
2681  printErrorHeader(filename, line);
2682  printError("Insufficient memory for reallocating buffer size storage.\n");
2683  return NULL;
2684  }
2685  BMSreallocMemoryArray(&buffer->used, newsize);
2686  if ( buffer->used == NULL )
2687  {
2688  printErrorHeader(filename, line);
2689  printError("Insufficient memory for reallocating buffer used storage.\n");
2690  return NULL;
2691  }
2692 
2693  /* init data */
2694  for (i = buffer->ndata; i < newsize; ++i)
2695  {
2696  buffer->data[i] = NULL;
2697  buffer->size[i] = 0;
2698  buffer->used[i] = FALSE;
2699  }
2700  buffer->ndata = newsize;
2701  }
2702  assert(buffer->firstfree < buffer->ndata);
2703 
2704  /* check, if the current buffer is large enough */
2705  bufnum = buffer->firstfree;
2706  assert( ! buffer->used[bufnum] );
2707  if ( buffer->size[bufnum] < size )
2708  {
2709  size_t newsize;
2710 
2711  /* enlarge buffer */
2712  newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, size);
2713  BMSreallocMemorySize(&buffer->data[bufnum], newsize);
2714 
2715  /* clear new memory */
2716  if( buffer->clean )
2717  {
2718  char* tmpptr = (char*)(buffer->data[bufnum]);
2719  size_t inc = buffer->size[bufnum] / sizeof(*tmpptr);
2720  tmpptr += inc;
2721 
2722  BMSclearMemorySize(tmpptr, newsize - buffer->size[bufnum]);
2723  }
2724  assert( newsize > buffer->size[bufnum] );
2725  buffer->totalmem += newsize - buffer->size[bufnum];
2726  buffer->size[bufnum] = newsize;
2727 
2728  if ( buffer->data[bufnum] == NULL )
2729  {
2730  printErrorHeader(filename, line);
2731  printError("Insufficient memory for reallocating buffer storage.\n");
2732  return NULL;
2733  }
2734  }
2735  assert( buffer->size[bufnum] >= size );
2736 
2737 #ifdef CHECKCLEANBUFFER
2738  /* check that the memory is cleared */
2739  if( buffer->clean )
2740  {
2741  char* tmpptr = (char*)(buffer->data[bufnum]);
2742  unsigned int inc = buffer->size[bufnum] / sizeof(*tmpptr);
2743  tmpptr += inc;
2744 
2745  while( --tmpptr >= (char*)(buffer->data[bufnum]) )
2746  assert(*tmpptr == '\0');
2747  }
2748 #endif
2749 
2750  ptr = buffer->data[bufnum];
2751  buffer->used[bufnum] = TRUE;
2752  buffer->firstfree++;
2753 
2754  debugMessage("Allocated buffer %llu/%llu at %p of size %llu (required size: %llu) for pointer %p.\n",
2755  (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum],
2756  (unsigned long long)(buffer->size[bufnum]), (unsigned long long)size, ptr);
2757 
2758 #else
2759  if( buffer->clean )
2760  {
2761  /* we should allocate at least one byte, otherwise BMSallocMemorySize will fail */
2762  size = MAX(size,1);
2763 
2764  BMSallocClearMemorySize(&ptr, size);
2765  }
2766  else
2767  {
2768  BMSallocMemorySize(&ptr, size);
2769  }
2770 #endif
2771 
2772  return ptr;
2773 }
2774 
2775 /** allocates the next unused buffer */
2777  BMS_BUFMEM* buffer, /**< memory buffer storage */
2778  size_t size, /**< minimal required size of the buffer */
2779  const char* filename, /**< source file of the function call */
2780  int line /**< line number in source file of the function call */
2781  )
2782 {
2783 #ifndef NDEBUG
2784  if ( size > MAXMEMSIZE )
2785  {
2786  printErrorHeader(filename, line);
2787  printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE);
2788  return NULL;
2789  }
2790 #endif
2791 
2792  return BMSallocBufferMemory_work(buffer, size, filename, line);
2793 }
2794 
2795 /** allocates the next unused buffer array */
2797  BMS_BUFMEM* buffer, /**< memory buffer storage */
2798  size_t num, /**< size of array to be allocated */
2799  size_t typesize, /**< size of components */
2800  const char* filename, /**< source file of the function call */
2801  int line /**< line number in source file of the function call */
2802  )
2803 {
2804 #ifndef NDEBUG
2805  if ( num > (MAXMEMSIZE / typesize) )
2806  {
2807  printErrorHeader(filename, line);
2808  printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE);
2809  return NULL;
2810  }
2811 #endif
2812 
2813  return BMSallocBufferMemory_work(buffer, num * typesize, filename, line);
2814 }
2815 
2816 /** allocates the next unused buffer and clears it */
2818  BMS_BUFMEM* buffer, /**< memory buffer storage */
2819  size_t num, /**< size of array to be allocated */
2820  size_t typesize, /**< size of components */
2821  const char* filename, /**< source file of the function call */
2822  int line /**< line number in source file of the function call */
2823  )
2824 {
2825  void* ptr;
2826 
2827  ptr = BMSallocBufferMemoryArray_call(buffer, num, typesize, filename, line);
2828  if ( ptr != NULL )
2829  BMSclearMemorySize(ptr, num * typesize);
2830 
2831  return ptr;
2832 }
2833 
2834 /** work for reallocating the buffer to at least the given size */
2835 INLINE static
2837  BMS_BUFMEM* buffer, /**< memory buffer storage */
2838  void* ptr, /**< pointer to the allocated memory buffer */
2839  size_t size, /**< minimal required size of the buffer */
2840  const char* filename, /**< source file of the function call */
2841  int line /**< line number in source file of the function call */
2842  )
2843 {
2844  void* newptr;
2845 #ifndef SCIP_NOBUFFERMEM
2846  size_t bufnum;
2847 #endif
2848 
2849 #ifndef SCIP_NOBUFFERMEM
2850  assert( buffer != NULL );
2851  assert( buffer->firstfree <= buffer->ndata );
2852  assert(!buffer->clean); /* reallocating clean buffer elements is not supported */
2853 
2854  /* if the pointer doesn't exist yet, allocate it */
2855  if ( ptr == NULL )
2856  return BMSallocBufferMemory_call(buffer, size, filename, line);
2857 
2858  assert( buffer->firstfree >= 1 );
2859 
2860  /* Search the pointer in the buffer list:
2861  * Usually, buffers are allocated and freed like a stack, such that the currently used pointer is
2862  * most likely at the end of the buffer list.
2863  */
2864  bufnum = buffer->firstfree - 1;
2865  while ( bufnum > 0 && buffer->data[bufnum] != ptr )
2866  --bufnum;
2867 
2868  newptr = ptr;
2869  assert( buffer->data[bufnum] == newptr );
2870  assert( buffer->used[bufnum] );
2871  assert( buffer->size[bufnum] >= 1 );
2872 
2873  /* check if the buffer has to be enlarged */
2874  if ( size > buffer->size[bufnum] )
2875  {
2876  size_t newsize;
2877 
2878  /* enlarge buffer */
2879  newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, size);
2880  BMSreallocMemorySize(&buffer->data[bufnum], newsize);
2881  assert( newsize > buffer->size[bufnum] );
2882  buffer->totalmem += newsize - buffer->size[bufnum];
2883  buffer->size[bufnum] = newsize;
2884  if ( buffer->data[bufnum] == NULL )
2885  {
2886  printErrorHeader(filename, line);
2887  printError("Insufficient memory for reallocating buffer storage.\n");
2888  return NULL;
2889  }
2890  newptr = buffer->data[bufnum];
2891  }
2892  assert( buffer->size[bufnum] >= size );
2893  assert( newptr == buffer->data[bufnum] );
2894 
2895  debugMessage("Reallocated buffer %llu/%llu at %p to size %llu (required size: %llu) for pointer %p.\n",
2896  (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum],
2897  (unsigned long long)(buffer->size[bufnum]), (unsigned long long)size, newptr);
2898 
2899 #else
2900  newptr = ptr;
2901  BMSreallocMemorySize(&newptr, size);
2902 #endif
2903 
2904  return newptr;
2905 }
2906 
2907 /** reallocates the buffer to at least the given size */
2909  BMS_BUFMEM* buffer, /**< memory buffer storage */
2910  void* ptr, /**< pointer to the allocated memory buffer */
2911  size_t size, /**< minimal required size of the buffer */
2912  const char* filename, /**< source file of the function call */
2913  int line /**< line number in source file of the function call */
2914  )
2915 {
2916 #ifndef NDEBUG
2917  if ( size > MAXMEMSIZE )
2918  {
2919  printErrorHeader(filename, line);
2920  printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE);
2921  return NULL;
2922  }
2923 #endif
2924 
2925  return BMSreallocBufferMemory_work(buffer, ptr, size, filename, line);
2926 }
2927 
2928 /** reallocates an array in the buffer to at least the given size */
2930  BMS_BUFMEM* buffer, /**< memory buffer storage */
2931  void* ptr, /**< pointer to the allocated memory buffer */
2932  size_t num, /**< size of array to be allocated */
2933  size_t typesize, /**< size of components */
2934  const char* filename, /**< source file of the function call */
2935  int line /**< line number in source file of the function call */
2936  )
2937 {
2938 #ifndef NDEBUG
2939  if ( num > (MAXMEMSIZE / typesize) )
2940  {
2941  printErrorHeader(filename, line);
2942  printError("Tried to allocate array of size exceeding %lu.\n", MAXMEMSIZE);
2943  return NULL;
2944  }
2945 #endif
2946 
2947  return BMSreallocBufferMemory_work(buffer, ptr, num * typesize, filename, line);
2948 }
2949 
2950 /** allocates the next unused buffer and copies the given memory into the buffer */
2952  BMS_BUFMEM* buffer, /**< memory buffer storage */
2953  const void* source, /**< memory block to copy into the buffer */
2954  size_t size, /**< minimal required size of the buffer */
2955  const char* filename, /**< source file of the function call */
2956  int line /**< line number in source file of the function call */
2957  )
2958 {
2959  void* ptr;
2960 
2961  assert( source != NULL );
2962 
2963  /* allocate a buffer of the given size */
2964  ptr = BMSallocBufferMemory_call(buffer, size, filename, line);
2965 
2966  /* copy the source memory into the buffer */
2967  if ( ptr != NULL )
2968  BMScopyMemorySize(ptr, source, size);
2969 
2970  return ptr;
2971 }
2972 
2973 /** allocates an array in the next unused buffer and copies the given memory into the buffer */
2975  BMS_BUFMEM* buffer, /**< memory buffer storage */
2976  const void* source, /**< memory block to copy into the buffer */
2977  size_t num, /**< size of array to be allocated */
2978  size_t typesize, /**< size of components */
2979  const char* filename, /**< source file of the function call */
2980  int line /**< line number in source file of the function call */
2981  )
2982 {
2983  void* ptr;
2984 
2985  assert( source != NULL );
2986 
2987  /* allocate a buffer of the given size */
2988  ptr = BMSallocBufferMemoryArray_call(buffer, num, typesize, filename, line);
2989 
2990  /* copy the source memory into the buffer */
2991  if ( ptr != NULL )
2992  BMScopyMemorySize(ptr, source, num * typesize);
2993 
2994  return ptr;
2995 }
2996 
2997 /** work for freeing a buffer */
2998 INLINE static
3000  BMS_BUFMEM* buffer, /**< memory buffer storage */
3001  void** ptr, /**< pointer to pointer to the allocated memory buffer */
3002  const char* filename, /**< source file of the function call */
3003  int line /**< line number in source file of the function call */
3004  )
3005 { /*lint --e{715}*/
3006  size_t bufnum;
3007 
3008  assert( buffer != NULL );
3009  assert( buffer->firstfree <= buffer->ndata );
3010  assert( buffer->firstfree >= 1 );
3011  assert( ptr != NULL );
3012  assert( *ptr != NULL );
3013 
3014  /* Search the pointer in the buffer list:
3015  * Usually, buffers are allocated and freed like a stack, such that the freed pointer is
3016  * most likely at the end of the buffer list.
3017  */
3018  bufnum = buffer->firstfree-1;
3019  while ( bufnum > 0 && buffer->data[bufnum] != *ptr )
3020  --bufnum;
3021 
3022 #ifdef CHECKBUFFERORDER
3023  if ( bufnum < buffer->firstfree - 1 )
3024  {
3025  warningMessage("[%s:%d]: freeing buffer in wrong order.\n", filename, line);
3026  }
3027 #endif
3028 
3029 #ifndef NDEBUG
3030  if ( bufnum == 0 && buffer->data[bufnum] != *ptr )
3031  {
3032  printErrorHeader(filename, line);
3033  printError("Tried to free unkown buffer pointer.\n");
3034  return;
3035  }
3036  if ( ! buffer->used[bufnum] )
3037  {
3038  printErrorHeader(filename, line);
3039  printError("Tried to free buffer pointer already freed.\n");
3040  return;
3041  }
3042 #endif
3043 
3044 #ifdef CHECKCLEANBUFFER
3045  /* check that the memory is cleared */
3046  if( buffer->clean )
3047  {
3048  size_t i;
3049  uint8_t* tmpptr = (uint8_t*)(buffer->data[bufnum]);
3050 
3051  for( i = 0; i < buffer->size[bufnum]; ++i )
3052  assert(tmpptr[i] == 0);
3053  }
3054 #endif
3055 
3056  assert( buffer->data[bufnum] == *ptr );
3057  buffer->used[bufnum] = FALSE;
3058 
3059  while ( buffer->firstfree > 0 && !buffer->used[buffer->firstfree-1] )
3060  --buffer->firstfree;
3061 
3062  debugMessage("Freed buffer %llu/%llu at %p of size %llu for pointer %p, first free is %llu.\n",
3063  (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum],
3064  (unsigned long long)(buffer->size[bufnum]), *ptr, (unsigned long long)(buffer->firstfree));
3065 
3066  *ptr = NULL;
3067 }
3068 
3069 /** frees a buffer and sets pointer to NULL */
3071  BMS_BUFMEM* buffer, /**< memory buffer storage */
3072  void** ptr, /**< pointer to pointer to the allocated memory buffer */
3073  const char* filename, /**< source file of the function call */
3074  int line /**< line number in source file of the function call */
3075  )
3076 { /*lint --e{715}*/
3077  assert( ptr != NULL );
3078 
3079 #ifndef SCIP_NOBUFFERMEM
3080  if ( *ptr != NULL )
3081  BMSfreeBufferMemory_work(buffer, ptr, filename, line);
3082  else
3083  {
3084  printErrorHeader(filename, line);
3085  printError("Tried to free null buffer pointer.\n");
3086  }
3087 #else
3088  BMSfreeMemory(ptr);
3089 #endif
3090 }
3091 
3092 /** frees a buffer if pointer is not NULL and sets pointer to NULL */
3094  BMS_BUFMEM* buffer, /**< memory buffer storage */
3095  void** ptr, /**< pointer to pointer to the allocated memory buffer */
3096  const char* filename, /**< source file of the function call */
3097  int line /**< line number in source file of the function call */
3098  )
3099 { /*lint --e{715}*/
3100  assert( ptr != NULL );
3101 
3102  if ( *ptr != NULL )
3103  {
3104 #ifndef SCIP_NOBUFFERMEM
3105  BMSfreeBufferMemory_work(buffer, ptr, filename, line);
3106 #else
3107  BMSfreeMemory(ptr);
3108 #endif
3109  }
3110 }
3111 
3112 /** gets number of used buffers */
3114  BMS_BUFMEM* buffer /**< memory buffer storage */
3115  )
3116 {
3117  assert( buffer != NULL );
3118 
3119  return buffer->firstfree;
3120 }
3121 
3122 /** returns the number of allocated bytes in the buffer memory */
3124  const BMS_BUFMEM* buffer /**< buffer memory */
3125  )
3126 {
3127 #ifdef CHECKMEM
3128  size_t totalmem = 0UL;
3129  size_t i;
3130 
3131  assert( buffer != NULL );
3132  for (i = 0; i < buffer->ndata; ++i)
3133  totalmem += buffer->size[i];
3134  assert( totalmem == buffer->totalmem );
3135 #endif
3136 
3137  return (long long) buffer->totalmem;
3138 }
3139 
3140 /** outputs statistics about currently allocated buffers to the screen */
3142  BMS_BUFMEM* buffer /**< memory buffer storage */
3143  )
3144 {
3145  size_t totalmem;
3146  size_t i;
3147 
3148  assert( buffer != NULL );
3149 
3150  totalmem = 0UL;
3151  for (i = 0; i < buffer->ndata; ++i)
3152  {
3153  printf("[%c] %8llu bytes at %p\n", buffer->used[i] ? '*' : ' ', (unsigned long long)(buffer->size[i]), buffer->data[i]);
3154  totalmem += buffer->size[i];
3155  }
3156  printf(" %8llu bytes total in %llu buffers\n", (unsigned long long)totalmem, (unsigned long long)(buffer->ndata));
3157 }
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:128
struct BMS_ChkMem BMS_CHKMEM
Definition: memory.h:295
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:2079
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:141
#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:2284
void * BMSallocBlockMemoryArray_call(BMS_BLKMEM *blkmem, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:1919
#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:2496
void BMSfreeBufferMemoryNull_call(BMS_BUFMEM *buffer, void **ptr, const char *filename, int line)
Definition: memory.c:3093
void * BMSduplicateBufferMemoryArray_call(BMS_BUFMEM *buffer, const void *source, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:2974
#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:2796
#define INLINE
Definition: def.h:123
size_t * size
Definition: memory.c:2490
#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:1940
#define FALSE
Definition: def.h:87
void * BMSallocClearBlockMemory_call(BMS_BLKMEM *blkmem, size_t size, const char *filename, int line)
Definition: memory.c:1902
void BMSdestroyChunkMemory_call(BMS_CHKMEM **chkmem, const char *filename, int line)
Definition: memory.c:1498
#define TRUE
Definition: def.h:86
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:2264
long long BMScheckEmptyBlockMemory_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2408
#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:2491
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:1998
#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:1958
#define BMSfreeMemory(ptr)
Definition: memory.h:138
void ** data
Definition: memory.c:2489
size_t totalmem
Definition: memory.c:2492
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:2817
#define CHUNKLENGTH_MIN
Definition: memory.c:686
long long BMSgetBufferMemoryUsed(const BMS_BUFMEM *buffer)
Definition: memory.c:3123
void BMSsetBufferMemoryArraygrowinit(BMS_BUFMEM *buffer, int arraygrowinit)
Definition: memory.c:2583
long long BMSgetBlockMemoryUsedMax_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2234
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:2642
size_t firstfree
Definition: memory.c:2495
static INLINE void BMSfreeBufferMemory_work(BMS_BUFMEM *buffer, void **ptr, const char *filename, int line)
Definition: memory.c:2999
#define LONGINT_FORMAT
Definition: memory.c:110
long long BMSgetBlockMemoryAllocated_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2204
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:2776
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:2170
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:2214
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:2254
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:2538
void * BMSduplicateBlockMemoryArray_call(BMS_BLKMEM *blkmem, const void *source, size_t num, size_t typesize, const char *filename, int line)
Definition: memory.c:2057
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:136
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:2571
#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:2497
BMS_BUFMEM * BMScreateBufferMemory_call(double arraygrowfac, int arraygrowinit, unsigned int clean, const char *filename, int line)
Definition: memory.c:2502
void BMSfreeBufferMemory_call(BMS_BUFMEM *buffer, void **ptr, const char *filename, int line)
Definition: memory.c:3070
void BMSfreeBlockMemory_call(BMS_BLKMEM *blkmem, void **ptr, size_t size, const char *filename, int line)
Definition: memory.c:2127
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:2929
#define BMSclearMemorySize(ptr, size)
Definition: memory.h:124
void BMSprintBufferMemory(BMS_BUFMEM *buffer)
Definition: memory.c:3141
void * BMSduplicateBlockMemory_call(BMS_BLKMEM *blkmem, const void *source, size_t size, const char *filename, int line)
Definition: memory.c:2037
static void destroyChkmem(BMS_CHKMEM **chkmem, long long *memsize)
Definition: memory.c:1289
long long BMSgetBlockMemoryUnused_call(const BMS_BLKMEM *blkmem)
Definition: memory.c:2224
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:3113
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:2951
#define BMSallocMemorySize(ptr, size)
Definition: memory.h:113
public methods for message output
#define BMSreallocMemorySize(ptr, size)
Definition: memory.h:119
#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:177
void BMSfreeBlockMemoryNull_call(BMS_BLKMEM *blkmem, void **ptr, size_t size, const char *filename, int line)
Definition: memory.c:2149
#define BMSallocClearMemorySize(ptr, size)
Definition: memory.h:115
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:120
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:2836
#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:2244
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:2600
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:430
unsigned int clean
Definition: memory.c:2493
void * BMSreallocBufferMemory_call(BMS_BUFMEM *buffer, void *ptr, size_t size, const char *filename, int line)
Definition: memory.c:2908
void BMSclearBlockMemory_call(BMS_BLKMEM *blkmem, const char *filename, int line)
Definition: memory.c:1762
size_t ndata
Definition: memory.c:2494
void BMSalignMemsize(size_t *size)
Definition: memory.c:761
#define printErrorHeader
Definition: pub_message.h:59
memory allocation routines