And as always, I didn't re-check a patch before sending it :) Here is a corrected version without any fprintf's.
-- Best regards, Aleksander Alekseev
diff --git a/src/backend/access/gin/ginbulk.c b/src/backend/access/gin/ginbulk.c index d6422ea..eac76c4 100644 --- a/src/backend/access/gin/ginbulk.c +++ b/src/backend/access/gin/ginbulk.c @@ -255,7 +255,7 @@ qsortCompareItemPointers(const void *a, const void *b) void ginBeginBAScan(BuildAccumulator *accum) { - rb_begin_iterate(accum->tree, LeftRightWalk); + rb_begin_left_right_walk(accum->tree, &accum->tree_walk); } /* @@ -271,7 +271,7 @@ ginGetBAEntry(BuildAccumulator *accum, GinEntryAccumulator *entry; ItemPointerData *list; - entry = (GinEntryAccumulator *) rb_iterate(accum->tree); + entry = (GinEntryAccumulator *) rb_left_right_walk(&accum->tree_walk); if (entry == NULL) return NULL; /* no more entries */ diff --git a/src/backend/lib/rbtree.c b/src/backend/lib/rbtree.c index 4fa8a1d..eb645a2 100644 --- a/src/backend/lib/rbtree.c +++ b/src/backend/lib/rbtree.c @@ -871,3 +871,278 @@ rb_iterate(RBTree *rb) return rb->iterate(rb); } + +/* + * Begin left right walk. + */ +void +rb_begin_left_right_walk(RBTree *rb, RBTreeLeftRightWalk * lrw) +{ + lrw->rb = rb; + lrw->last_visited = NULL; + lrw->is_over = (lrw->rb->root == RBNIL); +} + +/* + * Left right walk: get next node. Returns NULL if there is none. + */ +RBNode * +rb_left_right_walk(RBTreeLeftRightWalk * lrw) +{ + if (lrw->is_over) + return NULL; + + if (lrw->last_visited == NULL) + { + lrw->last_visited = lrw->rb->root; + while (lrw->last_visited->left != RBNIL) + lrw->last_visited = lrw->last_visited->left; + + return lrw->last_visited; + } + + if (lrw->last_visited->right != RBNIL) + { + lrw->last_visited = lrw->last_visited->right; + while (lrw->last_visited->left != RBNIL) + lrw->last_visited = lrw->last_visited->left; + + return lrw->last_visited; + } + + for (;;) + { + RBNode *came_from = lrw->last_visited; + + lrw->last_visited = lrw->last_visited->parent; + if (lrw->last_visited == NULL) + { + lrw->is_over = true; + break; + } + + if (lrw->last_visited->left == came_from) + break; /* came from left sub-tree, return current + * node */ + + /* else - came from right sub-tree, continue to move up */ + } + + return lrw->last_visited; +} + +/* + * Begin right left walk. + */ +void +rb_begin_right_left_walk(RBTree *rb, RBTreeRightLeftWalk * rlw) +{ + rlw->rb = rb; + rlw->last_visited = NULL; + rlw->is_over = (rlw->rb->root == RBNIL); +} + +/* + * Right left walk: get next node. Returns NULL if there is none. + */ +RBNode * +rb_right_left_walk(RBTreeRightLeftWalk * rlw) +{ + if (rlw->is_over) + return NULL; + + if (rlw->last_visited == NULL) + { + rlw->last_visited = rlw->rb->root; + while (rlw->last_visited->right != RBNIL) + rlw->last_visited = rlw->last_visited->right; + + return rlw->last_visited; + } + + if (rlw->last_visited->left != RBNIL) + { + rlw->last_visited = rlw->last_visited->left; + while (rlw->last_visited->right != RBNIL) + rlw->last_visited = rlw->last_visited->right; + + return rlw->last_visited; + } + + for (;;) + { + RBNode *came_from = rlw->last_visited; + + rlw->last_visited = rlw->last_visited->parent; + if (rlw->last_visited == NULL) + { + rlw->is_over = true; + break; + } + + if (rlw->last_visited->right == came_from) + break; /* came from right sub-tree, return current + * node */ + + /* else - came from left sub-tree, continue to move up */ + } + + return rlw->last_visited; +} + +/* + * Begin direct walk (a.k.a pre-order traversal). + * + * Pre-order traversal while duplicating nodes and edges can make a complete + * duplicate of a binary tree. It can also be used to make a prefix expression + * (Polish notation) from expression trees: traverse the expression tree + * pre-orderly. + * + * https://en.wikipedia.org/wiki/Tree_traversal#Applications + */ +void +rb_begin_direct_walk(RBTree *rb, RBTreeDirectWalk * dw) +{ + dw->rb = rb; + dw->last_visited = NULL; + dw->is_over = (dw->rb->root == RBNIL); +} + +/* + * Direct walk: get next node. Returns NULL if there is none. + */ +RBNode * +rb_direct_walk(RBTreeDirectWalk * dw) +{ + if (dw->is_over) + return NULL; + + if (dw->last_visited == NULL) + { + dw->last_visited = dw->rb->root; + return dw->last_visited; + } + + if (dw->last_visited->left != RBNIL) + { + dw->last_visited = dw->last_visited->left; + return dw->last_visited; + } + + do + { + if (dw->last_visited->right != RBNIL) + { + dw->last_visited = dw->last_visited->right; + break; + } + + /* go up and one step right */ + for (;;) + { + RBNode *came_from = dw->last_visited; + + dw->last_visited = dw->last_visited->parent; + if (dw->last_visited == NULL) + { + dw->is_over = true; + break; + } + + if ((dw->last_visited->right != came_from) && (dw->last_visited->right != RBNIL)) + { + dw->last_visited = dw->last_visited->right; + return dw->last_visited; + } + } + } + while (dw->last_visited != NULL); + + return dw->last_visited; +} + +/* + * Begin inverted walk (a.k.a post-order traversal). + */ +void +rb_begin_inverted_walk(RBTree *rb, RBTreeInvertedWalk * iw) +{ + iw->rb = rb; + iw->last_visited = NULL; + iw->next_step = NextStepNone; + iw->is_over = (iw->rb->root == RBNIL); +} + +/* + * Inverted walk: get next node. Returns NULL if there is none. + * + * Post-order traversal while deleting or freeing nodes and values can delete + * or free an entire binary tree. It can also generate a postfix + * representation of a binary tree. + * + * https://en.wikipedia.org/wiki/Tree_traversal#Applications + */ +RBNode * +rb_inverted_walk(RBTreeInvertedWalk * iw) +{ + RBNode *came_from; + + if (iw->is_over) + return NULL; + + if (iw->last_visited == NULL) + { + iw->last_visited = iw->rb->root; + iw->next_step = NextStepLeft; + } + +loop: + switch (iw->next_step) + { + case NextStepLeft: + came_from = iw->last_visited; + while (iw->last_visited->left != RBNIL) + iw->last_visited = iw->last_visited->left; + + iw->next_step = NextStepRight; + goto loop; + + case NextStepRight: + if (iw->last_visited->right != RBNIL) + { + iw->last_visited = iw->last_visited->right; + iw->next_step = NextStepLeft; + goto loop; + } + else /* not moved - return current, then go up */ + iw->next_step = NextStepUp; + break; + case NextStepUp: + for (;;) + { + came_from = iw->last_visited; + iw->last_visited = iw->last_visited->parent; + if (iw->last_visited == NULL) + { + iw->is_over = true; + break; /* end of iteration */ + } + + if (came_from == iw->last_visited->right) + { + /* return current, then continue to go up */ + break; + } + + /* otherwise we came from the left */ + iw->next_step = NextStepRight; + goto loop; + } + break; + default: /* should never happen but is usefull during + * debugging */ + elog(ERROR, "Unexpected next step value during inverted walk: %d\n", iw->next_step); + } + + return iw->last_visited; +} diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h index 68cfe0c..3438fb8 100644 --- a/src/include/access/gin_private.h +++ b/src/include/access/gin_private.h @@ -919,6 +919,7 @@ typedef struct GinEntryAccumulator *entryallocator; uint32 eas_used; RBTree *tree; + RBTreeLeftRightWalk tree_walk; } BuildAccumulator; extern void ginInitBA(BuildAccumulator *accum); diff --git a/src/include/lib/rbtree.h b/src/include/lib/rbtree.h index 73e83c3..541f978 100644 --- a/src/include/lib/rbtree.h +++ b/src/include/lib/rbtree.h @@ -63,4 +63,53 @@ extern void rb_delete(RBTree *rb, RBNode *node); extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl); extern RBNode *rb_iterate(RBTree *rb); +typedef enum RBTreeNextStep +{ + NextStepNone, + NextStepUp, + NextStepLeft, + NextStepRight +} RBTreeNextStep; + +typedef struct +{ + RBTree *rb; + RBNode *last_visited; + bool is_over; +} RBTreeLeftRightWalk; + +extern void rb_begin_left_right_walk(RBTree *rb, RBTreeLeftRightWalk * lrw); +extern RBNode *rb_left_right_walk(RBTreeLeftRightWalk * lrw); + +typedef struct +{ + RBTree *rb; + RBNode *last_visited; + bool is_over; +} RBTreeRightLeftWalk; + +extern void rb_begin_right_left_walk(RBTree *rb, RBTreeRightLeftWalk * rlw); +extern RBNode *rb_right_left_walk(RBTreeRightLeftWalk * rlw); + +typedef struct +{ + RBTree *rb; + RBNode *last_visited; + bool is_over; +} RBTreeDirectWalk; + +extern void rb_begin_direct_walk(RBTree *rb, RBTreeDirectWalk * dw); +extern RBNode *rb_direct_walk(RBTreeDirectWalk * dw); + +typedef struct +{ + RBTree *rb; + RBNode *last_visited; + RBTreeNextStep next_step; + bool is_over; +} RBTreeInvertedWalk; + +extern void rb_begin_inverted_walk(RBTree *rb, RBTreeInvertedWalk * dw); +extern RBNode *rb_inverted_walk(RBTreeInvertedWalk * dw); + #endif /* RBTREE_H */
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers