From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by mx.groups.io with SMTP id smtpd.web10.7710.1610543974672996276 for ; Wed, 13 Jan 2021 05:19:34 -0800 Authentication-Results: mx.groups.io; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=cVN77nxG; spf=pass (domain: redhat.com, ip: 63.128.21.124, mailfrom: philmd@redhat.com) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1610543973; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=0471MQp6s5B5w+XZ3vgQVdUtCC9Ezt9syUp1bhUcKug=; b=cVN77nxGzHiu9R3CEOogQHGyNCoS+hBSPLbDA4UEU5Wm2ViGG4lnpngz/iY88NW+1tv+2B 0+iIGQjdXH0QohCVx2qvoc8oiDWNWjl4eea+jj7aBOnijER+g0qreSCj/va/oyNsask1C2 r/4Nx3kdXuMzvplEFWRnYtacksYT6Mk= Received: from mail-wr1-f72.google.com (mail-wr1-f72.google.com [209.85.221.72]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-442-hR7KjbU4OcWbaetF5T7Osg-1; Wed, 13 Jan 2021 08:19:32 -0500 X-MC-Unique: hR7KjbU4OcWbaetF5T7Osg-1 Received: by mail-wr1-f72.google.com with SMTP id 88so945587wrc.17 for ; Wed, 13 Jan 2021 05:19:31 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=0471MQp6s5B5w+XZ3vgQVdUtCC9Ezt9syUp1bhUcKug=; b=CqxSikuNNDag2lxwvfx0aAOshrwhn7OLE9RlWsuxELBzKVlEgFAAnIf+yg0bDFS2UA tq16ktjm3MpZPIRpSalipWSpKbF35YFcPmxVe/0qfKnEU6H3qZ33EBFHmtSBAzjROoSM xE8IVV0davUdjLa9ywRAndni1v1hmW2yCM3iAZpviQF5+3y9VBntnKr9kWtIyjcc3959 JK0WBQ/6HC+t4sy9kXATuWnYxoCEs1R502xmM/bU77/JI/iujJt7046hpy2GP6CyuSCl xVwHazUQV07onou7PgJfLBw/0ogI5mBlkweqUcFGSMUy38Dla+7aiU7+paaujSJRzc5M tD+Q== X-Gm-Message-State: AOAM530rLhWGpvmNKo/Cp8soxKabK8+6Q9tW4OCYNzYcms2tvxrqLocb bblkKfXRbBInKLfRIq8Mpglz3B0WABKYIC2a5sZcBzLasY+8zlKyWa6b8IEsPKsawIIVDwinjJl OQ6vgdmh4B1wbOA== X-Received: by 2002:a7b:ce17:: with SMTP id m23mr2181491wmc.117.1610543970481; Wed, 13 Jan 2021 05:19:30 -0800 (PST) X-Google-Smtp-Source: ABdhPJx/FjGHWnGnHgDP65skfQ//E/AyL5CoztapIm4REWYs8lbY01EGbfs1QJkC6obg6ovLAy/tUQ== X-Received: by 2002:a7b:ce17:: with SMTP id m23mr2181469wmc.117.1610543970231; Wed, 13 Jan 2021 05:19:30 -0800 (PST) Return-Path: Received: from [192.168.1.36] (190.red-83-57-173.dynamicip.rima-tde.net. [83.57.173.190]) by smtp.gmail.com with ESMTPSA id c13sm2143224wml.44.2021.01.13.05.19.29 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 13 Jan 2021 05:19:29 -0800 (PST) Subject: Re: [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList() To: Laszlo Ersek , devel@edk2.groups.io Cc: Ray Ni , Zhichao Gao References: <20210113085453.10168-1-lersek@redhat.com> <20210113085453.10168-7-lersek@redhat.com> From: =?UTF-8?B?UGhpbGlwcGUgTWF0aGlldS1EYXVkw6k=?= Message-ID: <9edabdc1-c13d-1dfa-a16f-ff51d861a52c@redhat.com> Date: Wed, 13 Jan 2021 14:19:28 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.6.0 MIME-Version: 1.0 In-Reply-To: <20210113085453.10168-7-lersek@redhat.com> Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=philmd@redhat.com X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit On 1/13/21 9:54 AM, Laszlo Ersek wrote: > Introduce the ShellSortFileList() function, for sorting an > EFI_SHELL_FILE_INFO list, by FileName or by FullName. > > Duplicates can be kept in the same list, or separated out to a new list. > In either case, the relative order between duplicates does not change (the > sorting is stable). > > For the sorting, use OrderedCollectionLib rather than SortLib: > > - The PerformQuickSort() function from the latter has quadratic worst-case > time complexity, plus it is implemented recursively (see > "MdeModulePkg/Library/UefiSortLib/UefiSortLib.c"). It can also not > return an error on memory allocation failure. > > - In comparison, the Red-Black Tree instance of OrderedCollectionLib sorts > in O(n*log(n)) worst-case time, contains no recursion with the default > PcdValidateOrderedCollection=FALSE setting, and the OrderedCollectionLib > class APIs return errors appropriately. > > The OrderedCollectionLib APIs do not permit duplicates natively, but by > using lists as collection entries, stable sorting of duplicates can be > achieved. > > Cc: Philippe Mathieu-Daudé > Cc: Ray Ni > Cc: Zhichao Gao > Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151 > Signed-off-by: Laszlo Ersek > Reviewed-by: Zhichao Gao > --- > > Notes: > v2: > - no changes > - pick up Zhichao's R-b > > ShellPkg/ShellPkg.dsc | 1 + > ShellPkg/Include/Library/ShellCommandLib.h | 81 +++++ > ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf | 1 + > ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h | 19 ++ > ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c | 312 ++++++++++++++++++++ > 5 files changed, 414 insertions(+) Reviewed-by: Philippe Mathieu-Daude