From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS53758 23.128.96.0/24 X-Spam-Status: No, score=-3.9 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_PASS,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by dcvr.yhbt.net (Postfix) with ESMTP id 54F081F55B for ; Sun, 10 May 2020 16:38:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729023AbgEJQiB (ORCPT ); Sun, 10 May 2020 12:38:01 -0400 Received: from pb-smtp21.pobox.com ([173.228.157.53]:58511 "EHLO pb-smtp21.pobox.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728932AbgEJQiB (ORCPT ); Sun, 10 May 2020 12:38:01 -0400 Received: from pb-smtp21.pobox.com (unknown [127.0.0.1]) by pb-smtp21.pobox.com (Postfix) with ESMTP id 1D8F1C9B1F; Sun, 10 May 2020 12:37:59 -0400 (EDT) (envelope-from junio@pobox.com) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; s=sasl; bh=7G1qI+wsCNF7 vnoTdfbAAoEEKA4=; b=lflQPqaiM/+eUtOW29+tupSWxxL1l0xjCWI21jEbHZIT vuh9RA6zgBzM2ZpYwoCDyC8joul6qXTEJxSEmW6DzHqX6t5iZDT2BL1d10x71vUM 6rt/s1tERX+XAJTPZ78h7Pvif/vZ4RYAvJevlwbVsr/slCmPUEZXr6gLkHqkOLc= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; q=dns; s=sasl; b=kXNG4i +MZTjg/zOSfWDJ5JcVEdz7CQoh9K+kkdg9DL0MLhg7m5QNxALR22EWamevIa4ohd zUonfJGR1CyB9sqzCLpGpFNWZ3JFsAkgSBJjFvxoJn072rp421VRa3U0qP6ZUY1S 3XAjg33c/00aWblVl8Xd2F3pjPEeD/r1F74Yo= Received: from pb-smtp21.sea.icgroup.com (unknown [127.0.0.1]) by pb-smtp21.pobox.com (Postfix) with ESMTP id 137F5C9B1E; Sun, 10 May 2020 12:37:59 -0400 (EDT) (envelope-from junio@pobox.com) Received: from pobox.com (unknown [34.74.119.39]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by pb-smtp21.pobox.com (Postfix) with ESMTPSA id 5B7BFC9B1D; Sun, 10 May 2020 12:37:56 -0400 (EDT) (envelope-from junio@pobox.com) From: Junio C Hamano To: =?utf-8?Q?Ren=C3=A9?= Scharfe Cc: Brandon Williams , git , Jeff King Subject: Re: invalid tree and commit object References: <938f0818-7e57-b883-009f-01db88ef8f65@web.de> Date: Sun, 10 May 2020 09:37:54 -0700 In-Reply-To: (=?utf-8?Q?=22R?= =?utf-8?Q?en=C3=A9?= Scharfe"'s message of "Sun, 10 May 2020 11:07:25 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 X-Pobox-Relay-ID: 9A1729C4-92DC-11EA-9A82-8D86F504CC47-77302942!pb-smtp21.pobox.com Content-Transfer-Encoding: quoted-printable Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Ren=C3=A9 Scharfe writes: > Would a stack work? When we see a candidate non-directory, we put > it on the stack. When we see a candidate directory, we compare it > to the entry at the top of the stack using strcmp(). Equality > indicates a duplicate and we are done. If the directory name is > less then we can pop the entry from the stack and check again, as > we're past the point where a duplicate would be. Makes sense? Perfectly and quite excited ;-) I wonder if we can do the same in the unpack-trees side.