 |  | limi_hash_tabl |  |
 |  | li_has_tab.ads |  |
 | li_has_tab.adb |
|  | hash_tables | |
| | hash_tables | |
| limi_hash_tabl | ||
| positi_functio | ||
| stri_hash_tabl | ||
| st_str_has_tab | ||
| te_str_has_tab |
| | util | |
| | hash_tables/ | |
 | heaps/ | ||
| images/ | ||
| lists/ | ||
| maths/ | ||
| messages/ | ||
| pipes/ | ||
| primes/ | ||
| readers/ | ||
| strings/ | ||
| writers/ |
| | ada | |
| | bin/ | |
| engine/ | ||
| fonts/ | ||
| internal/ | ||
| text/ | ||
| util/ |
|  | Home | |
|  | Showcase | |
 | Snapshots | ||
 | Ada Source | ||
 | PHP Source | ||
 | Fonts |
|  | Sourceforge | |
|  | Summary | |
 | Downloads | ||
 | Browse CVS | ||
 | Donate | ||
 | Activity |
Hosted by
-- $Date: 2004/02/14 02:23:40 $
-- $Revision: 1.4 $
-- $Author: jcrocholl $
generic
-- Generic type of keys to access items.
type Key_Type is limited private;
-- Generic type of the items to be stored.
type Item_Type is limited private;
with function Hash
(Key : in Key_Type;
Max : in Positive)
return Positive
is <>;
with function Equal
(Left, Right : in Key_Type)
return Boolean
is <>;
-- Versatile implementation of hash tables.
-- - Generic to allow all kinds of content.
-- - Variable size (always prime).
package Limited_Hash_Tables is
-- Performance tuning parameters.
Default_Start_Size : constant := 13;
Max_Fill_Percentage : constant := 60;
-- Storage for hash table data.
type Pair is limited record
Key : Key_Type;
Item : Item_Type;
end record;
-- Access type for pairs.
type Pair_Access is access Pair;
type Hash_Table(Size : Positive) is private;
-- Instance of a hash table.
-- Needs to be created before it can be used.
type Hash_Table_Access is access Hash_Table;
---------------
-- Construction
---------------
-- Create a new hash table with the given table size.
function Create
(Size : in Positive := Default_Start_Size) -- Make room for this many pairs.
return Hash_Table_Access; -- The newly created hash table.
-- The given key already exists in the hash table.
Key_Exists : exception;
-- Check for available space in the table, grow if necessary, then
-- insert the pair into the table. Raises Key_Exists if the key is
-- already in use.
procedure Put
(This : in out Hash_Table_Access; -- Add pair to this hash table.
Pair : in Pair_Access); -- Insert this pair.
-----------------
-- Indexed access
-----------------
-- Get the index of a given key.
procedure Get_Index
(This : access Hash_Table; -- Get key from this hash table.
Key : in Key_Type; -- Iteration pointer to the current field.
Index : out Positive; -- The index of the requested key.
Found : out Boolean); -- True if the key was found.
-- The given key was not found in the hash table.
-- Raised by Get_Index.
Key_Not_Found : exception;
-- Get the index of a given key.
function Get_Index
(This : access Hash_Table; -- Get key from this hash table.
Key : in Key_Type) -- Iteration pointer to the current field.
return Positive; -- The index of the requested key.
-- Get the pair at a given index position.
function Get_Pair
(This : access Hash_Table; -- Get pair from this hash table.
Index : in Positive) -- Iteration pointer to the current field.
return Pair_Access; -- The requested pair.
-- Get the key at a given index position.
function Get_Key
(This : access Hash_Table; -- Get key from this hash table.
Index : in Positive) -- Iteration pointer to the current field.
return Key_Type; -- The requested key.
-- Get the item at a given index position.
function Get_Item
(This : access Hash_Table; -- Get item from this hash table.
Index : in Positive) -- Iteration pointer to the current field.
return Item_Type; -- The requested item.
------------
-- Iterating
------------
-- Iterate over the items in the table. You should start with an
-- Index of 0 and stop iterating as soon as Index is 0 again.
procedure Next
(This : access Hash_Table; -- Iterate through this hash table.
Index : in out Natural); -- Iteration pointer to the current field.
-- Iterate over the items in the table. You should start with an
-- Index of 0 and stop iterating as soon as Index is 0 again.
procedure Get_Next
(This : access Hash_Table; -- Get pair from this hash table.
Index : in out Natural; -- Iteration pointer to the current field.
Pair : out Pair_Access); -- The pair at the updated index position.
------------------------
-- Performance debugging
------------------------
-- Print a visual representation of the hash table's usage. Empty
-- fields are represented by a '-' character, used fields by '#'.
procedure Print_Usage
(This : access Hash_Table); -- Print usage of this hash table.
private
type Pair_Array is array(Positive range <>) of Pair_Access;
type Hash_Table(Size : Positive) is
record
Count : Natural;
Pairs : Pair_Array(1 .. Size);
end record;
end Limited_Hash_Tables;