1------------------------------------------------------------------------------ 2-- -- 3-- GNAT RUN-TIME COMPONENTS -- 4-- -- 5-- G N A T . D Y N A M I C _ H T A B L E S -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 1995-2010, AdaCore -- 10-- -- 11-- GNAT is free software; you can redistribute it and/or modify it under -- 12-- terms of the GNU General Public License as published by the Free Soft- -- 13-- ware Foundation; either version 3, or (at your option) any later ver- -- 14-- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- 15-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- 16-- or FITNESS FOR A PARTICULAR PURPOSE. -- 17-- -- 18-- As a special exception under Section 7 of GPL version 3, you are granted -- 19-- additional permissions described in the GCC Runtime Library Exception, -- 20-- version 3.1, as published by the Free Software Foundation. -- 21-- -- 22-- You should have received a copy of the GNU General Public License and -- 23-- a copy of the GCC Runtime Library Exception along with this program; -- 24-- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- 25-- <http://www.gnu.org/licenses/>. -- 26-- -- 27-- GNAT was originally developed by the GNAT team at New York University. -- 28-- Extensive contributions were provided by Ada Core Technologies Inc. -- 29-- -- 30------------------------------------------------------------------------------ 31 32-- Hash table searching routines 33 34-- This package contains two separate packages. The Simple_HTable package 35-- provides a very simple abstraction that associates one element to one 36-- key value and takes care of all allocations automatically using the heap. 37-- The Static_HTable package provides a more complex interface that allows 38-- complete control over allocation. 39 40-- This package provides a facility similar to that of GNAT.HTable, except 41-- that this package declares types that can be used to define dynamic 42-- instances of hash tables, while instantiations in GNAT.HTable creates a 43-- single instance of the hash table. 44 45-- Note that this interface should remain synchronized with those in 46-- GNAT.HTable to keep as much coherency as possible between these two 47-- related units. 48 49with Ada.Unchecked_Deallocation; 50package GNAT.Dynamic_HTables is 51 52 ------------------- 53 -- Static_HTable -- 54 ------------------- 55 56 -- A low-level Hash-Table abstraction, not as easy to instantiate as 57 -- Simple_HTable but designed to allow complete control over the 58 -- allocation of necessary data structures. Particularly useful when 59 -- dynamic allocation is not desired. The model is that each Element 60 -- contains its own Key that can be retrieved by Get_Key. Furthermore, 61 -- Element provides a link that can be used by the HTable for linking 62 -- elements with same hash codes: 63 64 -- Element 65 66 -- +-------------------+ 67 -- | Key | 68 -- +-------------------+ 69 -- : other data : 70 -- +-------------------+ 71 -- | Next Elmt | 72 -- +-------------------+ 73 74 generic 75 type Header_Num is range <>; 76 -- An integer type indicating the number and range of hash headers 77 78 type Element (<>) is limited private; 79 -- The type of element to be stored 80 81 type Elmt_Ptr is private; 82 -- The type used to reference an element (will usually be an access 83 -- type, but could be some other form of type such as an integer type). 84 85 Null_Ptr : Elmt_Ptr; 86 -- The null value of the Elmt_Ptr type 87 88 with procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr); 89 with function Next (E : Elmt_Ptr) return Elmt_Ptr; 90 -- The type must provide an internal link for the sake of the 91 -- staticness of the HTable. 92 93 type Key is limited private; 94 with function Get_Key (E : Elmt_Ptr) return Key; 95 with function Hash (F : Key) return Header_Num; 96 with function Equal (F1, F2 : Key) return Boolean; 97 98 package Static_HTable is 99 100 type Instance is private; 101 Nil : constant Instance; 102 103 procedure Reset (T : in out Instance); 104 -- Resets the hash table by releasing all memory associated with 105 -- it. The hash table can safely be reused after this call. For the 106 -- most common case where Elmt_Ptr is an access type, and Null_Ptr is 107 -- null, this is only needed if the same table is reused in a new 108 -- context. If Elmt_Ptr is other than an access type, or Null_Ptr is 109 -- other than null, then Reset must be called before the first use of 110 -- the hash table. 111 112 procedure Set (T : in out Instance; E : Elmt_Ptr); 113 -- Insert the element pointer in the HTable 114 115 function Get (T : Instance; K : Key) return Elmt_Ptr; 116 -- Returns the latest inserted element pointer with the given Key 117 -- or null if none. 118 119 procedure Remove (T : Instance; K : Key); 120 -- Removes the latest inserted element pointer associated with the 121 -- given key if any, does nothing if none. 122 123 function Get_First (T : Instance) return Elmt_Ptr; 124 -- Returns Null_Ptr if the Htable is empty, otherwise returns one 125 -- non specified element. There is no guarantee that 2 calls to this 126 -- function will return the same element. 127 128 function Get_Next (T : Instance) return Elmt_Ptr; 129 -- Returns a non-specified element that has not been returned by the 130 -- same function since the last call to Get_First or Null_Ptr if 131 -- there is no such element or Get_First has never been called. If 132 -- there is no call to 'Set' in between Get_Next calls, all the 133 -- elements of the Htable will be traversed. 134 135 private 136 137 type Instance_Data; 138 type Instance is access all Instance_Data; 139 Nil : constant Instance := null; 140 141 end Static_HTable; 142 143 ------------------- 144 -- Simple_HTable -- 145 ------------------- 146 147 -- A simple hash table abstraction, easy to instantiate, easy to use. 148 -- The table associates one element to one key with the procedure Set. 149 -- Get retrieves the Element stored for a given Key. The efficiency of 150 -- retrieval is function of the size of the Table parameterized by 151 -- Header_Num and the hashing function Hash. 152 153 generic 154 type Header_Num is range <>; 155 -- An integer type indicating the number and range of hash headers 156 157 type Element is private; 158 -- The type of element to be stored 159 160 No_Element : Element; 161 -- The object that is returned by Get when no element has been set for 162 -- a given key 163 164 type Key is private; 165 with function Hash (F : Key) return Header_Num; 166 with function Equal (F1, F2 : Key) return Boolean; 167 168 package Simple_HTable is 169 170 type Instance is private; 171 Nil : constant Instance; 172 173 procedure Set (T : in out Instance; K : Key; E : Element); 174 -- Associates an element with a given key. Overrides any previously 175 -- associated element. 176 177 procedure Reset (T : in out Instance); 178 -- Releases all memory associated with the table. The table can be 179 -- reused after this call (it is automatically allocated on the first 180 -- access to the table). 181 182 function Get (T : Instance; K : Key) return Element; 183 -- Returns the Element associated with a key or No_Element if the 184 -- given key has not associated element 185 186 procedure Remove (T : Instance; K : Key); 187 -- Removes the latest inserted element pointer associated with the 188 -- given key if any, does nothing if none. 189 190 function Get_First (T : Instance) return Element; 191 -- Returns No_Element if the Htable is empty, otherwise returns one 192 -- non specified element. There is no guarantee that two calls to this 193 -- function will return the same element, if the Htable has been 194 -- modified between the two calls. 195 196 function Get_Next (T : Instance) return Element; 197 -- Returns a non-specified element that has not been returned by the 198 -- same function since the last call to Get_First or No_Element if 199 -- there is no such element. If there is no call to 'Set' in between 200 -- Get_Next calls, all the elements of the Htable will be traversed. 201 -- To guarantee that all the elements of the Htable will be traversed, 202 -- no modification of the Htable (Set, Reset, Remove) should occur 203 -- between a call to Get_First and subsequent consecutive calls to 204 -- Get_Next, until one of these calls returns No_Element. 205 206 private 207 208 type Element_Wrapper; 209 type Elmt_Ptr is access all Element_Wrapper; 210 type Element_Wrapper is record 211 K : Key; 212 E : Element; 213 Next : Elmt_Ptr; 214 end record; 215 216 procedure Free is new 217 Ada.Unchecked_Deallocation (Element_Wrapper, Elmt_Ptr); 218 219 procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr); 220 function Next (E : Elmt_Ptr) return Elmt_Ptr; 221 function Get_Key (E : Elmt_Ptr) return Key; 222 223 package Tab is new Static_HTable 224 (Header_Num => Header_Num, 225 Element => Element_Wrapper, 226 Elmt_Ptr => Elmt_Ptr, 227 Null_Ptr => null, 228 Set_Next => Set_Next, 229 Next => Next, 230 Key => Key, 231 Get_Key => Get_Key, 232 Hash => Hash, 233 Equal => Equal); 234 235 type Instance is new Tab.Instance; 236 Nil : constant Instance := Instance (Tab.Nil); 237 238 end Simple_HTable; 239 240end GNAT.Dynamic_HTables; 241