Return to ordered.c CVS log

Up to [Research Unix] / researchv10no / ipc / mgrs / ns

Annotation of researchv10no/ipc/mgrs/ns/ordered.c, revision 1.1

1.1     ! root        1: #include <fio.h>
        !             2: #include <string.h>
        !             3: #include <libc.h>
        !             4: #include "dbtypes.h"
        !             5: 
        !             6: #define MAXDEPTH 32
        !             7: 
        !             8: /*
        !             9:  *  free the pointer list
        !            10:  */
        !            11: Ordered::~Ordered()
        !            12: {
        !            13:        if(ptr) {
        !            14:                free((char *)ptr);
        !            15:        }
        !            16: }
        !            17: 
        !            18: /*
        !            19:  *  Create the head of an ordered list.  It has `l' pointers and all
        !            20:  *  point nowhere.
        !            21:  */
        !            22: Ordered::Ordered(int l)
        !            23: {
        !            24:        int i;
        !            25: 
        !            26:        if(l>MAXDEPTH)
        !            27:                l = MAXDEPTH;
        !            28:        level = l-1;
        !            29:        ptr = (Ordered **)malloc(l*sizeof(Ordered *));
        !            30:        for(i=0; i<l; i++)
        !            31:                ptr[i] = (Ordered *)0;
        !            32: }
        !            33: 
        !            34: /*
        !            35:  *  insert a node into a list
        !            36:  */
        !            37: void
        !            38: Ordered::insert(Ordered *o)
        !            39: {
        !            40:        register Ordered *cp;
        !            41:        register int i;
        !            42:        Ordered *cptr[MAXDEPTH];
        !            43: 
        !            44:        /*
        !            45:         *  start all search pointers at the list head
        !            46:         */
        !            47:        cptr[o->level] = o;
        !            48: 
        !            49:        /*
        !            50:         *  find the last entry <= this one
        !            51:         */
        !            52:        for(i=o->level; i>=0; i--){
        !            53:                while(cp=cptr[i]->ptr[i]){
        !            54:                        if(cp->compare(this)>0)
        !            55:                                break;
        !            56:                        cptr[i] = cp;
        !            57:                }
        !            58:                if(i>0)
        !            59:                        cptr[i-1] = cptr[i];
        !            60:        }
        !            61: 
        !            62:        /*
        !            63:         *  pick a depth 
        !            64:         */
        !            65:        level = o->level+1;
        !            66:        i = nrand((1<<level)-1)+1;
        !            67:        for(; i; i = i>>1)
        !            68:                level--;
        !            69: 
        !            70:        /*
        !            71:         *  chain it after current nodes
        !            72:         */
        !            73:        ptr = (Ordered **)malloc((level+1)*sizeof(Ordered *));
        !            74:        for(i=0; i<=level; i++) {
        !            75:                ptr[i] = cptr[i]->ptr[i];
        !            76:                cptr[i]->ptr[i] = this;
        !            77:        }
        !            78: }
        !            79: 
        !            80: /*
        !            81:  *  search an ordered list
        !            82:  */
        !            83: Ordered *
        !            84: Ordered::search(Ordered *o)
        !            85: {
        !            86:        register int i, rv;
        !            87:        Ordered *cptr[MAXDEPTH];
        !            88: 
        !            89:        /*
        !            90:         *  start all search pointers at the list head
        !            91:         */
        !            92:        cptr[o->level] = o;
        !            93: 
        !            94:        /*
        !            95:         *  Find the first entry matching this key.  Note that
        !            96:         *  we return only if we find a match at level 0.  Otherwise
        !            97:         *  we may not find the first match.
        !            98:         */
        !            99:        for(i=o->level; i>=0; i--){
        !           100:                while(cptr[i]->ptr[i]){
        !           101:                        rv = cptr[i]->ptr[i]->compare(this);
        !           102:                        if(rv==0 && i==0)
        !           103:                                return cptr[i]->ptr[i];
        !           104:                        if(rv>=0)
        !           105:                                break;
        !           106:                        cptr[i] = cptr[i]->ptr[i];
        !           107:                }
        !           108:                if(i>0)
        !           109:                        cptr[i-1] = cptr[i];
        !           110:        }
        !           111: 
        !           112:        return (Ordered *)0;
        !           113: }
        !           114: 
        !           115: /*
        !           116:  *  output an ordered list
        !           117:  */
        !           118: void
        !           119: Ordered::printlist(int fd)
        !           120: {
        !           121:        Ordered *o;
        !           122: 
        !           123:        for(o=ptr[0]; o; o=o->ptr[0]){
        !           124:                Fprint(fd, "%d: ", o->level);
        !           125:                o->print(fd);
        !           126:                Fprint(fd, "\n");
        !           127:        }
        !           128: }
        !           129: 
        !           130: /*
        !           131:  *  output an ordered list element
        !           132:  */
        !           133: void
        !           134: Ordered::print(int fd)
        !           135: {
        !           136:        Fprint(fd, "element");
        !           137: }
        !           138: 
        !           139: /*
        !           140:  *  compare two ordered list elements
        !           141:  */
        !           142: int
        !           143: Ordered::compare(Ordered *o)
        !           144: {
        !           145:        return o-this;
        !           146: }

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