From patchwork Fri Oct 12 13:29:20 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Diego Novillo X-Patchwork-Id: 191130 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id CCB402C0082 for ; Sat, 13 Oct 2012 00:29:34 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1350653375; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:Date:From:To:Subject:Message-ID: MIME-Version:Content-Type:Content-Disposition:User-Agent: Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:Sender:Delivered-To; bh=LmqLAukr3TSoym+D5tR5 XVuOEw8=; b=XMpzn+TkDI2h0NulTzYIR3o4CUqlIYxUzOTE27ukgVNnQPINQV8D Rv0iAKEcahPXIgEAVJUDM/ryg6ZJr6jegZ0dPSGrCSSDQWlEU89ez5NAEj6cn7zq /AhJiqpFTfcUJWV0JV8UfKlG2E4ZMm15Vnus8rCS/D5W3gvDBReYb4M= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:X-Google-DKIM-Signature:Received:Received:Received:Received:Date:From:To:Subject:Message-ID:MIME-Version:Content-Type:Content-Disposition:User-Agent:X-Gm-Message-State:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=cuE6CnhU0cz45/mglIMRIBrd3CDngROSP6rJovvEa+ntEQVbKHS2VdRGzsmC0P FfPumUhXIYlI+pcp/DJCCliCRTZkqjCuvLEVOaZ8l3zxXnvvm8AoU+xUXvqiGmTo qeEN31YXfDqtdBo9cOB//CQLVMTbwDfuC3tE/iUAC/Rnk=; Received: (qmail 4572 invoked by alias); 12 Oct 2012 13:29:29 -0000 Received: (qmail 4564 invoked by uid 22791); 12 Oct 2012 13:29:28 -0000 X-SWARE-Spam-Status: No, hits=-5.3 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, KHOP_RCVD_TRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-qa0-f73.google.com (HELO mail-qa0-f73.google.com) (209.85.216.73) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 12 Oct 2012 13:29:22 +0000 Received: by mail-qa0-f73.google.com with SMTP id 6so64831qam.2 for ; Fri, 12 Oct 2012 06:29:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=date:from:to:subject:message-id:mime-version:content-type :content-disposition:organization:user-agent:x-gm-message-state; bh=qlNxJkB2CkMfkhEVEQTkyCgrQjnFM9hF6WTdfDqQu3A=; b=fO5zJDX70uh28fy67P6Lc6sXylFQ+rPywa1HDS7xv0oWd1bRWeGzdWU4IpRn4WsMUI z4uVxnbkd6TRH9RJrw1ujwjmRW9y0kdsQlTaHmRpFKB9hMw93lhP6h/B4U/TyDLqo3QC x3pOsbXDgkLksdylV6J8x7flC+Wer4SZS+omYgJQrLt+G3HG+WWNUVrw0f2evWfhJcDF slpjZR6UEvgvlm7eqWgiv1WDgyAOQSxPCQhJm4Whnbz/Vd3u5NhOTCQUNPlBSFGVnUUU xjThU5WGAuO6sUyUgJ695jNVeXBRDkjHEz5KdwHhhy/QESnTAcav1LY4NE+fEJn4GFMs AOqg== Received: by 10.236.153.6 with SMTP id e6mr2876433yhk.20.1350048561599; Fri, 12 Oct 2012 06:29:21 -0700 (PDT) Received: from wpzn4.hot.corp.google.com (216-239-44-65.google.com [216.239.44.65]) by gmr-mx.google.com with ESMTPS id l20si690550yhi.2.2012.10.12.06.29.21 (version=TLSv1/SSLv3 cipher=AES128-SHA); Fri, 12 Oct 2012 06:29:21 -0700 (PDT) Received: from torture.tor.corp.google.com (torture.tor.corp.google.com [172.30.222.16]) by wpzn4.hot.corp.google.com (Postfix) with ESMTP id 7695B1E0043; Fri, 12 Oct 2012 06:29:21 -0700 (PDT) Received: by torture.tor.corp.google.com (Postfix, from userid 54752) id E1403C0BD3; Fri, 12 Oct 2012 06:29:20 -0700 (PDT) Date: Fri, 12 Oct 2012 09:29:20 -0400 From: Diego Novillo To: gcc-patches@gcc.gnu.org, Lawrence Crowl , Andrew Macleod Subject: Add usage documentation for hash_table Message-ID: <20121012132920.GA9249@google.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-Gm-Message-State: ALoCoQkl8Igz7qo8Rl4osmH+48+5Z4XQT15VckFE6ooajb355SKykkiPY3oYVf74Xx7y8jo85LPiiLpPmggMau6gCv9yD0bLiDLMTR4u+uTe1YDNsi6AB96AKYvBDugCcdczX4ny7PG40jKfBeOvXJ7gMS93rLhL2WAZPhafNYNd12SS4trOIjMJMfCVMUFOX2sogn9kd3qZQeObaQVdZbgDb+LLFy5/GQRJ1R1KvU6wTT98Rvq/SM0= X-IsSubscribed: yes 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 Add usage documentation for hash_table. Andrew, does this help? Lawrence, I think I've gotten the details right, but please confirm. Tested by re-building stage 1. * hash-table.h: Add usage documentation. Tidy formatting. diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 3aa66a7..0c51be6 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -21,8 +21,121 @@ along with GCC; see the file COPYING3. If not see /* This file implements a typed hash table. - The implementation borrows from libiberty's hashtab. */ + The implementation borrows from libiberty's htab_t. + Hash tables are instantiated with two type arguments: + + 1- Element: A type describing the elements in the table. + This type must provide 3 declarations: + + - A typedef to create the type Element::T. This is the type + of the elements stored in the table. So, if you want the + hash table of MyType elements, declare 'typedef MyType T;'. + + - A function named 'hash' that takes a pointer to Element::T + and returns a hashval_t value. This is the hashing + function. + + - A function named 'equal' that takes two pointers to + Element::T and returns an int. This is the comparison + function. It should return nonzero if the elements are + equal, 0 otherwise. + + - A static function named 'remove' that takes an Element::T + pointer and frees the memory allocated by it. This is used + when individual elements of the table need to be disposed of + (e.g., when deleting a hash table, removing elements from + the table, etc). + + 2- Allocator: A template type implementing allocation and deallocation for + the table itself. + + This type takes as argument a type passed on by the hash table + allocation and deallocation functions. It must provide four + static functions: + + - Allocator::control_alloc: This allocates the control data + blocks for the table. + + - Allocator::control_free: This frees the control data blocks + for the table. + + - Allocator::data_alloc: This allocates the data elements in + the table. + + - Allocator::data_free: This deallocates the data elements in + the table. + + In general, you will not need to provide your own Allocator type. + By default, hash tables will use the class xcallocator, which uses + malloc/free for allocation. + + Additionally, this file provides two common types for implementing + element removal: + + - typed_free_remove: it implements the method 'remove' to call + free(). + + - typed_noop_remove: it implements the method 'remove' to do + nothing. + + To use either of these removal strategies, simply make your type a + derived class of one of these two. + + Example usage: + + 1- A hash table for MyType: + + // Derive from typed_noop_remove so element removal does nothing. + class MyType : typed_noop_remove + { + int f1; + OtherType f2; + + // Hash table support. Need a typedef and 2 static functions. + + // 'T' is the type used in all the hash table functions. + typedef MyType T; + + // The hashing function. 'T' and 'MyType' are equivalent here. + static inline hashval_t hash (const MyType *); + + // The equality function. 'T' and 'MyType' are equivalent here. + static inline int equal (const MyType *, const MyType *); + }; + + inline hashval_t + MyType::hash (const MyType *e) + { ... compute and return a hash value for E ... } + + inline int + MyType::equal (const MyType *p1, const MyType *p2) + { ... compare P1 vs P2. Return 1 if they are the same ... } + + + Note that since MyType derives from typed_noop_remove, it does not + need to provide a 'remove' function. It inherits it from + typed_noop_remove. + + To instantiate a hash table for MyType: + + hash_table mytype_hash; + + You can then used any of the functions in hash_table's public interface. + See hash_table for details. The interface is very similar to libiberty's + htab_t. + + + 2- A hash table of pointers. + + This file provides the template type 'pointer_hash' which can be + used to create hash tables of pointers to any type. This class uses + the same hashing function used by libiberty's hash_pointer. + + To create a hash table of pointers to MyType: + + hash_table > ptr_htab; +*/ #ifndef TYPED_HASHTAB_H #define TYPED_HASHTAB_H @@ -71,7 +184,7 @@ xcallocator ::control_free (Type *memory) { return ::free (memory); } - + /* Free memory for data blocks. */ @@ -125,8 +238,7 @@ pointer_hash::hash (const T *candidate) template inline int -pointer_hash::equal (const T *existing, - const T *candidate) +pointer_hash::equal (const T *existing, const T *candidate) { return existing == candidate; } @@ -185,17 +297,17 @@ struct hash_table_control /* User-facing hash table type. - The table stores elements of type Element. + The table stores elements of type Element::T. - It hashes elements with the hash function. + It hashes elements with the hash function in Element. The table currently works with relatively weak hash functions. Use typed_pointer_hash when hashing pointers instead of objects. - It compares elements with the equal function. + It compares elements with the equal function in Element. Two elements with the same hash may not be equal. Use typed_pointer_equal when hashing pointers instead of objects. - It removes elements with the remove function. + It removes elements with the remove function in the Allocator. This feature is useful for freeing memory. Use typed_null_remove when not freeing objects. Use typed_free_remove when doing a simple object free. @@ -248,8 +360,7 @@ public: /* Construct the hash table. The only useful operation next is create. */ -template class Allocator> +template class Allocator> inline hash_table ::hash_table () : htab (NULL) @@ -259,8 +370,7 @@ hash_table ::hash_table () /* See if the table has been created, as opposed to constructed. */ -template class Allocator> +template class Allocator> inline bool hash_table ::is_created () { @@ -270,8 +380,7 @@ hash_table ::is_created () /* Like find_with_hash, but compute the hash value from the element. */ -template class Allocator> +template class Allocator> inline typename Descr::T * hash_table ::find (const T *comparable) { @@ -281,11 +390,10 @@ hash_table ::find (const T *comparable) /* Like find_slot_with_hash, but compute the hash value from the element. */ -template class Allocator> +template class Allocator> inline typename Descr::T ** -hash_table -::find_slot (const T *comparable, enum insert_option insert) +hash_table ::find_slot (const T *comparable, + enum insert_option insert) { return find_slot_with_hash (comparable, Descr::hash (comparable), insert); } @@ -293,11 +401,9 @@ hash_table /* Like remove_elt_with_hash, but compute the hash value from the element. */ -template class Allocator> +template class Allocator> inline void -hash_table -::remove_elt (const T *comparable) +hash_table ::remove_elt (const T *comparable) { remove_elt_with_hash (comparable, Descr::hash (comparable)); } @@ -305,8 +411,7 @@ hash_table /* Return the current size of this hash table. */ -template class Allocator> +template class Allocator> inline size_t hash_table ::size() { @@ -316,8 +421,7 @@ hash_table ::size() /* Return the current number of elements in this hash table. */ -template class Allocator> +template class Allocator> inline size_t hash_table ::elements() { @@ -328,8 +432,7 @@ hash_table ::elements() /* Return the fraction of fixed collisions during all work with given hash table. */ -template class Allocator> +template class Allocator> inline double hash_table ::collisions() { @@ -342,8 +445,7 @@ hash_table ::collisions() /* Create a hash table with at least the given number of INITIAL_SLOTS. */ -template class Allocator> +template class Allocator> void hash_table ::create (size_t size) { @@ -364,8 +466,7 @@ hash_table ::create (size_t size) /* Dispose of a hash table. Free all memory and return this hash table to the non-created state. Naturally the hash table must already exist. */ -template class Allocator> +template class Allocator> void hash_table ::dispose () { @@ -389,11 +490,9 @@ hash_table ::dispose () This function also assumes there are no deleted entries in the table. HASH is the hash value for the element to be inserted. */ -template class Allocator> +template class Allocator> typename Descr::T ** -hash_table -::find_empty_slot_for_expand (hashval_t hash) +hash_table ::find_empty_slot_for_expand (hashval_t hash) { hashval_t index = hash_table_mod1 (hash, htab->size_prime_index); size_t size = htab->size; @@ -428,8 +527,7 @@ hash_table table entries is changed. If memory allocation fails, this function will abort. */ -template class Allocator> +template class Allocator> void hash_table ::expand () { @@ -491,11 +589,10 @@ hash_table ::expand () COMPARABLE element starting with the given HASH value. It cannot be used to insert or delete an element. */ -template class Allocator> +template class Allocator> typename Descr::T * -hash_table -::find_with_hash (const T *comparable, hashval_t hash) +hash_table ::find_with_hash (const T *comparable, + hashval_t hash) { hashval_t index, hash2; size_t size; @@ -534,12 +631,11 @@ hash_table write the value you want into the returned slot. When inserting an entry, NULL may be returned if memory allocation fails. */ -template class Allocator> +template class Allocator> typename Descr::T ** -hash_table -::find_slot_with_hash (const T *comparable, hashval_t hash, - enum insert_option insert) +hash_table ::find_slot_with_hash (const T *comparable, + hashval_t hash, + enum insert_option insert) { T **first_deleted_slot; hashval_t index, hash2; @@ -565,7 +661,7 @@ hash_table first_deleted_slot = &htab->entries[index]; else if (Descr::equal (entry, comparable)) return &htab->entries[index]; - + hash2 = hash_table_mod2 (hash, htab->size_prime_index); for (;;) { @@ -573,7 +669,7 @@ hash_table index += hash2; if (index >= size) index -= size; - + entry = htab->entries[index]; if (entry == HTAB_EMPTY_ENTRY) goto empty_entry; @@ -639,15 +735,15 @@ hash_table ::empty () useful when you've already done the lookup and don't want to do it again. */ -template class Allocator> +template class Allocator> void -hash_table -::clear_slot (T **slot) +hash_table ::clear_slot (T **slot) { - if (slot < htab->entries || slot >= htab->entries + htab->size - || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY) - abort (); + if (slot < htab->entries + || slot >= htab->entries + htab->size + || *slot == HTAB_EMPTY_ENTRY + || *slot == HTAB_DELETED_ENTRY) + gcc_unreachable (); Descr::remove (*slot); @@ -660,11 +756,10 @@ hash_table from hash table starting with the given HASH. If there is no matching element in the hash table, this function does nothing. */ -template class Allocator> +template class Allocator> void -hash_table -::remove_elt_with_hash (const T *comparable, hashval_t hash) +hash_table ::remove_elt_with_hash (const T *comparable, + hashval_t hash) { T **slot; @@ -683,13 +778,11 @@ hash_table each live entry. If CALLBACK returns false, the iteration stops. ARGUMENT is passed as CALLBACK's second argument. */ -template class Allocator> +template class Allocator> template void -hash_table -::traverse_noresize (Argument argument) +hash_table ::traverse_noresize (Argument argument) { T **slot; T **limit; @@ -712,13 +805,11 @@ hash_table /* Like traverse_noresize, but does resize the table when it is too empty to improve effectivity of subsequent calls. */ -template class Allocator> +template class Allocator> template void -hash_table -::traverse (Argument argument) +hash_table ::traverse (Argument argument) { size_t size = htab->size; if (elements () * 8 < size && size > 32)