Changeset 808

Timestamp:

07/11/07 12:28:05 (1 year ago)

Author:

alo

Message:

Files:

cherokee/trunk/cherokee/avl.c (modified) (27 diffs)

Legend:

: Unmodified
: Added
: Removed
: Modified
: Copied
: Moved

cherokee/trunk/cherokee/avl.c

r807	r808
27	27
28	28	struct cherokee_avl_node {
29		/* Tree */
30		short balance;
31		struct cherokee_avl_node *left;
32		struct cherokee_avl_node *right;
33
34		/* Info */
35		cherokee_buffer_t id;
36		void *value;
	29	/* Tree */
	30	short balance;
	31	struct cherokee_avl_node *left;
	32	struct cherokee_avl_node *right;
	33
	34	/* Info */
	35	cherokee_buffer_t id;
	36	void *value;
37	37	};
38	38
…	…
43	43	cherokee_avl_node_init (cherokee_avl_node_t *node)
44	44	{
45		node->balance = 0;
46		node->left = NULL;
47		node->right = NULL;
48		node->value = NULL;
49
50		cherokee_buffer_init (&node->id);
51		return ret_ok;
	45	node->balance = 0;
	46	node->left = NULL;
	47	node->right = NULL;
	48	node->value = NULL;
	49
	50	cherokee_buffer_init (&node->id);
	51	return ret_ok;
52	52	}
53	53
…	…
55	55	cherokee_avl_node_mrproper (cherokee_avl_node_t *node)
56	56	{
57		cherokee_buffer_mrproper (&node->id);
58		return ret_ok;
	57	cherokee_buffer_mrproper (&node->id);
	58	return ret_ok;
59	59	}
60	60
…	…
65	65	cherokee_avl_init (cherokee_avl_t *avl)
66	66	{
67		avl->root = NULL;
68		return ret_ok;
	67	avl->root = NULL;
	68	return ret_ok;
69	69	}
70	70
…	…
73	73	cherokee_avl_mrproper (cherokee_avl_t *avl)
74	74	{
75		return ret_ok;
	75	return ret_ok;
76	76	}
77	77
…	…
79	79	static int
80	80	compare_buffers (cherokee_buffer_t *A,
81		cherokee_buffer_t *B)
82		{
83		if (A->len > B->len)
84		return A->len - B->len;
85		else if (B->len > A->len)
86		return - (B->len - A->len);
87		else
88		return strcmp (A->buf, B->buf);
	81	cherokee_buffer_t *B)
	82	{
	83	if (A->len > B->len)
	84	return A->len - B->len;
	85	else if (B->len > A->len)
	86	return - (B->len - A->len);
	87	else
	88	return strcmp (A->buf, B->buf);
89	89	}
90	90
…	…
92	92	find_smallest_child (cherokee_avl_node_t root, cherokee_avl_node_t ret_parent_node, cherokee_avl_node_t *ret_node)
93	93	{
94		cherokee_avl_node_t *node = root;
95		cherokee_avl_node_t *parent = NULL;
96
97		while (node->left != NULL) {
98		parent = node;
99		node = node->left;
100		}
	94	cherokee_avl_node_t *node = root;
	95	cherokee_avl_node_t *parent = NULL;
	96
	97	while (node->left != NULL) {
	98	parent = node;
	99	node = node->left;
	100	}
101	101
102		*ret_node = node;
103		*ret_parent_node = parent;
104
105		return ret_ok;
	102	*ret_node = node;
	103	*ret_parent_node = parent;
	104
	105	return ret_ok;
106	106	}
107	107
…	…
109	109	find_biggest_child (cherokee_avl_node_t root, cherokee_avl_node_t ret_parent_node, cherokee_avl_node_t *ret_node)
110	110	{
111		cherokee_avl_node_t *node = root;
112		cherokee_avl_node_t *parent = NULL;
113
114		while (node->right != NULL) {
115		parent = node;
116		node = node->right;
117		}
	111	cherokee_avl_node_t *node = root;
	112	cherokee_avl_node_t *parent = NULL;
	113
	114	while (node->right != NULL) {
	115	parent = node;
	116	node = node->right;
	117	}
118	118
119		*ret_node = node;
120		*ret_parent_node = parent;
121
122		return ret_ok;
	119	*ret_node = node;
	120	*ret_parent_node = parent;
	121
	122	return ret_ok;
123	123	}
124	124
…	…
127	127	find_parent_node (cherokee_avl_t avl, cherokee_buffer_t key, cherokee_avl_node_t ret_parent_node, cherokee_avl_node_t ret_node)
128	128	{
129		int re;
130		cherokee_avl_node_t *node = avl->root;
131		cherokee_avl_node_t *parent_node = NULL;
132
133		/* It is empty
134		*/
135		if (node == NULL)
136		return ret_not_found;
	129	int re;
	130	cherokee_avl_node_t *node = avl->root;
	131	cherokee_avl_node_t *parent_node = NULL;
	132
	133	/* It is empty
	134	*/
	135	if (node == NULL)
	136	return ret_not_found;
137	137
138		/* If it's the top node
139		*/
140		if (compare_buffers (&node->id, key) == 0) {
141		*ret_parent_node = NULL;
142		*ret_node = node;
143		return ret_ok;
144		}
145
146		while (node != NULL) {
147		re = compare_buffers (&node->id, key);
	138	/* If it's the top node
	139	*/
	140	if (compare_buffers (&node->id, key) == 0) {
	141	*ret_parent_node = NULL;
	142	*ret_node = node;
	143	return ret_ok;
	144	}
	145
	146	while (node != NULL) {
	147	re = compare_buffers (&node->id, key);
148	148
149		if (re < 0) {
150		parent_node = node;
151		node = node->left;
152		} else if (re > 0) {
153		parent_node = node;
154		node = node->right;
155		} else {
156		*ret_node = node;
157		*ret_parent_node = parent_node;
158		return ret_ok;
159		}
160		}
161		return ret_not_found;
	149	if (re < 0) {
	150	parent_node = node;
	151	node = node->left;
	152	} else if (re > 0) {
	153	parent_node = node;
	154	node = node->right;
	155	} else {
	156	*ret_node = node;
	157	*ret_parent_node = parent_node;
	158	return ret_ok;
	159	}
	160	}
	161	return ret_not_found;
162	162	}
163	163
…	…
166	166	find_node (cherokee_avl_t avl, cherokee_buffer_t key, cherokee_avl_node_t **ret_node)
167	167	{
168		cherokee_avl_node_t *ignored_parent;
169		return find_parent_node (avl, key, &ignored_parent, ret_node);
	168	cherokee_avl_node_t *ignored_parent;
	169	return find_parent_node (avl, key, &ignored_parent, ret_node);
170	170	}
171	171
…	…
174	174	cherokee_avl_get (cherokee_avl_t avl, cherokee_buffer_t key, void **value)
175	175	{
176		ret_t ret;
177		cherokee_avl_node_t *ret_node = NULL;
178
179		ret = find_node (avl, key, &ret_node);
180		if (ret != ret_ok)
181		return ret;
182		if (ret_node == NULL)
183		return ret_error;
184
185		*value = ret_node->value;
186		return ret_ok;
	176	ret_t ret;
	177	cherokee_avl_node_t *ret_node = NULL;
	178
	179	ret = find_node (avl, key, &ret_node);
	180	if (ret != ret_ok)
	181	return ret;
	182	if (ret_node == NULL)
	183	return ret_error;
	184
	185	*value = ret_node->value;
	186	return ret_ok;
187	187	}
188	188
…	…
191	191	rotate_right_once (cherokee_avl_node_t **root)
192	192	{
193		cherokee_avl_node_t A = root;
194		cherokee_avl_node_t B = (root)->left;
195
196		A->left = B->right;
197		B->right = A;
198		*root = B;
199		A->balance = 0;
200		B->balance = 0;
	193	cherokee_avl_node_t A = root;
	194	cherokee_avl_node_t B = (root)->left;
	195
	196	A->left = B->right;
	197	B->right = A;
	198	*root = B;
	199	A->balance = 0;
	200	B->balance = 0;
201	201	}
202	202
…	…
204	204	rotate_left_once (cherokee_avl_node_t **root)
205	205	{
206		cherokee_avl_node_t A = root;
207		cherokee_avl_node_t B = (root)->right;
208
209		A->right = B->left;
210		B->left = A;
211		*root = B;
212		A->balance = 0;
213		B->balance = 0;
	206	cherokee_avl_node_t A = root;
	207	cherokee_avl_node_t B = (root)->right;
	208
	209	A->right = B->left;
	210	B->left = A;
	211	*root = B;
	212	A->balance = 0;
	213	B->balance = 0;
214	214	}
215	215
…	…
217	217	rotate_right_twice (cherokee_avl_node_t **root)
218	218	{
219		cherokee_avl_node_t A = root;
220		cherokee_avl_node_t B = (root)->left;
221
222		*root = B->right;
223		B->right = (*root)->left;
224		A->left = (*root)->right;
225		(*root)->left = B;
226		(*root)->right = A;
227
228		switch ((*root)->balance) {
229		case -1:
230		A->balance = 1;
231		B->balance = 0;
232		break;
233		case 0:
234		A->balance = 0;
235		B->balance = 0;
236		break;
237		case 1:
238		A->balance = 0;
239		B->balance = -1;
240		break;
241		}
242		(*root)->balance = 0;
	219	cherokee_avl_node_t A = root;
	220	cherokee_avl_node_t B = (root)->left;
	221
	222	*root = B->right;
	223	B->right = (*root)->left;
	224	A->left = (*root)->right;
	225	(*root)->left = B;
	226	(*root)->right = A;
	227
	228	switch ((*root)->balance) {
	229	case -1:
	230	A->balance = 1;
	231	B->balance = 0;
	232	break;
	233	case 0:
	234	A->balance = 0;
	235	B->balance = 0;
	236	break;
	237	case 1:
	238	A->balance = 0;
	239	B->balance = -1;
	240	break;
	241	}
	242	(*root)->balance = 0;
243	243	}
244	244
…	…
246	246	rotate_left_twice (cherokee_avl_node_t **root)
247	247	{
248		cherokee_avl_node_t A = root;
249		cherokee_avl_node_t B = (root)->right;
250
251		*root = B->left;
252		B->left = (*root)->right;
253		A->right = (*root)->left;
254		(*root)->left = A;
255		(*root)->right = B;
256
257		switch ((*root)->balance) {
258		case -1:
259		A->balance = 0;
260		B->balance = 1;
261		break;
262		case 0:
263		A->balance = 0;
264		B->balance = 0;
265		break;
266		case 1:
267		A->balance = -1;
268		B->balance = 0;
269		break;
270		}
271		(*root)->balance = 0;
	248	cherokee_avl_node_t A = root;
	249	cherokee_avl_node_t B = (root)->right;
	250
	251	*root = B->left;
	252	B->left = (*root)->right;
	253	A->right = (*root)->left;
	254	(*root)->left = A;
	255	(*root)->right = B;
	256
	257	switch ((*root)->balance) {
	258	case -1:
	259	A->balance = 0;
	260	B->balance = 1;
	261	break;
	262	case 0:
	263	A->balance = 0;
	264	B->balance = 0;
	265	break;
	266	case 1:
	267	A->balance = -1;
	268	B->balance = 0;
	269	break;
	270	}
	271	(*root)->balance = 0;
272	272	}
273	273
…	…
276	276	balance (cherokee_avl_node_t **root)
277	277	{
278		switch ((*root)->balance) {
279		case 0: /* no height increase */
280		return false;
281		case 1:
282		case -1: /* height increase */
283		return true;
284
285		case -2:
286		if ((*root)->left->balance <= 0)
287		rotate_right_once (root);
288		else
289		rotate_right_twice (root);
290		break;
291
292		case 2:
293		if ((*root)->right->balance >= 0)
294		rotate_left_once (root);
295		else
296		rotate_left_twice (root);
297		break;
298
299		default:
300		SHOULDNT_HAPPEN;
301		}
302
303		return false;
	278	switch ((*root)->balance) {
	279	case 0: /* no height increase */
	280	return false;
	281	case 1:
	282	case -1: /* height increase */
	283	return true;
	284
	285	case -2:
	286	if ((*root)->left->balance <= 0)
	287	rotate_right_once (root);
	288	else
	289	rotate_right_twice (root);
	290	break;
	291
	292	case 2:
	293	if ((*root)->right->balance >= 0)
	294	rotate_left_once (root);
	295	else
	296	rotate_left_twice (root);
	297	break;
	298
	299	default:
	300	SHOULDNT_HAPPEN;
	301	}
	302
	303	return false;
304	304	}
305	305
…	…
313	313	add_node (cherokee_avl_node_t *root, cherokee_avl_node_t node)
314	314	{
315		int re;
316		cherokee_boolean_t grew;
317
318		/* If the tree is empty..
319		*/
320		if (*root == NULL) {
321		*root = node;
322		return true;
323		}
324
325		/* Comparet the key
326		*/
327		re = compare_buffers (&(*root)->id, &node->id);
328		if (re < 0) {
329		/* Insert it on the left */
330		grew = add_node (&(*root)->left, node);
331		if (grew) {
332		(*root)->balance--;
333		return balance (root);
334		}
335		} else if (re > 0) {
336		/* Insert it on the right */
337		grew = add_node (&(*root)->right, node);
338		if (grew) {
339		(*root)->balance++;
340		return balance (root);
341		}
342		} else {
343		return -1;
344		}
345
346		return false;
	315	int re;
	316	cherokee_boolean_t grew;
	317
	318	/* If the tree is empty..
	319	*/
	320	if (*root == NULL) {
	321	*root = node;
	322	return true;
	323	}
	324
	325	/* Comparet the key
	326	*/
	327	re = compare_buffers (&(*root)->id, &node->id);
	328	if (re < 0) {
	329	/* Insert it on the left */
	330	grew = add_node (&(*root)->left, node);
	331	if (grew) {
	332	(*root)->balance--;
	333	return balance (root);
	334	}
	335	} else if (re > 0) {
	336	/* Insert it on the right */
	337	grew = add_node (&(*root)->right, node);
	338	if (grew) {
	339	(*root)->balance++;
	340	return balance (root);
	341	}
	342	} else {
	343	return -1;
	344	}
	345
	346	return false;
347	347	}
348	348
…	…
351	351	cherokee_avl_add (cherokee_avl_t avl, cherokee_buffer_t key, void *value)
352	352	{
353		int re;
354		ret_t ret;
355		CHEROKEE_NEW_STRUCT (n, avl_node);
356
357		/* Create the new AVL node
358		*/
359		ret = cherokee_avl_node_init (n);
360		if (unlikely (ret != ret_ok)) return ret;
361
362		n->value = value;
363		cherokee_buffer_add_buffer (&n->id, key);
364
365		/* Add th node to the tree
366		*/
367		re = add_node (&avl->root, n);
368		if (re == -1) {
369		cherokee_avl_node_mrproper (n);
370		free (n);
371		return ret_deny;
372		}
373
374		return ret_ok;
	353	int re;
	354	ret_t ret;
	355	CHEROKEE_NEW_STRUCT (n, avl_node);
	356
	357	/* Create the new AVL node
	358	*/
	359	ret = cherokee_avl_node_init (n);
	360	if (unlikely (ret != ret_ok)) return ret;
	361
	362	n->value = value;
	363	cherokee_buffer_add_buffer (&n->id, key);
	364
	365	/* Add th node to the tree
	366	*/
	367	re = add_node (&avl->root, n);
	368	if (re == -1) {
	369	cherokee_avl_node_mrproper (n);
	370	free (n);
	371	return ret_deny;
	372	}
	373
	374	return ret_ok;
375	375	}
376	376
…	…
379	379	cherokee_avl_del (cherokee_avl_t avl, cherokee_buffer_t key, void **value)
380	380	{
381		ret_t ret;
382		cherokee_avl_node_t *node = NULL;
383		cherokee_avl_node_t *parent = NULL;
384		cherokee_avl_node_t *tmp = NULL;
385		cherokee_avl_node_t *tmp_pa = NULL;
386
387		/* Find the node and its parent
388		*/
389		ret = find_parent_node (avl, key, &parent, &node);
390		if (ret != ret_ok) return ret;
391
392		/* We've got the node, read the returning value
393		*/
394		if (value)
395		*value = node->value;
396
397		/* Leaf: simply elimitate it
398		*/
399		if (!node->left && !node->right) {
400		if (parent == NULL) {
401		avl->root = NULL;
402		return ret_ok;
403		}
404
405		if (parent->left == node) {
406		parent->left = NULL;
407		parent->balance++;
408
409		} else if (parent->right == node) {
410		parent->right = NULL;
411		parent->balance--;
412		}
413
414		return ret_ok;
415		}
416
417		/* If it has only one child
418		*/
419		if (node->left && !node->right) {
420		tmp = node->left;
421
422		} else if (!node->left && node->right) {
423		tmp = node->right;
424		}
425
426		if (tmp) {
427
428		if (parent->left == node) {
429		parent->left = tmp;
430		} else if (parent->right == node) {
431		parent->right = tmp;
432		}
433
434		return ret_ok;
435		}
436
437		/* In the case it has more two child
438		*/
439		if (node->balance < 0) {
440		ret = find_smallest_child (node, &tmp, &tmp_pa);
441		} else {
442		ret = find_biggest_child (node, &tmp, &tmp_pa);
443		}
444		if (ret != ret_ok) {
445		SHOULDNT_HAPPEN;
446		return ret;
447		}
448
449		/* Remove the node */
450		if (tmp_pa->left == tmp) {
451		tmp_pa->left = NULL;
452		parent->balance++;
453		} else {
454		tmp_pa->right = NULL;
455		parent->balance--;
456		}
457
458		/* Put it in place */
459		if (parent->left == node) {
460		parent->left = tmp;
461		} else {
462		parent->right = tmp;
463		}
464
465		return ret_ok;
	381	ret_t ret;
	382	cherokee_avl_node_t *node = NULL;
	383	cherokee_avl_node_t *parent = NULL;
	384	cherokee_avl_node_t *tmp = NULL;
	385	cherokee_avl_node_t *tmp_pa = NULL;
	386
	387	/* Find the node and its parent
	388	*/
	389	ret = find_parent_node (avl, key, &parent, &node);
	390	if (ret != ret_ok) return ret;
	391
	392	/* We've got the node, read the returning value
	393	*/
	394	if (value)
	395	*value = node->value;
	396
	397	/* Leaf: simply elimitate it
	398	*/
	399	if (!node->left && !node->right) {
	400	if (parent == NULL) {
	401	avl->root = NULL;
	402	return ret_ok;
	403	}
	404
	405	if (parent->left == node) {
	406	parent->left = NULL;
	407	parent->balance++;
	408
	409	} else if (parent->right == node) {
	410	parent->right = NULL;
	411	parent->balance--;
	412	}
	413
	414	return ret_ok;
	415	}
	416
	417	/* If it has only one child
	418	*/
	419	if (node->left && !node->right) {
	420	tmp = node->left;
	421
	422	} else if (!node->left && node->right) {
	423	tmp = node->right;
	424	}
	425
	426	if (tmp) {
	427
	428	if (parent->left == node) {
	429	parent->left = tmp;
	430	} else if (parent->right == node) {
	431	parent->right = tmp;
	432	}
	433
	434	return ret_ok;
	435	}
	436
	437	/* In the case it has more two child
	438	*/
	439	if (node->balance < 0) {
	440	ret = find_smallest_child (node, &tmp, &tmp_pa);
	441	} else {
	442	ret = find_biggest_child (node, &tmp, &tmp_pa);
	443	}
	444	if (ret != ret_ok) {
	445	SHOULDNT_HAPPEN;
	446	return ret;
	447	}
	448
	449	/* Remove the node */
	450	if (tmp_pa->left == tmp) {
	451	tmp_pa->left = NULL;
	452	parent->balance++;
	453	} else {
	454	tmp_pa->right = NULL;
	455	parent->balance--;
	456	}
	457
	458	/* Put it in place */
	459	if (parent->left == node) {
	460	parent->left = tmp;
	461	} else {
	462	parent->right = tmp;
	463	}
	464
	465	return ret_ok;
466	466	}
467	467
…	…
473	473	while_node (cherokee_avl_node_t node, cherokee_avl_while_func_t func, void param, cherokee_buffer_t key, void value)
474	474	{
475		ret_t ret;
476
477		if (node == NULL)
478		return ret_ok;
479
480		/* Returning values
481		*/
482		if (key)
483		*key = &node->id;
484		if (value)
485		*value = &node->value;
486
487		/* Walk the children
488		*/
489		if (node->right) {
490		ret = while_node (node->right, func, param, key, value);
491		if (ret != ret_ok) return ret;
492		}
493
494		ret = func (&node->id, node->value, param);
495		if (ret != ret_ok) return ret;
496
497		if (node->left) {
498		ret = while_node (node->left, func, param, key, value);
499		if (ret != ret_ok) return ret;
500		}
	475	ret_t ret;
	476
	477	if (node == NULL)
	478	return ret_ok;
	479
	480	/* Returning values
	481	*/
	482	if (key)
	483	*key = &node->id;
	484	if (value)
	485	*value = &node->value;
	486
	487	/* Walk the children
	488	*/
	489	if (node->right) {
	490	ret = while_node (node->right, func, param, key, value);
	491	if (ret != ret_ok) return ret;
	492	}
	493
	494	ret = func (&node->id, node->value, param);
	495	if (ret != ret_ok) return ret;
	496
	497	if (node->left) {
	498	ret = while_node (node->left, func, param, key, value);
	499	if (ret != ret_ok) return ret;
	500	}
501	501
502		return ret_ok;
	502	return ret_ok;
503	503	}
504	504
…	…
506	506	cherokee_avl_while (cherokee_avl_t avl, cherokee_avl_while_func_t func, void param, cherokee_buffer_t key, void value)
507	507	{
508		return while_node (avl->root, func, param, key, value);
	508	return while_node (avl->root, func, param, key, value);
509	509	}
510	510
…	…
512	512	cherokee_avl_len_each (cherokee_buffer_t key, void value, void *param)
513	513	{
514		((size_t )param) += 1;
515		return ret_ok;
	514	((size_t )param) += 1;
	515	return ret_ok;
516	516	}
517	517
…	…
519	519	cherokee_avl_len (cherokee_avl_t avl, size_t len)
520	520	{
521		*len = 0;
522		return cherokee_avl_while (avl, cherokee_avl_len_each, len, NULL, NULL);
	521	*len = 0;
	522	return cherokee_avl_while (avl, cherokee_avl_len_each, len, NULL, NULL);
523	523	}
524	524
…	…
532	532	print_node (cherokee_avl_node_t *node)
533	533	{
534		if (! node) {
535		printf ("<null />\n");
536		return;
537		}
538
539		printf ("<node key=\"%s\" value=\"%p\">\n", node->id.buf, node->value);
540		print_node (node->left);
541		print_node (node->right);
542		printf ("</node>\n");
	534	if (! node) {
	535	printf ("<null />\n");
	536	return;
	537	}
	538
	539	printf ("<node key=\"%s\" value=\"%p\">\n", node->id.buf, node->value);
	540	print_node (node->left);
	541	print_node (node->right);
	542	printf ("</node>\n");
543	543	}
544	544
…	…
547	547	cherokee_avl_print (cherokee_avl_t *avl)
548	548	{
549		/* TIP: Pipe the output of this method through Tidy to
550		* reindent the tree. Eg: ./whatever \| tidy -i -xml -q
551		*/
552		print_node (avl->root);
553		return ret_ok;
	549	/* TIP: Pipe the output of this method through Tidy to
	550	* reindent the tree. Eg: ./whatever \| tidy -i -xml -q
	551	*/
	552	print_node (avl->root);
	553	return ret_ok;
554	554	}
555	555
…	…
558	558	check_node (cherokee_avl_node_t *node)
559	559	{
560		int re;
561
562		/* Empty */
563		if (node == NULL)
564		return ret_ok;
565
566		/* No child */
567		if ((node->left == NULL) &&
568		(node->right == NULL))
569		return ret_ok;
570
571		/* Check order */
572		if (node->left) {
573		re = compare_buffers (&node->id, &node->left->id);
574		if (re >= 0) {
575		PRINT_ERROR ("Invalid link: node('%s') -> node('%s')\n",
576		node->id.buf, node->left->id.buf);
577		}
578		}
579
580		if (node->right) {
581		re = compare_buffers (&node->id, &node->left->id);
582		if (re <= 0) {
583		PRINT_ERROR ("Invalid link: node('%s') -> node('%s')\n",
584		node->id.buf, node->right->id.buf);
585		}
586		}
587
588		/* Check balance */
589		if (( node->left && node->right && (node->balance != 0)) \|\|
590		(!node->left && node->right && (node->balance != 1)) \|\|
591		( node->left && !node->right && (node->balance != -1)))
592		{
593		PRINT_ERROR ("Wrong balance=%d at '%s'\n", node->balance, node->id.buf);
594		}
595
596		return ret_ok;
	560	int re;
	561
	562	/* Empty */
	563	if (node == NULL)
	564	return ret_ok;
	565
	566	/* No child */
	567	if ((node->left == NULL) &&
	568	(node->right == NULL))
	569	return ret_ok;
	570
	571	/* Check order */
	572	if (node->left) {
	573	re = compare_buffers (&node->id, &node->left->id);
	574	if (re >= 0) {
	575	PRINT_ERROR ("Invalid link: node('%s') -> node('%s')\n",
	576	node->id.buf, node->left->id.buf);
	577	}
	578	}
	579
	580	if (node->right) {
	581	re = compare_buffers (&node->id, &node->left->id);
	582	if (re <= 0) {
	583	PRINT_ERROR ("Invalid link: node('%s') -> node('%s')\n",
	584	node->id.buf, node->right->id.buf);
	585	}
	586	}
	587

Navigation

Changeset 808

Legend:

cherokee/trunk/cherokee/avl.c