GCC Middle and Back End API Reference
Static Public Member Functions
xcallocator< Type > Struct Template Reference

#include <hash-table.h>

Static Public Member Functions

static Type * control_alloc (size_t count)
static Type * data_alloc (size_t count)
static void control_free (Type *memory)
static void data_free (Type *memory)

Detailed Description

template<typename Type>
struct xcallocator< Type >

A type-safe hash table template. Copyright (C) 2012-2013 Free Software Foundation, Inc. Contributed by Lawrence Crowl crowl.nosp@m.@goo.nosp@m.gle.c.nosp@m.om

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 http://www.gnu.org/licenses/. This file implements a typed hash table. The implementation borrows from libiberty's htab_t in hashtab.h.

INTRODUCTION TO TYPES

Users of the hash table generally need to be aware of three types.

  1. The type being placed into the hash table. This type is called the value type.

  1. The type used to describe how to handle the value type within the hash table. This descriptor type provides the hash table with several things.

    • A typedef named 'value_type' to the value type (from above).
    • A static member function named 'hash' that takes a value_type pointer and returns a hashval_t value.
    • A typedef named 'compare_type' that is used to test when an value is found. This type is the comparison type. Usually, it will be the same as value_type. If it is not the same type, you must generally explicitly compute hash values and pass them to the hash table.
    • A static member function named 'equal' that takes a value_type pointer and a compare_type pointer, and returns a bool.
    • A static function named 'remove' that takes an value_type pointer and frees the memory allocated by it. This function 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).
  1. The type of the hash table itself. (More later.)

In very special circumstances, users may need to know about a fourth type.

  1. The template type used to describe how hash table memory is allocated. This type is called the allocator type. It is parameterized on the value type. It provides four functions.

    • A static member function named 'control_alloc'. This function allocates the control data blocks for the table.
    • A static member function named 'control_free'. This function frees the control data blocks for the table.
    • A static member function named 'data_alloc'. This function allocates the data elements in the table.
    • A static member function named 'data_free'. This function deallocates the data elements in the table.

Hash table are instantiated with two type arguments. 

 The descriptor type, (2) above.

 The allocator type, (4) above.  In general, you will not need to

provide your own allocator type. By default, hash tables will use the class template xcallocator, which uses malloc/free for allocation.

DEFINING A DESCRIPTOR TYPE

The first task in using the hash table is to describe the element type. We compose this into a few steps.

  1. Decide on a removal policy for values stored in the table. This header provides class templates for the two most common policies.

    typed_free_remove implements the static 'remove' member function by calling free().

    typed_noop_remove implements the static 'remove' member function by doing nothing.

    You can use these policies by simply deriving the descriptor type from one of those class template, with the appropriate argument.

    Otherwise, you need to write the static 'remove' member function in the descriptor class.

  1. Choose a hash function. Write the static 'hash' member function.
  1. Choose an equality testing function. In most cases, its two arguments will be value_type pointers. If not, the first argument must be a value_type pointer, and the second argument a compare_type pointer.

AN EXAMPLE DESCRIPTOR TYPE

Suppose you want to put some_type into the hash table. You could define the descriptor type as follows.

struct some_type_hasher : typed_noop_remove <some_type> Deriving from typed_noop_remove means that we get a 'remove' that does nothing. This choice is good for raw values. { typedef some_type value_type; typedef some_type compare_type; static inline hashval_t hash (const value_type *); static inline bool equal (const value_type *, const compare_type *); };

inline hashval_t some_type_hasher::hash (const value_type *e) { ... compute and return a hash value for E ... }

inline bool some_type_hasher::equal (const value_type *p1, const compare_type *p2) { ... compare P1 vs P2. Return true if they are the 'same' ... }

AN EXAMPLE HASH_TABLE DECLARATION

To instantiate a hash table for some_type:

hash_table <some_type_hasher> some_type_hash_table;

There is no need to mention some_type directly, as the hash table will obtain it using some_type_hasher::value_type.

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.

EASY DESCRIPTORS FOR POINTERS

The class template pointer_hash provides everything you need to hash pointers (as opposed to what they point to). So, to instantiate a hash table over pointers to whatever_type,

hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;

HASH TABLE ITERATORS

The hash table provides standard C++ iterators. For example, consider a hash table of some_info. We wish to consume each element of the table:

extern void consume (some_info *);

We define a convenience typedef and the hash table:

typedef hash_table <some_info_hasher> info_table_type; info_table_type info_table;

Then we write the loop in typical C++ style:

for (info_table_type::iterator iter = info_table.begin (); iter != info_table.end (); ++iter) if ((*iter).status == INFO_READY) consume (&*iter);

Or with common sub-expression elimination:

for (info_table_type::iterator iter = info_table.begin (); iter != info_table.end (); ++iter) { some_info &elem = *iter; if (elem.status == INFO_READY) consume (&elem); }

One can also use a more typical GCC style:

typedef some_info *some_info_p; some_info *elem_ptr; info_table_type::iterator iter; FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter) if (elem_ptr->status == INFO_READY) consume (elem_ptr); The ordinary memory allocator. FIXME (crowl): This allocator may be extracted for wider sharing later.

Member Function Documentation

template<typename Type >
Type * xcallocator< Type >::control_alloc ( size_t  count)
inlinestatic

Allocate memory for COUNT control blocks.

References count.

template<typename Type >
void xcallocator< Type >::control_free ( Type *  memory)
inlinestatic

Free memory for control blocks.

template<typename Type >
Type * xcallocator< Type >::data_alloc ( size_t  count)
inlinestatic

Allocate memory for COUNT data blocks.

template<typename Type >
void xcallocator< Type >::data_free ( Type *  memory)
inlinestatic

Free memory for data blocks.

The documentation for this struct was generated from the following file: