129807 - nssList_Clone() is O(n^2) if list->sortFunc is not NULL

Status: NEW

(NSS :: Libraries, defect, P2)

Description

[Wan-Teh Chang]

nssList_Clone() first creates an empty list.  Then it
steps through the old list and calls nssList_Add() to
add the same data to the new list.

If list->sortFunc is not NULL, the old list is sorted and
nssList_Add() needs to invoke the sort function k times
when the new list has k elements.  To clone a list with
n elements, the sort function will be invoked
0 + 1 + 2 + ... + (n-1) = n*(n-1)/2 times.

If list->sortFunc is NULL, nssList_Clone() is O(n)
because nssList_Add() is O(1).

Comment 1

[Ian McGreer]

sigh.  The list code is really not good, I wrote it to solve a problem, then
overused it.  I've been thinking of ways to remove dependencies on it (i.e.,
better ways of solving the problems that nssList is currently being used for).

Should this be a 3.4.1 bug?  The obvious fix is to clone the list directly
instead of using nssList_Add.

Comment 2

[Wan-Teh Chang]

Yes, cloning the list directly is the solution.

Setting target milestone 3.4.1, priority P2.

Comment 3

[Wan-Teh Chang]

Changed the QA contact to Bishakha.

Comment 4

[Wan-Teh Chang]

Set target milestone to NSS 3.5.

Comment 5

[Wan-Teh Chang]

Moved to target milestone 3.8 because the original
NSS 3.7 release has been renamed 3.8.

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

Remove target milestone of 3.8, since these bugs didn't get into that release.

Comment 7

[Anna Weine]

Attachment: Bug 129807 - Modifying the list_clone() function to just copy the nodes, without any sort