> This entirely removes the highly suboptimal duplicates checking from
> the passwd-walking loop.  In contrast to your linear-list 
> duplicates-finding solution, which runs on O(n^2), this method would be
> in O(n log n), which should be optimal for that application.

It won't matter that this is O(n^2) unless there are (probably)
10s of thousands of uids.
> 
> If you use arrays as a representation for the lists, you can use
> the C lib function mergesort(3) for sorting; merge sort in general
> has the advantage that it works best on presorted sequences, such as
> the passwd file, which one can assume is partially sorted (new passwd
> entries with higher uids tend to get added to the end.)

That would involve you using realloc to get one big list...
Which will scan very quickly anyway.

If you are worried about massive numbers of uids the sparsed bitmap
will save memory.


	David

-- 
David Laight: david@l8s.co.uk