Return to st_alloc.h CVS log

Up to [MW Coherent from dump] / coherent / f / usr / include / kernel

Annotation of coherent/f/usr/include/kernel/st_alloc.h, revision 1.1

1.1     ! root        1: #ifndef __KERNEL_ST_ALLOC_H__
        !             2: #define        __KERNEL_ST_ALLOC_H__
        !             3: 
        !             4: /*
        !             5:  *-IMPORTS:
        !             6:  *     <common/ccompat.h>
        !             7:  *             __CONST__
        !             8:  *             __PROTO__
        !             9:  *             __VOID__
        !            10:  *             __PROTO ()
        !            11:  *     <common/xdebug.h>
        !            12:  *             __LOCAL__
        !            13:  */
        !            14: 
        !            15: #include <limits.h>
        !            16: #include <common/ccompat.h>
        !            17: #include <common/xdebug.h>
        !            18: #include <common/_size.h>
        !            19: 
        !            20: 
        !            21: /*
        !            22:  * Definitions/declarations for the quick arena manager.
        !            23:  *
        !            24:  * The quick arena manager's basic algorithm utilizes a heap (in the sense
        !            25:  * defined below) to implement a binary-searchable index of block buckets
        !            26:  * ordered by size.
        !            27:  *
        !            28:  * The primariy characteristic of this algorithm is its' speed ; the growth
        !            29:  * rate of the execution time is O (log W), where W is the number of words in
        !            30:  * the arena being managed. 
        !            31:  *
        !            32:  * This implementation is directly derived from the article in which this
        !            33:  * algorithm first appeared;
        !            34:  *
        !            35:  *     "Efficient Implementation of the First-Fit Strategy for Dynamic
        !            36:  *      Storage Allocation"
        !            37:  *     R. P. Brent, Australian National University
        !            38:  *     ACM Transactions on Programming Languages and Systems
        !            39:  *     Volume 11, No. 3, July 1989 pp 388-403.
        !            40:  */
        !            41: 
        !            42: 
        !            43: /*
        !            44:  * This source code deviates somewhat from the terminology used in the
        !            45:  * article, due to the large number of ambiguous terms here. The following
        !            46:  * definitions are used exclusively in the commentary and selection of
        !            47:  * identifiers within this source code :
        !            48:  *
        !            49:  *     heap            a balanced binary tree with implicit links, esp.
        !            50:  *                     used to perform max/min calculations or binary search
        !            51:  *
        !            52:  *     arena           the memory area being managed
        !            53:  *
        !            54:  *     block           a single unit of contiguous allocated or free memory
        !            55:  *
        !            56:  *     bucket          a subsection of the heap containing zero or more
        !            57:  *                     blocks
        !            58:  */
        !            59: 
        !            60: 
        !            61: /*
        !            62:  * Definition of the type of an underlying machine address for each one of
        !            63:  * the pointer types used in the arena control structure.
        !            64:  *
        !            65:  * An interesting question : what type should be being used for the heap
        !            66:  * control words, short or long? If a short is used for the size of a
        !            67:  * control word, then we are limited to 64k bytes for the size of a single
        !            68:  * allocation arena.
        !            69:  */
        !            70: 
        !            71: typedef int                    _ST_WORD_T;
        !            72: 
        !            73: #if    INT_MAX > SHRT_MAX
        !            74: #define        _ST_SIZE_MASK           0x7FFFFFFF
        !            75: #define        _ST_FREE_MASK           0x80000000
        !            76: #else
        !            77: #define        _ST_SIZE_MASK           0x7FFF
        !            78: #define        _ST_FREE_MASK           0x8000
        !            79: #endif
        !            80: 
        !            81: typedef _ST_WORD_T           * _ST_ADDR_T;
        !            82: 
        !            83: #define        _ST_HEAP_ADDR(q,a)      (a)
        !            84: #define        _ST_HEAP_BUCKET(q,a)    (((char *) (a) - (char *) (q)->_arena_base) / ((q)->_words_per_bucket * sizeof (_ST_WORD_T)))
        !            85: 
        !            86: 
        !            87: /*
        !            88:  * For the control word of a block, it is *vital* that all used blocks
        !            89:  * compare as "<" with a free block, and that free blocks test as normal
        !            90:  * integers.
        !            91:  */
        !            92: 
        !            93: #define        _ST_BLOCK_CONTROL(q,a)          (* _ST_HEAP_ADDR (q, (a)))
        !            94: #define        _ST_BLOCK_SIZE(c)               ((c) & _ST_SIZE_MASK)
        !            95: #define        _ST_BLOCK_FREE(c)               (((c) & _ST_FREE_MASK) == 0)
        !            96: #define        _ST_BLOCK_SET_FREE(q,a,n)       (void) (_ST_BLOCK_CONTROL (q, (a)) = (n) & ~ _ST_FREE_MASK)
        !            97: #define        _ST_BLOCK_SET_USED(q,a,n)       (void) (_ST_BLOCK_CONTROL (q, (a)) = (n) | _ST_FREE_MASK)
        !            98: 
        !            99: 
        !           100: #define        _ST_HEAP_BIGGEST(q,s)   ((q)->_bucket_biggest [s])
        !           101: #define        _ST_HEAP_FIRST(q,s)     ((q)->_bucket_first [s])
        !           102: 
        !           103: #define        _ST_BUCKET_SIBLING(b)   (b ^ 1)
        !           104: #define        _ST_BUCKET_PARENT(b)    (b >>= 1)
        !           105: 
        !           106: #define        _ST_HEAP_NEXT(a,c)      ((_ST_ADDR_T) ((a) + _ST_BLOCK_SIZE (c)))
        !           107: #define        _ST_HEAP_NEXT_RAW(a,c)  ((_ST_ADDR_T) ((a) + (c)))
        !           108: 
        !           109: #define        _ST_SET_ERROR(q,e)      ((q)->_heap_error = (e))
        !           110: #define        _ST_HEAP_ERROR(q)       ((q)->_heap_error)
        !           111: 
        !           112: 
        !           113: /*
        !           114:  * Help clients initialise the arena.
        !           115:  */
        !           116: 
        !           117: #define        _ST_HEAP_CONTROL_SIZE(segs)\
        !           118:        (sizeof (struct _st_heap_control) + \
        !           119:                (segs) * (2 * sizeof (_ST_WORD_T) + sizeof (_ST_ADDR_T)))
        !           120: 
        !           121: /*
        !           122:  * Allocation control block. This block is normally followed by vectors
        !           123:  * containing a maximum block size heap and a vector defining the first free
        !           124:  * block in an allocation bucket.
        !           125:  */
        !           126: 
        !           127: struct _st_heap_control {
        !           128: 
        !           129:        int             _buckets_inuse;         /* number of active buckets */
        !           130:        int             _buckets_maximum;       /* maximum possible buckets */
        !           131:        int             _words_per_bucket;      /* memory words per bucket */
        !           132:        size_t          _arena_size;            /* total bytes in arena */
        !           133: 
        !           134:        _ST_WORD_T    * _bucket_biggest;        /* bucket size ordered heap */
        !           135:        _ST_ADDR_T    * _bucket_first;          /* address of first block */
        !           136:        _ST_ADDR_T      _arena_base;
        !           137:                                                /*
        !           138:                                                 * base address of the first
        !           139:                                                 * word in the arena, same as
        !           140:                                                 * _bucket_first [0]
        !           141:                                                 */
        !           142:        _ST_ADDR_T      _arena_end;
        !           143:                                                /*
        !           144:                                                 * Address of last word in
        !           145:                                                 * the arena +1
        !           146:                                                 */
        !           147:        __CONST__ char * _heap_error;
        !           148:                                                /*
        !           149:                                                 * If this heap is corrupt,
        !           150:                                                 * points to a string that
        !           151:                                                 * describes the problem
        !           152:                                                 */
        !           153: };
        !           154: 
        !           155: typedef struct _st_heap_control _ST_HEAP_CONTROL, * _ST_HEAP_CONTROL_P;
        !           156: 
        !           157: 
        !           158: /*
        !           159:  * As an additional check, we can make clients of st_disp () pass in the
        !           160:  * size of the block to free as (i) an additional assertion check against
        !           161:  * bugs, and (ii) because a faster/less overhead implementation of the
        !           162:  * algorithm might be possible where there is no header for allocated blocks
        !           163:  * (the free blocks contain a size and a pointer to the next free block).
        !           164:  */
        !           165: 
        !           166: #define        USE_ST_SIZE
        !           167: 
        !           168: #ifdef USE_ST_SIZE
        !           169: #define        ST_FREE_SIZE(x)         , x
        !           170: #else
        !           171: #define        ST_FREE_SIZE(x)
        !           172: #endif
        !           173: 
        !           174: 
        !           175: /*
        !           176:  * Public function prototypes
        !           177:  */
        !           178: 
        !           179: __EXTERN_C_BEGIN__
        !           180: 
        !           181: int            st_assert       __PROTO ((_ST_HEAP_CONTROL_P _q));
        !           182: __VOID__      *        st_alloc        __PROTO ((_ST_HEAP_CONTROL_P _q,
        !           183:                                          size_t _size));
        !           184: int            st_free         __PROTO ((_ST_HEAP_CONTROL_P _q,
        !           185:                                          __VOID__ * _a
        !           186:                                          ST_FREE_SIZE (size_t _size)));
        !           187: __VOID__      *        st_realloc      __PROTO ((_ST_HEAP_CONTROL_P _q,
        !           188:                                          __VOID__ * _a, size_t _newsize
        !           189:                                          ST_FREE_SIZE (size_t _oldsize)));
        !           190: void           st_init         __PROTO ((_ST_HEAP_CONTROL_P _q));
        !           191: void           st_ctor         __PROTO ((_ST_HEAP_CONTROL_P _q, int _segs,
        !           192:                                          size_t _arensize,
        !           193:                                          _ST_ADDR_T _arenabase));
        !           194: size_t         st_maxavail     __PROTO ((_ST_HEAP_CONTROL_P _q));
        !           195: 
        !           196: __EXTERN_C_END__
        !           197: 
        !           198: #endif /* ! defined (__KERNEL_ST_ALLOC_H__) */

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