Return to b1btr.h CVS log

Up to [CSRG BSD Unix] / 43BSD / contrib / B / src / bint

Annotation of 43BSD/contrib/B/src/bint/b1btr.h, revision 1.1

1.1     ! root        1: /* Copyright (c) Stichting Mathematisch Centrum, Amsterdam, 1985. */
        !             2: 
        !             3: /*
        !             4:   $Header: b1btr.h,v 1.4 85/08/22 16:41:40 timo Exp $
        !             5: */
        !             6: 
        !             7: /* Private definitions for the b-tree module */
        !             8: 
        !             9: #ifndef INTEGRATION
        !            10: 
        !            11: extern bool comp_ok;
        !            12: #define reqerr(s) error(s)
        !            13: 
        !            14: /*********************************************************************/
        !            15: /* items
        !            16: /*********************************************************************/
        !            17: 
        !            18: typedef char texitem;
        !            19: typedef value lisitem;
        !            20: typedef struct pair {value k, a;} tabitem;
        !            21: typedef struct onpair {value ka, u;} keysitem;
        !            22: typedef union itm {
        !            23:     texitem c;
        !            24:     lisitem l;
        !            25:     tabitem t;
        !            26: } item, *itemarray, *itemptr;
        !            27: 
        !            28: #define Charval(pitm) ((pitm)->c)
        !            29: #define Keyval(pitm) ((pitm)->l)
        !            30: #define Ascval(pitm) ((pitm)->t.a)
        !            31: 
        !            32: /* Xt = itemtype, do not change these, their order is used */
        !            33: #define Ct (0)
        !            34: #define Lt (1)
        !            35: #define Tt (2)
        !            36: #define Kt (3)
        !            37: 
        !            38: /* Itemwidth, used for offset in btreenodes */
        !            39: typedef char width;
        !            40: #define Itemwidth(it) (itemwidth[it])
        !            41: extern char itemwidth[];       /*  uses: */
        !            42: #define Cw (sizeof(texitem))
        !            43: #define Lw (sizeof(lisitem))
        !            44: #define Tw (sizeof(tabitem))
        !            45: #define Kw (sizeof(keysitem))
        !            46: 
        !            47: /*********************************************************************/
        !            48: /* sizes of btrees
        !            49: /*********************************************************************/
        !            50: 
        !            51: #define Bigsize (-1)
        !            52: #define Stail(r,s) ((r) > Maxint - (s) ? Bigsize : (r)+(s))
        !            53: #define Ssum(r,s)  ((r) EQ Bigsize || (s) EQ Bigsize ? Bigsize : Stail(r,s))
        !            54: #define Sincr(r)   ((r) EQ Bigsize ? Bigsize : Stail(r,1))
        !            55: #define Sadd2(r)   ((r) EQ Bigsize ? Bigsize : Stail(r,2))
        !            56: #define Sdiff(r,s) ((r) EQ Bigsize || (s) EQ Bigsize ? Bigsize : (r)-(s))
        !            57: #define Sdecr(r)   ((r) EQ Bigsize ? Bigsize : (r)-(1))
        !            58: value treesize();      /* btreeptr pnode */
        !            59: 
        !            60: /*********************************************************************/
        !            61: /* (A,B)-btrees
        !            62: /*********************************************************************/
        !            63: 
        !            64: /* innernodes: using A=6 B=12 */
        !            65: #define Mininner 5             /* A - 1 */
        !            66: #define Maxinner 11            /* B - 1 */
        !            67: /* bottomnodes */
        !            68: #define Minbottom 11
        !            69: #define Maxbottom 22
        !            70: /* rangenodes */
        !            71: #define Biglim         (Maxbottom+1)
        !            72: 
        !            73: typedef struct btrnode {
        !            74:     HEADER; int size;
        !            75:     char **g;
        !            76: }
        !            77: btreenode, *btreeptr;
        !            78: 
        !            79: typedef struct innernode {
        !            80:     HEADER; int size;
        !            81:     btreeptr ptr[Maxinner+1]; itemarray iitm;
        !            82: }
        !            83: innernode, *innerptr;
        !            84: 
        !            85: typedef struct itexnode {
        !            86:     HEADER; int size;
        !            87:     btreeptr ptr[Maxinner+1]; texitem icitm[Maxinner];
        !            88: }
        !            89: itexnode, *itexptr;
        !            90: 
        !            91: typedef struct ilisnode {
        !            92:     HEADER; int size;
        !            93:     btreeptr ptr[Maxinner+1]; lisitem ilitm[Maxinner];
        !            94: }
        !            95: ilisnode, *ilisptr;
        !            96: 
        !            97: typedef struct itabnode {
        !            98:     HEADER; int size;
        !            99:     btreeptr ptr[Maxinner+1]; tabitem ititm[Maxinner];
        !           100: }
        !           101: itabnode, *itabptr;
        !           102: 
        !           103: typedef struct bottomnode {
        !           104:     HEADER; int size;
        !           105:     itemarray bitm;
        !           106: }
        !           107: bottomnode, *bottomptr;
        !           108: 
        !           109: typedef struct btexnode {
        !           110:     HEADER; int size;
        !           111:     texitem bcitm[Maxbottom];
        !           112: }
        !           113: btexnode, *btexptr;
        !           114: 
        !           115: typedef struct blisnode {
        !           116:     HEADER; int size;
        !           117:     lisitem blitm[Maxbottom];
        !           118: }
        !           119: blisnode, *blisptr;
        !           120: 
        !           121: typedef struct btabnode {
        !           122:     HEADER; int size;
        !           123:     tabitem btitm[Maxbottom];
        !           124: }
        !           125: btabnode, *btabptr;
        !           126: 
        !           127: typedef struct rangenode {
        !           128:     HEADER; int size;
        !           129:     lisitem lwb, upb;
        !           130: }
        !           131: rangenode, *rangeptr;
        !           132: 
        !           133: #define Bnil ((btreeptr) 0)
        !           134: 
        !           135: #define Flag(pnode)    ((pnode)->type)
        !           136: #define Inner  'i'
        !           137: #define Bottom 'b'
        !           138: #define Irange  '.'
        !           139: #define Crange  '\''
        !           140: 
        !           141: #define Lim(pnode)     ((pnode)->len)
        !           142: #define Minlim(pnode)  (Flag(pnode) EQ Inner ? Mininner : Minbottom)
        !           143: #define Maxlim(pnode)  (Flag(pnode) EQ Inner ? Maxinner : Maxbottom)
        !           144: #define SetRangeLim(pnode) (Size(pnode) EQ Bigsize || Size(pnode) > Maxbottom\
        !           145:                            ? Biglim : Size(pnode))
        !           146: 
        !           147: #define Size(pnode)    ((pnode)->size)
        !           148: 
        !           149: #define Ptr(pnode,l)   (((innerptr) (pnode))->ptr[l])
        !           150: /* pointer to item in innernode: */
        !           151: #define Piitm(pnode,l,w) ((itemptr) (((char*)&(((innerptr) (pnode))->iitm)) + ((l)*(w))))
        !           152: /* pointer to item in bottomnode: */
        !           153: #define Pbitm(pnode,l,w) ((itemptr) (((char*)&(((bottomptr) (pnode))->bitm)) + ((l)*(w))))
        !           154: #define Ichar(pnode,l) (((itexptr) (pnode))->icitm[l])
        !           155: #define Bchar(pnode,l) (((btexptr) (pnode))->bcitm[l])
        !           156: 
        !           157: #define Lwbval(pnode)  (((rangeptr) (pnode))->lwb)
        !           158: #define Upbval(pnode)  (((rangeptr) (pnode))->upb)
        !           159: #define Lwbchar(pnode)  (Bchar(Root(Lwbval(pnode)), 0))
        !           160: #define Upbchar(pnode)  (Bchar(Root(Upbval(pnode)), 0))
        !           161: 
        !           162: #define Maxheight 20        /* should be some function of B */
        !           163: 
        !           164: /* Procedure merge(); */
        !           165:     /* btreeptr pleft; itemptr pitm; btreeptr pright; literal it; */
        !           166: bool rebalance();
        !           167:     /* btreeptr *pptr1; itemptr pitm; btreeptr pptr2;
        !           168:        intlet minlim, maxlim; literal it; */
        !           169: /* Procedure restore_child(); */
        !           170:     /* btreeptr pparent; intlet ichild, minl, maxl; literal it; */
        !           171: bool inodeinsert();
        !           172:     /* btreeptr pnode, *pptr; itemptr pitm; intlet at; literal it; */
        !           173: bool bnodeinsert();
        !           174:     /* btreeptr pnode, *pptr; itemptr pitm; intlet at; literal it; */
        !           175: bool i_search();
        !           176:     /* btreeptr pnode; value key; intlet *pl; width iw; */
        !           177: bool b_search();
        !           178:     /* btreeptr pnode; value key; intlet *pl; width iw; */
        !           179: 
        !           180: /*********************************************************************/
        !           181: /* texts only (mbte.c)
        !           182: /*********************************************************************/
        !           183: 
        !           184: btreeptr trimbtextnode(); /* btreeptr pnode, intlet from,to */
        !           185: btreeptr trimitextnode(); /* btreeptr pnode, intlet from,to */
        !           186: bool join_itm();
        !           187:     /* btreeptr pnode, *pptr; itemptr pitm; bool after */
        !           188: 
        !           189: /*********************************************************************/
        !           190: /* lists only (mbli.c)
        !           191: /*********************************************************************/
        !           192: 
        !           193: btreeptr spawncrangenode(); /* value lwb, upb */
        !           194: /* Procedure set_size_and_lim(); */    /* btreeptr pnode */
        !           195: /* PRrocedure ir_to_bottomnode(); */   /* btreeptr *pptr; */
        !           196: bool ins_itm();
        !           197:     /* btreeptr *pptr1; itemptr pitm; btreeptr *pptr2; literal it; */
        !           198: /* Procedure rem_greatest(); */
        !           199:     /* btreeptr *pptr; itemptr prepl_itm; literal it; */
        !           200: bool rem_itm(); 
        !           201:     /* btreeptr *pptr1; itemptr pitm;
        !           202:        itemptr p_insitm; btreeptr *pptr2; bool *psplit;
        !           203:        literal it; */
        !           204: 
        !           205: /*********************************************************************/
        !           206: /* tables only (mbla.c)
        !           207: /*********************************************************************/
        !           208: 
        !           209: bool rpl_itm(); 
        !           210:     /* btreeptr *pptr1, *pptr2; itemptr pitm; bool *p_added */
        !           211: bool del_itm(); 
        !           212:     /* btreeptr *pptr1; itemptr pitm */
        !           213: value assocval();      /* btreeptr pnode; value key; */
        !           214: bool assocloc();
        !           215:     /* value **ploc; btreeptr pnode; value key; */
        !           216: bool u_assoc();        /* btreeptr pnode; value key; */
        !           217: 
        !           218: /***************** Texts, lists and tables ********************/
        !           219: /* Procedure move_itm(); */    /* itemptr pdes, psrc; literal it; */
        !           220: bool get_th_item();    /* itemptr pitm; value num, v; */
        !           221: 
        !           222: #endif !INTEGRATION

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