Page Menu
Home
FreeBSD
Search
Configure Global Search
Log In
Files
F6903706
treerace.c
dougm (Doug Moore)
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Flag For Later
Award Token
Authored By
dougm
Jul 8 2020, 9:33 AM
2020-07-08 09:33:38 (UTC+0)
Size
948 B
Referenced Files
None
Subscribers
None
treerace.c
View Options
#include
<assert.h>
#include
<stdio.h>
#include
<stdlib.h>
//#include <sys/tree.h>
#include
<stdint.h>
#if 0
#include "freebsd/src/sys/sys/dm.tree.h"
#else
#include
"freebsd/src/sys/sys/tree.h"
#endif
struct
item
{
RB_ENTRY
(
item
)
it_entry
;
int
val
;
};
static
int
item_cmp
(
struct
item
*
a
,
struct
item
*
b
)
{
return
a
->
val
<
b
->
val
?
-1
:
a
->
val
>
b
->
val
;
}
RB_HEAD
(
item_tree
,
item
)
tree
=
RB_INITIALIZER
(
&
tree
);
RB_GENERATE_STATIC
(
item_tree
,
item
,
it_entry
,
item_cmp
);
int
main
()
{
int
maxsize
=
10000
;
int
count
;
struct
item
*
ins
=
malloc
(
sizeof
(
*
ins
));
for
(
count
=
0
;
count
<
100000000
;
++
count
)
{
ins
->
val
=
count
;
if
(
RB_INSERT
(
item_tree
,
&
tree
,
ins
)
==
NULL
)
ins
=
malloc
(
sizeof
(
*
ins
));
if
(
count
>=
maxsize
)
{
struct
item
key
;
key
.
val
=
count
-
maxsize
;
struct
item
*
found
=
RB_FIND
(
item_tree
,
&
tree
,
&
key
);
if
(
found
!=
NULL
)
{
RB_REMOVE
(
item_tree
,
&
tree
,
found
);
free
(
found
);
}
}
}
return
0
;
}
File Metadata
Details
Attached
Mime Type
text/x-c
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
2684207
Default Alt Text
treerace.c (948 B)
Attached To
Mode
D25480: Change from red-black to wavl balancing for RB trees
Attached
Detach File
Event Timeline
Log In to Comment