Return to _arr_map.c CVS log

Up to [Research Unix] / researchv10no / cmd / cfront / libC / new

Annotation of researchv10no/cmd/cfront/libC/new/_arr_map.c, revision 1.1

1.1     ! root        1: /*ident        "@(#)C++env:lib/new/_arr_map.c  1.3" */
        !             2: /**************************************************************************
        !             3:                         Copyright (c) 1984 AT&T
        !             4:                           All Rights Reserved   
        !             5: 
        !             6:         THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T
        !             7:       
        !             8:         The copyright notice above does not evidence any        
        !             9:         actual or intended publication of such source code.
        !            10: 
        !            11: *****************************************************************************/
        !            12: 
        !            13: 
        !            14: // manage the global table of array pointers and counts
        !            15: #include <values.h>
        !            16: #include <new.h>
        !            17: 
        !            18: // !!!!  only works if sizeof(long) >= sizeof(void*)  !!!!
        !            19: 
        !            20: typedef void*  KEYTYP; // generic array address
        !            21: void   __insert_new_array(KEYTYP key, int count);
        !            22:        // key is a pointer to a new array.  It must
        !            23:        //      be non-zero
        !            24:        //      not already be in the table
        !            25:        // count is the number of elements in the array.  May be zero
        !            26: int    __remove_old_array(KEYTYP key);
        !            27:        // removes an old array from the table.  Returns the count or -1 if not found
        !            28: 
        !            29: // choose 2 <= DIGIT_SIZE <= 6
        !            30: // smaller numbers waste less space and are slower, larger numbers waste more
        !            31: // space and are faster
        !            32: 
        !            33: // control the size of blocks grabbed from the free store (and frequency of
        !            34: // allocations) with RECORDS_BLOCK_COUNT and NODES_BLOCK_COUNT
        !            35: 
        !            36: // a trie based on groups of DIGIT_SIZE bits from the key
        !            37: #define DIGIT_SIZE     5
        !            38: // each node contains 2 ** DIGIT_SIZE entries
        !            39: #define NODE_SIZE      (1 << DIGIT_SIZE)
        !            40: #define MASK_BITS      (1 << DIGIT_SIZE) - 1
        !            41: // a few low order bits are uninteresting and are rotated around to the top
        !            42: #define LOW_BITS       2
        !            43: #define LOW_MASK       ((1 << LOW_BITS) - 1)
        !            44: // the number of groups in a word
        !            45: #define POSITIONS      ((BITS(long) - 1) / DIGIT_SIZE + 1)
        !            46: // control the size of blocks grabbed from new
        !            47: #define RECORDS_BLOCK_COUNT    150
        !            48: #define NODES_BLOCK_COUNT      10
        !            49: 
        !            50: // avoid name space clashes
        !            51: #define pnd __pnd
        !            52: #define Node_Pool __Node_Pool
        !            53: #define Record_Pool __Record_Pool
        !            54: #define pnd_internal_node __pnd_internal_node
        !            55: 
        !            56: class pnd;
        !            57: class pnd_internal_node;
        !            58: 
        !            59: class RECORD {
        !            60: friend pnd;
        !            61: friend void    __insert_new_array(KEYTYP addr, int count);
        !            62:        inline void*    operator new(size_t);
        !            63:        inline void     operator delete(void* p, size_t);
        !            64:                inline RECORD(unsigned long k, int cnt);
        !            65:                inline ~RECORD();
        !            66:        unsigned long   key;    // rotated address of array
        !            67:        int     count;  // number of elements of array
        !            68: };
        !            69: 
        !            70: class Record_Pool;
        !            71: 
        !            72: class Record_shell {
        !            73: friend Record_Pool;
        !            74:        Record_shell*   next;
        !            75:        char    dummy[sizeof(RECORD) - sizeof(Record_shell*)];
        !            76: };
        !            77: 
        !            78: class Record_Pool {
        !            79: friend RECORD;
        !            80:        static Record_shell*    top;
        !            81:                Record_Pool();
        !            82:        Record_shell    slot[RECORDS_BLOCK_COUNT];
        !            83:        static void*    alloc() {
        !            84:                        if (top == 0)
        !            85:                                new Record_Pool;
        !            86:                        void*   ans = top;
        !            87:                        top = top->next;
        !            88:                        return ans;
        !            89:                }
        !            90:        static void     free(Record_shell* p) {
        !            91:                        p->next = top;
        !            92:                        top = p;
        !            93:                }
        !            94: };
        !            95: 
        !            96: inline void*
        !            97: RECORD::operator new(size_t)
        !            98: {
        !            99:        return Record_Pool::alloc();
        !           100: }
        !           101: inline void
        !           102: RECORD::operator delete(void* p, size_t)
        !           103: {
        !           104:        Record_Pool::free((Record_shell*)p);
        !           105: }
        !           106: 
        !           107: inline
        !           108: RECORD::RECORD(unsigned long k, int cnt)
        !           109: : key(k), count(cnt)
        !           110: {}
        !           111: 
        !           112: inline RECORD::~RECORD() {}
        !           113: 
        !           114: class pnd_internal_item {
        !           115: friend pnd;
        !           116: friend pnd_internal_node;
        !           117:        union   {
        !           118:                RECORD* ext_leaf;
        !           119:                pnd_internal_node*      nodep;
        !           120:        };
        !           121:        int     this_is_leaf;
        !           122:        int     is_node() { return !this_is_leaf && nodep; }
        !           123:        int     is_leaf() { return this_is_leaf; }
        !           124:        int     is_null() { return !nodep; }
        !           125:        pnd_internal_node*      next_node() { return nodep; }
        !           126:        RECORD* external_leaf() { return ext_leaf; }
        !           127:        void    make_leaf(RECORD* p) { this_is_leaf = 1; ext_leaf = p; }
        !           128:        void    make_node(pnd_internal_node* cp) { this_is_leaf = 0; nodep = cp; }
        !           129:        void    make_null() {this_is_leaf = 0; nodep = 0; }
        !           130: };
        !           131: 
        !           132: class Node_Pool;
        !           133: 
        !           134: class pnd_internal_node {
        !           135: friend pnd;
        !           136: friend void    __insert_new_array(KEYTYP key, int count);
        !           137:        inline void*    operator new(size_t i);
        !           138:        inline void     operator delete(void* p, size_t i);
        !           139:        pnd_internal_node();
        !           140:        inline ~pnd_internal_node();
        !           141:        pnd_internal_item       item[NODE_SIZE];
        !           142:        int     busy_count;
        !           143: };
        !           144:        
        !           145: class Node_shell {
        !           146: friend Node_Pool;
        !           147:        Node_shell*     next;
        !           148:        char    dummy[sizeof(pnd_internal_node) - sizeof(Node_shell*)];
        !           149: };
        !           150: 
        !           151: class Node_Pool {
        !           152: friend pnd_internal_node;
        !           153:        static Node_shell*      top;
        !           154:                Node_Pool();
        !           155:        Node_shell      slot[NODES_BLOCK_COUNT];
        !           156:        static void*    alloc() {
        !           157:                        if (top == 0)
        !           158:                                new Node_Pool;
        !           159:                        void*   ans = top;
        !           160:                        top = top->next;
        !           161:                        return ans;
        !           162:                }
        !           163:        static void     free(void* p) {
        !           164:                        ((Node_shell*)p)->next = top;
        !           165:                        top = (Node_shell*)p;
        !           166:                }
        !           167: };
        !           168: 
        !           169: inline void*
        !           170: pnd_internal_node::operator new(size_t)
        !           171: {
        !           172:        return Node_Pool::alloc();
        !           173: }
        !           174: inline void
        !           175: pnd_internal_node::operator delete(void* p, size_t)
        !           176: {
        !           177:        Node_Pool::free(p);
        !           178: }
        !           179: 
        !           180: inline pnd_internal_node::~pnd_internal_node() {}
        !           181: 
        !           182: class pnd  {
        !           183: friend void    __insert_new_array(KEYTYP key, int count);
        !           184: friend int     __remove_old_array(KEYTYP key);
        !           185:        static pnd*     the_table;
        !           186:        pnd_internal_item       contents;
        !           187:        // int  sze;
        !           188:                pnd();
        !           189:        static void     initialize();
        !           190:        void    insert(KEYTYP, int);
        !           191:        int     remove(KEYTYP); // returns count or -1 if not found
        !           192: };
        !           193: 
        !           194: void
        !           195: __insert_new_array(KEYTYP key, int count)
        !           196: {
        !           197:        if (pnd::the_table == 0)
        !           198:                pnd::initialize();
        !           199:        pnd::the_table->insert(key, count);
        !           200: }
        !           201: 
        !           202: int
        !           203: __remove_old_array(KEYTYP key)
        !           204: {
        !           205:        return pnd::the_table->remove(key);
        !           206: }
        !           207: 
        !           208: pnd_internal_node::pnd_internal_node()
        !           209: {
        !           210:        register pnd_internal_item*     itemp = &item[0];
        !           211:        register int i = NODE_SIZE;
        !           212:        while (i--)
        !           213:                (itemp++)->make_null();
        !           214:        busy_count = 0;
        !           215: }
        !           216: 
        !           217: void
        !           218: pnd::insert(KEYTYP addr, int cnt)
        !           219: {
        !           220:        register unsigned long  mask = MASK_BITS;
        !           221:        register unsigned long  key = (unsigned long)addr & LOW_MASK;
        !           222:        if (key)
        !           223:                key <<= BITS(long) - LOW_BITS;
        !           224:        key |= (unsigned long)addr >> LOW_BITS;
        !           225:        RECORD* new_rec = new RECORD(key, cnt);
        !           226:        register int    unshift = 0;
        !           227:        register pnd_internal_item*     itemp = &contents;
        !           228:        register pnd_internal_node*     nodep = 0;
        !           229:        for (;; mask <<= DIGIT_SIZE, unshift += DIGIT_SIZE) {
        !           230:                if (itemp->is_null())
        !           231:                        break;
        !           232:                if (itemp->is_leaf()) {
        !           233:                        if (itemp->external_leaf()->key == key){
        !           234:                                itemp->external_leaf()->count = cnt;
        !           235:                                delete new_rec;  // didn't need it after all
        !           236:                                return; // should rarely happen
        !           237:                        }
        !           238:                        break;
        !           239:                }
        !           240:                nodep = itemp->next_node();
        !           241:                // assert(nodep);
        !           242:                itemp = &nodep->item[(key & mask) >> unshift];
        !           243:        }
        !           244:        // sze++;
        !           245:        if (itemp->is_null()) {
        !           246:                itemp->make_leaf(new_rec);
        !           247:                if (nodep)
        !           248:                        nodep->busy_count++;
        !           249:                return;
        !           250:        }
        !           251:        // assert(itemp->is_leaf());
        !           252:        RECORD* temp = itemp->external_leaf();
        !           253:        unsigned long   other_key = temp->key;
        !           254:        // assert(other_key != key);
        !           255:        unsigned long   ind1, ind2;
        !           256:        for (;; mask <<= DIGIT_SIZE, unshift += DIGIT_SIZE) {
        !           257:                itemp->make_node(nodep = new pnd_internal_node);
        !           258:                // assert(pos.curr_depth < POSITIONS);
        !           259:                ind1 = (other_key & mask) >> unshift;
        !           260:                ind2 = (key & mask) >> unshift;
        !           261:                if (ind1 != ind2) break;        // I hope so!
        !           262:                nodep->busy_count = 1;
        !           263:                itemp = &nodep->item[ind1];
        !           264:        }
        !           265:        nodep->item[ind1].make_leaf(temp);
        !           266:        nodep->item[ind2].make_leaf(new_rec);
        !           267:        nodep->busy_count = 2;
        !           268:        return;
        !           269: }
        !           270: 
        !           271: int
        !           272: pnd::remove(KEYTYP addr)
        !           273: {
        !           274:        pnd_internal_item*      curr_pos[POSITIONS];
        !           275:        int     curr_depth;
        !           276:        if (addr == 0) return -1;
        !           277:        register unsigned long  mask = MASK_BITS;
        !           278:        register unsigned long  key = (unsigned long)addr & LOW_MASK;
        !           279:        if (key)
        !           280:                key <<= BITS(long) - LOW_BITS;
        !           281:        key |= (unsigned long)addr >> LOW_BITS;
        !           282:        register int    unshift = 0;
        !           283:        register pnd_internal_item*     itemp = &contents;
        !           284:        register pnd_internal_node*     nodep = 0;
        !           285:        for (curr_depth = -1;; mask <<= DIGIT_SIZE, unshift += DIGIT_SIZE) {
        !           286:                // assert(curr_depth < POSITIONS);
        !           287:                if (itemp->is_null())
        !           288:                        return -1;
        !           289:                if (itemp->is_leaf())
        !           290:                        if (itemp->external_leaf()->key == key)
        !           291:                                break;
        !           292:                        else
        !           293:                                return -1;
        !           294:                nodep = itemp->next_node();
        !           295:                // assert(nodep);
        !           296:                curr_pos[++curr_depth] = itemp =
        !           297:                                &nodep->item[(key & mask) >> unshift];
        !           298:        }
        !           299:        // assert(itemp->is_leaf());
        !           300:        // assert(itemp->external_leaf()->key == key);
        !           301:        RECORD* old_p = itemp->external_leaf();
        !           302:        // sze--;
        !           303:        int     ans = old_p->count;
        !           304:        delete old_p;
        !           305:        itemp->make_null();
        !           306:        if (curr_depth == -1 || // it was a singleton set
        !           307:                        --(nodep->busy_count) > 1)      // easy case
        !           308:                return ans;
        !           309:        // assert(nodep->busy_count == 1);
        !           310:        register pnd_internal_item*     itp = &nodep->item[0];
        !           311:        while (itp->is_null() || itp == itemp) itp++;
        !           312:        if (!itp->is_leaf())    // unfortunate case
        !           313:                return ans;
        !           314:        RECORD* temp = itp->external_leaf();
        !           315:        // assert(temp->key != key);
        !           316:        for (;;) {
        !           317:                delete nodep;
        !           318:                if (curr_depth-- == 0) {
        !           319:                        // assert(sze == 1);
        !           320:                        contents.make_leaf(temp);
        !           321:                        return ans;
        !           322:                }
        !           323:                nodep = curr_depth == 0 ? contents.next_node() :
        !           324:                                curr_pos[curr_depth-1]->next_node();
        !           325:                if (nodep->busy_count > 1) {
        !           326:                        curr_pos[curr_depth]->make_leaf(temp);
        !           327:                        return ans;
        !           328:                }
        !           329:                // assert(nodep->busy_count == 1);
        !           330:        }
        !           331: }
        !           332: 
        !           333: pnd::pnd()
        !           334: /* : sze(0) */
        !           335: {
        !           336:        contents.make_null();
        !           337: }
        !           338: 
        !           339: void
        !           340: pnd::initialize()
        !           341: {
        !           342:        the_table = new pnd;
        !           343: }
        !           344: 
        !           345: Record_Pool::Record_Pool()
        !           346: {
        !           347:        register int    i = RECORDS_BLOCK_COUNT;
        !           348:        register Record_shell*  p = slot;
        !           349:        register Record_shell*  q;
        !           350:        while (--i) {
        !           351:                q = p++;
        !           352:                q->next = p;
        !           353:        }
        !           354:        p->next = top;
        !           355:        top = slot;
        !           356: }
        !           357: 
        !           358: Node_Pool::Node_Pool()
        !           359: {
        !           360:        register int    i = NODES_BLOCK_COUNT;
        !           361:        register Node_shell*    p = slot;
        !           362:        register Node_shell*    q;
        !           363:        while (--i) {
        !           364:                q = p++;
        !           365:                q->next = p;
        !           366:        }
        !           367:        p->next = top;
        !           368:        top = slot;
        !           369: }
        !           370: 
        !           371: 

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