用rbtree存储目录结构。key是 parent + file name。
最近有一个需求，知道一个目录下的某个文件，需要匹配同目录下，同名但后缀不同的文件。
这种场景，rbtree能加速吗？
例子：
#include "rbtree.h"
#include <stdio.h>
#include <string.h>
struct photo
{
struct rb_node name_node;
long parent;
char name[64];
};
#define PHOTO_NAME(n) ((struct photo *)(n))
static int name_cmp(struct photo *l, long r, const char *r_name)
{
if (r > l->parent)
return 1;
else if (r < l->parent)
return -1;
return strcmp(r_name, l->name);
}
static int photo_name_key_cmp(struct rb_node *l, const void *key)
{
long r = (long)((void **)key)[0];
const char *r_name = ((void **)key)[1];
return name_cmp(PHOTO_NAME(l), r, r_name);
}
static int photo_name_cmp(struct rb_node *l, struct rb_node *r)
{
return name_cmp(PHOTO_NAME(l), PHOTO_NAME(r)->parent, PHOTO_NAME(r)->name);
}
struct photo photos[] = {
{ .parent = 1, .name = "13" },
{ .parent = 1, .name = "123" },
{ .parent = 1, .name = "123.jpg" },
{ .parent = 1, .name = "123.mov" },
{ .parent = 1, .name = "123.heic" },
{ .parent = 1, .name = "124.jpg" },
{ .parent = 1, .name = "124.mov" },
{ .parent = 1, .name = "124.heic" },
{ .parent = 1, .name = "125.jpg" },
{ .parent = 1, .name = "125.mov" },
{ .parent = 1, .name = "125.heic" },
{ .parent = 2, .name = "123.jpg" },
{ .parent = 2, .name = "123.mov" },
{ .parent = 2, .name = "123.heic" },
{ .parent = 2, .name = "124.jpg" },
{ .parent = 2, .name = "124.mov" },
{ .parent = 2, .name = "124.heic" },
{ .parent = 2, .name = "125.jpg" },
{ .parent = 2, .name = "125.mov" },
{ .parent = 2, .name = "125.heic" },
{ .parent = 3, .name = "123.jpg" },
{ .parent = 3, .name = "123.mov" },
{ .parent = 3, .name = "123.heic" },
{ .parent = 3, .name = "124.jpg" },
{ .parent = 3, .name = "124.mov" },
{ .parent = 3, .name = "124.heic" },
{ .parent = 3, .name = "125.jpg" },
{ .parent = 3, .name = "125.mov" },
{ .parent = 3, .name = "125.heic" },
};
struct rb_tree tree;
int main(int argc, char **argv)
{
int i;
struct photo *p;
rb_init(&tree);
for (i = 0; i < sizeof(photos)/sizeof(photos[0]); i++) {
int ret;
ret = rb_insert(&tree, &photos[i].name_node, photo_name_cmp);
printf("insert return %d\n", ret);
}
rb_for_each_entry(p, &tree, name_node) {
printf("photo parent %ld name %s\n", p->parent, p->name);
}
return 0;
}构造一些目录结构，插入，然后打印树里面的顺序。
注意这里用strcmp比较name的时候，要把right node的放前面。因为：
int strcmp(const char *s1, const char *s2);
strcmp() returns an integer indicating the result of the comparison, as follows:
• 0, if the s1 and s2 are equal;
• a negative value if s1 is less than s2;
• a positive value if s1 is greater than s2.
如果right node的name大，会返回正数。
编译后，运行。
photo parent 1 name 123 photo parent 1 name 123.heic photo parent 1 name 123.jpg photo parent 1 name 123.mov photo parent 1 name 124.heic photo parent 1 name 124.jpg photo parent 1 name 124.mov photo parent 1 name 125.heic photo parent 1 name 125.jpg photo parent 1 name 125.mov photo parent 1 name 13 photo parent 2 name 123.heic photo parent 2 name 123.jpg photo parent 2 name 123.mov photo parent 2 name 124.heic photo parent 2 name 124.jpg photo parent 2 name 124.mov photo parent 2 name 125.heic photo parent 2 name 125.jpg photo parent 2 name 125.mov photo parent 3 name 123.heic photo parent 3 name 123.jpg photo parent 3 name 123.mov photo parent 3 name 124.heic photo parent 3 name 124.jpg photo parent 3 name 124.mov photo parent 3 name 125.heic photo parent 3 name 125.jpg photo parent 3 name 125.mov
可以看到，顺序是parent优先排序，name后排序。
如果前缀相同，那么他们是紧密排列在一起的。
这就意味着，这是可以快速搜索的。只要通过前缀找到第一个。
核心前提是：
如果3个文件，2个前缀相同。1个前缀不同。那么前缀不同的，不可能插入到2个前缀相同的之间。
因此可以通过
rb_find_first()/rb_next_match匹配到。
封装为宏
rb_for_each_entry_match
struct rb_node *rb_find_first(struct rb_tree *tree, const void *key,
int (*cmp)(struct rb_node *, const void *))
{
struct rb_node *node = tree->root;
struct rb_node *match = NULL;
while (node) {
int ret = cmp(node, key);
if (ret <= 0) {
if (!ret)
match = node;
node = node->left;
}
else if (ret > 0)
node = node->right;
}
return match;
}
struct rb_node *rb_next_match(struct rb_node *node, const void *key,
int (*cmp)(struct rb_node *, const void *))
{
node = rb_next(node);
if (node && cmp(node, key))
node = NULL;
return node;
}
#define rb_for_each_entry_match(pos, tree, member, key, cmp) \
for (pos = rb_entry_safe(rb_find_first(tree, key, cmp), typeof(*pos), member); \
pos; \
pos = rb_entry_safe(rb_next_match(&pos->member, key, cmp), typeof(*pos), member))写一个前缀匹配比较函数。便利出来如下：
static int photo_name_cmp_prefix(struct rb_node *_l, const void *key)
{
long r = (long)((void **)key)[0];
const char *name = ((void **)key)[1];
struct photo *l = PHOTO_NAME(_l);
if (r > l->parent)
return 1;
else if (r < l->parent)
return -1;
return strncmp(name, l->name, strlen(name));
}
void *key[2] = { (void *)1, "12" };
rb_for_each_entry_match(p, &tree, name_node, (const void *)key, photo_name_cmp_prefix) {
printf("match parent %ld name %s\n", p->parent, p->name);
}key为parent 1，前缀12。运行匹配出来所有前缀为12的
match parent 1 name 123 match parent 1 name 123.heic match parent 1 name 123.jpg match parent 1 name 123.mov match parent 1 name 124.heic match parent 1 name 124.jpg match parent 1 name 124.mov match parent 1 name 125.heic match parent 1 name 125.jpg match parent 1 name 125.mov