From patchwork Fri Dec 13 18:11:00 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1209349 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-515935-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="XIOS9+iE"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="BIlb5urY"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47ZJlC3jh1z9sPV for ; Sat, 14 Dec 2019 05:16:23 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; q=dns; s= default; b=pmxjmYmMyoHTzXQtxWzoHY7J+SljObf3ZeRlUfehYg8lQBU5PzhAD kct4pSsFcL49umQftcWA3mXgebt5U4FzUOkp9Lc32f9Y/gxN7msUcZ/CJaaRqvkF RMib2vpTKL1OTSnOJcYknaKSqjYEOp5RrXn0KWspOSivAJ9rpPi4FQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; s=default; bh=VnrqoJB0KVuoAKtxELZ92ZfbIxY=; b=XIOS9+iE+nPvDy2RHnXx+NhtSW/k cnJFYZ6mR5QwGXjHCiBaAAY489RVkOBZpxkS+n4JCGOvbWzxro5yCbcQOnJKdGD/ wDO5ENqHn3uE0zC2biHYUkpUs/7j17VhJ9A7JN/wXWac59CN7ZHVdcWiGkcBqUOq uAv8sacIKKugsEc= Received: (qmail 103109 invoked by alias); 13 Dec 2019 18:12:19 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 101018 invoked by uid 89); 13 Dec 2019 18:11:58 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.6 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT autolearn=ham version=3.3.1 spammy=key_type, tmh, UD:tm.h X-HELO: us-smtp-1.mimecast.com Received: from us-smtp-delivery-1.mimecast.com (HELO us-smtp-1.mimecast.com) (205.139.110.120) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 13 Dec 2019 18:11:50 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1576260708; 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=1t/WYb+qxsRj7YLzELZYi6Vf6aBFx/GKpzpj44ZX3ok=; b=BIlb5urYjNfBtR4feUdMBIjcFqkbXfXK/PWp6xBPTh7DqlO/ziwx97PpOhbmdgO5j6pHbF fUdCeemdDWNTBnuXlgIefPfMU4AXawunn5Ctk5hkNLVCOC3RarCdF05XyjWuWf1V72078X KDHmcTZsjc5Otu8qkexU5wAREjSByfU= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-12-r5hPl4ADNrOfhQtQTQDFYw-1; Fri, 13 Dec 2019 13:11:44 -0500 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 1E3CC107ACC9 for ; Fri, 13 Dec 2019 18:11:44 +0000 (UTC) Received: from t470.redhat.com (ovpn-117-164.phx2.redhat.com [10.3.117.164]) by smtp.corp.redhat.com (Postfix) with ESMTP id B28A24B4; Fri, 13 Dec 2019 18:11:43 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [PATCH 11/45] Add ordered_hash_map Date: Fri, 13 Dec 2019 13:11:00 -0500 Message-Id: <20191213181134.1830-12-dmalcolm@redhat.com> In-Reply-To: <20191213181134.1830-1-dmalcolm@redhat.com> References: <20191213181134.1830-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-IsSubscribed: yes This patch adds an ordered_hash_map template, which is similar to hash_map, but preserves insertion order. gcc/ChangeLog: * Makefile.in (OBJS): Add ordered-hash-map-tests.o. * ordered-hash-map-tests.cc: New file. * ordered-hash-map.h: New file. * selftest-run-tests.c (selftest::run_tests): Call selftest::ordered_hash_map_tests_cc_tests. * selftest.h (selftest::ordered_hash_map_tests_cc_tests): New decl. --- gcc/Makefile.in | 1 + gcc/ordered-hash-map-tests.cc | 247 ++++++++++++++++++++++++++++++++++ gcc/ordered-hash-map.h | 184 +++++++++++++++++++++++++ gcc/selftest-run-tests.c | 1 + gcc/selftest.h | 1 + 5 files changed, 434 insertions(+) create mode 100644 gcc/ordered-hash-map-tests.cc create mode 100644 gcc/ordered-hash-map.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index c1ca429935d4..77a12d5c7258 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1443,6 +1443,7 @@ OBJS = \ optinfo-emit-json.o \ options-save.o \ opts-global.o \ + ordered-hash-map-tests.o \ passes.o \ plugin.o \ postreload-gcse.o \ diff --git a/gcc/ordered-hash-map-tests.cc b/gcc/ordered-hash-map-tests.cc new file mode 100644 index 000000000000..266f60c06b63 --- /dev/null +++ b/gcc/ordered-hash-map-tests.cc @@ -0,0 +1,247 @@ +/* Unit tests for ordered-hash-map.h. + Copyright (C) 2015-2019 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "opts.h" +#include "hash-set.h" +#include "fixed-value.h" +#include "alias.h" +#include "flags.h" +#include "symtab.h" +#include "tree-core.h" +#include "stor-layout.h" +#include "tree.h" +#include "stringpool.h" +#include "ordered-hash-map.h" +#include "selftest.h" + +#if CHECKING_P + +namespace selftest { + +/* Populate *OUT_KVS with the key/value pairs of M. */ + +template +static void +get_kv_pairs (const HashMap &m, + auto_vec > *out_kvs) +{ + for (typename HashMap::iterator iter = m.begin (); + iter != m.end (); + ++iter) + out_kvs->safe_push (std::make_pair ((*iter).first, (*iter).second)); +} + +/* Construct an ordered_hash_map and verify that + various operations work correctly. */ + +static void +test_map_of_strings_to_int () +{ + ordered_hash_map m; + + const char *ostrich = "ostrich"; + const char *elephant = "elephant"; + const char *ant = "ant"; + const char *spider = "spider"; + const char *millipede = "Illacme plenipes"; + const char *eric = "half a bee"; + + /* A fresh hash_map should be empty. */ + ASSERT_EQ (0, m.elements ()); + ASSERT_EQ (NULL, m.get (ostrich)); + + /* Populate the hash_map. */ + ASSERT_EQ (false, m.put (ostrich, 2)); + ASSERT_EQ (false, m.put (elephant, 4)); + ASSERT_EQ (false, m.put (ant, 6)); + ASSERT_EQ (false, m.put (spider, 8)); + ASSERT_EQ (false, m.put (millipede, 750)); + ASSERT_EQ (false, m.put (eric, 3)); + + /* Verify that we can recover the stored values. */ + ASSERT_EQ (6, m.elements ()); + ASSERT_EQ (2, *m.get (ostrich)); + ASSERT_EQ (4, *m.get (elephant)); + ASSERT_EQ (6, *m.get (ant)); + ASSERT_EQ (8, *m.get (spider)); + ASSERT_EQ (750, *m.get (millipede)); + ASSERT_EQ (3, *m.get (eric)); + + /* Verify that the order of insertion is preserved. */ + auto_vec > kvs; + get_kv_pairs (m, &kvs); + ASSERT_EQ (kvs.length (), 6); + ASSERT_EQ (kvs[0].first, ostrich); + ASSERT_EQ (kvs[0].second, 2); + ASSERT_EQ (kvs[1].first, elephant); + ASSERT_EQ (kvs[1].second, 4); + ASSERT_EQ (kvs[2].first, ant); + ASSERT_EQ (kvs[2].second, 6); + ASSERT_EQ (kvs[3].first, spider); + ASSERT_EQ (kvs[3].second, 8); + ASSERT_EQ (kvs[4].first, millipede); + ASSERT_EQ (kvs[4].second, 750); + ASSERT_EQ (kvs[5].first, eric); + ASSERT_EQ (kvs[5].second, 3); +} + +/* Construct an ordered_hash_map using int_hash and verify that various + operations work correctly. */ + +static void +test_map_of_int_to_strings () +{ + const int EMPTY = -1; + const int DELETED = -2; + typedef int_hash int_hash_t; + ordered_hash_map m; + + const char *ostrich = "ostrich"; + const char *elephant = "elephant"; + const char *ant = "ant"; + const char *spider = "spider"; + const char *millipede = "Illacme plenipes"; + const char *eric = "half a bee"; + + /* A fresh hash_map should be empty. */ + ASSERT_EQ (0, m.elements ()); + ASSERT_EQ (NULL, m.get (2)); + + /* Populate the hash_map. */ + ASSERT_EQ (false, m.put (2, ostrich)); + ASSERT_EQ (false, m.put (4, elephant)); + ASSERT_EQ (false, m.put (6, ant)); + ASSERT_EQ (false, m.put (8, spider)); + ASSERT_EQ (false, m.put (750, millipede)); + ASSERT_EQ (false, m.put (3, eric)); + + /* Verify that we can recover the stored values. */ + ASSERT_EQ (6, m.elements ()); + ASSERT_EQ (*m.get (2), ostrich); + ASSERT_EQ (*m.get (4), elephant); + ASSERT_EQ (*m.get (6), ant); + ASSERT_EQ (*m.get (8), spider); + ASSERT_EQ (*m.get (750), millipede); + ASSERT_EQ (*m.get (3), eric); + + /* Verify that the order of insertion is preserved. */ + auto_vec > kvs; + get_kv_pairs (m, &kvs); + ASSERT_EQ (kvs.length (), 6); + ASSERT_EQ (kvs[0].first, 2); + ASSERT_EQ (kvs[0].second, ostrich); + ASSERT_EQ (kvs[1].first, 4); + ASSERT_EQ (kvs[1].second, elephant); + ASSERT_EQ (kvs[2].first, 6); + ASSERT_EQ (kvs[2].second, ant); + ASSERT_EQ (kvs[3].first, 8); + ASSERT_EQ (kvs[3].second, spider); + ASSERT_EQ (kvs[4].first, 750); + ASSERT_EQ (kvs[4].second, millipede); + ASSERT_EQ (kvs[5].first, 3); + ASSERT_EQ (kvs[5].second, eric); +} + +/* Verify that we can remove items from an ordered_hash_map. */ + +static void +test_removal () +{ + ordered_hash_map m; + + const char *ostrich = "ostrich"; + ASSERT_EQ (false, m.put (ostrich, 2)); + + ASSERT_EQ (1, m.elements ()); + ASSERT_EQ (2, *m.get (ostrich)); + + { + auto_vec > kvs; + get_kv_pairs (m, &kvs); + ASSERT_EQ (kvs.length (), 1); + ASSERT_EQ (kvs[0].first, ostrich); + ASSERT_EQ (kvs[0].second, 2); + } + + m.remove (ostrich); + + ASSERT_EQ (0, m.elements ()); + { + auto_vec > kvs; + get_kv_pairs (m, &kvs); + ASSERT_EQ (kvs.length (), 0); + } + + /* Reinsertion (with a different value). */ + ASSERT_EQ (false, m.put (ostrich, 42)); + ASSERT_EQ (1, m.elements ()); + ASSERT_EQ (42, *m.get (ostrich)); + { + auto_vec > kvs; + get_kv_pairs (m, &kvs); + ASSERT_EQ (kvs.length (), 1); + ASSERT_EQ (kvs[0].first, ostrich); + ASSERT_EQ (kvs[0].second, 42); + } +} + +/* Verify that ordered_hash_map's copy-ctor works. */ + +static void +test_copy_ctor () +{ + ordered_hash_map m; + + const char *ostrich = "ostrich"; + ASSERT_EQ (false, m.put (ostrich, 2)); + + ASSERT_EQ (1, m.elements ()); + ASSERT_EQ (2, *m.get (ostrich)); + + ordered_hash_map copy (m); + ASSERT_EQ (1, copy.elements ()); + ASSERT_EQ (2, *copy.get (ostrich)); + + /* Remove from source. */ + m.remove (ostrich); + ASSERT_EQ (0, m.elements ()); + + /* Copy should be unaffected. */ + ASSERT_EQ (1, copy.elements ()); + ASSERT_EQ (2, *copy.get (ostrich)); +} + +/* Run all of the selftests within this file. */ + +void +ordered_hash_map_tests_cc_tests () +{ + test_map_of_strings_to_int (); + test_map_of_int_to_strings (); + test_removal (); + test_copy_ctor (); +} + +} // namespace selftest + +#endif /* CHECKING_P */ diff --git a/gcc/ordered-hash-map.h b/gcc/ordered-hash-map.h new file mode 100644 index 000000000000..4e35cadcfa18 --- /dev/null +++ b/gcc/ordered-hash-map.h @@ -0,0 +1,184 @@ +/* A type-safe hash map that retains the insertion order of keys. + Copyright (C) 2019 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + + +#ifndef GCC_ORDERED_HASH_MAP_H +#define GCC_ORDERED_HASH_MAP_H + +/* Notes: + - The keys must be PODs, since vec<> uses assignment to populate slots + without properly initializing them. + - doesn't have GTY support. + - supports removal, but retains order of original insertion. + (Removal might be better handled by using a doubly-linked list + of nodes, holding the values). */ + +template +class ordered_hash_map +{ + typedef typename Traits::key_type Key; + +public: + ordered_hash_map () {} + + ordered_hash_map (const ordered_hash_map &other) + : m_map (other.m_map), + m_keys (other.m_keys.length ()), + m_key_index (other.m_key_index) + { + unsigned i; + Key key; + FOR_EACH_VEC_ELT (other.m_keys, i, key) + m_keys.quick_push (key); + } + + /* If key K isn't already in the map add key K with value V to the map, and + return false. Otherwise set the value of the entry for key K to be V and + return true. */ + + bool put (const Key &k, const Value &v) + { + bool existed = m_map.put (k, v); + if (!existed) + { + bool key_present; + int &slot = m_key_index.get_or_insert (k, &key_present); + if (!key_present) + { + slot = m_keys.length (); + m_keys.safe_push (k); + } + } + return existed; + } + + /* If the passed in key is in the map return its value otherwise NULL. */ + + Value *get (const Key &k) + { + return m_map.get (k); + } + + /* Removing a key removes it from the map, but retains the insertion + order. */ + + void remove (const Key &k) + { + m_map.remove (k); + } + + size_t elements () const { return m_map.elements (); } + + class iterator + { + public: + explicit iterator (const ordered_hash_map &map, unsigned idx) : + m_ordered_hash_map (map), m_idx (idx) {} + + iterator &operator++ () + { + /* Increment m_idx until we find a non-deleted element, or go beyond + the end. */ + while (1) + { + ++m_idx; + if (valid_index_p ()) + break; + } + return *this; + } + + /* Can't use std::pair here, because GCC before 4.3 don't handle + std::pair where template parameters are references well. + See PR86739. */ + struct reference_pair { + const Key &first; + Value &second; + + reference_pair (const Key &key, Value &value) + : first (key), second (value) {} + + template + operator std::pair () const { return std::pair (first, second); } + }; + + reference_pair operator* () + { + const Key &k = m_ordered_hash_map.m_keys[m_idx]; + Value *slot + = const_cast (m_ordered_hash_map).get (k); + gcc_assert (slot); + return reference_pair (k, *slot); + } + + bool + operator != (const iterator &other) const + { + return m_idx != other.m_idx; + } + + /* Treat one-beyond-the-end as valid, for handling the "end" case. */ + + bool valid_index_p () const + { + if (m_idx > m_ordered_hash_map.m_keys.length ()) + return false; + if (m_idx == m_ordered_hash_map.m_keys.length ()) + return true; + const Key &k = m_ordered_hash_map.m_keys[m_idx]; + Value *slot + = const_cast (m_ordered_hash_map).get (k); + return slot != NULL; + } + + const ordered_hash_map &m_ordered_hash_map; + unsigned m_idx; + }; + + /* Standard iterator retrieval methods. */ + + iterator begin () const + { + iterator i = iterator (*this, 0); + while (!i.valid_index_p () && i != end ()) + ++i; + return i; + } + iterator end () const { return iterator (*this, m_keys.length ()); } + +private: + /* The underlying map. */ + hash_map m_map; + + /* The ordering of the keys. */ + auto_vec m_keys; + + /* For each key that's ever been in the map, its index within m_keys. */ + hash_map m_key_index; +}; + +/* Two-argument form. */ + +template, + Value> > +class ordered_hash_map; + +#endif /* GCC_ORDERED_HASH_MAP_H */ diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c index 9563c9e831de..156575a6695c 100644 --- a/gcc/selftest-run-tests.c +++ b/gcc/selftest-run-tests.c @@ -76,6 +76,7 @@ selftest::run_tests () cgraph_c_tests (); optinfo_emit_json_cc_tests (); opt_problem_cc_tests (); + ordered_hash_map_tests_cc_tests (); /* Mid-level data structures. */ input_c_tests (); diff --git a/gcc/selftest.h b/gcc/selftest.h index 0e4e07635333..81ee3046b927 100644 --- a/gcc/selftest.h +++ b/gcc/selftest.h @@ -242,6 +242,7 @@ extern void input_c_tests (); extern void json_cc_tests (); extern void opt_problem_cc_tests (); extern void optinfo_emit_json_cc_tests (); +extern void ordered_hash_map_tests_cc_tests (); extern void predict_c_tests (); extern void pretty_print_c_tests (); extern void range_tests ();