Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf80e782

Browse files
committed
Remove pre-order and post-order traversal logic for red-black trees.
This code isn't used, and there's no clear reason why anybody would everwant to use it. These traversal mechanisms don't yield a visitation orderthat is semantically meaningful for any external purpose, nor are theyany faster or simpler than the left-to-right or right-to-left traversals.(In fact, some rough testing suggests they are slower :-(.) Moreover,these mechanisms are impossible to test in any arm's-length fashion; doingso requires knowledge of the red-black tree's internal implementation.Hence, let's just jettison them.Discussion:https://postgr.es/m/17735.1505003111@sss.pgh.pa.us
1 parentc824c7e commitf80e782

File tree

2 files changed

+3
-131
lines changed

2 files changed

+3
-131
lines changed

‎src/backend/lib/rbtree.c‎

Lines changed: 2 additions & 127 deletions
Original file line numberDiff line numberDiff line change
@@ -62,17 +62,6 @@ struct RBTree
6262

6363
staticRBNodesentinel= {RBBLACK,RBNIL,RBNIL,NULL};
6464

65-
/*
66-
* Values used in the RBTreeIterator.next_state field, with an
67-
* InvertedWalk iterator.
68-
*/
69-
typedefenumInvertedWalkNextStep
70-
{
71-
NextStepBegin,
72-
NextStepUp,
73-
NextStepLeft,
74-
NextStepRight
75-
}InvertedWalkNextStep;
7665

7766
/*
7867
* rb_create: create an empty RBTree
@@ -567,6 +556,7 @@ rb_delete_node(RBTree *rb, RBNode *z)
567556
RBNode*x,
568557
*y;
569558

559+
/* This is just paranoia: we should only get called on a valid node */
570560
if (!z||z==RBNIL)
571561
return;
572562

@@ -730,114 +720,6 @@ rb_right_left_iterator(RBTreeIterator *iter)
730720
returniter->last_visited;
731721
}
732722

733-
staticRBNode*
734-
rb_direct_iterator(RBTreeIterator*iter)
735-
{
736-
if (iter->last_visited==NULL)
737-
{
738-
iter->last_visited=iter->rb->root;
739-
returniter->last_visited;
740-
}
741-
742-
if (iter->last_visited->left!=RBNIL)
743-
{
744-
iter->last_visited=iter->last_visited->left;
745-
returniter->last_visited;
746-
}
747-
748-
do
749-
{
750-
if (iter->last_visited->right!=RBNIL)
751-
{
752-
iter->last_visited=iter->last_visited->right;
753-
break;
754-
}
755-
756-
/* go up and one step right */
757-
for (;;)
758-
{
759-
RBNode*came_from=iter->last_visited;
760-
761-
iter->last_visited=iter->last_visited->parent;
762-
if (iter->last_visited==NULL)
763-
{
764-
iter->is_over= true;
765-
break;
766-
}
767-
768-
if ((iter->last_visited->right!=came_from)&& (iter->last_visited->right!=RBNIL))
769-
{
770-
iter->last_visited=iter->last_visited->right;
771-
returniter->last_visited;
772-
}
773-
}
774-
}
775-
while (iter->last_visited!=NULL);
776-
777-
returniter->last_visited;
778-
}
779-
780-
staticRBNode*
781-
rb_inverted_iterator(RBTreeIterator*iter)
782-
{
783-
RBNode*came_from;
784-
RBNode*current;
785-
786-
current=iter->last_visited;
787-
788-
loop:
789-
switch ((InvertedWalkNextStep)iter->next_step)
790-
{
791-
/* First call, begin from root */
792-
caseNextStepBegin:
793-
current=iter->rb->root;
794-
iter->next_step=NextStepLeft;
795-
gotoloop;
796-
797-
caseNextStepLeft:
798-
while (current->left!=RBNIL)
799-
current=current->left;
800-
801-
iter->next_step=NextStepRight;
802-
gotoloop;
803-
804-
caseNextStepRight:
805-
if (current->right!=RBNIL)
806-
{
807-
current=current->right;
808-
iter->next_step=NextStepLeft;
809-
gotoloop;
810-
}
811-
else/* not moved - return current, then go up */
812-
iter->next_step=NextStepUp;
813-
break;
814-
815-
caseNextStepUp:
816-
came_from=current;
817-
current=current->parent;
818-
if (current==NULL)
819-
{
820-
iter->is_over= true;
821-
break;/* end of iteration */
822-
}
823-
elseif (came_from==current->right)
824-
{
825-
/* return current, then continue to go up */
826-
break;
827-
}
828-
else
829-
{
830-
/* otherwise we came from the left */
831-
Assert(came_from==current->left);
832-
iter->next_step=NextStepRight;
833-
gotoloop;
834-
}
835-
}
836-
837-
iter->last_visited=current;
838-
returncurrent;
839-
}
840-
841723
/*
842724
* rb_begin_iterate: prepare to traverse the tree in any of several orders
843725
*
@@ -849,7 +731,7 @@ rb_inverted_iterator(RBTreeIterator *iter)
849731
* tree are allowed.
850732
*
851733
* The iterator state is stored in the 'iter' struct. The caller should
852-
* treat it as opaque struct.
734+
* treat it asanopaque struct.
853735
*/
854736
void
855737
rb_begin_iterate(RBTree*rb,RBOrderControlctrl,RBTreeIterator*iter)
@@ -867,13 +749,6 @@ rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter)
867749
caseRightLeftWalk:/* visit right, then self, then left */
868750
iter->iterate=rb_right_left_iterator;
869751
break;
870-
caseDirectWalk:/* visit self, then left, then right */
871-
iter->iterate=rb_direct_iterator;
872-
break;
873-
caseInvertedWalk:/* visit left, then right, then self */
874-
iter->iterate=rb_inverted_iterator;
875-
iter->next_step=NextStepBegin;
876-
break;
877752
default:
878753
elog(ERROR,"unrecognized rbtree iteration order: %d",ctrl);
879754
}

‎src/include/lib/rbtree.h‎

Lines changed: 1 addition & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -35,9 +35,7 @@ typedef struct RBTree RBTree;
3535
typedefenumRBOrderControl
3636
{
3737
LeftRightWalk,/* inorder: left child, node, right child */
38-
RightLeftWalk,/* reverse inorder: right, node, left */
39-
DirectWalk,/* preorder: node, left child, right child */
40-
InvertedWalk/* postorder: left child, right child, node */
38+
RightLeftWalk/* reverse inorder: right, node, left */
4139
}RBOrderControl;
4240

4341
/*
@@ -52,7 +50,6 @@ struct RBTreeIterator
5250
RBTree*rb;
5351
RBNode*(*iterate) (RBTreeIterator*iter);
5452
RBNode*last_visited;
55-
charnext_step;
5653
boolis_over;
5754
};
5855

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp