Return to ordered.c CVS log

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

Annotation of researchv10dc/ipc/mgrs/ns/ordered.c, revision 1.1.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.