← Back to branch summary

~ubuntu-branches/ubuntu/edgy/ncbi-tools6/edgy

« back to all changes in this revision

Viewing changes to connect/ncbi_heapmgr.c

  • Committer: Bazaar Package Importer
  • Author(s): Barry deFreese
  • Date: 2006-07-19 23:28:07 UTC
  • mfrom: (1.1.5 upstream)
  • Revision ID: james.westby@ubuntu.com-20060719232807-et3cdmcjgmnyleyx
Tags: 6.1.20060507-3ubuntu1
Re-merge with Debian

Show diffs side-by-side

added added

removed removed

Lines of Context:
connect/ncbi_heapmgr.c
1
 
/*  $Id: ncbi_heapmgr.c,v 6.27 2005/01/27 19:00:17 lavr Exp $
 
1
/*  $Id: ncbi_heapmgr.c,v 6.31 2006/04/28 16:19:44 lavr Exp $
2
2
 * ===========================================================================
3
3
 *
4
4
 *                            PUBLIC DOMAIN NOTICE
39
39
 * which points to the block header, marked as allocated and guaranteed
40
40
 * to have enough space to hold the requested data size; or 0 meaning, that the
41
41
 * heap has no more room to provide such a block (reasons for that:
42
 
 * heap is corrupted, heap has no provision to be expanded, expansion failed,
 
42
 * heap is corrupt, heap has no provision to be expanded, expansion failed,
43
43
 * or the heap was attached read-only).
44
44
 *
45
45
 * An application program can then use the data field on its need,
58
58
 * with 'HEAP_Free' call, supplying the address of the block header
59
59
 * as an argument.
60
60
 *
61
 
 * Prior the heap use, the initialization is required, which comprises
 
61
 * Prior to the heap use, the initialization is required, which comprises
62
62
 * call to either 'HEAP_Create' or 'HEAP_Attach' with the information about
63
 
 * the base heap pointer. 'HEAP_Create' also requires the size of initial
 
63
 * the base heap pointer. 'HEAP_Create' also takes the size of initial
64
64
 * heap area (if there is one), and size of chunk (usually, a page size)
65
65
 * to be used in heap expansions (defaults to alignment if provided as 0).
66
66
 * Additionally (but not compulsory) the application program can provide
67
 
 * heap manager with 'expand' routine, which is supposed to be called,
68
 
 * when no more room is available in the heap, or the heap was not
 
67
 * heap manager with 'resize' routine, which is supposed to be called,
 
68
 * when no more room is available in the heap, or the heap has not been
69
69
 * preallocated (base = 0 in 'HEAP_Create'), and given the arguments:
70
70
 * - current heap base address (or 0 if this is the very first heap alloc),
71
 
 * - new required heap size (or 0 if this is the very last call to deallocate
 
71
 * - new required heap size (or 0 if this is the last call to deallocate
72
72
 * the entire heap). 
73
 
 * If successful, the expand routine must return the new heap base
 
73
 * If successful, the resize routine must return the new heap base
74
74
 * address (if any) of expanded heap area, and where the exact copy of
75
75
 * the current heap is made.
76
76
 *
77
77
 * Note that all heap base pointers must be aligned on a 'double' boundary.
78
78
 * Please also be warned not to store pointers to the heap area, as a
79
 
 * garbage collection can clobber them. Within a block, however,
 
79
 * garbage collection can clobber them.  Within a block, however,
80
80
 * it is possible to use local pointers (offsets), which remain same
81
81
 * regardless of garbage collections.
82
82
 *
84
84
 * the next block (either free, or used) from the heap.  Given a NULL-pointer,
85
85
 * this function returns the very first block, whereas all subsequent calls
86
86
 * with the argument being the last observed block results in the next block 
87
 
 * returned. NULL comes back when no more blocks exist in the heap.
 
87
 * returned.  NULL comes back when no more blocks exist in the heap.
88
88
 *
89
 
 * Note that for proper heap operations, no allocations should happen between
 
89
 * Note that for proper heap operations, no allocation(s) should happen between
90
90
 * successive calls to 'HEAP_Walk', whereas deallocation of the seen block
91
91
 * is okay.
92
92
 *
93
93
 * Explicit heap traversing should not overcome the heap limit,
94
94
 * as any information above the limit is not maintained by the heap manager.
95
 
 * Every heap operation guarantees, that there are no adjacent free blocks,
 
95
 * Every heap operation guarantees that there are no adjacent free blocks,
96
96
 * only used blocks can follow each other sequentially.
97
97
 *
98
98
 * To discontinue to use the heap, 'HEAP_Destroy' or 'HEAP_Detach' can be
99
 
 * called. The former deallocates the heap (by means of a call to 'expand'),
 
99
 * called.  The former deallocates the heap (by means of a call to 'resize'),
100
100
 * the latter just removes the heap handle, retaining the heap data intact.
101
101
 * Later, such a heap could be used again if attached with 'HEAP_Attach'.
102
102
 *
105
105
 * 'HEAP_Destroy' will not destroy the heap data.
106
106
 *
107
107
 * Note also, that 'HEAP_Create' always does heap reset, that is the
108
 
 * memory area pointed by 'base' (if not 0) gets reformatted and lose
 
108
 * memory area pointed to by 'base' (if not 0) gets reformatted and lose
109
109
 * all previous contents.
110
110
 *
111
111
 */
115
115
#include <stdlib.h>
116
116
#include <string.h>
117
117
 
 
118
#if defined(NCBI_OS_MSWIN)  &&  defined(_WIN64)
 
119
/* Disable ptr->long conversion warning (even on explicit cast!) */
 
120
#  pragma warning (disable : 4311)
 
121
#endif /*NCBI_OS_MSWIN && _WIN64*/
 
122
 
118
123
 
119
124
struct SHEAP_tag {
120
 
    void*         base;
121
 
    TNCBI_Size    size;
122
 
    TNCBI_Size    chunk;
123
 
    FHEAP_Expand  expand;
124
 
    void*         arg;
125
 
    int/*bool*/   copy;    /* (!=0) keeps user's serial number if provided */
 
125
    void*          base;    /* Current base of heap extent:  !base == !size  */
 
126
    TNCBI_Size     size;    /* Current size of heap extent:  !base == !size  */
 
127
    TNCBI_Size     chunk;   /* == 0 when the heap is read-only               */
 
128
    FHEAP_Resize   resize;  /* != NULL when resizeable (only for non-RO heaps*/
 
129
    void*          arg;     /* Aux argument to pass to "resize"              */
 
130
    unsigned int   refc;    /* Reference counter (copy heaps only,0=original)*/
 
131
    int            serial;  /* Serial number as assigned by user(Attach|Copy)*/
126
132
};
127
133
 
128
134
 
134
140
#define HEAP_FREE             0
135
141
#define HEAP_ISFREE(b)        (((b)->flag & ~HEAP_LAST) == HEAP_FREE)
136
142
#define HEAP_ISUSED(b)        (((b)->flag & ~HEAP_LAST) == HEAP_USED)
137
 
#define HEAP_ISLAST(b)        ((b)->flag & HEAP_LAST)
 
143
#define HEAP_ISLAST(b)        ( (b)->flag &  HEAP_LAST)
138
144
 
139
145
 
140
146
HEAP HEAP_Create(void* base,       TNCBI_Size   size,
141
 
                 TNCBI_Size chunk, FHEAP_Expand expand, void* arg)
 
147
                 TNCBI_Size chunk, FHEAP_Resize resize, void* arg)
142
148
{
 
149
    TNCBI_Size min_size;
143
150
    SHEAP_Block* b;
144
151
    HEAP heap;
145
152
 
 
153
    if (!base != !size)
 
154
        return 0;
 
155
    min_size = size ? (TNCBI_Size) HEAP_ALIGN(sizeof(*b) + 1) : 0;
 
156
    if (size < min_size) {
 
157
        CORE_LOGF(eLOG_Error, ("Heap Create: Storage too small "
 
158
                               "(provided %u, required %u+)",
 
159
                               (unsigned) size, (unsigned) min_size));
 
160
        return 0;
 
161
    }
 
162
    if (!(heap = (HEAP) malloc(sizeof(*heap))))
 
163
        return 0;
 
164
    heap->base   = base;
 
165
    heap->size   = size;
 
166
    heap->chunk  = chunk        ? (TNCBI_Size) HEAP_ALIGN(chunk) : 0;
 
167
    heap->resize = heap->chunk  ? resize                         : 0;
 
168
    heap->arg    = heap->resize ? arg                            : 0;
 
169
    heap->refc   = 0/*original*/;
 
170
    heap->serial = 0;
 
171
    if (base) {
 
172
        /* Reformat the pre-allocated heap */
 
173
        if (HEAP_ALIGN(base) != (unsigned long) base) {
 
174
            CORE_LOGF(eLOG_Warning,
 
175
                     ("Heap Create: Unaligned base (0x%08lX)", (long) base));
 
176
        }
 
177
        b = (SHEAP_Block*) base;
 
178
        b->flag = HEAP_FREE | HEAP_LAST;
 
179
        b->size = size;
 
180
    }
 
181
    return heap;
 
182
}
 
183
 
 
184
 
 
185
HEAP HEAP_AttachEx(const void* base, TNCBI_Size size, int serial)
 
186
{
 
187
    HEAP heap;
 
188
 
146
189
    if (!base != !size || !(heap = (HEAP) malloc(sizeof(*heap))))
147
190
        return 0;
148
 
    chunk = (TNCBI_Size) HEAP_ALIGN(chunk);
149
 
    if (!base) {
150
 
        size = (TNCBI_Size) _HEAP_ALIGN(sizeof(*b) + 1, chunk);
151
 
        if (!size || !expand || !(base = (*expand)(0, size, arg))) {
152
 
            CORE_LOGF(eLOG_Warning,
153
 
                      ("Heap Create: Cannot create (size = %u)",
154
 
                       (unsigned)(size ? size : sizeof(*b))));
155
 
            free(heap);
156
 
            return 0;
157
 
        }
158
 
    }
159
 
    if ((void*) HEAP_ALIGN(base) != base) {
160
 
        CORE_LOGF(eLOG_Warning,
161
 
                  ("Heap Create: Unaligned base (0x%08lX)", (long) base));
162
 
    }
163
 
    if (size < (TNCBI_Size) HEAP_ALIGN(sizeof(*b) + 1)) {
164
 
        CORE_LOGF(eLOG_Warning, ("Heap Create: Heap is too small (%u, %u)",
165
 
                                 (unsigned) size, (unsigned) sizeof(*b)));
166
 
    }
167
 
    heap->base   = base;
168
 
    heap->size   = size;
169
 
    heap->chunk  = chunk;
170
 
    heap->expand = expand;
171
 
    heap->arg    = expand ? arg : 0;
172
 
    heap->copy   = 0/*original*/;
173
 
    b = (SHEAP_Block*) heap->base;
174
 
    b->flag = HEAP_FREE | HEAP_LAST;
175
 
    b->size = size;
176
 
    return heap;
177
 
}
178
 
 
179
 
 
180
 
HEAP HEAP_AttachEx(const void* base, TNCBI_Size size)
181
 
{
182
 
    HEAP heap;
183
 
 
184
 
    if (!base || !size || !(heap = (HEAP) malloc(sizeof(*heap))))
185
 
        return 0;
186
 
    if ((void*) HEAP_ALIGN(base) != base) {
 
191
    if (HEAP_ALIGN(base) != (unsigned long) base) {
187
192
        CORE_LOGF(eLOG_Warning,
188
193
                  ("Heap Attach: Unaligned base (0x%08lX)", (long) base));
189
194
    }
190
195
    heap->base   = (void*) base;
191
196
    heap->size   = size;
192
197
    heap->chunk  = 0/*read-only*/;
193
 
    heap->expand = 0;
 
198
    heap->resize = 0;
194
199
    heap->arg    = 0;
195
 
    heap->copy   = 0/*original*/;
 
200
    heap->refc   = 0/*original*/;
 
201
    heap->serial = serial;
196
202
    return heap;
197
203
}
198
204
 
199
205
 
200
 
HEAP HEAP_Attach(const void* base)
 
206
HEAP HEAP_Attach(const void* base, int serial)
201
207
{
202
 
    TNCBI_Size size;
203
 
    SHEAP_Block* b;
 
208
    TNCBI_Size size = 0;
204
209
 
205
 
    if (!base)
206
 
        return 0;
207
 
    size = 0;
208
 
    for (b = (SHEAP_Block*) base; ; b = (SHEAP_Block*)((char*) b + b->size)) {
209
 
        if (!HEAP_ISUSED(b) && !HEAP_ISFREE(b)) {
210
 
            CORE_LOGF(eLOG_Warning,
211
 
                      ("Heap Attach: Heap corrupted (0x%08X, %u)",
212
 
                       b->flag, (unsigned) b->size));
213
 
            return 0;
 
210
    if (base) {
 
211
        const SHEAP_Block* b = (const SHEAP_Block*) base;
 
212
        unsigned int n;
 
213
        for (n = 0; ; n++) {
 
214
            if (!HEAP_ISUSED(b) && !HEAP_ISFREE(b)) {
 
215
                CORE_LOGF(eLOG_Warning,
 
216
                          ("Heap Attach: Heap corrupted (%u, 0x%08X, %u)",
 
217
                           n, b->flag, (unsigned) b->size));
 
218
                return 0;
 
219
            }
 
220
            size += b->size;
 
221
            if (HEAP_ISLAST(b))
 
222
                break;
 
223
            b = (const SHEAP_Block*)((const char*) b + b->size);
214
224
        }
215
 
        size += b->size;
216
 
        if (HEAP_ISLAST(b))
217
 
            break;
218
225
    }
219
 
    return HEAP_AttachEx(base, size);
 
226
    return HEAP_AttachEx(base, size, serial);
220
227
}
221
228
 
222
229
 
233
240
    assert(HEAP_ISFREE(b));
234
241
    if (!HEAP_ISLAST(b) && HEAP_ISFREE(n)) {
235
242
        b->size += n->size;
236
 
        b->flag = n->flag;
 
243
        b->flag  = n->flag;
237
244
        n = (SHEAP_Block*)((char*) n + n->size);
238
245
    }
 
246
    assert(!p || (SHEAP_Block*)((char*) p + p->size) == b);
239
247
    if (p && HEAP_ISFREE(p)) {
240
248
        p->size += b->size;
241
 
        p->flag = b->flag;
 
249
        p->flag  = b->flag;
242
250
    }
243
251
    return n;
244
252
}
245
253
 
246
254
 
247
255
/* Collect garbage in the heap, moving all contents to the
248
 
 * top of the heap, and merging all free blocks at the end
249
 
 * in one large free block. Return pointer to that free block.
 
256
 * top of, and merging all free blocks at the end into one
 
257
 * large free block.  Return pointer to that free block, or
 
258
 * NULL if there is no free space in the heap.
250
259
 */
251
260
static SHEAP_Block* s_HEAP_Collect(HEAP heap)
252
261
{
257
266
            f = b;
258
267
        else if (HEAP_ISUSED(b) && f) {
259
268
            unsigned int last = b->flag & HEAP_LAST;
260
 
            TNCBI_Size save = f->size;
 
269
            TNCBI_Size   size = f->size;
261
270
 
262
271
            memmove(f, b, b->size);
263
272
            f->flag &= ~HEAP_LAST;
264
273
            f = (SHEAP_Block*)((char*) f + f->size);
265
274
            f->flag = HEAP_FREE | last;
266
 
            f->size = save;
 
275
            f->size = size;
267
276
            b = s_HEAP_Join(0, f);
268
277
            continue;
269
278
        }
274
283
 
275
284
 
276
285
/* Take the block 'b' (maybe split in two, if it's roomy enough)
277
 
 * for use of by at most 'size' bytes (including block header).
278
 
 * Return the block to use if taken okay; 0 otherwise.
 
286
 * for use of by at most 'size' bytes (aligned, and block header included).
 
287
 * Return the block to use.
279
288
 */
280
289
static SHEAP_Block* s_HEAP_Take(SHEAP_Block* b, TNCBI_Size size)
281
290
{
282
291
    unsigned int last = b->flag & HEAP_LAST;
283
292
 
284
 
    if (b->size >= size + sizeof(*b)) {
 
293
    assert(b->size >= size);
 
294
    if (b->size > size + sizeof(*b)) {
285
295
        SHEAP_Block* n = (SHEAP_Block*)((char*) b + size);
286
296
 
287
297
        n->flag = HEAP_FREE | last;
295
305
}
296
306
 
297
307
 
 
308
static const char* s_HEAP_Id(char* buf, HEAP h)
 
309
{
 
310
    if (!h  || !h->refc)
 
311
        return "";
 
312
    sprintf(buf, "[%u]", h->refc);
 
313
    return buf;
 
314
}
 
315
 
 
316
 
298
317
SHEAP_Block* HEAP_Alloc(HEAP heap, TNCBI_Size size)
299
318
{
300
319
    SHEAP_Block* b, *p = 0;
301
320
    TNCBI_Size free = 0;
 
321
    unsigned int n;
 
322
    char _id[32];
302
323
 
303
 
    if (!heap || size < 1) {
304
 
        if (size)
305
 
            CORE_LOG(eLOG_Warning, "Heap Alloc: Cannot alloc in NULL heap");
 
324
    if (!heap) {
 
325
        CORE_LOG(eLOG_Warning, "Heap Alloc: Cannot alloc in NULL heap");
306
326
        return 0;
307
327
    }
 
328
    assert(!heap->base == !heap->size);
 
329
    if (size < 1)
 
330
        return 0;
308
331
 
309
332
    if (!heap->chunk) {
310
 
        CORE_LOG(eLOG_Warning, "Heap Alloc: Heap is read-only");
 
333
        CORE_LOGF(eLOG_Warning, ("Heap Alloc%s: Heap is read-only",
 
334
                                 s_HEAP_Id(_id, heap)));
311
335
        return 0;
312
336
    }
313
337
 
314
338
    size = (TNCBI_Size) HEAP_ALIGN(sizeof(*b) + size);
315
339
 
316
340
    b = (SHEAP_Block*) heap->base;
317
 
    while ((char*) b < (char*) heap->base + heap->size) {
 
341
    for (n = 0; (char*) b < (char*) heap->base + heap->size; n++) {
318
342
        if (HEAP_ISFREE(b)) {
319
343
            /* if an empty, large enough block found, then take it! */
320
344
            if (b->size >= size)
322
346
            free += b->size;
323
347
        } else if (!HEAP_ISUSED(b)) {
324
348
            CORE_LOGF(eLOG_Warning,
325
 
                      ("Heap Alloc: Heap corrupted (0x%08X, %u)",
326
 
                       b->flag, (unsigned) b->size));
 
349
                      ("Heap Alloc%s: Heap corrupted (%u, 0x%08X, %u)",
 
350
                       s_HEAP_Id(_id, heap), n, b->flag, (unsigned) b->size));
327
351
            return 0;
328
352
        }
329
353
        p = b;
330
354
        b = (SHEAP_Block*)((char*) b + b->size);
331
355
    }
 
356
    assert(!p || HEAP_ISLAST(p));
332
357
 
333
358
    /* Heap exhausted, no free block found */
334
359
    if (free >= size)
335
360
        b = s_HEAP_Collect(heap);
336
 
    else if (!heap->expand)
 
361
    else if (!heap->resize)
337
362
        return 0;
338
363
    else {
339
364
        TNCBI_Size hsize =
341
366
        ptrdiff_t dp = (char*) p - (char*) heap->base;
342
367
        void* base;
343
368
 
344
 
        if (!(base = (*heap->expand)(heap->base, hsize, heap->arg)))
 
369
        if (!(base = (*heap->resize)(heap->base, hsize, heap->arg)))
345
370
            return 0;
346
371
        p = (SHEAP_Block*)((char*) base + dp);
347
 
        if (!HEAP_ISLAST(p))
348
 
            CORE_LOG(eLOG_Warning, "Heap Alloc: Last block lost");
349
 
        if (HEAP_ISUSED(p)) {
350
 
            p->flag &= ~HEAP_LAST;
351
 
            /* New block is the very top on the heap */
352
 
            b = (SHEAP_Block*)((char*) base + heap->size);
353
 
            b->size = hsize - heap->size;
354
 
            b->flag = HEAP_FREE | HEAP_LAST;
355
 
        } else {
356
 
            /* Extend last free block */
357
 
            p->size += hsize - heap->size;
 
372
        if (!heap->base) {
 
373
            p->flag = HEAP_FREE | HEAP_LAST;
 
374
            p->size = hsize;
358
375
            b = p;
 
376
        } else {
 
377
            if (!HEAP_ISLAST(p)) {
 
378
                CORE_LOGF(eLOG_Warning, ("Heap Alloc%s: Last block marker "
 
379
                                         "lost", s_HEAP_Id(_id, heap)));
 
380
            }
 
381
            if (HEAP_ISUSED(p)) {
 
382
                p->flag &= ~HEAP_LAST;
 
383
                /* New block is the very top on the heap */
 
384
                b = (SHEAP_Block*)((char*) base + heap->size);
 
385
                b->size = hsize - heap->size;
 
386
                b->flag = HEAP_FREE | HEAP_LAST;
 
387
            } else {
 
388
                /* Extend last free block */
 
389
                p->size += hsize - heap->size;
 
390
                b = p;
 
391
            }
359
392
        }
360
393
        heap->base = base;
361
394
        heap->size = hsize;
362
395
    }
363
 
    assert(b && HEAP_ISFREE(b) && b->size >= size);
 
396
    assert(b && HEAP_ISFREE(b));
364
397
    return s_HEAP_Take(b, size);
365
398
}
366
399
 
367
400
 
368
401
void HEAP_Free(HEAP heap, SHEAP_Block* ptr)
369
402
{
370
 
    SHEAP_Block* b, *p = 0;
 
403
    SHEAP_Block* b, *p;
 
404
    unsigned int n;
 
405
    char _id[32];
371
406
 
372
 
    if (!heap || !ptr) {
373
 
        if (ptr)
374
 
            CORE_LOG(eLOG_Warning, "Heap Free: Cannot free in NULL heap");
 
407
    if (!heap) {
 
408
        CORE_LOG(eLOG_Warning, "Heap Free: Cannot free in NULL heap");
375
409
        return;
376
410
    }
 
411
    assert(!heap->base == !heap->size);
 
412
    if (!ptr)
 
413
        return;
377
414
 
378
415
    if (!heap->chunk) {
379
 
        CORE_LOG(eLOG_Warning, "Heap Free: Heap is read-only");
 
416
        CORE_LOGF(eLOG_Warning, ("Heap Free%s: Heap is read-only",
 
417
                                 s_HEAP_Id(_id, heap)));
380
418
        return;
381
419
    }
382
420
 
383
421
    b = (SHEAP_Block*) heap->base;
384
 
    while ((char*) b < (char*) heap->base + heap->size) {
 
422
    for (p = 0, n = 0; (char*) b < (char*) heap->base + heap->size; n++) {
385
423
        if (HEAP_ISFREE(b)) {
386
424
            if (b == ptr) {
387
 
                CORE_LOG(eLOG_Warning, "Heap Free: Freeing free block");
 
425
                CORE_LOGF(eLOG_Warning, ("Heap Free%s: Freeing free block",
 
426
                                         s_HEAP_Id(_id, heap)));
388
427
                return;
389
428
            }
390
429
        } else if (HEAP_ISUSED(b)) {
395
434
            }
396
435
        } else {
397
436
            CORE_LOGF(eLOG_Warning,
398
 
                      ("Heap Free: Heap corrupted (0x%08X, %u)",
399
 
                       b->flag, (unsigned) b->size));
 
437
                      ("Heap Free%s: Heap corrupted (%u, 0x%08X, %u)",
 
438
                       s_HEAP_Id(_id, heap), n, b->flag, (unsigned) b->size));
400
439
            return;
401
440
        }
402
441
        p = b;
403
442
        b = (SHEAP_Block*)((char*) p + p->size);
404
443
    }
405
 
    CORE_LOG(eLOG_Warning, "Heap Free: Block not found");
 
444
    CORE_LOGF(eLOG_Warning, ("Heap Free%s: Block not found",
 
445
                             s_HEAP_Id(_id, heap)));
406
446
}
407
447
 
408
448
 
409
449
SHEAP_Block* HEAP_Walk(const HEAP heap, const SHEAP_Block* p)
410
450
{
411
451
    SHEAP_Block* b;
 
452
    char _id[32];
412
453
 
413
454
    if (!heap) {
414
455
        CORE_LOG(eLOG_Warning, "Heap Walk: NULL heap");
415
456
        return 0;
416
457
    }
417
 
    if (!p ||
418
 
        ((char*) p >= (char*) heap->base &&
419
 
         (char*) p <  (char*) heap->base + heap->size)) {
 
458
    assert(!heap->base == !heap->size);
 
459
 
 
460
    if (!p || ((char*) p >= (char*) heap->base &&
 
461
               (char*) p <  (char*) heap->base + heap->size)) {
420
462
        b = (SHEAP_Block*)(p ? (char*) p + p->size : (char*) heap->base);
421
463
        if ((char*) b < (char*) heap->base + heap->size) {
422
 
            if (b->size >= sizeof(*b) &&
423
 
                b->size == (TNCBI_Size) HEAP_ALIGN(b->size) &&
424
 
                (char*) b + b->size <= (char*) heap->base + heap->size &&
425
 
                (HEAP_ISFREE(b) || HEAP_ISUSED(b))) {
 
464
            if (b->size >= sizeof(*b)/*compatibility: ">" should be here now*/
 
465
                && b->size == (TNCBI_Size) HEAP_ALIGN(b->size)
 
466
                && (char*) b + b->size <= (char*) heap->base + heap->size
 
467
                && (HEAP_ISFREE(b) || HEAP_ISUSED(b))) {
426
468
                /* Block 'b' seems valid, but... */
427
469
                if (!p)
428
470
                    return b;
429
 
                if (HEAP_ISLAST(p))
430
 
                    CORE_LOG(eLOG_Warning, "Heap Walk: Misplaced last block");
431
 
                else if (HEAP_ISFREE(b) && HEAP_ISFREE(p)) {
 
471
                if (HEAP_ISLAST(p)) {
 
472
                    CORE_LOGF(eLOG_Warning, ("Heap Walk%s: Misplaced last "
 
473
                                             "block", s_HEAP_Id(_id, heap)));
 
474
                } else if (HEAP_ISFREE(p) && HEAP_ISFREE(b)) {
432
475
                    const SHEAP_Block* c = (const SHEAP_Block*) heap->base;
433
476
                    while ((char*) c < (char*) p) {
434
477
                        if (HEAP_ISFREE(c) &&
438
481
                    }
439
482
                    if ((char*) c < (char*) p)
440
483
                        return b;
441
 
                    CORE_LOG(eLOG_Warning, "Heap Walk: Adjacent free blocks");
 
484
                    CORE_LOGF(eLOG_Warning, ("Heap Walk%s: Adjacent free "
 
485
                                             "blocks", s_HEAP_Id(_id, heap)));
442
486
                } else
443
487
                    return b;
444
 
            } else
 
488
            } else {
445
489
                CORE_LOGF(eLOG_Warning,
446
 
                          ("Heap Walk: Heap corrupted (0x%08X, %u)",
447
 
                           b->flag, (unsigned) b->size));
448
 
        } else if ((char*) b > (char*) heap->base + heap->size)
449
 
            CORE_LOG(eLOG_Warning, "Heap Walk: Heap corrupted");
450
 
        else if (!HEAP_ISLAST(p))
451
 
            CORE_LOG(eLOG_Warning, "Heap Walk: Last block lost");
452
 
    } else
453
 
        CORE_LOG(eLOG_Warning, "Heap Walk: Alien pointer passed");
 
490
                          ("Heap Walk%s: Heap corrupted (0x%08X, %u)",
 
491
                           s_HEAP_Id(_id, heap), b->flag, (unsigned) b->size));
 
492
            }
 
493
        } else if ((char*) b > (char*) heap->base + heap->size) {
 
494
            CORE_LOGF(eLOG_Warning, ("Heap Walk%s: Heap corrupted",
 
495
                                     s_HEAP_Id(_id, heap)));
 
496
        } else if (b && !HEAP_ISLAST(p)) {
 
497
            CORE_LOGF(eLOG_Warning, ("Heap Walk%s: Last block lost",
 
498
                                     s_HEAP_Id(_id, heap)));
 
499
        }
 
500
    } else {
 
501
        CORE_LOGF(eLOG_Warning, ("Heap Walk%s: Alien pointer",
 
502
                                 s_HEAP_Id(_id, heap)));
 
503
    }
454
504
    return 0;
455
505
}
456
506
 
457
507
 
458
 
TNCBI_Size HEAP_Trim(HEAP heap)
 
508
HEAP HEAP_Trim(HEAP heap)
459
509
{
460
510
    TNCBI_Size   size, last_size;
461
511
    SHEAP_Block* f;
462
512
 
463
513
    if (!heap)
464
514
        return 0;
 
515
 
465
516
    if (!heap->chunk) {
466
517
        CORE_LOG(eLOG_Error, "Heap Trim: Heap is read-only");
467
518
        return 0;
468
519
    }
469
520
 
470
 
    if (!(f =s_HEAP_Collect(heap)) || HEAP_ISUSED(f) || f->size < heap->chunk){
 
521
    if (!(f = s_HEAP_Collect(heap)) || f->size < heap->chunk) {
 
522
        assert(!f || HEAP_ISFREE(f));
471
523
        last_size = 0;
472
 
        size      = heap->size;
473
 
    } else if ((char*) f != heap->base) {
474
 
        assert(f->size >= _HEAP_ALIGNMENT);
475
 
        last_size = f->size % heap->chunk;
476
 
        if (last_size) {
477
 
            if (last_size < _HEAP_ALIGNMENT)
478
 
                last_size += heap->chunk;
479
 
            size = heap->size - f->size + last_size;
480
 
        } else {
481
 
            SHEAP_Block* b = (SHEAP_Block*) heap->base, *p = 0;
482
 
            while (b != f) {
483
 
                p = b;
484
 
                b = (SHEAP_Block*)((char*) b + b->size);
485
 
            }
486
 
            size = heap->size - f->size;
487
 
            assert(p);
488
 
            f = p;
 
524
        size = heap->size;
 
525
    } else if (!(last_size = f->size % heap->chunk)) {
 
526
        SHEAP_Block* b = (SHEAP_Block*) heap->base, *p = 0;
 
527
        while (b != f) {
 
528
            p = b;
 
529
            b = (SHEAP_Block*)((char*) b + b->size);
489
530
        }
 
531
        size = heap->size - f->size;
 
532
        f = p;
490
533
    } else {
491
 
        last_size = heap->chunk;
492
 
        size      = heap->chunk;
 
534
        if (last_size <= sizeof(*f))
 
535
            last_size = _HEAP_ALIGN(sizeof(*f) + 1, heap->chunk);
 
536
        size = heap->size - f->size + last_size;
493
537
    }
494
538
 
495
 
    assert(size % heap->chunk == 0);
496
 
    if (heap->expand) {
497
 
        void* base = (*heap->expand)(heap->base, size, heap->arg);
498
 
        if (!base)
 
539
    if (heap->resize) {
 
540
        void* base = (*heap->resize)(heap->base, size, heap->arg);
 
541
        if (!size)
 
542
            assert(!base);
 
543
        else if (!base)
499
544
            return 0;
500
545
        if (f) {
501
546
            ptrdiff_t dp = (char*) f - (char*) heap->base;
508
553
        heap->size = size;
509
554
    } else if (size != heap->size)
510
555
        CORE_LOG(eLOG_Error, "Heap Trim: Heap is not trimmable");
511
 
    return heap->size;
 
556
 
 
557
    assert(!heap->base == !heap->size);
 
558
    return heap;
512
559
}
513
560
 
514
561
 
515
 
HEAP HEAP_CopySerial(const HEAP heap, size_t extra, int serial)
 
562
HEAP HEAP_Copy(const HEAP heap, size_t extra, int serial)
516
563
{
517
564
    HEAP   newheap;
518
 
    void*  newbase;
519
 
 
 
565
    size_t size;
 
566
 
 
567
    if (!heap)
 
568
        return 0;
 
569
    assert(!heap->base == !heap->size);
 
570
 
 
571
    size  = HEAP_ALIGN(heap->size);
520
572
    extra = HEAP_ALIGN(extra);
521
 
    if (!heap ||
522
 
        !(newbase = malloc(HEAP_ALIGN(heap->size) + extra + sizeof(*newheap))))
 
573
    if (!(newheap = (HEAP)malloc(HEAP_ALIGN(sizeof(*newheap)) + size + extra)))
523
574
        return 0;
524
 
    memcpy(newbase, heap->base, heap->size);
525
 
    newheap = (HEAP)((char*) newbase + HEAP_ALIGN(heap->size) + extra);
526
 
    newheap->base   = newbase;
 
575
    newheap->base   = (heap->base
 
576
                       ? (char*) newheap + HEAP_ALIGN(sizeof(*newheap))
 
577
                       : 0);
527
578
    newheap->size   = heap->size;
528
579
    newheap->chunk  = 0/*read-only*/;
529
 
    newheap->expand = 0;
 
580
    newheap->resize = 0;
530
581
    newheap->arg    = 0;
531
 
    newheap->copy   = serial ? serial : 1/*copy*/;
 
582
    newheap->refc   = 1/*copy*/;
 
583
    newheap->serial = serial;
 
584
    if (heap->size) {
 
585
        memcpy((char*) newheap->base,  heap->base,           heap->size);
 
586
        memset((char*) newheap->base + heap->size, 0, size - heap->size);
 
587
    }
532
588
    return newheap;
533
589
}
534
590
 
535
591
 
 
592
HEAP HEAP_CopySerial(const HEAP heap, size_t extra, int serial)
 
593
{
 
594
    return HEAP_Copy(heap, extra, serial);
 
595
}
 
596
 
 
597
 
 
598
void HEAP_AddRef(HEAP heap)
 
599
{
 
600
    if (!heap)
 
601
        return;
 
602
    assert(!heap->base == !heap->size);
 
603
    if (heap->refc) {
 
604
        heap->refc++;
 
605
        assert(heap->refc);
 
606
    }
 
607
}
 
608
 
 
609
 
536
610
void HEAP_Detach(HEAP heap)
537
611
{
538
 
    if (heap)
539
 
        free(heap->copy ? heap->base : heap);
 
612
    if (!heap)
 
613
        return;
 
614
    assert(!heap->base == !heap->size);
 
615
    if (!heap->refc  ||  !--heap->refc) {
 
616
        memset(heap, 0, sizeof(*heap));
 
617
        free(heap);
 
618
    }
540
619
}
541
620
 
542
621
 
543
622
void HEAP_Destroy(HEAP heap)
544
623
{
545
 
    if (heap) {
546
 
        if (!heap->chunk && !heap->copy)
547
 
            CORE_LOG(eLOG_Warning, "Heap Destroy: Heap is read-only");
548
 
        else if (heap->expand/*NB: false for heap copies*/)
549
 
            (*heap->expand)(heap->base, 0, heap->arg);
550
 
        HEAP_Detach(heap);
551
 
    }
 
624
    if (!heap)
 
625
        return;
 
626
    assert(!heap->base == !heap->size);
 
627
    if (!heap->chunk  &&  !heap->refc)
 
628
        CORE_LOG(eLOG_Warning, "Heap Destroy: Heap is read-only");
 
629
    else if (heap->resize/*NB: NULL for heap copies*/)
 
630
        verify((*heap->resize)(heap->base, 0, heap->arg) == 0);
 
631
    HEAP_Detach(heap);
552
632
}
553
633
 
554
634
 
555
635
void* HEAP_Base(const HEAP heap)
556
636
{
557
 
    return heap ? heap->base : 0;
 
637
    if (!heap)
 
638
        return 0;
 
639
    assert(!heap->base == !heap->size);
 
640
    return heap->base;
558
641
}
559
642
 
560
643
 
561
644
TNCBI_Size HEAP_Size(const HEAP heap)
562
645
{
563
 
    return heap ? heap->size : 0;
 
646
    if (!heap)
 
647
        return 0;
 
648
    assert(!heap->base == !heap->size);
 
649
    return heap->size;
564
650
}
565
651
 
566
652
 
567
653
int HEAP_Serial(const HEAP heap)
568
654
{
569
 
    return heap ? heap->copy : 0;
 
655
    if (!heap)
 
656
        return 0;
 
657
    assert(!heap->base == !heap->size);
 
658
    return heap->serial;
570
659
}
571
660
 
572
661
 
573
662
/*
574
663
 * --------------------------------------------------------------------------
575
664
 * $Log: ncbi_heapmgr.c,v $
 
665
 * Revision 6.31  2006/04/28 16:19:44  lavr
 
666
 * Disable W4311 for MSVC/W64
 
667
 *
 
668
 * Revision 6.30  2006/03/06 20:26:00  lavr
 
669
 * Added a paranoid assert() to check ref.-count overflow
 
670
 *
 
671
 * Revision 6.29  2006/03/06 14:22:48  lavr
 
672
 * Cast (void*) to (char*) to allow ptr arithmetics
 
673
 *
 
674
 * Revision 6.28  2006/03/05 17:35:56  lavr
 
675
 * API revised to allow to create ref-counted heap copies
 
676
 *
576
677
 * Revision 6.27  2005/01/27 19:00:17  lavr
577
678
 * Explicit cast of malloc()ed memory
578
679
 *