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

Commite57519a

Browse files
committed
Add missing inequality searches to rbtree
PostgreSQL contains the implementation of the red-black tree. The red-blacktree is the ordered data structure, and one of its advantages is the abilityto do inequality searches. This commit adds rbt_find_less() andrbt_find_great() functions implementing these searches. While these searchesaren't yet used in the core code, they might be useful for extensions.Discussion:https://postgr.es/m/CAGRrpzYE8-7GCoaPjOiL9T_HY605MRax-2jgTtLq236uksZ1Sw%40mail.gmail.comAuthor: Steve Chavez, Alexander KorotkovReviewed-by: Alexander Korotkov
1 parent8d51d7f commite57519a

File tree

3 files changed

+166
-0
lines changed

3 files changed

+166
-0
lines changed

‎src/backend/lib/rbtree.c

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -161,6 +161,68 @@ rbt_find(RBTree *rbt, const RBTNode *data)
161161
returnNULL;
162162
}
163163

164+
/*
165+
* rbt_find_great: search for a greater value in an RBTree
166+
*
167+
* If equal_match is true, this will be a great or equal search.
168+
*
169+
* Returns the matching tree entry, or NULL if no match is found.
170+
*/
171+
RBTNode*
172+
rbt_find_great(RBTree*rbt,constRBTNode*data,boolequal_match)
173+
{
174+
RBTNode*node=rbt->root;
175+
RBTNode*greater=NULL;
176+
177+
while (node!=RBTNIL)
178+
{
179+
intcmp=rbt->comparator(data,node,rbt->arg);
180+
181+
if (equal_match&&cmp==0)
182+
returnnode;
183+
elseif (cmp<0)
184+
{
185+
greater=node;
186+
node=node->left;
187+
}
188+
else
189+
node=node->right;
190+
}
191+
192+
returngreater;
193+
}
194+
195+
/*
196+
* rbt_find_less: search for a lesser value in an RBTree
197+
*
198+
* If equal_match is true, this will be a less or equal search.
199+
*
200+
* Returns the matching tree entry, or NULL if no match is found.
201+
*/
202+
RBTNode*
203+
rbt_find_less(RBTree*rbt,constRBTNode*data,boolequal_match)
204+
{
205+
RBTNode*node=rbt->root;
206+
RBTNode*lesser=NULL;
207+
208+
while (node!=RBTNIL)
209+
{
210+
intcmp=rbt->comparator(data,node,rbt->arg);
211+
212+
if (equal_match&&cmp==0)
213+
returnnode;
214+
elseif (cmp>0)
215+
{
216+
lesser=node;
217+
node=node->right;
218+
}
219+
else
220+
node=node->left;
221+
}
222+
223+
returnlesser;
224+
}
225+
164226
/*
165227
* rbt_leftmost: fetch the leftmost (smallest-valued) tree node.
166228
* Returns NULL if tree is empty.

‎src/include/lib/rbtree.h

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,8 @@ extern RBTree *rbt_create(Size node_size,
6767
void*arg);
6868

6969
externRBTNode*rbt_find(RBTree*rbt,constRBTNode*data);
70+
externRBTNode*rbt_find_great(RBTree*rbt,constRBTNode*data,boolequal_match);
71+
externRBTNode*rbt_find_less(RBTree*rbt,constRBTNode*data,boolequal_match);
7072
externRBTNode*rbt_leftmost(RBTree*rbt);
7173

7274
externRBTNode*rbt_insert(RBTree*rbt,constRBTNode*data,bool*isNew);

‎src/test/modules/test_rbtree/test_rbtree.c

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -278,6 +278,107 @@ testfind(int size)
278278
}
279279
}
280280

281+
/*
282+
* Check the correctness of the rbt_find_less() and rbt_find_great() functions
283+
* by searching for an equal key and iterating the lesser keys then the greater
284+
* keys.
285+
*/
286+
staticvoid
287+
testfindltgt(intsize)
288+
{
289+
RBTree*tree=create_int_rbtree();
290+
291+
/*
292+
* Using the size as the random key to search wouldn't allow us to get at
293+
* least one greater match, so we do size - 1
294+
*/
295+
intrandomKey=pg_prng_uint64_range(&pg_global_prng_state,0,size-1);
296+
boolkeyDeleted;
297+
IntRBTreeNodesearchNode= {.key=randomKey};
298+
IntRBTreeNode*lteNode;
299+
IntRBTreeNode*gteNode;
300+
IntRBTreeNode*node;
301+
302+
/* Insert natural numbers */
303+
rbt_populate(tree,size,1);
304+
305+
/*
306+
* Since the search key is included in the naturals of the tree, we're
307+
* sure to find an equal match
308+
*/
309+
lteNode= (IntRBTreeNode*)rbt_find_less(tree, (RBTNode*)&searchNode, true);
310+
gteNode= (IntRBTreeNode*)rbt_find_great(tree, (RBTNode*)&searchNode, true);
311+
312+
if (lteNode==NULL||lteNode->key!=searchNode.key)
313+
elog(ERROR,"rbt_find_less() didn't find the equal key");
314+
315+
if (gteNode==NULL||gteNode->key!=searchNode.key)
316+
elog(ERROR,"rbt_find_great() didn't find the equal key");
317+
318+
if (lteNode!=gteNode)
319+
elog(ERROR,"rbt_find_less() and rbt_find_great() found different equal keys");
320+
321+
/* Find the rest of the naturals lesser than the search key */
322+
keyDeleted= false;
323+
for (;searchNode.key>0;searchNode.key--)
324+
{
325+
/*
326+
* Find the next key. If the current key is deleted, we can pass
327+
* equal_match == true and still find the next one.
328+
*/
329+
node= (IntRBTreeNode*)rbt_find_less(tree, (RBTNode*)&searchNode,
330+
keyDeleted);
331+
332+
/* ensure we find a lesser match */
333+
if (!node|| !(node->key<searchNode.key))
334+
elog(ERROR,"rbt_find_less() didn't find a lesser key");
335+
336+
/* randomly delete the found key or leave it */
337+
keyDeleted= (pg_prng_uint64_range(&pg_global_prng_state,0,1)==1);
338+
if (keyDeleted)
339+
rbt_delete(tree, (RBTNode*)node);
340+
}
341+
342+
/* Find the rest of the naturals greater than the search key */
343+
keyDeleted= false;
344+
for (searchNode.key=randomKey;searchNode.key<size-1;searchNode.key++)
345+
{
346+
/*
347+
* Find the next key. If the current key is deleted, we can pass
348+
* equal_match == true and still find the next one.
349+
*/
350+
node= (IntRBTreeNode*)rbt_find_great(tree, (RBTNode*)&searchNode,
351+
keyDeleted);
352+
353+
/* ensure we find a greater match */
354+
if (!node|| !(node->key>searchNode.key))
355+
elog(ERROR,"rbt_find_great() didn't find a greater key");
356+
357+
/* randomly delete the found key or leave it */
358+
keyDeleted= (pg_prng_uint64_range(&pg_global_prng_state,0,1)==1);
359+
if (keyDeleted)
360+
rbt_delete(tree, (RBTNode*)node);
361+
}
362+
363+
/* Check out of bounds searches find nothing */
364+
searchNode.key=-1;
365+
node= (IntRBTreeNode*)rbt_find_less(tree, (RBTNode*)&searchNode, true);
366+
if (node!=NULL)
367+
elog(ERROR,"rbt_find_less() found non-inserted element");
368+
searchNode.key=0;
369+
node= (IntRBTreeNode*)rbt_find_less(tree, (RBTNode*)&searchNode, false);
370+
if (node!=NULL)
371+
elog(ERROR,"rbt_find_less() found non-inserted element");
372+
searchNode.key=size;
373+
node= (IntRBTreeNode*)rbt_find_great(tree, (RBTNode*)&searchNode, true);
374+
if (node!=NULL)
375+
elog(ERROR,"rbt_find_great() found non-inserted element");
376+
searchNode.key=size-1;
377+
node= (IntRBTreeNode*)rbt_find_great(tree, (RBTNode*)&searchNode, false);
378+
if (node!=NULL)
379+
elog(ERROR,"rbt_find_great() found non-inserted element");
380+
}
381+
281382
/*
282383
* Check the correctness of the rbt_leftmost operation.
283384
* This operation should always return the smallest element of the tree.
@@ -408,6 +509,7 @@ test_rb_tree(PG_FUNCTION_ARGS)
408509
testleftright(size);
409510
testrightleft(size);
410511
testfind(size);
512+
testfindltgt(size);
411513
testleftmost(size);
412514
testdelete(size,Max(size /10,1));
413515
PG_RETURN_VOID();

0 commit comments

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