Return to st_alloc.c CVS log

Up to [MW Coherent from dump] / coherent / b / STREAMS / conf / streams / src

Annotation of coherent/b/STREAMS/conf/streams/src/st_alloc.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Main C routines for the quick heap manager.
        !             3:  *
        !             4:  * This implementation is directly derived from the article in which this
        !             5:  * algorithm first appeared ;
        !             6:  *
        !             7:  *     "Efficient Implementation of the First-Fit Strategy for Dynamic
        !             8:  *      Storage Allocation"
        !             9:  *     R. P. Brent, Australian National University
        !            10:  *     ACM Transactions on Programming Languages and Systems
        !            11:  *     Volume 11, No. 3, July 1989 pp 388-403.
        !            12:  */
        !            13: 
        !            14: /*
        !            15:  *-IMPORTS:
        !            16:  *     <common/ccompat.h>
        !            17:  *             __CONST__
        !            18:  *             __USE_PROTO__
        !            19:  *             __ARGS ()
        !            20:  *     <common/xdebug.h>
        !            21:  *             __LOCAL__
        !            22:  *     <stddef.h>
        !            23:  *             NULL
        !            24:  */
        !            25: 
        !            26: #include <common/ccompat.h>
        !            27: #include <common/xdebug.h>
        !            28: #include <stddef.h>
        !            29: 
        !            30: #include <kernel/st_alloc.h>
        !            31: 
        !            32: 
        !            33: /*
        !            34:  * Since this code can be used in an embedded environment, we may not want to
        !            35:  * use the C library version of assert () to report errors. On the other hand,
        !            36:  * in a hosted environment we might.
        !            37:  */
        !            38: 
        !            39: #if    _HOSTED
        !            40: 
        !            41: #include <assert.h>
        !            42: 
        !            43: #define        ASSERT(x)       assert (x)
        !            44: 
        !            45: #else
        !            46: 
        !            47: #include <sys/debug.h>
        !            48: 
        !            49: #endif
        !            50: 
        !            51: 
        !            52: /*
        !            53:  * In several places in the code we need to adjust pointer values by +1 or -1
        !            54:  * to account for the space taken up the by the links between adjacent
        !            55:  * blocks, allocated or not.
        !            56:  *
        !            57:  * Here we define some private macros to help deal with this. While it is
        !            58:  * correct and reasonably documented as it stands, we will likely want to
        !            59:  * implement a variant algorithm that does not keep allocated blocks on a
        !            60:  * list. This should reduce both search time and space overhead, with the
        !            61:  * expense of requiring the user to supply the original block size. For now,
        !            62:  * we pay both penalties.
        !            63:  */
        !            64: 
        !            65: #define _ST_WORD_S     sizeof (_ST_WORD_T)
        !            66: 
        !            67: #define        _ST_AHDR_SIZE   1               /* word size of an allocated header */
        !            68: 
        !            69: #define        _ST_BYTE2WORD(s) ((s + (1 + _ST_AHDR_SIZE) * _ST_WORD_S - 1) / _ST_WORD_S)
        !            70:                                        /*
        !            71:                                         * _ST_BYTE2WORD () converts a size
        !            72:                                         * passed in by a client into a block
        !            73:                                         * word size, which includes space
        !            74:                                         * for the allocated-block header.
        !            75:                                         */
        !            76: #define        _ST_WORD2BYTE(s) ((s - _ST_AHDR_SIZE) * _ST_WORD_S)
        !            77:                                        /*
        !            78:                                         * _ST_WORD2BYTE () reverses the
        !            79:                                         * mapping given by _ST_BYTE2WORD ().
        !            80:                                         */
        !            81: #define        _ST_ADDR2PTR(q,a)       ((__VOID__ *) a)
        !            82:                                        /*
        !            83:                                         * Mapping from an _ST_ADDR_T to a
        !            84:                                         * user pointer to real memory.
        !            85:                                         */
        !            86: #define        _ST_PTR2ADDR(q,a)       ((_ST_WORD_T *) a)
        !            87:                                        /*
        !            88:                                         * Mapping from a user pointer to
        !            89:                                         * an _ST_ADDR_T.
        !            90:                                         */
        !            91: 
        !            92: #define        _ST_BUCKET_BASE(q,b) (q->_arena_base + (b) * q->_words_per_bucket)
        !            93: 
        !            94: /*
        !            95:  * This function does some general checks on the consistency of the contents
        !            96:  * of the _ST_HEAP_CONTROL block passed as "q". If the contents of the control
        !            97:  * block (and the auxiliary arrays which are part of it) do not pass muster,
        !            98:  * then the _qheap_error member of the control block is set, and the function
        !            99:  * returns an error indication.
        !           100:  *
        !           101:  * The return value is 0 if the control block tested OK, -1 if it did not.
        !           102:  */
        !           103: 
        !           104: #if    __USE_PROTO__
        !           105: int (st_assert) (_ST_HEAP_CONTROL_P q)
        !           106: #else
        !           107: int
        !           108: st_assert __ARGS ((q))
        !           109: _ST_HEAP_CONTROL_P     q;
        !           110: #endif
        !           111: {
        !           112:        _ST_ADDR_T      scan;
        !           113:        int             count, cntl, bucket;
        !           114: 
        !           115:        scan = _ST_BUCKET_BASE (q, 0);
        !           116: 
        !           117:        for (bucket = 0 ; bucket < q->_buckets_inuse ; bucket ++) {
        !           118:                _ST_ADDR_T      end;
        !           119:                int             max;
        !           120: 
        !           121: 
        !           122:                if ((end = _ST_BUCKET_BASE (q, bucket + 1)) > q->_arena_end)
        !           123:                        end = q->_arena_end;
        !           124: 
        !           125:                /*
        !           126:                 * Verify that _ST_HEAP_FIRST () points within the bucket,
        !           127:                 * to the current value of scan if there are blocks in this
        !           128:                 * bucket.
        !           129:                 */
        !           130: 
        !           131: 
        !           132:                if (scan < end &&
        !           133:                    _ST_HEAP_FIRST (q, bucket) != scan) {
        !           134: 
        !           135:                        _ST_SET_ERROR (q, "Bad first block pointer in bucket");
        !           136:                        return -1;
        !           137:                } else if (scan >= end && _ST_HEAP_FIRST (q, bucket) < end) {
        !           138: 
        !           139:                        _ST_SET_ERROR (q, "First block pointer should be pointing past bucket end");
        !           140:                        return -1;
        !           141:                }
        !           142: 
        !           143: 
        !           144:                /*
        !           145:                 * Walk over the contents of the bucket to verify the maximum
        !           146:                 * block size within the bucket. We also check here for
        !           147:                 * consecutive unmerged free blocks.
        !           148:                 */
        !           149: 
        !           150:                count = max = 0;
        !           151: 
        !           152:                while (scan < end) {
        !           153: 
        !           154:                        cntl = _ST_BLOCK_CONTROL (q, scan);
        !           155: 
        !           156:                        if (_ST_BLOCK_FREE (cntl)) {    /* block is free */
        !           157: 
        !           158:                                if (cntl > max)
        !           159:                                        max = cntl;
        !           160: 
        !           161:                                if (++ count > 1) {
        !           162: 
        !           163:                                        _ST_SET_ERROR (q, "Adjacent free blocks not merged");
        !           164:                                        return -1;
        !           165:                                }
        !           166:                        } else                          /* block in use */
        !           167:                                count = 0;
        !           168: 
        !           169:                        scan = _ST_HEAP_NEXT (scan, cntl);
        !           170:                }
        !           171: 
        !           172:                if (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) != max) {
        !           173: 
        !           174:                        _ST_SET_ERROR (q, "Incorrect maximum free block size");
        !           175:                        return -1;
        !           176:                }
        !           177: 
        !           178: 
        !           179:                /*
        !           180:                 * Check for unmerged free blocks between bucket boundaries.
        !           181:                 */
        !           182: 
        !           183:                if (count != 0 && scan < q->_arena_end &&
        !           184:                    _ST_BLOCK_FREE (_ST_BLOCK_CONTROL (q, scan))) {
        !           185: 
        !           186:                        _ST_SET_ERROR (q, "Unmerged free blocks between block boundaries");
        !           187:                        return -1;
        !           188:                }
        !           189:        }
        !           190: 
        !           191: 
        !           192:        if (scan != q->_arena_end) {
        !           193: 
        !           194:                _ST_SET_ERROR (q, "Last block too large!");
        !           195:                return -1;
        !           196:        }
        !           197: 
        !           198:        return 0;
        !           199: }
        !           200: 
        !           201: 
        !           202: /*
        !           203:  * st_double () doubles the depth of the index heap, assuming that
        !           204:  * _buckets_inuse < _buckets_maximum / 2
        !           205:  *
        !           206:  * For internal use only.
        !           207:  */
        !           208: 
        !           209: #if    __USE_PROTO__
        !           210: __LOCAL__ void (st_double) (_ST_HEAP_CONTROL_P q)
        !           211: #else
        !           212: __LOCAL__ void
        !           213: st_double __ARGS ((q))
        !           214: _ST_HEAP_CONTROL_P     q;
        !           215: #endif
        !           216: {
        !           217:        int i,k;
        !           218: 
        !           219:        ASSERT (q->_buckets_inuse * 2 <= q->_buckets_maximum);
        !           220: 
        !           221: 
        !           222:        /*
        !           223:         * The new buckets don't have any blocks starting within them, so
        !           224:         * set the base address over the top.
        !           225:         */
        !           226: 
        !           227:        k = q->_buckets_inuse;
        !           228:        for (i = 0 ; i < k ; i ++)
        !           229:                q->_bucket_first [i + k] = q->_arena_end;
        !           230: 
        !           231:        /*
        !           232:         * The bucket size heap needs to be expanded by copying the maximum
        !           233:         * sizes down for the preexisting buckets, and inserting zeroes for
        !           234:         * the new buckets.
        !           235:         *      eg      max(b1,b2) b1 b2
        !           236:         *      becomes max(b1,b2) max(b1,b2) 0 b1 b2 0 0
        !           237:         */
        !           238: 
        !           239:        for (; k > 0 ; k >>= 1)
        !           240:                for (i = 0 ; i < k ; i ++) {
        !           241: 
        !           242:                        _ST_HEAP_BIGGEST (q, 2 * k + i) = _ST_HEAP_BIGGEST (q, k + i);
        !           243:                        _ST_HEAP_BIGGEST (q, 3 * k + i) = 0;
        !           244:                }
        !           245: 
        !           246:        q->_buckets_inuse <<= 1;
        !           247: }
        !           248: 
        !           249: 
        !           250: /*
        !           251:  * st_reduced () does the housekeeping necessary if a block with control word
        !           252:  * at "a" has been allocated, or merged with a block on it's left in a
        !           253:  * different segment. Note that we count on a block having been freed/
        !           254:  * allocated and having a valid control word.
        !           255:  *
        !           256:  * It should be that case that the _ST_HEAP_FIRST () has already been updated
        !           257:  * in order for this routine to correctly calculate the sizes
        !           258:  *
        !           259:  * This implementation modifies this function, in that a test
        !           260:  *     if (BlockIsFree && CurrentMaximum > SizeOfNewBlock)
        !           261:  *             return;
        !           262:  * from the C transliteration of the published algorithm has been moved out
        !           263:  * to the callers of this function. This allows the callers to use a block
        !           264:  * size value cached in their locals to perform the calculation, rather than
        !           265:  * making this function fetch the control word for the block. This is NOT
        !           266:  * an important size/speed optimisation (although parts of the original test
        !           267:  * have been elided in the broken-out version), rather it allows algorithms
        !           268:  * like realloc () considerably more latitude in the order in which things
        !           269:  * are done.
        !           270:  *
        !           271:  * This function was called blfix1 () in the published algorithm. The original
        !           272:  * algorithm passed in the block address, but since we have moved the check
        !           273:  * discussed above outside, we only need the bucket number.
        !           274:  */
        !           275: 
        !           276: #if    __USE_PROTO__
        !           277: __LOCAL__ void (st_reduced) (_ST_HEAP_CONTROL_P q, int bucket)
        !           278: #else
        !           279: __LOCAL__ void
        !           280: st_reduced __ARGS ((q, bucket))
        !           281: _ST_HEAP_CONTROL_P     q;
        !           282: int                    bucket;
        !           283: #endif
        !           284: {
        !           285:        _ST_ADDR_T first, next;
        !           286:        _ST_WORD_T max;
        !           287: 
        !           288: #if 0  /* this test moved out to our callers */
        !           289:        /*
        !           290:         * if (BlockIsFree && CurrentMaximum > SizeOfNewBlock) then there
        !           291:         * is nothing to be done to segment "bucket".
        !           292:         */
        !           293: 
        !           294:        max = _ST_BLOCK_CONTROL (q, a);
        !           295:        if (_ST_BLOCK_FREE (max) &&
        !           296:            _ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) > _ST_BLOCK_SIZE (max))
        !           297:                return;
        !           298: #endif
        !           299: 
        !           300:        /*
        !           301:         * Work out address of first block in "current" bucket, and the
        !           302:         * base address of the "next" bucket. Note that we have to test to
        !           303:         * see if "next" winds up past the end of space because the total
        !           304:         * size of the arena may not divide evenly into buckets..
        !           305:         */
        !           306: 
        !           307:        first = _ST_HEAP_FIRST (q, bucket);
        !           308:        next = q->_arena_base + (bucket + 1) * q->_words_per_bucket;
        !           309: 
        !           310:        if (next >= q->_arena_end)
        !           311:                next = q->_arena_end;
        !           312: 
        !           313:        /*
        !           314:         * Calculate (by walking the block chain) the new maximum size free
        !           315:         * block in this bucket, which may now be empty.
        !           316:         */
        !           317: 
        !           318:        max = 0;
        !           319:        while (first < next) {  /* There is a block starting in this bucket */
        !           320:                _ST_WORD_T cntl = _ST_BLOCK_CONTROL (q, first);
        !           321: 
        !           322:                ASSERT (cntl != 0);
        !           323: 
        !           324:                if (max < cntl)
        !           325:                        max = cntl;
        !           326: 
        !           327:                first = _ST_HEAP_NEXT (first, cntl);
        !           328:        }
        !           329: 
        !           330: 
        !           331:        /*
        !           332:         * Now propagate the new maximum size information up the heap.
        !           333:         */
        !           334: 
        !           335:        bucket += q->_buckets_inuse;
        !           336:        _ST_HEAP_BIGGEST (q, 0) = 0;    /* sentinel */
        !           337: 
        !           338:        while (_ST_HEAP_BIGGEST (q, bucket) > max) {
        !           339:                int temp;
        !           340: 
        !           341:                _ST_HEAP_BIGGEST (q, bucket) = max;
        !           342: 
        !           343:                temp = _ST_HEAP_BIGGEST (q, _ST_BUCKET_SIBLING (bucket));
        !           344:                if (max < temp)
        !           345:                        max = temp;
        !           346: 
        !           347:                bucket = _ST_BUCKET_PARENT (bucket);
        !           348:        }
        !           349: }
        !           350: 
        !           351: 
        !           352: /*
        !           353:  * st_grown () does the housekeeping necessary after a block with control word
        !           354:  * at "a" is freed, or merged with a block on its right, or created by
        !           355:  * splitting (with "a" on the right of the split, in a different bucket than
        !           356:  * the start of the original block that was split)
        !           357:  *
        !           358:  * This function was called blfix2 () in the published algorithm.
        !           359:  */
        !           360: 
        !           361: #if    __USE_PROTO__
        !           362: __LOCAL__ void (st_grown) (_ST_HEAP_CONTROL_P q, _ST_ADDR_T a, int bucket)
        !           363: #else
        !           364: __LOCAL__ void
        !           365: st_grown __ARGS ((q, a, bucket))
        !           366: _ST_HEAP_CONTROL_P     q;
        !           367: _ST_ADDR_T             a;
        !           368: int                    bucket;
        !           369: #endif
        !           370: {
        !           371:        int     max;
        !           372: 
        !           373:        ASSERT (bucket == _ST_HEAP_BUCKET (q, a));
        !           374: 
        !           375: 
        !           376:        /*
        !           377:         * Expand the number of buckets in the heap if necessary.
        !           378:         */
        !           379: 
        !           380:        while (bucket >= q->_buckets_inuse)
        !           381:                st_double (q);
        !           382: 
        !           383:        /*
        !           384:         * This may be a new first free block.
        !           385:         */
        !           386: 
        !           387:        if (_ST_HEAP_FIRST (q, bucket) > a)
        !           388:                _ST_HEAP_FIRST (q, bucket) = a;
        !           389: 
        !           390:        /*
        !           391:         * Propagate changed block-size information upwards through heap.
        !           392:         */
        !           393: 
        !           394:        bucket += q->_buckets_inuse;
        !           395:        max = _ST_BLOCK_CONTROL (q, a);
        !           396:        _ST_HEAP_BIGGEST (q, 0) = max;  /* sentinel */
        !           397: 
        !           398:        while (_ST_HEAP_BIGGEST (q, bucket) < max) {
        !           399: 
        !           400:                _ST_HEAP_BIGGEST (q, bucket) = max;
        !           401: 
        !           402:                bucket = _ST_BUCKET_PARENT (bucket);
        !           403:        }
        !           404: }
        !           405: 
        !           406: 
        !           407: /*
        !           408:  * Returns the predecessor block to "a", which is guaranteed to exist thanks
        !           409:  * to the dummy first block.
        !           410:  *
        !           411:  * If the address passed in does not belong to a valid block then the value
        !           412:  * returned is the same value that was passed in, ie "a".
        !           413:  */
        !           414: 
        !           415: #if    __USE_PROTO__
        !           416: __LOCAL__ _ST_ADDR_T (st_pred) (_ST_HEAP_CONTROL_P q, _ST_ADDR_T a, int bucket)
        !           417: #else
        !           418: __LOCAL__ _ST_ADDR_T
        !           419: st_pred __ARGS ((q, a, bucket))
        !           420: _ST_HEAP_CONTROL_P     q;
        !           421: _ST_ADDR_T             a;
        !           422: int                    bucket;
        !           423: #endif
        !           424: {
        !           425:        _ST_ADDR_T prev, scan;
        !           426: 
        !           427:        ASSERT (bucket == _ST_HEAP_BUCKET (q, a));
        !           428: 
        !           429: 
        !           430:        /*
        !           431:         * If the passed-in block is the first in the bucket, then the
        !           432:         * predecessor lives in the rightmost non-empty bucket to the left.
        !           433:         */
        !           434: 
        !           435:        if (_ST_HEAP_FIRST (q, bucket) == a) {
        !           436:                /*
        !           437:                 * We walk the heap to find the nearest bucket on the left
        !           438:                 * that has a free block in it, as buckets that do not
        !           439:                 * contain free blocks may not contain a valid "first block"
        !           440:                 * entry, since due to block coalescence these entries may
        !           441:                 * refer to blocks which have been combined with others.
        !           442:                 *
        !           443:                 * st_pred () is the only code which is affected by this.
        !           444:                 */
        !           445: 
        !           446:                bucket += q->_buckets_inuse;
        !           447: 
        !           448:                _ST_HEAP_BIGGEST (q, 0) = 1;    /* boundary */
        !           449: 
        !           450:                while (_ST_HEAP_BIGGEST (q, bucket - 1) == 0)
        !           451:                        bucket = _ST_BUCKET_PARENT (bucket);
        !           452: 
        !           453:                /*
        !           454:                 * Code here fixes two known "defects" in the original
        !           455:                 * published algorithm.
        !           456:                 *  (i) In the case where "bucket" above could reach the root
        !           457:                 *      node (eg, every word of storage had been previously
        !           458:                 *      allocated), the "bucket" would go to zero and the
        !           459:                 *      descend code would loop indefinitely.
        !           460:                  * (ii) In the case where storage in the left subtree of the
        !           461:                  *     heap relative to the initial point is completely
        !           462:                 *      allocated, the code to climb the heap will eventually
        !           463:                 *      look into the next higher level of the heap once
        !           464:                  *     "bucket" became a power of two (unless defect (i)
        !           465:                 *      occurred instead) and as a result would descend into
        !           466:                 *      the wrong part of the heap.
        !           467:                 *
        !           468:                 * We check here for "bucket" being a power of two, in which
        !           469:                 * case we snap the result of the search to the lowest bucket
        !           470:                 * on the left.
        !           471:                 */
        !           472: 
        !           473: #define        IS_POWER_OF_TWO(n) (((n - 1) ^ n) >= n)
        !           474: 
        !           475:                if (! IS_POWER_OF_TWO (bucket)) {
        !           476: 
        !           477:                        bucket --;
        !           478: 
        !           479:                        while (bucket < q->_buckets_inuse) {
        !           480: 
        !           481:                                bucket = 2 * bucket + 1;
        !           482:                                if (_ST_HEAP_BIGGEST (q, bucket) <= 0)
        !           483:                                        bucket --;
        !           484:                        }
        !           485: 
        !           486:                        bucket -= q->_buckets_inuse;
        !           487:                } else
        !           488:                        bucket = 0;
        !           489:        }
        !           490: 
        !           491: 
        !           492:        /*
        !           493:         * Either way, find the predecessor block by following the internal
        !           494:         * block linkage within this bucket.
        !           495:         */
        !           496: 
        !           497:        scan = _ST_HEAP_FIRST (q, bucket);
        !           498:        do {
        !           499:                prev = scan;
        !           500:                scan = _ST_HEAP_NEXT (scan, _ST_BLOCK_CONTROL (q, scan));
        !           501: 
        !           502:                ASSERT (prev != scan);
        !           503:        } while (scan < a);
        !           504: 
        !           505:        if (scan != a) {
        !           506: 
        !           507:                _ST_SET_ERROR (q, "Unable to find previous for block");
        !           508:                return a;       /* flag error by returning same */
        !           509:        }
        !           510: 
        !           511:        return prev;
        !           512: }
        !           513: 
        !           514: 
        !           515: /*
        !           516:  * Returns the index of a block of at least "size" words, or 0 if no such
        !           517:  * block exists.
        !           518:  */
        !           519: 
        !           520: #if    __USE_PROTO__
        !           521: __VOID__ * (st_alloc) (_ST_HEAP_CONTROL_P q, size_t size)
        !           522: #else
        !           523: __VOID__ *
        !           524: st_alloc __ARGS ((q, size))
        !           525: _ST_HEAP_CONTROL_P     q;
        !           526: size_t                 size;
        !           527: #endif
        !           528: {
        !           529:        int             n, bucket, cntl;
        !           530:        _ST_ADDR_T      scan;
        !           531: 
        !           532:        /*
        !           533:         * Before we begin, convert the size_t passed in into a word count.
        !           534:         * Note that we assume that the integer division of a size_t will
        !           535:         * be optimised by the compiler into an appropriate number of right-
        !           536:         * shifts (since a size_t is always unsigned, right?).
        !           537:         *
        !           538:         * We store the result into an integer because the free/used
        !           539:         * comparison means we involve the sign bit.
        !           540:         */
        !           541: 
        !           542:        n = _ST_BYTE2WORD (size);       /* includes header size */
        !           543: 
        !           544: 
        !           545:        /*
        !           546:         * Since the node at the top of the size heap contains the size of
        !           547:         * the largest available block, quickly determine whether or not
        !           548:         * this request can be satisfied at all.
        !           549:         */
        !           550: 
        !           551:        if (_ST_HEAP_BIGGEST (q, 1) < n)
        !           552:                return 0;
        !           553: 
        !           554: 
        !           555:        /*
        !           556:         * Now traverse the heap to find the first bucket containing a block
        !           557:         * of sufficient size to satisfy the request.
        !           558:         */
        !           559: 
        !           560:        bucket = 1;
        !           561: 
        !           562:        while (bucket < q->_buckets_inuse) {
        !           563: 
        !           564:                bucket = 2 * bucket;
        !           565:                if (_ST_HEAP_BIGGEST (q, bucket) < n)
        !           566:                        bucket ++;
        !           567:        }
        !           568: 
        !           569:        bucket -= q->_buckets_inuse;
        !           570: 
        !           571: 
        !           572:        /*
        !           573:         * Now traverse the internal linkage within the bucket to find the
        !           574:         * first block of the requisite size.
        !           575:         */
        !           576: 
        !           577:        scan = _ST_HEAP_FIRST (q, bucket);
        !           578: 
        !           579:        while ((cntl = _ST_BLOCK_CONTROL (q, scan)) < n) {
        !           580: 
        !           581:                ASSERT (cntl != 0);
        !           582:                scan = _ST_HEAP_NEXT (scan, cntl);
        !           583:        }
        !           584: 
        !           585: 
        !           586:        /*
        !           587:         * Now "scan" contains the index of the control word of the
        !           588:         * desired block.
        !           589:         */
        !           590: 
        !           591:        _ST_BLOCK_SET_USED (q, scan, n);
        !           592: 
        !           593: 
        !           594:        /*
        !           595:         * The published algorithm used a variable here to hold the result
        !           596:         * of a test on the basis that the call to st_grown () below might
        !           597:         * change the result. Actually, st_grown () would not change the
        !           598:         * result, but since st_grown () may call st_double () and alter
        !           599:         * the offset of the leaf layer of the block heap, that would
        !           600:         * invalidate his test. Since our "bucket" does not have that offset
        !           601:         * built into it, we perform the test when needed.
        !           602:         *
        !           603:         * Note that we still perform st_grown () before st_reduced (), as
        !           604:         * in the original. The reason for this was not explicated, but
        !           605:         * appears to be because doing it in this order may reduce the
        !           606:         * average number of heap nodes visited due to the particular heap
        !           607:         * update termination conditions.
        !           608:         */
        !           609: 
        !           610:        /*
        !           611:         * If necessary, split block; this may require a call to st_grown ()
        !           612:         * if the block created by the split is not in the same bucket.
        !           613:         */
        !           614: 
        !           615:        if (cntl > n) {
        !           616:                _ST_ADDR_T      next = _ST_HEAP_NEXT (scan, n);
        !           617:                int             next_bucket;
        !           618: 
        !           619:                _ST_BLOCK_SET_FREE (q, next, cntl - n);
        !           620: 
        !           621:                if ((next_bucket = _ST_HEAP_BUCKET (q, next)) > bucket)
        !           622:                        st_grown (q, next, next_bucket);
        !           623:        }
        !           624: 
        !           625:        if (cntl == _ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse))
        !           626:                st_reduced (q, bucket);
        !           627: 
        !           628:        return _ST_ADDR2PTR (q, _ST_HEAP_NEXT (scan, _ST_AHDR_SIZE));
        !           629: }
        !           630: 
        !           631: 
        !           632: /*
        !           633:  * Release a block of memory obtained using st_alloc (), where "a" is the
        !           634:  * memory word index that was returned by st_alloc ().
        !           635:  *
        !           636:  * Note that this function comes in two flavours, depending on whether you
        !           637:  * want clients to have to pass in the block-size.
        !           638:  */
        !           639: 
        !           640: #if    __USE_PROTO__
        !           641: int (st_free) (_ST_HEAP_CONTROL_P q, __VOID__ * a ST_FREE_SIZE (size_t size))
        !           642: #else
        !           643: int
        !           644: #ifdef USE_ST_SIZE
        !           645: st_free __ARGS ((q, a, size))
        !           646: size_t                 size;
        !           647: #else
        !           648: st_free __ARGS ((q, a))
        !           649: #endif
        !           650: _ST_HEAP_CONTROL_P     q;
        !           651: __VOID__             * a;
        !           652: #endif
        !           653: {
        !           654:        int             bucket, cntl, temp;
        !           655:        _ST_ADDR_T      prev, next, addr;
        !           656:        int             reduce = 0;     /* optimisation flag, see below */
        !           657: 
        !           658:        addr = _ST_HEAP_NEXT_RAW (_ST_PTR2ADDR (q, a), - _ST_AHDR_SIZE);
        !           659: 
        !           660:        cntl = _ST_BLOCK_CONTROL (q, addr);
        !           661: 
        !           662:        if (_ST_BLOCK_FREE (cntl))
        !           663:                return -1;              /* Block already free */
        !           664: 
        !           665:        cntl = _ST_BLOCK_SIZE (cntl);
        !           666: 
        !           667: #ifdef USE_ST_SIZE
        !           668:        /*
        !           669:         * As discussed in st_alloc (), we convert a passed-in byte count
        !           670:         * into a word count to isolate the clients from the notion of
        !           671:         * what we are using as a "word".
        !           672:         *
        !           673:         * The expression we want to test is
        !           674:         *      cntl == ceil (size / sizeof (_ST_WORD_T)) + 1
        !           675:         * where the + 1 factor is for the block size header.
        !           676:         */
        !           677: 
        !           678:        if (cntl != _ST_BYTE2WORD (size))
        !           679:                return -2;              /* Block size mismatch */
        !           680: #endif
        !           681: 
        !           682:        bucket = _ST_HEAP_BUCKET (q, addr);
        !           683: 
        !           684: 
        !           685:        /*
        !           686:         * Locate the previous block. Note that we attempt this operation
        !           687:         * considerably earlier than we really need to; this is done since
        !           688:         * it is the only really reliable way of verifying that the address
        !           689:         * given to this routine really does belong to a block that was
        !           690:         * allocated with st_alloc ().
        !           691:         *
        !           692:         * (Note that the above statement is only true for versions of the
        !           693:         * algorithm that maintain allocated blocks on the block list)
        !           694:         */
        !           695: 
        !           696:        if ((prev = st_pred (q, addr, bucket)) == addr)
        !           697:                return -3;              /* not a valid block */
        !           698: 
        !           699:        /*
        !           700:         * Now that we have performed some sanity checks, free the block.
        !           701:         */
        !           702: 
        !           703:        _ST_BLOCK_SET_FREE (q, addr, cntl);
        !           704: 
        !           705: 
        !           706:        /*
        !           707:         * Check the next rightmost block to see if we should merge with it.
        !           708:         */
        !           709: 
        !           710:        next = _ST_HEAP_NEXT (addr, cntl);
        !           711: 
        !           712:        if (next < q->_arena_end &&
        !           713:            _ST_BLOCK_FREE (temp = _ST_BLOCK_CONTROL (q, next))) {
        !           714:                /*
        !           715:                 * Merge the new block with its immediate neighbour on the
        !           716:                 * right. Note that we elide the _ST_BLOCK_SIZE () of temp
        !           717:                 * immediately below because _ST_BLOCK_SET_FREE masks the
        !           718:                 * third argument anyway.
        !           719:                 */
        !           720: 
        !           721:                _ST_BLOCK_SET_FREE (q, addr, cntl += temp);
        !           722: 
        !           723:                temp = _ST_HEAP_BUCKET (q, next);
        !           724: 
        !           725:                /*
        !           726:                 * Do we need to recalculate the maximum block size
        !           727:                 * for the block that "next" is in ? Yes, iff
        !           728:                 * heap_biggest (temp) == block_size (next).
        !           729:                 * We elide the call to _ST_BLOCK_SIZE below since
        !           730:                 * we know the block is free, hence needs no masking.
        !           731:                 */
        !           732: 
        !           733:                reduce = _ST_HEAP_BIGGEST (q, temp + q->_buckets_inuse) ==
        !           734:                                _ST_BLOCK_CONTROL (q, next);
        !           735:                ASSERT (_ST_HEAP_BIGGEST (q, temp + q->_buckets_inuse) >=
        !           736:                                _ST_BLOCK_CONTROL (q, next));
        !           737:                if (temp > bucket) {
        !           738: 
        !           739:                        _ST_HEAP_FIRST (q, temp) = _ST_HEAP_NEXT (addr, cntl);
        !           740: 
        !           741:                        if (reduce) {
        !           742: 
        !           743:                                st_reduced (q, temp);
        !           744:                                reduce = 0;
        !           745:                        }
        !           746:                } else
        !           747:                        ASSERT (_ST_HEAP_FIRST (q, temp) != next);
        !           748:        }
        !           749: 
        !           750: 
        !           751:        /*
        !           752:         * Check the next leftmost block to see if we should merge with it.
        !           753:         */
        !           754:        /*
        !           755:         * Optimisation note: the published version of the algorithm
        !           756:         * does a normal call to st_reduced () below. However, since we
        !           757:         * are freeing a block, we note that the only circumstance where
        !           758:         * this will be at all necessary is when the block we are freeing
        !           759:         * was merged with a block on it's right which was the previous
        !           760:         * largest free block (or at least the same size). We can thus
        !           761:         * reduce the number of calls to st_reduced () by putting in an
        !           762:         * extra guard condition with a flag set above.
        !           763:         *
        !           764:         * Is this worth the effort? Let's profile it and see.
        !           765:         */
        !           766: 
        !           767:        if (_ST_BLOCK_FREE (temp = _ST_BLOCK_CONTROL (q, prev))) {
        !           768: 
        !           769:                _ST_BLOCK_SET_FREE (q, prev, cntl += temp);
        !           770: 
        !           771:                /*
        !           772:                 * If we are merging with a block in a previous bucket, then
        !           773:                 * we must adjust our "first block" and call st_reduced () to
        !           774:                 * update the size heap.
        !           775:                 */
        !           776: 
        !           777:                if (_ST_HEAP_FIRST (q, bucket) == addr) {
        !           778: 
        !           779:                        _ST_HEAP_FIRST (q, bucket) = _ST_HEAP_NEXT (prev, cntl);
        !           780: 
        !           781:                        /*
        !           782:                         * As discussed above, we call st_reduced () iff
        !           783:                         * we have merged with a block on the right of a
        !           784:                         * size that indicates recomputing is necessary.
        !           785:                         */
        !           786: 
        !           787:                        if (reduce) {
        !           788: 
        !           789:                                ASSERT (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) <=
        !           790:                                        _ST_BLOCK_CONTROL (q, addr));
        !           791:                                st_reduced (q, bucket);
        !           792:                        }
        !           793: 
        !           794:                        /*
        !           795:                         * We cannot incrementally update "bucket" since
        !           796:                         * "prev" may refer to address a number of buckets
        !           797:                         * prior to "addr".
        !           798:                         */
        !           799: 
        !           800:                        bucket = _ST_HEAP_BUCKET (q, prev);
        !           801:                }
        !           802: 
        !           803:                st_grown (q, prev, bucket);
        !           804: 
        !           805:        } else if (cntl > _ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse)) {
        !           806:                /*
        !           807:                 * The total size of the newly freed block exceeds the
        !           808:                 * previous maximum block size of the current bucket, so call
        !           809:                 * st_grown () to update the size heap.
        !           810:                 *
        !           811:                 * Note that st_alloc () calls st_grown () without performing
        !           812:                 * the size test like we do, because st_alloc () may want the
        !           813:                 * heap size doubled. Here, that cannot happen, so we avoid
        !           814:                 * the call.
        !           815:                 */
        !           816: 
        !           817:                st_grown (q, addr, bucket);
        !           818:        }
        !           819: 
        !           820:        return 0;
        !           821: }
        !           822: 
        !           823: 
        !           824: #ifndef        _ST_BLOCK_COPY
        !           825: 
        !           826: /*
        !           827:  * Helper function which supplies a default block-copy routine for the
        !           828:  * st_realloc () function in case there is no special-purpose copy routine
        !           829:  * in the target environment.
        !           830:  */
        !           831: 
        !           832: #if    __USE_PROTO__
        !           833: __LOCAL__  void (st_copy) (_ST_WORD_T * dest, __CONST__ _ST_WORD_T * src,
        !           834:                           size_t copywords)
        !           835: #else
        !           836: __LOCAL__ void
        !           837: st_copy __ARGS ((dest, src, copywords))
        !           838: _ST_WORD_T           * dest;
        !           839: _ST_WORD_T           * src;
        !           840: size_t                 copywords;
        !           841: #endif
        !           842: {
        !           843:        while (copywords --)
        !           844:                * dest ++ = * src ++;
        !           845: }
        !           846: 
        !           847: #define        _ST_BLOCK_COPY(q,d,s,n) st_copy (_ST_HEAP_ADDR (q, d), _ST_HEAP_ADDR(q, s), n)
        !           848: 
        !           849: #endif /* ! defined (_ST_BLOCK_COPY) */
        !           850: 
        !           851: 
        !           852: /*
        !           853:  * Request that the block of memory at address "a" be grown (or shrunk) in
        !           854:  * size to "newsize" bytes (possibly from "oldsize" bytes). The returned
        !           855:  * value is the base address of the new block of memory, which may be
        !           856:  * different than the old address. If the block was moved, then the contents
        !           857:  * are guarenteed to be preserved bit-for-bit, but the client must take
        !           858:  * responsibility for relocating pointers.
        !           859:  *
        !           860:  * If it is not possible for the allocator to either grow or relocate the
        !           861:  * block due to a lack of space, st_realloc () returns 0, which for us can
        !           862:  * never be a valid return address. In this case, the original block has been
        !           863:  * left untouched.
        !           864:  *
        !           865:  * Note that this function comes in two flavours, depending on whether you
        !           866:  * want clients to have to pass in the block-size.
        !           867:  *
        !           868:  * --------------------------------------------------------------------------
        !           869:  *
        !           870:  * Design note: there are many, many ways that this function could be
        !           871:  * implemented, depending on how sensitive you are to issues of code size,
        !           872:  * execution speed, or arena space efficiency.
        !           873:  *
        !           874:  * The possible checks are (in order of execution time reduction)
        !           875:  *   (i) Check to see if the block can be extended upwards,
        !           876:  *  (ii) Find the previous block to see if it can be extended downwards,
        !           877:  * (iii) See if we can grow both down and up to fulfil the request,
        !           878:  *  (iv) Find any other block of sufficient size to fulfil the request.
        !           879:  *
        !           880:  * The primary criterion I have set for this routine is that it must always
        !           881:  * succeed in finding memory to saisfy the request. Note that the number of
        !           882:  * cases that this produces as a result is extremely large, but that it seems
        !           883:  * better to fulfil a user's request than to fail it simply on the basis that
        !           884:  * we want the common case to be fast.
        !           885:  *
        !           886:  * For now, we'll prefer not to copy, and reduce our code size by just
        !           887:  * relying on st_alloc () and st_free () for the worst case... but be aware
        !           888:  * that it might be a good idea to set a "realloc mode" in the heap control
        !           889:  * block that specifies how we order operations in the case where we break
        !           890:  * out the details of new () and disp ().
        !           891:  */
        !           892: 
        !           893: #if    __USE_PROTO__
        !           894: __VOID__ * (st_realloc) (_ST_HEAP_CONTROL_P q, __VOID__ * a, size_t newsize
        !           895:                         ST_FREE_SIZE (size_t oldsize))
        !           896: #else
        !           897: __VOID__ *
        !           898: #ifdef USE_ST_SIZE
        !           899: st_realloc __ARGS ((q, a, newsize, oldsize))
        !           900: size_t                 oldsize;
        !           901: #else
        !           902: st_realloc __ARGS ((q, a, newsize))
        !           903: #endif
        !           904: _ST_HEAP_CONTROL_P     q;
        !           905: __VOID__             * a;
        !           906: size_t                 newsize;
        !           907: #endif
        !           908: {
        !           909:        int             bucket, cntl, prev_reduce, next_bucket, next_first;
        !           910:        int             delta;          /* block size change in words */
        !           911:        _ST_ADDR_T      prev, addr, next;
        !           912: 
        !           913:        addr = _ST_HEAP_NEXT_RAW (_ST_PTR2ADDR (q, a), -1);
        !           914: 
        !           915:        cntl = _ST_BLOCK_CONTROL (q, addr);
        !           916: 
        !           917:        if (_ST_BLOCK_FREE (cntl))
        !           918:                return (_ST_ADDR_T) -1; /* Block is free ! */
        !           919: 
        !           920:        cntl = _ST_BLOCK_SIZE (cntl);   /* work with free units */
        !           921: 
        !           922: 
        !           923:        /*
        !           924:         * Before we begin, let's convert newsize (and optionally oldsize)
        !           925:         * to word counts from byte counts. This may mean that both round
        !           926:         * to the same word count and we don't need to do anything (big win!)
        !           927:         */
        !           928: 
        !           929:        newsize = _ST_BYTE2WORD (newsize);
        !           930: 
        !           931: #ifdef USE_ST_SIZE
        !           932:        if (cntl != _ST_BYTE2WORD (oldsize))
        !           933:                return (_ST_ADDR_T) -2; /* Block size mismatch */
        !           934: #endif
        !           935:        if ((delta = newsize - cntl) == 0)
        !           936:                return a;               /* Already done! What service! */
        !           937: 
        !           938:        bucket = _ST_HEAP_BUCKET (q, addr);
        !           939: 
        !           940: 
        !           941:        /*
        !           942:         * Locate the previous block, so that we can see if we can grow
        !           943:         * down into it. Note that in the variant system where allocated
        !           944:         * blocks are not part of a chain (in order to save space) that by
        !           945:         * finding the previous free block we achieve an equivalent result,
        !           946:         * since we cannot grow down unless we have an adjacent free block.
        !           947:         *
        !           948:         * Note also that in the case where allocated blocks are not
        !           949:         * chained, finding the previous free block is a prerequisite to
        !           950:         * finding the subsequent free block.
        !           951:         */
        !           952: 
        !           953:        if ((prev = st_pred (q, addr, bucket)) == addr)
        !           954:                return (_ST_ADDR_T) -3; /* not a valid block */
        !           955: 
        !           956: 
        !           957:        /*
        !           958:         * Now that we have performed some sanity checks, look to see how
        !           959:         * we should grow the block.
        !           960:         */
        !           961: 
        !           962:        /*
        !           963:         * Check the next rightmost block to see if we can grow into it.
        !           964:         * If we are shrinking the allocation, this is trivially true.
        !           965:         *
        !           966:         * To save ourselves a local, we re-use "bucket" here as the amount
        !           967:         * of free space in the next rightmost block. We need to keep this
        !           968:         * value for the next test so that we can expand both up and down
        !           969:         * if necessary.
        !           970:         */
        !           971: 
        !           972:        bucket = 0;
        !           973:        prev_reduce = 0;
        !           974: 
        !           975:        if ((next = _ST_HEAP_NEXT (addr, cntl)) < q->_arena_end &&
        !           976:            _ST_BLOCK_FREE (cntl = _ST_BLOCK_CONTROL (q, next)))
        !           977:                bucket = cntl;  /* available adjacent words */
        !           978: 
        !           979:        if (bucket >= delta) {
        !           980:                /*
        !           981:                 * Whether we are growing or shrinking, we have enough room.
        !           982:                 * Set the block's new size, and skip to the common code below
        !           983:                 * which adjusts the right edge of a block by "delta" words.
        !           984:                 */
        !           985: 
        !           986:                ASSERT (next < q->_arena_end ||
        !           987:                        (next == q->_arena_end && delta < 0));
        !           988: 
        !           989:                _ST_BLOCK_SET_USED (q, addr, newsize);
        !           990: 
        !           991: 
        !           992:                /*
        !           993:                 * Go to the common exit sequence for in-place adjustment,
        !           994:                 * after setting "prev" to be the base of the block that we
        !           995:                 * will return to the user.
        !           996:                 */
        !           997: 
        !           998:                prev = addr;
        !           999: 
        !          1000:                goto adjust_right;
        !          1001:        }
        !          1002: 
        !          1003: 
        !          1004:        /*
        !          1005:         * Check the next leftmost block to see if we should move down. Note
        !          1006:         * that we add in the free size of the right block to the calculation
        !          1007:         * so that we can expand both down and up to fill space.
        !          1008:         *
        !          1009:         * Given that we have to copy, however, we'll drop to the bottom of
        !          1010:         * the available room.
        !          1011:         */
        !          1012: 
        !          1013:        if (_ST_BLOCK_FREE (cntl = _ST_BLOCK_CONTROL (q, prev)) &&
        !          1014:            (cntl + bucket) >= delta) {
        !          1015:                /*
        !          1016:                 * Well, we have enough space. Now, let's make "delta" equal
        !          1017:                 * to the amount by which we need to adjust the block on
        !          1018:                 * the right.
        !          1019:                 */
        !          1020: 
        !          1021:                delta -= cntl;
        !          1022: 
        !          1023: 
        !          1024:                /*
        !          1025:                 * We set the "prev" block as used now for st_reduced ().
        !          1026:                 */
        !          1027: 
        !          1028:                _ST_BLOCK_SET_USED (q, prev, newsize);
        !          1029: 
        !          1030: 
        !          1031:                /*
        !          1032:                 * Since we are vaporising the original block at "addr", we
        !          1033:                 * should deal with checking to see if it was the first block
        !          1034:                 * in it's bucket, otherwise we may wind up with a dangling
        !          1035:                 * pointer. For now, we just point it to the successor to
        !          1036:                 * "addr", and if this this does not turn out to be correct,
        !          1037:                 * the common code to move the LHS below will do the right
        !          1038:                 * thing.
        !          1039:                 */
        !          1040: 
        !          1041:                if (_ST_HEAP_FIRST (q, (bucket = _ST_HEAP_BUCKET (q, addr)))
        !          1042:                    == addr)
        !          1043:                        _ST_HEAP_FIRST (q, bucket) = next;
        !          1044: 
        !          1045:                /*
        !          1046:                 * If we want to move the block down, then we should update
        !          1047:                 * the heap information related to the block we are moving
        !          1048:                 * into before we move into it.
        !          1049:                 *
        !          1050:                 * Everything relating to what happens to the right edge of
        !          1051:                 * the block will be dealt with below, so all we have to do
        !          1052:                 * here is determine whether to call st_reduced ().
        !          1053:                 *
        !          1054:                 * We don't actually call st_reduced () here, since until the
        !          1055:                 * left edge has been dealt with there can be a temporary
        !          1056:                 * loss of block connectivity.
        !          1057:                 */
        !          1058: 
        !          1059:                bucket = _ST_HEAP_BUCKET (q, prev);
        !          1060: 
        !          1061:                if (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) == cntl)
        !          1062:                        prev_reduce = 1;
        !          1063: 
        !          1064:                /*
        !          1065:                 * Now, copy the original data from the block at "addr". How
        !          1066:                 * much to copy? Re-fetch the block size from the control
        !          1067:                 * word for now, although this may have to change to use
        !          1068:                 * "oldsize" if this is changed to use a variant algorithm
        !          1069:                 * where allocated blocks are not part of a list.
        !          1070:                 *
        !          1071:                 * How to perform the copy? Each target system will probably
        !          1072:                 * have it's own routine for performing a word-aligned, word-
        !          1073:                 * counted, upward-only high-speed block copy. Here, we
        !          1074:                 * request the services of that routine, with a default
        !          1075:                 * provided just prior to this code in case there is no
        !          1076:                 * special facility for that purpose.
        !          1077:                 *
        !          1078:                 * Note that we perform the move now because there is no way
        !          1079:                 * that the move can invalidate the block header (if any) in
        !          1080:                 * the rightmost block. We know this because the size that we
        !          1081:                 * are copying by is the size of the original block, and we
        !          1082:                 * are moving down, so we can't write over anything after the
        !          1083:                 * original block.
        !          1084:                 */
        !          1085: 
        !          1086:                _ST_BLOCK_COPY (q, _ST_HEAP_NEXT (prev, _ST_AHDR_SIZE),
        !          1087:                                _ST_HEAP_NEXT (addr, _ST_AHDR_SIZE),
        !          1088:                                _ST_BLOCK_SIZE (_ST_BLOCK_CONTROL (q, addr)) - _ST_AHDR_SIZE);
        !          1089: 
        !          1090:                /*
        !          1091:                 * Now, do the common part.
        !          1092:                 */
        !          1093: 
        !          1094:                ASSERT (_ST_HEAP_NEXT (next, delta) ==
        !          1095:                                _ST_HEAP_NEXT (prev, newsize));
        !          1096: 
        !          1097:                goto adjust_right;
        !          1098:        }
        !          1099: 
        !          1100: 
        !          1101:        /*
        !          1102:         * We have tried to move the block more-or-less in place, and the
        !          1103:         * some of the block and both neighbours does not yield enough space,
        !          1104:         * so we try and realloc () the naive way, using st_alloc () and
        !          1105:         * st_free (). We re-use these routines and just adjust for the fact
        !          1106:         * that they measure sizes in bytes rather than duplicating the code.
        !          1107:         *
        !          1108:         * Please note that the "prev" returned by st_alloc () has already
        !          1109:         * had the adjustment by 1 word to skip over the control block.
        !          1110:         */
        !          1111: 
        !          1112: 
        !          1113:        if ((prev = _ST_PTR2ADDR (q, st_alloc (q, _ST_WORD2BYTE (newsize))))
        !          1114:            == 0)
        !          1115:                return 0;
        !          1116: 
        !          1117: 
        !          1118:        /*
        !          1119:         * Do the block copy of the original contents and release them.
        !          1120:         * See the discussion above on the block copier.
        !          1121:         *
        !          1122:         * Note that we pass the address "a" into st_free (), as "addr" is
        !          1123:         * adjusted to point at the control word.
        !          1124:         */
        !          1125: 
        !          1126:        _ST_BLOCK_COPY (q, prev, _ST_HEAP_NEXT (addr, _ST_AHDR_SIZE),
        !          1127:                        _ST_BLOCK_SIZE (_ST_BLOCK_CONTROL (q, addr)) - _ST_AHDR_SIZE);
        !          1128: 
        !          1129:        if (st_free (q, a ST_FREE_SIZE (oldsize)) != 0) {
        !          1130:                /*
        !          1131:                 * What the duece! Throw the bums out on their ears!
        !          1132:                 */
        !          1133: 
        !          1134:                ASSERT (1 == 0);
        !          1135:        }
        !          1136: 
        !          1137: 
        !          1138:        return _ST_ADDR2PTR (q, prev);
        !          1139: 
        !          1140: 
        !          1141:        /*
        !          1142:         * Perform the necessary adjustments to the index heap for the
        !          1143:         * event that is happening on the right-hand side of the original
        !          1144:         * block. The block boundary on the right is being moved by "delta"
        !          1145:         * words from it's *original* location, ie the block at "next" is
        !          1146:         * being either grown by -delta or shrunk by delta, or remaining
        !          1147:         * unaffected. If next is being shrunk, then we know at this point
        !          1148:         * that "next" is free. If it's being grown, then "next" could be
        !          1149:         * either free or allocated, so we may have to create a new block.
        !          1150:         */
        !          1151: 
        !          1152: adjust_right:
        !          1153: 
        !          1154:        /*
        !          1155:         * Common case: fetch the current statistics of the "next" block and
        !          1156:         * set us up so that we point at the location of the new block.
        !          1157:         */
        !          1158: 
        !          1159:        if (next < q->_arena_end) {
        !          1160: 
        !          1161:                cntl = _ST_BLOCK_CONTROL (q, next);
        !          1162:                bucket = _ST_HEAP_BUCKET (q, next);
        !          1163: 
        !          1164:                /*
        !          1165:                 * We record whether or not "next" has an _ST_HEAP_FIRST ()
        !          1166:                 * pointer looking at it so we can update it below depending
        !          1167:                 * on how we move things around.
        !          1168:                 */
        !          1169: 
        !          1170:                next_first = _ST_HEAP_FIRST (q, bucket) == next;
        !          1171:        } else {
        !          1172:                /*
        !          1173:                 * Treat the end of the world as an allocated block.
        !          1174:                 */
        !          1175: 
        !          1176:                cntl = -1;
        !          1177:                next_first = bucket = 0;
        !          1178:        }
        !          1179: 
        !          1180:        next = _ST_HEAP_NEXT (next, delta);
        !          1181:        next_bucket = _ST_HEAP_BUCKET (q, next);
        !          1182: 
        !          1183: 
        !          1184:        if (delta > 0) {                /* eat into "next", which is free */
        !          1185:                /*
        !          1186:                 * If we need to, make the _ST_HEAP_FIRST () pointer track
        !          1187:                 * the block. Note that there is no harm in this if "next"
        !          1188:                 * actually lives a few buckets along, in fact it's required
        !          1189:                 * that if there's no blocks in the bucket, _ST_HEAP_FIRST ()
        !          1190:                 * must point beyond the end of the bucket.
        !          1191:                 */
        !          1192: 
        !          1193:                if (next_first)
        !          1194:                        _ST_HEAP_FIRST (q, bucket) = next;
        !          1195: 
        !          1196:                /*
        !          1197:                 * Grow up into our neighbour. This case is basically
        !          1198:                 * identical to the regular allocation algorithm except that
        !          1199:                 * we don't have to reserve space for a new control word.
        !          1200:                 *
        !          1201:                 * The comments in st_alloc () also apply here, see above.
        !          1202:                 *
        !          1203:                 * Note that since we know that "next" is free, we also know
        !          1204:                 * that "cntl" is a positive integer and doesn't need masking.
        !          1205:                 */
        !          1206: 
        !          1207:                if (cntl > delta) {
        !          1208:                        /*
        !          1209:                         * Create a free block, which may cause a call to
        !          1210:                         * st_grown () if it begins in another bucket. Like
        !          1211:                         * st_alloc (), we call st_grown () whether or not
        !          1212:                         * it needs to propagate size information up the
        !          1213:                         * index heap, because we may require that the size
        !          1214:                         * of the index heap be doubled as a side-effect of
        !          1215:                         * the overflow into the next bucket.
        !          1216:                         */
        !          1217: 
        !          1218:                        _ST_BLOCK_SET_FREE (q, next, cntl - delta);
        !          1219: 
        !          1220:                        if (next_bucket > bucket)
        !          1221:                                st_grown (q, next, next_bucket);
        !          1222:                } else {
        !          1223:                        /*
        !          1224:                         * In this case, "next" has been completely eaten
        !          1225:                         * up, so we just let the common code below deal with
        !          1226:                         * shrinking the "biggest free".
        !          1227:                         *
        !          1228:                         * I make lots of gratuitous assertions, don't I?
        !          1229:                         */
        !          1230: 
        !          1231:                        ASSERT (cntl == delta);
        !          1232:                }
        !          1233: 
        !          1234: 
        !          1235:                /*
        !          1236:                 * Regardless of whether we have created a new block, we
        !          1237:                 * should see whether we should adjust the "largest free"
        !          1238:                 * for the bucket, according to the usual rules.
        !          1239:                 */
        !          1240: 
        !          1241:                if (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) == cntl)
        !          1242:                        st_reduced (q, bucket);
        !          1243:        } else if (delta < 0) {         /* "-delta" free words below "next" */
        !          1244:                /*
        !          1245:                 * This code is the inverse of the above, except that we
        !          1246:                 * may not be affecting the actual "next" block if it is
        !          1247:                 * in use.
        !          1248:                 *
        !          1249:                 * Note that in this scenario, "next_bucket" has the inverse
        !          1250:                 * of the normal relation to "bucket", since it may be below
        !          1251:                 * "bucket".
        !          1252:                 */
        !          1253: 
        !          1254:                _ST_BLOCK_SET_FREE (q, next, (_ST_BLOCK_FREE (cntl) ? cntl : 0)
        !          1255:                                                - delta);
        !          1256: 
        !          1257:                if (next_bucket < bucket) {
        !          1258: 
        !          1259:                        _ST_HEAP_FIRST (q, bucket) =
        !          1260:                                _ST_HEAP_NEXT (next, _ST_BLOCK_CONTROL (q, next));
        !          1261: 
        !          1262:                        /*
        !          1263:                         * We don't want to call st_reduced () if the original
        !          1264:                         * "next" block wasn't free. It won't hurt things,
        !          1265:                         * but it wastes time. However, since "cntl" is
        !          1266:                         * negative in that case, the test below will always
        !          1267:                         * fail in that situation.
        !          1268:                         */
        !          1269: 
        !          1270:                        if (_ST_HEAP_BIGGEST (q, bucket + q->_buckets_inuse) == cntl)
        !          1271:                                st_reduced (q, bucket);
        !          1272:                }
        !          1273: 
        !          1274: 
        !          1275:                if (_ST_BLOCK_CONTROL (q, next) > _ST_HEAP_BIGGEST (q, next_bucket + q->_buckets_inuse))
        !          1276:                        st_grown (q, next, next_bucket);
        !          1277:        }
        !          1278: 
        !          1279:        if (prev_reduce != 0)
        !          1280:                st_reduced (q, _ST_HEAP_BUCKET (q, prev));
        !          1281: 
        !          1282: 
        !          1283:        return _ST_ADDR2PTR (q, _ST_HEAP_NEXT (prev, 1));
        !          1284: }
        !          1285: 
        !          1286: 
        !          1287: /*
        !          1288:  * Initialise an arena.
        !          1289:  */
        !          1290: 
        !          1291: #if    __USE_PROTO__
        !          1292: void (st_init) (_ST_HEAP_CONTROL_P q)
        !          1293: #else
        !          1294: void
        !          1295: st_init __ARGS ((q))
        !          1296: _ST_HEAP_CONTROL_P     q;
        !          1297: #endif
        !          1298: {
        !          1299:        q->_heap_error = NULL;
        !          1300:        q->_buckets_inuse = 1;
        !          1301:        q->_words_per_bucket = (q->_arena_size + q->_buckets_maximum - 1)
        !          1302:                                        / q->_buckets_maximum;
        !          1303: 
        !          1304:        _ST_HEAP_BIGGEST (q, 1) = q->_arena_size;
        !          1305: 
        !          1306:        _ST_HEAP_FIRST (q, 0) = q->_arena_base;
        !          1307: 
        !          1308:        _ST_BLOCK_SET_FREE (q, q->_arena_base, q->_arena_size);
        !          1309: 
        !          1310:        /*
        !          1311:         * Create dummy sentinel block.
        !          1312:         */
        !          1313: 
        !          1314:        st_alloc (q, 0);
        !          1315: 
        !          1316:        return;
        !          1317: }
        !          1318: 
        !          1319: 
        !          1320: /*
        !          1321:  * As above, but a full construction.
        !          1322:  */
        !          1323: 
        !          1324: #if    __USE_PROTO__
        !          1325: void (st_ctor) (_ST_HEAP_CONTROL_P q, int segs, size_t arensize,
        !          1326:                _ST_ADDR_T arenabase)
        !          1327: #else
        !          1328: void
        !          1329: st_ctor __ARGS ((q, segs, arensize, arenabase))
        !          1330: _ST_HEAP_CONTROL_P     q;
        !          1331: int                    segs;
        !          1332: size_t                 arensize;
        !          1333: _ST_ADDR_T             arenabase;
        !          1334: #endif
        !          1335: {
        !          1336:        q->_buckets_maximum = segs;
        !          1337:        q->_arena_size = arensize;
        !          1338:        q->_arena_base = (_ST_ADDR_T) arenabase;
        !          1339:        q->_arena_end = _ST_HEAP_NEXT (arenabase, arensize);
        !          1340: 
        !          1341:        q->_bucket_biggest = (_ST_WORD_T *) (q + 1);
        !          1342:        q->_bucket_first = (_ST_ADDR_T *) (q->_bucket_biggest + segs * 2);
        !          1343: 
        !          1344:        /*
        !          1345:         * Perform regular initialisation.
        !          1346:         */
        !          1347: 
        !          1348:        st_init (q);
        !          1349: }
        !          1350: 
        !          1351: 
        !          1352: /*
        !          1353:  * Return a size suitable for requesting the largest currently available
        !          1354:  * block of memory.
        !          1355:  *
        !          1356:  * Thanks to the way the index heap is constructed, this is in fact
        !          1357:  * trivially implementable.
        !          1358:  */
        !          1359: 
        !          1360: #if    __USE_PROTO__
        !          1361: size_t (st_maxavail) (_ST_HEAP_CONTROL_P q)
        !          1362: #else
        !          1363: size_t
        !          1364: st_maxavail __ARGS ((q))
        !          1365: _ST_HEAP_CONTROL_P     q;
        !          1366: #endif
        !          1367: {
        !          1368:        return _ST_WORD2BYTE (_ST_HEAP_BIGGEST (q, 0));
        !          1369: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.