bug#45570: [PATCH] system: Assert, that user and group names are unique.

[Leo Prikler <leo.prikler@student.tugraz.at>]

Hi,

Am Mittwoch, den 06.01.2021, 14:32 +0100 schrieb Ludovic Courtès:
> Hi,
> 
> Leo Prikler <leo.prikler@student.tugraz.at> skribis:
> 
> > > > +    ((first . rest)
> > > > +     (if (member first rest =) ; (srfi srfi-1) member
> > > > +         (cons first (find-duplicates rest =))
> > > > +         (find-duplicates rest =)))))
> > > 
> > > Note that this is quadratic; it’s fine as long as we don’t have
> > > “too
> > > many” users, which may be the case in general.
> > It is indeed quadratic, but would there even be an n log n
> > solution?
> > I've once done an n log n sort+delete-duplicates!, perhaps that'd
> > be a
> > nicer solution here?
> 
> You could first build a hash table or vhash or set with all the
> names,
> then traverse again the list of names and check whether they’re in
> that
> table.  That’d be linear (assuming the table is well balanced), but
> the
> constant factor would be higher.
Yeah, I think the hash table solution would make the most sense here. 
Since VHashes are based on VLists, they're not actually purely
functional, are they?

> > >   (define (assert-unique-account-names users)
> > >     (match (find-duplicates things …)
> > >       (() #t)
> > >       (lst
> > >        (raise (formatted-message (G_ "the following accounts
> > > appear
> > > more than once:~{ ~a~}~%"
> > >                                  lst))))))
> > > 
> > > ?
> > That'd be weird for duplicate duplicates, hence just reporting the
> > first.
> 
> You could do (delete-duplicates lst) in the message above?
Sure, but that'd be O(n^2) on top of O(n^2), which is less than ideal.
I think I'll try working on a hash-based implementation for now.

Regards,
Leo