1 #ifndef CONNECT___NCBI_HEAPMGR__H 2 #define CONNECT___NCBI_HEAPMGR__H 3 4 /* $Id: ncbi_heapmgr.h,v 6.29 2013/06/24 19:04:36 kazimird Exp $ 5 * =========================================================================== 6 * 7 * PUBLIC DOMAIN NOTICE 8 * National Center for Biotechnology Information 9 * 10 * This software/database is a "United States Government Work" under the 11 * terms of the United States Copyright Act. It was written as part of 12 * the author's official duties as a United States Government employee and 13 * thus cannot be copyrighted. This software/database is freely available 14 * to the public for use. The National Library of Medicine and the U.S. 15 * Government have not placed any restriction on its use or reproduction. 16 * 17 * Although all reasonable efforts have been taken to ensure the accuracy 18 * and reliability of the software and data, the NLM and the U.S. 19 * Government do not and cannot warrant the performance or results that 20 * may be obtained by using this software or data. The NLM and the U.S. 21 * Government disclaim all warranties, express or implied, including 22 * warranties of performance, merchantability or fitness for any particular 23 * purpose. 24 * 25 * Please cite the author in any work or product based on this material. 26 * 27 * =========================================================================== 28 * 29 * Authors: Anton Lavrentiev, Denis Vakatov 30 * 31 * File Description: 32 * Simple heap manager with a primitive garbage collection 33 * 34 */ 35 36 #include <connect/ncbi_types.h> 37 38 39 /** @addtogroup ServiceSupport 40 * 41 * @{ 42 */ 43 44 45 #ifdef __cplusplus 46 extern "C" { 47 #endif 48 49 50 /* Heap handle 51 */ 52 struct SHEAP_tag; 53 typedef struct SHEAP_tag* HEAP; 54 55 56 /* Header of a heap block 57 */ 58 typedef struct { 59 unsigned int flag; /* (flag & 1) == 0 if the block is vacant */ 60 TNCBI_Size size; /* size of the block (including the block header) */ 61 } SHEAP_Block; 62 63 64 /* Callback to resize the heap (a la 'realloc'). 65 * NOTE: the returned address must be aligned at the 'double' boundary! 66 * 67 * old_base | new_size | Expected result 68 * ------------+------------+-------------------------------------------------- 69 * non-NULL | 0 | Deallocate old_base, return 0 70 * non-NULL | non-zero | Reallocate to the requested size, return new base 71 * 0 | non-zero | Allocate anew, return base (return 0 on error) 72 * 0 | 0 | Do nothing, return 0 73 * ------------+------------+-------------------------------------------------- 74 * Note that reallocation can request either to expand or to shrink the heap 75 * extent. When (re-)allocation fails, the callback should return 0 (and must 76 * retain the original heap extent / content, if any). When expected to return 77 * 0, this callback must always do so. 78 */ 79 typedef void* (*FHEAP_Resize) 80 (void* old_base, /* current base of the heap to be expanded */ 81 TNCBI_Size new_size, /* requested new heap size (zero to deallocate heap) */ 82 void* auxarg /* user-supplied argument, see HEAP_Create() below */ 83 ); 84 85 86 /* Create new heap. 87 * NOTE: the initial heap base must be aligned at a 'double' boundary! 88 */ 89 extern NCBI_XCONNECT_EXPORT HEAP HEAP_Create 90 (void* base, /* initial heap base (use "resize" if NULL) */ 91 TNCBI_Size size, /* initial heap size */ 92 TNCBI_Size chunk_size, /* minimal increment size */ 93 FHEAP_Resize resize, /* NULL if not resizeable */ 94 void* auxarg /* a user argument to pass to "resize" */ 95 ); 96 97 98 /* Attach to an already existing heap (in read-only mode), calculating the heap 99 * extent by a heap end marker (but only within the maximal specified size). 100 */ 101 extern NCBI_XCONNECT_EXPORT HEAP HEAP_Attach 102 (const void* base, /* base of the heap to attach to */ 103 TNCBI_Size maxsize, /* maximal heap extent, or 0 for unlimited search */ 104 int serial /* serial number to assign */ 105 ); 106 107 /* Expedited HEAP_Attach() that does not calculate heap extent on its own */ 108 extern NCBI_XCONNECT_EXPORT HEAP HEAP_AttachFast 109 (const void* base, /* base of the heap to attach to */ 110 TNCBI_Size size, /* heap extent -- must be non-0 for non-NULL base */ 111 int serial /* serial number to assign */ 112 ); 113 114 115 /* Allocate a new block of memory in the heap toward either the base or the 116 * end of the heap, depending on the "hint" parameter: 117 * "hint" == 0 for base; 118 * "hint" != 0 for end. 119 * Return NULL if allocation has failed. 120 */ 121 extern NCBI_XCONNECT_EXPORT SHEAP_Block* HEAP_Alloc 122 (HEAP heap, /* heap handle */ 123 TNCBI_Size size, /* data size of the block to accommodate */ 124 int/*bool*/ hint 125 ); 126 127 128 /* Deallocate a block pointed to by "ptr". 129 */ 130 extern NCBI_XCONNECT_EXPORT void HEAP_Free 131 (HEAP heap, /* heap handle */ 132 SHEAP_Block* ptr /* block to deallocate */ 133 ); 134 135 136 /* Deallocate a block pointed to by "ptr" and having "prev" as its predecessor 137 * (NULL if "ptr" is the first on the heap) -- a faster variant of HEAP_Free(). 138 * NOTE: Since the block pointed to by "ptr" may cause free blocks to 139 * coalesce, to use this call again while walking the following rule must 140 * be utilized: If "prev" was free, "prev" must not get advanced; 141 * otherwise, "prev" must be updated with "ptr"'s value. 142 * NOTE: This call will be removed. 143 */ 144 extern NCBI_XCONNECT_EXPORT void HEAP_FreeFast 145 (HEAP heap, /* heap handle */ 146 SHEAP_Block* ptr, /* block to deallocate */ 147 const SHEAP_Block* prev /* block's predecessor */ 148 ); 149 150 151 /* Iterate through the heap blocks. 152 * Return pointer to the block following the block "prev". 153 * Return NULL if "prev" is the last block of the heap. 154 */ 155 extern NCBI_XCONNECT_EXPORT SHEAP_Block* HEAP_Walk 156 (const HEAP heap, /* heap handle */ 157 const SHEAP_Block* prev /* if 0, then get the first heap block */ 158 ); 159 160 161 /* Same as HEAP_Walk() but skip over free blocks so that only used blocks show 162 * (nevertheless it can also accept prev pointing to a free block). 163 */ 164 extern NCBI_XCONNECT_EXPORT SHEAP_Block* HEAP_Next 165 (const HEAP heap, /* heap handle */ 166 const SHEAP_Block* prev /* if 0, then get the first used heap block */ 167 ); 168 169 170 /* Trim the heap, making garbage collection first. Returned is 171 * the resultant heap, which has its last block (if any) trimmed to the 172 * size of the heap chunk size as specified at the time of the heap creation. 173 * No change in size is made if the last block is not free or large 174 * enough to allow the trimming. NULL gets returned on NULL or read-only 175 * heaps, or if a resize error has occurred. 176 * Note that trimming can cause the entire heap extent (of an empty heap) 177 * to deallocate (so that HEAP_Base() and HEAP_Size() will both return 0). 178 */ 179 extern NCBI_XCONNECT_EXPORT HEAP HEAP_Trim(HEAP heap); 180 181 182 /* Make a snapshot of a given heap. Return a read-only heap 183 * (like the one after HEAP_Attach[Fast]()), which must be freed by a call 184 * to either HEAP_Detach() or HEAP_Destroy() when no longer needed. 185 * A copy is created reference-counted (with the initial ref.count set to 1). 186 */ 187 extern NCBI_XCONNECT_EXPORT HEAP HEAP_Copy 188 (const HEAP orig, /* original heap to copy from */ 189 size_t extra, /* extra amount to add past the heap extent */ 190 int serial /* serial number to assign */ 191 ); 192 193 194 /* Add reference counter to the given copy heap (no effect on 195 * a heap, which have been HEAP_Create()'d or HEAP_Attach[Fast]()'d). 196 * The heap handle then will be destroyed only when the internal 197 * reference counter reaches 0. No internal locking is provided. 198 * Return the resultant value of the reference counter. 199 */ 200 extern NCBI_XCONNECT_EXPORT unsigned int HEAP_AddRef(HEAP heap); 201 202 203 /* Detach heap (previously attached by HEAP_Attach[Fast]). 204 * For copy heap, it decrements an internal ref. counter by one, and 205 * destroys the heap handle if and only if the counter has reached 0. 206 * No internal locking of the reference counter is provided. 207 * For heaps that are results of the HEAP_Copy() call, 208 * both HEAP_Detach() and HEAP_Destroy() can be used interchangeably. 209 * Return the remaining value of the reference counter (0 if the heap is gone). 210 */ 211 extern NCBI_XCONNECT_EXPORT unsigned int HEAP_Detach(HEAP heap); 212 213 214 /* Destroy heap (previously created by HEAP_Create()). 215 * For copy heaps -- see comments for HEAP_Detach() above. 216 * Return the remaining value of the reference counter (0 if the heap is gone). 217 */ 218 extern NCBI_XCONNECT_EXPORT unsigned int HEAP_Destroy(HEAP heap); 219 220 221 /* Get base address of the heap. 222 * Return NULL if heap is passed as NULL, or when the heap is completely empty. 223 */ 224 extern NCBI_XCONNECT_EXPORT void* HEAP_Base(const HEAP heap); 225 226 227 /* Get the extent of the heap. 228 * Return 0 if heap is passed as NULL, or when the heap is completely empty. 229 */ 230 extern NCBI_XCONNECT_EXPORT TNCBI_Size HEAP_Size(const HEAP heap); 231 232 233 /* Get a serial number of the heap as assigned by Attach or Copy. 234 * Return 0 if the heap is not a copy but the original, or passed as NULL. 235 */ 236 extern NCBI_XCONNECT_EXPORT int HEAP_Serial(const HEAP heap); 237 238 239 /* Set heap access speed (and ignore second parameter): 240 * fast == eOn turns on fast heap operations (default); 241 * fast == eOff turns off fast heap operations (more checks, slower); 242 * fast == eDefault does not change the current setting. 243 * This call is intended for internal uses; and default settings (fast ops 244 * w/o structure integrity checks) should suffice for most users. 245 */ 246 extern NCBI_XCONNECT_EXPORT void HEAP_Options(ESwitch fast, ESwitch unused); 247 248 249 #ifdef __cplusplus 250 } /* extern "C" */ 251 #endif 252 253 254 /* @} */ 255 256 #endif /* CONNECT___NCBI_HEAPMGR__H */ 257