On Mon, Nov 11, 2019 at 05:34:46PM +0100, Jan Kara wrote:
> Hi Sascha!
>
> On Mon 11-11-19 09:57:45, Sascha Hauer wrote:
> > On Wed, Nov 06, 2019 at 11:14:28AM +0100, Jan Kara wrote:
> > > > +/**
> > > > + * ubifs_dqblk_find_next - find the next qid
> > > > + * @c: UBIFS file-system description object
> > > > + * @qid: The qid to look for
> > > > + *
> > > > + * Find the next dqblk entry with a qid that is bigger or equally big than the
> > > > + * given qid. Returns the next dqblk entry if found or NULL if no dqblk exists
> > > > + * with a qid that is at least equally big.
> > > > + */
> > > > +static struct ubifs_dqblk *ubifs_dqblk_find_next(struct ubifs_info *c,
> > > > + struct kqid qid)
> > > > +{
> > > > + struct rb_node *node = c->dqblk_tree[qid.type].rb_node;
> > > > + struct ubifs_dqblk *next = NULL;
> > > > +
> > > > + while (node) {
> > > > + struct ubifs_dqblk *ud = rb_entry(node, struct ubifs_dqblk, rb);
> > > > +
> > > > + if (qid_eq(qid, ud->kqid))
> > > > + return ud;
> > > > +
> > > > + if (qid_lt(qid, ud->kqid)) {
> > > > + if (!next || qid_lt(ud->kqid, next->kqid))
> ^^^
> This condition looks superfluous as it should be always true. The last node
> where you went left should be the least greater node if you didn't find the
> exact match...
You are right. I can't say why I thought this is necessary when I wrote
this.
>
> > > > + next = ud;
> > > > +
> > > > + node = node->rb_left;
> > > > + } else {
> > > > + node = node->rb_right;
> > > > + }
> > > > + }
> > > > +
> > > > + return next;
> > > > +}
> > >
> > > Why not use rb_next() here? It should do what you need, shouldn't it?
> >
> > I could use rb_next(), but it defeats the purpose of a tree to iterate
> > over the whole tree to find an entry. If I wanted that I would have used
> > a list.
>
> I wasn't quite clear in my suggestion and now that I look at it it was
> actually misleading. I'm sorry for that. So a second try :):
>
> You have ubifs_dqblk_find() and ubifs_dqblk_find_next() doing very similar
> rbtree traversal. I think you could remove that duplication by using
> ubifs_dqblk_find_next() from ubifs_dqblk_find()?
Ok, with this the two functions can be simplified to:
/**
* ubifs_dqblk_find_next - find the next qid
* @c: UBIFS file-system description object
* @qid: The qid to look for
*
* Find the next dqblk entry with a qid that is bigger or equally big than the
* given qid. Returns the next dqblk entry if found or NULL if no dqblk exists
* with a qid that is at least equally big.
*/
static struct ubifs_dqblk *ubifs_dqblk_find_next(struct ubifs_info *c,
struct kqid qid)
{
struct rb_node *node = c->dqblk_tree[qid.type].rb_node;
struct ubifs_dqblk *next = NULL;
while (node) {
struct ubifs_dqblk *ud = rb_entry(node, struct ubifs_dqblk, rb);
if (qid_eq(qid, ud->kqid))
return ud;
if (qid_lt(qid, ud->kqid)) {
next = ud;
node = node->rb_left;
} else {
node = node->rb_right;
}
}
return next;
}
/**
* ubifs_dqblk_find - find qid in tree
* @c: UBIFS file-system description object
* @qid: The qid to look for
*
* This walks the dqblk tree and searches a given qid. Returns the dqblk entry
* when found or NULL otherwise.
*/
static struct ubifs_dqblk *ubifs_dqblk_find(struct ubifs_info *c,
struct kqid qid)
{
struct ubifs_dqblk *next = NULL;
next = ubifs_dqblk_find_next(c, qid);
if (next && qid_eq(qid, next->kqid))
return next;
return NULL;
}
If this looks good now I'll integrate it for the next round. I'll delay
sending a new version until Richard has had a look into this series.
Sascha
--
Pengutronix e.K. | |
Steuerwalder Str. 21 | http://www.pengutronix.de/ |
31137 Hildesheim, Germany | Phone: +49-5121-206917-0 |
Amtsgericht Hildesheim, HRA 2686 | Fax: +49-5121-206917-5555 |
