lkml.org 
[lkml]   [2014]   [Nov]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH vfs 1/2] lib: implement ptrset
On Thu, 13 Nov 2014 17:09:27 -0500 Tejun Heo <tj@kernel.org> 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.




\
 
 \ /
  Last update: 2014-11-14 00:01    [W:0.365 / U:0.020 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site