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