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