From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from [87.239.111.99] (localhost [127.0.0.1]) by dev.tarantool.org (Postfix) with ESMTP id 92CC7560EB1; Mon, 31 Jul 2023 23:30:43 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 92CC7560EB1 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1690835443; bh=glg3Vf6Vq/0UvRNXEU4mL65+raZX+p9RuMnN8NnlNLI=; h=To:Date:In-Reply-To:References:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=jKdW6WKKxijreXMt0225ma2m2vgpUAjlYMUA6/jcBTw2qNRj8inljQA3URED86iAr gOakm0dIx9lk708qkZtEQYiy1Zey3srxVwxOx82bt9xl3OT7eB4MaTR1UsCKfGl+sm 2E7zWAye48HHWemPHJIP/OHtlwt4MD1ILT5CmaGw= Received: from mail-lf1-f50.google.com (mail-lf1-f50.google.com [209.85.167.50]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id B7100560EB1 for ; Mon, 31 Jul 2023 23:30:13 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org B7100560EB1 Received: by mail-lf1-f50.google.com with SMTP id 2adb3069b0e04-4fe1489ced6so8004877e87.0 for ; Mon, 31 Jul 2023 13:30:13 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690835413; x=1691440213; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Wh6caj9gX7BHQ5TzS0ashZql0G+gE6impime1fdQki8=; b=I97cGUvjygk/KUcfqCQ7QPUsc6grMwq79gaX2up6KfLtqBi2P6Trc5VyPi8mpFJkWb +h4jFQbdJyIYllBEo8pyIN/M0O1WGhCyn6rgU968vdmKJspzgrArnh6PvDLGg/S9Y5iN 0pl/tJ7hxmUzs03+ewakNWNxCUfgR1wWx1NgmnAT5re3DzKTLF9po4fFMmgvLJvuvVhs ynpFATtbWR3i8bg5QE30KWZg6NoPTnWLqZEiuP4IkPL/FAUjlYEr5V/WXKDRdaojlTUS S2E+Hiup+7knA7TC7lUCcBA3DTxx/AdVhxDqfM8Rn8fYEWO5nJ8ScmsIof4WPwtDkp0Z NekQ== X-Gm-Message-State: ABy/qLZYlVyflmfO2aRrw1xWnfagNNPq8zn0djJQkMGP4CSmPIfsqt4r WPJkqdom43WVcTAwpF4roHe6vDJb53scog== X-Google-Smtp-Source: APBJJlGzGZJmIrV7ZKc+H5h6zZLxx4oMUaOlRkRTcpxAgfMtuKgKHoy20HcMNj9GKERmRY/YbLExpQ== X-Received: by 2002:a05:6512:20cd:b0:4f8:70d8:28f8 with SMTP id u13-20020a05651220cd00b004f870d828f8mr568978lfr.55.1690835412575; Mon, 31 Jul 2023 13:30:12 -0700 (PDT) Received: from localhost.localdomain (95-24-1-220.broadband.corbina.ru. [95.24.1.220]) by smtp.gmail.com with ESMTPSA id r25-20020ac24d19000000b004fe1f1c0ee4sm1814906lfi.82.2023.07.31.13.30.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 31 Jul 2023 13:30:12 -0700 (PDT) X-Google-Original-From: Maxim Kokryashkin To: tarantool-patches@dev.tarantool.org, skaplun@tarantool.org, imun@tarantool.org Date: Mon, 31 Jul 2023 23:30:03 +0300 Message-ID: X-Mailer: git-send-email 2.41.0 In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH luajit v3 1/4] utils: remove unnecessary insertion in AVL-tree X-BeenThere: tarantool-patches@dev.tarantool.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Maxim Kokryashkin via Tarantool-patches Reply-To: Maxim Kokryashkin Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" This patch fixes a bug in the AVL-tree implementation, which produced unnecessary inserts of values into nodes, instead of replacement. Needed for tarantool/tarantool#8700 --- .../tarantool-tests/gh-5813-resolving-of-c-symbols.test.lua | 6 ++---- tools/utils/avl.lua | 4 ++-- tools/utils/symtab.lua | 2 +- 3 files changed, 5 insertions(+), 7 deletions(-) diff --git a/test/tarantool-tests/gh-5813-resolving-of-c-symbols.test.lua b/test/tarantool-tests/gh-5813-resolving-of-c-symbols.test.lua index 30b8a3ca..c448248a 100644 --- a/test/tarantool-tests/gh-5813-resolving-of-c-symbols.test.lua +++ b/test/tarantool-tests/gh-5813-resolving-of-c-symbols.test.lua @@ -25,10 +25,8 @@ local function tree_contains(node, name) if node == nil then return false else - for i = 1, #node.value do - if node.value[i].name == name then - return true - end + if node.value.name == name then + return true end return tree_contains(node.left, name) or tree_contains(node.right, name) end diff --git a/tools/utils/avl.lua b/tools/utils/avl.lua index d5baa534..81ef9265 100644 --- a/tools/utils/avl.lua +++ b/tools/utils/avl.lua @@ -78,7 +78,7 @@ end function M.insert(node, key, value) assert(key, "Key can't be nil") if node == nil then - return create_node(key, { value }) + return create_node(key, value) end if key < node.key then @@ -86,7 +86,7 @@ function M.insert(node, key, value) elseif key > node.key then node.right = M.insert(node.right, key, value) else - table.insert(node.value, value) + node.value = value end update_height(node) diff --git a/tools/utils/symtab.lua b/tools/utils/symtab.lua index c26a9e8c..7f6c78f0 100644 --- a/tools/utils/symtab.lua +++ b/tools/utils/symtab.lua @@ -176,7 +176,7 @@ function M.demangle(symtab, loc) local key, value = avl.floor(symtab.cfunc, addr) if key then - return string_format("%s:%#x", value[gen].name, key) + return string_format("%s:%#x", value.name, key) end return string_format("CFUNC %#x", addr) -- 2.41.0