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