#include "stdio.h" #include "setjmp.h" #include "isamstr.h" #include "isam.h" /* checked good 6-7-84 */ /*************************************************************** * File ISAM5.C * * these are the function return type declarations * ***************************************************************/ extern long l3alloc(), l2alloc(); extern char *calpl2(), *calpl3(); extern int keycmp(); extern void l3split(); extern void grread(), fmove(), lmove(), l2write(); extern void l2read(), l3write(), l3read(), wl2write(), wl2read(); extern void wl3write(); extern void keymove(); extern M_ELEM mbinsh(); extern M_ELEM shift(); extern L2_ELEM l2binsh(); extern L3_ELEM l3binsh(); /*************************************************************** * balance side links in l2 blocks for deletes * ***************************************************************/ int readjust() { M_ELEM a,b; int i; int lc,uc; /* find first lower main element entry whose l2 group count is 2 more than the current group count. variable lc is the number of elements from cama. variable a points to lower match */ for(lc=1, i = cama->group + 1, a = (M_ELEM)calpl2(-1, cama); a >= bm_ptr; lc++, a = (M_ELEM)calpl2(-1, a)) { if(a->group > i) break; } /* find first higher main element entry whose l2 group count is 2 more than the current group count. variable uc is the number of elements from cama. variable b points to higher match */ for(uc=1, b = (M_ELEM)calpl2(1, cama); b < (M_ELEM)calpl2(cm_ent, bm_ptr); uc++, b = (M_ELEM)calpl2(1, b)) { if(b->group > i) break; } /* if none found lower then lc set to 0 */ if(a < bm_ptr) lc = 0; /* if none found higher then set uc to 0 */ if(b >= (M_ELEM)calpl2(cm_ent, bm_ptr)) uc = 0; /* if higher element found */ if(uc) { /* if lower element found */ if(lc) /* set farthest away to 0 */ if(lc < uc) uc = 0; else lc = 0; } else /* no higher found, if no lower we are balanced and return */ if(!lc) return(TRUE); l2read((a = uc ? b : a)->offset); shift(a, cama, lc); l2read(l2_group = cama->offset); return(FALSE); } /* **************************************************************** * shift moves one l2 link from start to end in * * buffle fashion. dir tells whether from higher * * to lower main element verses lower to higher. * ***************************************************************/ M_ELEM shift(start, end, dir) M_ELEM start, end; int dir; { int i = 0; M_ELEM a = start, c = 0; long l_offset, l2_hold = l2_cur; long lowhold; if(dir) { /* shift highlink from current to lowlink of next higher main element l2 group and continue until the b main element is reached */ do { while(highlink) l2read(highlink); wl2read(lowlink); l_offset = wl2_highlink; wl2_highlink = 0; wl2write(lowlink); keymove(a->key, lowkey); if(a == start) lowhold = lowlink; lowlink = 0; l2_drty = TRUE; if((a = (M_ELEM)((char *)a + melem))->group) { wl2read(highlink = a->offset); if((!(i++)) && l2_hold == l_offset) c = a; while(wl2_lowlink) wl2read(highlink = wl2_lowlink); keymove(wl2_lowkey, ((L2_ELEM) calpl2(l2_ent - 1, bl2_ptr))->key); l2write(wl2_lowlink = l_offset); wl2write(highlink); l2read(a->offset); /* adjust centering on shift throughs */ if(end != a) a->offset = lowlink; } else { a->offset = l2_cur; keymove(a->key, ((L2_ELEM)calpl2(l2_ent - 1, bl2_ptr))->key); } } while(a < end); /* adjust centering in highest group */ if(!(a->group & 1) && a->group) a->offset = lowlink; /* adjust centering of cama */ if(!(start->group & 1)) { if(start->group == 2) { l2_group = start->offset = lowhold; l2read(start->offset); } else { l2read(start->offset); l2_group = start->offset = lowlink; } } } else { /* shift lowlinks of current to high link of next lower group and continue through variable a */ do { while(lowlink) l2read(lowlink); wl2read(highlink); l_offset = wl2_lowlink; wl2_lowlink = 0; wl2write(highlink); highlink = 0; l2_drty = TRUE; if((a = (M_ELEM)((char *)a - melem))->group) { wl2read(lowlink = a->offset); if((!(i++)) && l2_hold == l_offset) c = a; while(wl2_highlink) wl2read(lowlink = wl2_highlink); keymove(lowkey, ((L2_ELEM) calpl2(wl2_ent - 1, wbl2_ptr))->key); keymove(a->key, ((L2_ELEM) calpl2(l2_ent - 1, bl2_ptr))->key); l2write(wl2_highlink = l_offset); wl2write(lowlink); l2read(a->offset); /* center shift throughs */ if(a != end) a->offset = highlink; } else { a->offset = l2_cur; keymove(a->key, ((L2_ELEM)calpl2(l2_ent - 1, bl2_ptr))->key); } } while(a > end); /* center lowest group */ if(a->group & 1) a->offset = highlink; /* center cama group */ if(start->group & 1) { l2read(start->offset); l2_group = start->offset = highlink; } } /* lower count for shift out */ start->group--; /* increase count for shift in (a and b are equal here) */ end->group++; return(c); } /* **************************************************************** * balance side links in l2 blocks for inserts * ***************************************************************/ void adjust() { M_ELEM a,b; int i; int lc,uc; long l2_hold = l2_cur; /* find first lower main element entry whose l2 group count is 2 more than the current group count. variable lc is the number of elements from cama. variable a points to lower match */ for(lc = 1, i = cama->group - 1, a = (M_ELEM)calpl2(-1, cama); a >= bm_ptr; lc++, a = (M_ELEM)calpl2(-1, a)) { if(a->group < i) break; } /* find first higher main element entry whose l2 group count is 2 move than the current group count. variable uc is the number of elements from cama. variable b points to higher match */ for(uc=1, b = (M_ELEM)calpl2(1, cama); b < (M_ELEM)calpl2(cm_ent, bm_ptr); uc++, b = (M_ELEM)calpl2(1, b)) { if(b->group < i) break; } /* if none found lower then lc set to 0 */ if(a < bm_ptr) lc = 0; /* if none found higher then uc set to 0 */ if(b >= (M_ELEM)calpl2(cm_ent, bm_ptr)) uc = 0; /* if higher element found */ if(uc) { /* if lower element found */ if(lc) /* set farthest away to 0 */ if(lc < uc) uc = 0; else lc = 0; } else /* no higher found, if no lower we are balanced and return */ if(!lc) return; if(a = shift(cama, uc ? b : a, uc)) l2_group = (cama = a)->offset; l2read(l2_hold); }