unofficial mirror of bug-guix@gnu.org 
 help / color / mirror / code / Atom feed
From: "Ludovic Courtès" <ludo@gnu.org>
To: Leo Prikler <leo.prikler@student.tugraz.at>
Cc: 45570@debbugs.gnu.org, conjaroy@gmail.com
Subject: bug#45570: [PATCH] system: Assert, that user and group names are unique.
Date: Thu, 07 Jan 2021 09:29:59 +0100	[thread overview]
Message-ID: <87im89jgjc.fsf@gnu.org> (raw)
In-Reply-To: <ae66ed3a5c4b862c9cc9ae2bdb6954a51434d79c.camel@student.tugraz.at> (Leo Prikler's message of "Wed, 06 Jan 2021 22:00:03 +0100")

Hi,

Leo Prikler <leo.prikler@student.tugraz.at> skribis:

> 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?

Their implementation is not “purely functional” but it’s
inconsequential; it’s a persistent data structure, and that’s what
matters (info "(guile) VLists").

>> > >   (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.

Yes, but it’s a small ‘n’, typically one or two.

Ludo’.




  reply	other threads:[~2021-01-07  8:31 UTC|newest]

Thread overview: 15+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-12-31 18:14 bug#45570: operating-system definitions allow duplicate passwd and group entries Jason Conroy
2021-01-01 11:13 ` bug#45570: [PATCH] system: Assert, that user and group names are unique Leo Prikler
2021-01-02  1:16   ` Danny Milosavljevic
2021-01-02  5:57 ` Leo Prikler
2021-01-06  9:56   ` Ludovic Courtès
2021-01-06 12:34     ` Leo Prikler
2021-01-06 13:32       ` Ludovic Courtès
2021-01-06 21:00         ` Leo Prikler
2021-01-07  8:29           ` Ludovic Courtès [this message]
2021-01-06 21:21 ` bug#45570: [PATCH v2] " Leo Prikler
2021-01-07  8:35   ` Ludovic Courtès
2021-01-07 11:13     ` Leo Prikler
2021-01-07 11:10 ` bug#45570: [PATCH v3] " Leo Prikler
2021-01-11 13:09   ` Ludovic Courtès
2021-01-11 15:06     ` Leo Prikler

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://guix.gnu.org/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=87im89jgjc.fsf@gnu.org \
    --to=ludo@gnu.org \
    --cc=45570@debbugs.gnu.org \
    --cc=conjaroy@gmail.com \
    --cc=leo.prikler@student.tugraz.at \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/guix.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).