[unix-history] / usr / src / cmd / compact / tree.c

#include "compact.h"


insert (ch)
int ch;
{
	register struct node *pp;
	register int c;
	union cio d;
	register struct index *qt, *wt;

	c = ch;
	wt = NEW;
	pp = bottom++;
	bottom -> fath . fp = pp;
	in [c] . flags = (SEEN | FBIT);
	d . integ = bottom -> sp [0] . ch = pp -> sp [1] . ch;
	in [c] . fp = in [d . integ] . fp = pp -> sp [1] . p = wt -> pt = bottom;
	bottom -> fath . flags = (LLEAF | RLEAF | FBIT);
	pp -> fath . flags &= ~RLEAF;
	in [d . integ] . flags = SEEN;

	bottom -> count [0] = pp -> count [1];
	qt = pp -> top [1];
	bottom -> top [0] = qt;
	bottom -> sp [1] . ch = c;
	bottom -> count [1] = 0;
	bottom -> top [1] = qt -> next = wt;
	wt -> next = NULL;
}

uptree (ch)
int ch;
{
	register struct node *r;
	union treep q, s;
	int rs, qs, ss, ts;
	longint rc, qc, sc;
	struct node *t;
	register struct index *rt, *qt, *st;

	r = in [ch] . fp;
	rs = in [ch] . flags & FBIT;

	do {
		(r -> count [rs])++;
		rc = r -> count [rs];
		rt = r -> top [rs];
	
		for ( ; ; ) {
			qs = ss = 1 - rs;
			s . p = r + rs;
			sc = (s . p) -> count [ss];
			st = (s . p) -> top [ss];
	
			if (rs)
				if (r == bottom) {
					sc = rc - 2;
					st = NULL;
				}
				else;
			else if (r == dict) {
				qc = rc + 1;
				qt = head;
				break;
			}

			q . p = r - qs;
			qc = (q . p) -> count [qs];
			qt = (q . p) -> top [qs];
			if (rc <= qc) break;

			t = qt -> pt;
			ts = (rc <= t -> count [0] ? 1 : 0);

			/* exchange pointers of (t, ts) and (r, rs) */

			q . ch = t -> sp [ts] . ch;	/*  {					*/
			s . ch = r -> sp [rs] . ch;	/*  {					*/
			t -> sp [ts] . ch = s . ch;	/*  {					*/
			r -> sp [rs] . ch = q . ch;	/*  { change code when Cory gets v. 7	*/
							/*  {					*/
			exch (t, ts, q . ch, r, rs);	/*  {					*/
			exch (r, rs, s . ch, t, ts);	/*  {					*/

			qs = (rs ? RLEAF : LLEAF);
			ss = (ts ? RLEAF : LLEAF);
			if (((r -> fath . flags & qs) << rs) ^ ((t -> fath . flags & ss) << ts)) {
				r -> fath . flags ^= qs;
				t -> fath . flags ^= ss;
			}

			(t -> count [ts])++;
			(r -> count [rs])--;
			(qt -> pt) += ts;
			r = t;
			rs = ts;
		}

		if (rc == qc) {
			r -> top [rs] = qt;
			if (rc > sc + 1) {
				qt -> next = st;

				/* dispose of rt */

				rt -> next = flist;
				flist = rt;
			}
			else st -> pt = s . p;
		}

		else if (rc == sc + 1) {

			/* create new index at rt */

			rt = NEW;
			rt -> next = st;
			rt -> pt = r;
			qt -> next = rt;
			if (st) st -> pt = s . p;
			r -> top [rs] = rt;
		}

		rs = r -> fath . flags & FBIT;
		r = r -> fath . fp;

	} while (r);
	dirp = head -> next;
	dirq = dirp -> next;
}

exch (v, vs, x, w, ws)
struct node *v, *w;
union treep x;
int vs, ws;
{

	if (v -> fath . flags & (vs ? RLEAF : LLEAF)) {
		in [x . ch] . fp = w;
		in [x . ch] . flags &= ~01;
		if (ws) in [x . ch] . flags |= ws;
	}
	else {
		(x . p) -> fath . fp = w;
		(x . p) -> fath . flags &= ~01;
		if (ws) (x . p) -> fath . flags |= ws;
	}
}
Commit	Line	Data
b60e6348 CMM	1	#include "compact.h"
	2
	3
	4	insert (ch)
	5	int ch;
	6	{
	7	register struct node *pp;
	8	register int c;
	9	union cio d;
	10	register struct index qt, wt;
	11
	12	c = ch;
	13	wt = NEW;
	14	pp = bottom++;
	15	bottom -> fath . fp = pp;
	16	in [c] . flags = (SEEN \| FBIT);
	17	d . integ = bottom -> sp [0] . ch = pp -> sp [1] . ch;
	18	in [c] . fp = in [d . integ] . fp = pp -> sp [1] . p = wt -> pt = bottom;
	19	bottom -> fath . flags = (LLEAF \| RLEAF \| FBIT);
	20	pp -> fath . flags &= ~RLEAF;
	21	in [d . integ] . flags = SEEN;
	22
	23	bottom -> count [0] = pp -> count [1];
	24	qt = pp -> top [1];
	25	bottom -> top [0] = qt;
	26	bottom -> sp [1] . ch = c;
	27	bottom -> count [1] = 0;
	28	bottom -> top [1] = qt -> next = wt;
	29	wt -> next = NULL;
	30	}
	31
	32	uptree (ch)
	33	int ch;
	34	{
	35	register struct node *r;
	36	union treep q, s;
	37	int rs, qs, ss, ts;
	38	longint rc, qc, sc;
	39	struct node *t;
	40	register struct index rt, qt, *st;
	41
	42	r = in [ch] . fp;
	43	rs = in [ch] . flags & FBIT;
	44
	45	do {
	46	(r -> count [rs])++;
	47	rc = r -> count [rs];
	48	rt = r -> top [rs];
	49
	50	for ( ; ; ) {
	51	qs = ss = 1 - rs;
	52	s . p = r + rs;
	53	sc = (s . p) -> count [ss];
	54	st = (s . p) -> top [ss];
	55
	56	if (rs)
	57	if (r == bottom) {
	58	sc = rc - 2;
	59	st = NULL;
	60	}
	61	else;
	62	else if (r == dict) {
	63	qc = rc + 1;
	64	qt = head;
65	break;
66	}
67
68	q . p = r - qs;
69	qc = (q . p) -> count [qs];
70	qt = (q . p) -> top [qs];
71	if (rc <= qc) break;
72
73	t = qt -> pt;
74	ts = (rc <= t -> count [0] ? 1 : 0);
75
76	/* exchange pointers of (t, ts) and (r, rs) */
77
78	q . ch = t -> sp [ts] . ch; /* { */
79	s . ch = r -> sp [rs] . ch; /* { */
80	t -> sp [ts] . ch = s . ch; /* { */
81	r -> sp [rs] . ch = q . ch; /* { change code when Cory gets v. 7 */
82	/* { */
83	exch (t, ts, q . ch, r, rs); /* { */
84	exch (r, rs, s . ch, t, ts); /* { */
85
86	qs = (rs ? RLEAF : LLEAF);
87	ss = (ts ? RLEAF : LLEAF);
88	if (((r -> fath . flags & qs) << rs) ^ ((t -> fath . flags & ss) << ts)) {
89	r -> fath . flags ^= qs;
90	t -> fath . flags ^= ss;
91	}
92
93	(t -> count [ts])++;
94	(r -> count [rs])--;
95	(qt -> pt) += ts;
96	r = t;
97	rs = ts;
98	}
99
100	if (rc == qc) {
101	r -> top [rs] = qt;
102	if (rc > sc + 1) {
103	qt -> next = st;
104
105	/* dispose of rt */
106
107	rt -> next = flist;
108	flist = rt;
109	}
110	else st -> pt = s . p;
111	}
112
113	else if (rc == sc + 1) {
114
115	/* create new index at rt */
116
117	rt = NEW;
118	rt -> next = st;
119	rt -> pt = r;
120	qt -> next = rt;
121	if (st) st -> pt = s . p;
122	r -> top [rs] = rt;
123	}
124
125	rs = r -> fath . flags & FBIT;
126	r = r -> fath . fp;
127
128	} while (r);
129	dirp = head -> next;
130	dirq = dirp -> next;
131	}
132
133	exch (v, vs, x, w, ws)
134	struct node v, w;
135	union treep x;
136	int vs, ws;
137	{
138
139	if (v -> fath . flags & (vs ? RLEAF : LLEAF)) {
140	in [x . ch] . fp = w;
141	in [x . ch] . flags &= ~01;
142	if (ws) in [x . ch] . flags \|= ws;
143	}
144	else {
145	(x . p) -> fath . fp = w;
146	(x . p) -> fath . flags &= ~01;
147	if (ws) (x . p) -> fath . flags \|= ws;
148	}
149	}