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-2013, 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. This mirrors the interface of GNAT.HTable.Static_HTable, 58 -- but does require dynamic allocation (since we allow multiple instances 59 -- of the table). The model is that each Element contains its own Key that 60 -- can be retrieved by Get_Key. Furthermore, Element provides a link that 61 -- can be used by the HTable for linking elements with same hash codes: 62 63 -- Element 64 65 -- +-------------------+ 66 -- | Key | 67 -- +-------------------+ 68 -- : other data : 69 -- +-------------------+ 70 -- | Next Elmt | 71 -- +-------------------+ 72 73 generic 74 type Header_Num is range <>; 75 -- An integer type indicating the number and range of hash headers 76 77 type Element (<>) is limited private; 78 -- The type of element to be stored 79 80 type Elmt_Ptr is private; 81 -- The type used to reference an element (will usually be an access 82 -- type, but could be some other form of type such as an integer type). 83 84 Null_Ptr : Elmt_Ptr; 85 -- The null value of the Elmt_Ptr type 86 87 with procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr); 88 with function Next (E : Elmt_Ptr) return Elmt_Ptr; 89 -- The type must provide an internal link for the sake of the 90 -- staticness of the HTable. 91 92 type Key is limited private; 93 with function Get_Key (E : Elmt_Ptr) return Key; 94 with function Hash (F : Key) return Header_Num; 95 with function Equal (F1, F2 : Key) return Boolean; 96 97 package Static_HTable is 98 99 type Instance is private; 100 Nil : constant Instance; 101 102 procedure Reset (T : in out Instance); 103 -- Resets the hash table by releasing all memory associated with 104 -- it. The hash table can safely be reused after this call. For the 105 -- most common case where Elmt_Ptr is an access type, and Null_Ptr is 106 -- null, this is only needed if the same table is reused in a new 107 -- context. If Elmt_Ptr is other than an access type, or Null_Ptr is 108 -- other than null, then Reset must be called before the first use of 109 -- the hash table. 110 111 procedure Set (T : in out Instance; E : Elmt_Ptr); 112 -- Insert the element pointer in the HTable 113 114 function Get (T : Instance; K : Key) return Elmt_Ptr; 115 -- Returns the latest inserted element pointer with the given Key 116 -- or null if none. 117 118 procedure Remove (T : Instance; K : Key); 119 -- Removes the latest inserted element pointer associated with the 120 -- given key if any, does nothing if none. 121 122 function Get_First (T : Instance) return Elmt_Ptr; 123 -- Returns Null_Ptr if the Htable is empty, otherwise returns one 124 -- non specified element. There is no guarantee that 2 calls to this 125 -- function will return the same element. 126 127 function Get_Next (T : Instance) return Elmt_Ptr; 128 -- Returns a non-specified element that has not been returned by the 129 -- same function since the last call to Get_First or Null_Ptr if 130 -- there is no such element or Get_First has never been called. If 131 -- there is no call to 'Set' in between Get_Next calls, all the 132 -- elements of the Htable will be traversed. 133 134 private 135 type Instance_Data; 136 type Instance is access all Instance_Data; 137 Nil : constant Instance := null; 138 end Static_HTable; 139 140 ------------------- 141 -- Simple_HTable -- 142 ------------------- 143 144 -- A simple hash table abstraction, easy to instantiate, easy to use. 145 -- The table associates one element to one key with the procedure Set. 146 -- Get retrieves the Element stored for a given Key. The efficiency of 147 -- retrieval is function of the size of the Table parameterized by 148 -- Header_Num and the hashing function Hash. 149 150 generic 151 type Header_Num is range <>; 152 -- An integer type indicating the number and range of hash headers 153 154 type Element is private; 155 -- The type of element to be stored 156 157 No_Element : Element; 158 -- The object that is returned by Get when no element has been set for 159 -- a given key 160 161 type Key is private; 162 with function Hash (F : Key) return Header_Num; 163 with function Equal (F1, F2 : Key) return Boolean; 164 165 package Simple_HTable is 166 167 type Instance is private; 168 Nil : constant Instance; 169 170 procedure Set (T : in out Instance; K : Key; E : Element); 171 -- Associates an element with a given key. Overrides any previously 172 -- associated element. 173 174 procedure Reset (T : in out Instance); 175 -- Releases all memory associated with the table. The table can be 176 -- reused after this call (it is automatically allocated on the first 177 -- access to the table). 178 179 function Get (T : Instance; K : Key) return Element; 180 -- Returns the Element associated with a key or No_Element if the 181 -- given key has not associated element 182 183 procedure Remove (T : Instance; K : Key); 184 -- Removes the latest inserted element pointer associated with the 185 -- given key if any, does nothing if none. 186 187 function Get_First (T : Instance) return Element; 188 -- Returns No_Element if the Htable is empty, otherwise returns one 189 -- non specified element. There is no guarantee that two calls to this 190 -- function will return the same element, if the Htable has been 191 -- modified between the two calls. 192 193 function Get_Next (T : Instance) return Element; 194 -- Returns a non-specified element that has not been returned by the 195 -- same function since the last call to Get_First or No_Element if 196 -- there is no such element. If there is no call to 'Set' in between 197 -- Get_Next calls, all the elements of the Htable will be traversed. 198 -- To guarantee that all the elements of the Htable will be traversed, 199 -- no modification of the Htable (Set, Reset, Remove) should occur 200 -- between a call to Get_First and subsequent consecutive calls to 201 -- Get_Next, until one of these calls returns No_Element. 202 203 private 204 205 type Element_Wrapper; 206 type Elmt_Ptr is access all Element_Wrapper; 207 type Element_Wrapper is record 208 K : Key; 209 E : Element; 210 Next : Elmt_Ptr; 211 end record; 212 213 procedure Free is new 214 Ada.Unchecked_Deallocation (Element_Wrapper, Elmt_Ptr); 215 216 procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr); 217 function Next (E : Elmt_Ptr) return Elmt_Ptr; 218 function Get_Key (E : Elmt_Ptr) return Key; 219 220 package Tab is new Static_HTable 221 (Header_Num => Header_Num, 222 Element => Element_Wrapper, 223 Elmt_Ptr => Elmt_Ptr, 224 Null_Ptr => null, 225 Set_Next => Set_Next, 226 Next => Next, 227 Key => Key, 228 Get_Key => Get_Key, 229 Hash => Hash, 230 Equal => Equal); 231 232 type Instance is new Tab.Instance; 233 Nil : constant Instance := Instance (Tab.Nil); 234 235 end Simple_HTable; 236 237end GNAT.Dynamic_HTables; 238