On Thu, 13 Nov 2014 17:09:27 -0500 Tejun Heo <[email protected]> wrote:
> Implement set of pointers. Pointers can be added, deleted and
> iterated. It's currently implemented as a thin rbtree wrapper making
> addition and removal O(log N). A drawback is that iteration isn't RCU
> safe, which is okay for now. This will be used to remove
> inode->i_devices.
>
Confused.
>
> --- /dev/null
> +++ b/include/linux/ptrset.h
> @@ -0,0 +1,74 @@
> +/*
> + * include/linux/ptrset.h - set of pointers
> + *
> + * Copyright (C) 2014 Tejun Heo, Red Hat Inc.
> + *
> + * A ptrset contains an unordered set of pointers. Pointers can be added,
> + * deleted and iterated. Addition and removal complexities are O(log N)
> + * where N is the total number of elements in the ptrset.
> + */
> +
> +#ifndef __PTRSET_H
> +#define __PTRSET_H
> +
> +#include <linux/preempt.h>
> +#include <linux/rbtree.h>
> +
> +struct ptrset {
> + struct rb_root root;
> +};
> +
> +struct ptrset_elem {
> + void *ptr;
> + struct rb_node node;
> +};
> +
> +struct ptrset_iter {
> + struct ptrset_elem *pos;
> + struct ptrset_elem *next;
> +};
This seems rather slow and bloaty. Why not
struct tjpointer {
struct list_head list;
void *pointer;
};
And then callers do things like
struct tjpointer *tjp;
lock();
for_each_tjpointer(tjp, &my_tjpointer_list) {
foo(tjp->ptr);
}
tjpointer_del(tjp);
unlock();
That's less storage, vastly less support code, insertion and removal
are O(1) and it doesn't need the ghastly preload thing.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
