Scippy

SCIP

Solving Constraint Integer Programs

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