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