diff options
| author | Heikki Linnakangas <heikki.linnakangas@iki.fi> | 2016-09-02 08:39:39 +0300 |
|---|---|---|
| committer | Heikki Linnakangas <heikki.linnakangas@iki.fi> | 2016-09-02 08:39:39 +0300 |
| commit | 9f85784cae4d057f307b83b0d33edede33434f04 (patch) | |
| tree | 199b29051330542df1f8e3e9353dae492798f8a2 /src/include/lib/rbtree.h | |
| parent | 76f9dd4fa82270899f7b56b002b5d34226dc99d8 (diff) | |
| download | postgresql-9f85784cae4d057f307b83b0d33edede33434f04.tar.gz postgresql-9f85784cae4d057f307b83b0d33edede33434f04.zip | |
Support multiple iterators in the Red-Black Tree implementation.
While we don't need multiple iterators at the moment, the interface is
nicer and less dangerous this way.
Aleksander Alekseev, with some changes by me.
Diffstat (limited to 'src/include/lib/rbtree.h')
| -rw-r--r-- | src/include/lib/rbtree.h | 22 |
1 files changed, 19 insertions, 3 deletions
diff --git a/src/include/lib/rbtree.h b/src/include/lib/rbtree.h index 73e83c367a1..4537c587ac2 100644 --- a/src/include/lib/rbtree.h +++ b/src/include/lib/rbtree.h @@ -22,7 +22,6 @@ */ typedef struct RBNode { - char iteratorState; /* workspace for iterating through tree */ char color; /* node's current color, red or black */ struct RBNode *left; /* left child, or RBNIL if none */ struct RBNode *right; /* right child, or RBNIL if none */ @@ -41,6 +40,22 @@ typedef enum RBOrderControl InvertedWalk /* postorder: left child, right child, node */ } RBOrderControl; +/* + * RBTreeIterator holds state while traversing a tree. This is declared + * here so that callers can stack-allocate this, but must otherwise be + * treated as an opaque struct. + */ +typedef struct RBTreeIterator RBTreeIterator; + +struct RBTreeIterator +{ + RBTree *rb; + RBNode *(*iterate) (RBTreeIterator *iter); + RBNode *last_visited; + char next_step; + bool is_over; +}; + /* Support functions to be provided by caller */ typedef int (*rb_comparator) (const RBNode *a, const RBNode *b, void *arg); typedef void (*rb_combiner) (RBNode *existing, const RBNode *newdata, void *arg); @@ -60,7 +75,8 @@ extern RBNode *rb_leftmost(RBTree *rb); extern RBNode *rb_insert(RBTree *rb, const RBNode *data, bool *isNew); extern void rb_delete(RBTree *rb, RBNode *node); -extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl); -extern RBNode *rb_iterate(RBTree *rb); +extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, + RBTreeIterator *iter); +extern RBNode *rb_iterate(RBTreeIterator *iter); #endif /* RBTREE_H */ |