ViewVC Help

View File | Revision Log | Show Annotations | View Changeset | Root Listing

root/svn/ircd-hybrid/trunk/src/patricia.c

Comparing ircd-hybrid/trunk/src/patricia.c (file contents):
Revision 6259 by michael, Sat Jul 11 12:18:43 2015 UTC vs.
Revision 6607 by michael, Thu Oct 22 18:35:52 2015 UTC

#	Line 63 | Line 63 | prefix_tochar (prefix_t * prefix)
63		return ((u_char *) & prefix->add.sin);
64		}
65
66	<	static int
66	>	static int
67		comp_with_mask (void *addr, void *dest, u_int mask)
68		{
69
#	Line 116 | Line 116 | my_inet_pton (int af, const char *src, v
116
117		#define PATRICIA_MAX_THREADS            16
118
119	<	/*
119	>	/*
120		* convert prefix information to ascii string with length
121		* thread safe and (almost) re-entrant implementation
122		*/
#	Line 438 | Line 438 | patricia_search_exact (patricia_tree_t *
438		if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
439		#ifdef PATRICIA_DEBUG
440		if (node->prefix)
441	<	fprintf (stderr, "patricia_search_exact: take right %s/%d\n",
441	>	fprintf (stderr, "patricia_search_exact: take right %s/%d\n",
442		prefix_toa (node->prefix), node->prefix->bitlen);
443		else
444	<	fprintf (stderr, "patricia_search_exact: take right at %u\n",
444	>	fprintf (stderr, "patricia_search_exact: take right at %u\n",
445		node->bit);
446		#endif /* PATRICIA_DEBUG */
447		node = node->r;
#	Line 449 | Line 449 | patricia_search_exact (patricia_tree_t *
449		else {
450		#ifdef PATRICIA_DEBUG
451		if (node->prefix)
452	<	fprintf (stderr, "patricia_search_exact: take left %s/%d\n",
452	>	fprintf (stderr, "patricia_search_exact: take left %s/%d\n",
453		prefix_toa (node->prefix), node->prefix->bitlen);
454		else
455	<	fprintf (stderr, "patricia_search_exact: take left at %u\n",
455	>	fprintf (stderr, "patricia_search_exact: take left at %u\n",
456		node->bit);
457		#endif /* PATRICIA_DEBUG */
458		node = node->l;
#	Line 464 | Line 464 | patricia_search_exact (patricia_tree_t *
464
465		#ifdef PATRICIA_DEBUG
466		if (node->prefix)
467	<	fprintf (stderr, "patricia_search_exact: stop at %s/%d\n",
467	>	fprintf (stderr, "patricia_search_exact: stop at %s/%d\n",
468		prefix_toa (node->prefix), node->prefix->bitlen);
469		else
470		fprintf (stderr, "patricia_search_exact: stop at %u\n", node->bit);
#	Line 476 | Line 476 | patricia_search_exact (patricia_tree_t *
476		if (comp_with_mask (prefix_tochar (node->prefix), prefix_tochar (prefix),
477		bitlen)) {
478		#ifdef PATRICIA_DEBUG
479	<	fprintf (stderr, "patricia_search_exact: found %s/%d\n",
479	>	fprintf (stderr, "patricia_search_exact: found %s/%d\n",
480		prefix_toa (node->prefix), node->prefix->bitlen);
481		#endif /* PATRICIA_DEBUG */
482		return (node);
#	Line 510 | Line 510 | patricia_search_best2 (patricia_tree_t *
510
511		if (node->prefix) {
512		#ifdef PATRICIA_DEBUG
513	<	fprintf (stderr, "patricia_search_best: push %s/%d\n",
513	>	fprintf (stderr, "patricia_search_best: push %s/%d\n",
514		prefix_toa (node->prefix), node->prefix->bitlen);
515		#endif /* PATRICIA_DEBUG */
516		stack[cnt++] = node;
#	Line 519 | Line 519 | patricia_search_best2 (patricia_tree_t *
519		if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
520		#ifdef PATRICIA_DEBUG
521		if (node->prefix)
522	<	fprintf (stderr, "patricia_search_best: take right %s/%d\n",
522	>	fprintf (stderr, "patricia_search_best: take right %s/%d\n",
523		prefix_toa (node->prefix), node->prefix->bitlen);
524		else
525	<	fprintf (stderr, "patricia_search_best: take right at %u\n",
525	>	fprintf (stderr, "patricia_search_best: take right at %u\n",
526		node->bit);
527		#endif /* PATRICIA_DEBUG */
528		node = node->r;
#	Line 530 | Line 530 | patricia_search_best2 (patricia_tree_t *
530		else {
531		#ifdef PATRICIA_DEBUG
532		if (node->prefix)
533	<	fprintf (stderr, "patricia_search_best: take left %s/%d\n",
533	>	fprintf (stderr, "patricia_search_best: take left %s/%d\n",
534		prefix_toa (node->prefix), node->prefix->bitlen);
535		else
536	<	fprintf (stderr, "patricia_search_best: take left at %u\n",
536	>	fprintf (stderr, "patricia_search_best: take left at %u\n",
537		node->bit);
538		#endif /* PATRICIA_DEBUG */
539		node = node->l;
#	Line 550 | Line 550 | patricia_search_best2 (patricia_tree_t *
550		if (node == NULL)
551		fprintf (stderr, "patricia_search_best: stop at null\n");
552		else if (node->prefix)
553	<	fprintf (stderr, "patricia_search_best: stop at %s/%d\n",
553	>	fprintf (stderr, "patricia_search_best: stop at %s/%d\n",
554		prefix_toa (node->prefix), node->prefix->bitlen);
555		else
556		fprintf (stderr, "patricia_search_best: stop at %u\n", node->bit);
#	Line 562 | Line 562 | patricia_search_best2 (patricia_tree_t *
562		while (--cnt >= 0) {
563		node = stack[cnt];
564		#ifdef PATRICIA_DEBUG
565	<	fprintf (stderr, "patricia_search_best: pop %s/%d\n",
565	>	fprintf (stderr, "patricia_search_best: pop %s/%d\n",
566		prefix_toa (node->prefix), node->prefix->bitlen);
567		#endif /* PATRICIA_DEBUG */
568	<	if (comp_with_mask (prefix_tochar (node->prefix),
568	>	if (comp_with_mask (prefix_tochar (node->prefix),
569		prefix_tochar (prefix),
570		node->prefix->bitlen) && node->prefix->bitlen <= bitlen) {
571		#ifdef PATRICIA_DEBUG
572	<	fprintf (stderr, "patricia_search_best: found %s/%d\n",
572	>	fprintf (stderr, "patricia_search_best: found %s/%d\n",
573		prefix_toa (node->prefix), node->prefix->bitlen);
574		#endif /* PATRICIA_DEBUG */
575		return (node);
#	Line 607 | Line 607 | patricia_lookup (patricia_tree_t *patric
607		node->data = NULL;
608		patricia->head = node;
609		#ifdef PATRICIA_DEBUG
610	<	fprintf (stderr, "patricia_lookup: new_node #0 %s/%d (head)\n",
610	>	fprintf (stderr, "patricia_lookup: new_node #0 %s/%d (head)\n",
611		prefix_toa (prefix), prefix->bitlen);
612		#endif /* PATRICIA_DEBUG */
613		patricia->num_active_node++;
#	Line 626 | Line 626 | patricia_lookup (patricia_tree_t *patric
626		break;
627		#ifdef PATRICIA_DEBUG
628		if (node->prefix)
629	<	fprintf (stderr, "patricia_lookup: take right %s/%d\n",
629	>	fprintf (stderr, "patricia_lookup: take right %s/%d\n",
630		prefix_toa (node->prefix), node->prefix->bitlen);
631		else
632		fprintf (stderr, "patricia_lookup: take right at %u\n", node->bit);
#	Line 638 | Line 638 | patricia_lookup (patricia_tree_t *patric
638		break;
639		#ifdef PATRICIA_DEBUG
640		if (node->prefix)
641	<	fprintf (stderr, "patricia_lookup: take left %s/%d\n",
641	>	fprintf (stderr, "patricia_lookup: take left %s/%d\n",
642		prefix_toa (node->prefix), node->prefix->bitlen);
643		else
644		fprintf (stderr, "patricia_lookup: take left at %u\n", node->bit);
#	Line 651 | Line 651 | patricia_lookup (patricia_tree_t *patric
651
652		assert (node->prefix);
653		#ifdef PATRICIA_DEBUG
654	<	fprintf (stderr, "patricia_lookup: stop at %s/%d\n",
654	>	fprintf (stderr, "patricia_lookup: stop at %s/%d\n",
655		prefix_toa (node->prefix), node->prefix->bitlen);
656		#endif /* PATRICIA_DEBUG */
657
#	Line 686 | Line 686 | patricia_lookup (patricia_tree_t *patric
686		parent = node->parent;
687		#ifdef PATRICIA_DEBUG
688		if (node->prefix)
689	<	fprintf (stderr, "patricia_lookup: up to %s/%d\n",
689	>	fprintf (stderr, "patricia_lookup: up to %s/%d\n",
690		prefix_toa (node->prefix), node->prefix->bitlen);
691		else
692		fprintf (stderr, "patricia_lookup: up to %u\n", node->bit);
#	Line 695 | Line 695 | patricia_lookup (patricia_tree_t *patric
695
696		if (differ_bit == bitlen && node->bit == bitlen) {
697		if (node->prefix) {
698	<	#ifdef PATRICIA_DEBUG
699	<	fprintf (stderr, "patricia_lookup: found %s/%d\n",
698	>	#ifdef PATRICIA_DEBUG
699	>	fprintf (stderr, "patricia_lookup: found %s/%d\n",
700		prefix_toa (node->prefix), node->prefix->bitlen);
701		#endif /* PATRICIA_DEBUG */
702		return (node);
#	Line 730 | Line 730 | patricia_lookup (patricia_tree_t *patric
730		node->l = new_node;
731		}
732		#ifdef PATRICIA_DEBUG
733	<	fprintf (stderr, "patricia_lookup: new_node #2 %s/%d (child)\n",
733	>	fprintf (stderr, "patricia_lookup: new_node #2 %s/%d (child)\n",
734		prefix_toa (prefix), prefix->bitlen);
735		#endif /* PATRICIA_DEBUG */
736		return (new_node);
#	Line 757 | Line 757 | patricia_lookup (patricia_tree_t *patric
757		}
758		node->parent = new_node;
759		#ifdef PATRICIA_DEBUG
760	<	fprintf (stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n",
760	>	fprintf (stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n",
761		prefix_toa (prefix), prefix->bitlen);
762		#endif /* PATRICIA_DEBUG */
763		}
#	Line 791 | Line 791 | patricia_lookup (patricia_tree_t *patric
791		}
792		node->parent = glue;
793		#ifdef PATRICIA_DEBUG
794	<	fprintf (stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
794	>	fprintf (stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
795		prefix_toa (prefix), prefix->bitlen);
796		#endif /* PATRICIA_DEBUG */
797		}
#	Line 809 | Line 809 | patricia_remove (patricia_tree_t *patric
809
810		if (node->r && node->l) {
811		#ifdef PATRICIA_DEBUG
812	<	fprintf (stderr, "patricia_remove: #0 %s/%d (r & l)\n",
812	>	fprintf (stderr, "patricia_remove: #0 %s/%d (r & l)\n",
813		prefix_toa (node->prefix), node->prefix->bitlen);
814		#endif /* PATRICIA_DEBUG */
815
816		/* this might be a placeholder node -- have to check and make sure
817		* there is a prefix aossciated with it ! */
818	<	if (node->prefix != NULL)
818	>	if (node->prefix != NULL)
819		Deref_Prefix (node->prefix);
820		node->prefix = NULL;
821		/* Also I needed to clear data pointer -- masaki */
#	Line 825 | Line 825 | patricia_remove (patricia_tree_t *patric
825
826		if (node->r == NULL && node->l == NULL) {
827		#ifdef PATRICIA_DEBUG
828	<	fprintf (stderr, "patricia_remove: #1 %s/%d (!r & !l)\n",
828	>	fprintf (stderr, "patricia_remove: #1 %s/%d (!r & !l)\n",
829		prefix_toa (node->prefix), node->prefix->bitlen);
830		#endif /* PATRICIA_DEBUG */
831		parent = node->parent;
#	Line 872 | Line 872 | patricia_remove (patricia_tree_t *patric
872		}
873
874		#ifdef PATRICIA_DEBUG
875	<	fprintf (stderr, "patricia_remove: #2 %s/%d (r ^ l)\n",
875	>	fprintf (stderr, "patricia_remove: #2 %s/%d (r ^ l)\n",
876		prefix_toa (node->prefix), node->prefix->bitlen);
877		#endif /* PATRICIA_DEBUG */
878		if (node->r) {
#	Line 931 | Line 931 | try_search_exact (patricia_tree_t *tree,
931		printf ("try_search_exact: not found\n");
932		}
933		else {
934	<	printf ("try_search_exact: %s/%d found\n",
934	>	printf ("try_search_exact: %s/%d found\n",
935		prefix_toa (node->prefix), node->prefix->bitlen);
936		}
937		Deref_Prefix (prefix);
#	Line 958 | Line 958 | try_search_best (patricia_tree_t *tree,
958		if ((node = patricia_search_best (tree, prefix)) == NULL)
959		printf ("try_search_best: not found\n");
960		else
961	<	printf ("try_search_best: %s/%d found\n",
961	>	printf ("try_search_best: %s/%d found\n",
962		prefix_toa (node->prefix), node->prefix->bitlen);
963		Deref_Prefix (prefix);
964		return (node);

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines