Bug 14309 - Can we utilize binary search for doubly LL
Summary: Can we utilize binary search for doubly LL
Status: NEW
Alias: None
Product: Samba 4.1 and newer
Classification: Unclassified
Component: Winbind (show other bugs)
Version: unspecified
Hardware: All All
: P5 normal (vote)
Target Milestone: ---
Assignee: Samba QA Contact
QA Contact: Samba QA Contact
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2020-03-03 07:14 UTC by Amit Kumar
Modified: 2020-03-03 08:00 UTC (History)
0 users

See Also:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Amit Kumar 2020-03-03 07:14:58 UTC 
./source3/smbd/dir.c

static struct dptr_struct *dptr_get(struct smbd_server_connection *sconn,
                                    int key, bool forclose)
...
        for (dptr = sconn->searches.dirptrs; dptr != NULL; dptr = dptr->next) {
                if(dptr->dnum != key) {
                        continue;
                }
..

Above for() is linear search.
And I see dptr_struct is doubly LL.
struct dptr_struct {
        struct dptr_struct *next, *prev;

Can we add dnum in increasing or decreasing order, making it contender for binary search?

O(logn) is far less than O(n) for 1000+ elements even!!
Comment 1 Ralph Böhme 2020-03-03 08:00:21 UTC 
Amit, thanks for looking into improving Samba.

To me this doesn't look to be a bug, but instead a possible performance improvement which you may want to discuss on the samba-technical mailing list.

I don't think Samba bugzilla is the right place to discuss this.

If you agree, please close the bugs and start a discussion on the mailing list. Thanks!