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