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