LCOV - code coverage report
Current view: top level - gee - hashmap.vala (source / functions) Coverage Total Hit
Test: vala 0.57.0.298-a8cae1 Lines: 84.2 % 215 181
Test Date: 2024-04-25 11:34:36 Functions: - 0 0

            Line data    Source code
       1              : /* hashmap.vala
       2              :  *
       3              :  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
       4              :  * Copyright (C) 1997-2000  GLib Team and others
       5              :  * Copyright (C) 2007-2009  Jürg Billeter
       6              :  *
       7              :  * This library is free software; you can redistribute it and/or
       8              :  * modify it under the terms of the GNU Lesser General Public
       9              :  * License as published by the Free Software Foundation; either
      10              :  * version 2.1 of the License, or (at your option) any later version.
      11              : 
      12              :  * This library is distributed in the hope that it will be useful,
      13              :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      14              :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      15              :  * Lesser General Public License for more details.
      16              : 
      17              :  * You should have received a copy of the GNU Lesser General Public
      18              :  * License along with this library; if not, write to the Free Software
      19              :  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
      20              :  *
      21              :  * Author:
      22              :  *      Jürg Billeter <j@bitron.ch>
      23              :  */
      24              : 
      25              : using GLib;
      26              : 
      27              : /**
      28              :  * Hashtable implementation of the Map interface.
      29              :  */
      30         1538 : public class Vala.HashMap<K,V> : Map<K,V> {
      31              :         public override int size {
      32         8530 :                 get { return _nnodes; }
      33              :         }
      34              : 
      35              :         public HashFunc<K> key_hash_func {
      36     16603171 :                 set { _key_hash_func = value; }
      37              :         }
      38              : 
      39              :         public EqualFunc<K> key_equal_func {
      40     16603171 :                 set { _key_equal_func = value; }
      41              :         }
      42              : 
      43              :         public EqualFunc<V> value_equal_func {
      44     16603171 :                 set { _value_equal_func = value; }
      45              :         }
      46              : 
      47              :         private int _array_size;
      48              :         private int _nnodes;
      49     33203242 :         private Node<K,V>[] _nodes;
      50              : 
      51              :         // concurrent modification protection
      52     16603171 :         private int _stamp = 0;
      53              : 
      54              :         private HashFunc<K> _key_hash_func;
      55              :         private EqualFunc<K> _key_equal_func;
      56              :         private EqualFunc<V> _value_equal_func;
      57              : 
      58              :         private const int MIN_SIZE = 11;
      59              :         private const int MAX_SIZE = 13845163;
      60              : 
      61     33206342 :         public HashMap (HashFunc<K> key_hash_func = GLib.direct_hash, EqualFunc<K> key_equal_func = GLib.direct_equal, EqualFunc<V> value_equal_func = GLib.direct_equal) {
      62     16603171 :                 this.key_hash_func = key_hash_func;
      63     16603171 :                 this.key_equal_func = key_equal_func;
      64     16603171 :                 this.value_equal_func = value_equal_func;
      65     16603171 :                 _array_size = MIN_SIZE;
      66     16603171 :                 _nodes = new Node<K,V>[_array_size];
      67              :         }
      68              : 
      69      4913562 :         public override Set<K> get_keys () {
      70      4913562 :                 return new KeySet<K,V> (this);
      71              :         }
      72              : 
      73            3 :         public override Collection<V> get_values () {
      74            3 :                 return new ValueCollection<K,V> (this);
      75              :         }
      76              : 
      77         1662 :         public override Vala.MapIterator<K,V> map_iterator () {
      78         1662 :                 return new MapIterator<K,V> (this);
      79              :         }
      80              : 
      81    139347525 :         private Node<K,V>** lookup_node (K key) {
      82    139347525 :                 uint hash_value = _key_hash_func (key);
      83    139347525 :                 Node<K,V>** node = &_nodes[hash_value % _array_size];
      84    225798686 :                 while ((*node) != null && (hash_value != (*node)->key_hash || !_key_equal_func ((*node)->key, key))) {
      85     86451161 :                         node = &((*node)->next);
      86              :                 }
      87              :                 return node;
      88              :         }
      89              : 
      90      1388808 :         public override bool contains (K key) {
      91      1388808 :                 Node<K,V>** node = lookup_node (key);
      92      1388808 :                 return (*node != null);
      93              :         }
      94              : 
      95     98411206 :         public override V? get (K key) {
      96     98411206 :                 Node<K,V>* node = (*lookup_node (key));
      97     98411206 :                 if (node != null) {
      98     33158322 :                         return node->value;
      99              :                 } else {
     100     98411206 :                         return null;
     101              :                 }
     102              :         }
     103              : 
     104     39547408 :         public override void set (K key, V value) {
     105     39547408 :                 Node<K,V>** node = lookup_node (key);
     106     39547408 :                 if (*node != null) {
     107       787698 :                         (*node)->value = value;
     108              :                 } else {
     109     38759710 :                         uint hash_value = _key_hash_func (key);
     110     38759710 :                         *node = new Node<K,V> (key, value, hash_value);
     111     38759710 :                         _nnodes++;
     112     38759710 :                         resize ();
     113              :                 }
     114     39547408 :                 _stamp++;
     115              :         }
     116              : 
     117          103 :         public override bool remove (K key) {
     118          103 :                 Node<K,V>** node = lookup_node (key);
     119          103 :                 if (*node != null) {
     120          103 :                         Node<K,V> next = (owned) (*node)->next;
     121              : 
     122          103 :                         (*node)->key = null;
     123          103 :                         (*node)->value = null;
     124          103 :                         delete *node;
     125              : 
     126          103 :                         *node = (owned) next;
     127              : 
     128          103 :                         _nnodes--;
     129          103 :                         resize ();
     130          103 :                         _stamp++;
     131          103 :                         return true;
     132              :                 }
     133          103 :                 return false;
     134              :         }
     135              : 
     136     16609460 :         public override void clear () {
     137    202922372 :                 for (int i = 0; i < _array_size; i++) {
     138    186312912 :                         Node<K,V> node = (owned) _nodes[i];
     139    225072507 :                         while (node != null) {
     140     38759595 :                                 Node<K,V> next = (owned) node.next;
     141     38759595 :                                 node.key = null;
     142     38759595 :                                 node.value = null;
     143     38759595 :                                 node = (owned) next;
     144              :                         }
     145              :                 }
     146     16609460 :                 _nnodes = 0;
     147     16609460 :                 resize ();
     148              :         }
     149              : 
     150     55369273 :         private void resize () {
     151     98031757 :                 if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
     152     12793496 :                     (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
     153     42662484 :                         int new_array_size = (int) SpacedPrimes.closest (_nnodes);
     154     42662484 :                         new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
     155              : 
     156     42662484 :                         Node<K,V>[] new_nodes = new Node<K,V>[new_array_size];
     157              : 
     158    989361600 :                         for (int i = 0; i < _array_size; i++) {
     159              :                                 Node<K,V> node;
     160    473349558 :                                 Node<K,V> next = null;
     161    562319898 :                                 for (node = (owned) _nodes[i]; node != null; node = (owned) next) {
     162     44485170 :                                         next = (owned) node.next;
     163     44485170 :                                         uint hash_val = node.key_hash % new_array_size;
     164     44485170 :                                         node.next = (owned) new_nodes[hash_val];
     165     44485170 :                                         new_nodes[hash_val] = (owned) node;
     166              :                                 }
     167              :                         }
     168     42662484 :                         _nodes = (owned) new_nodes;
     169     42662484 :                         _array_size = new_array_size;
     170              :                 }
     171              :         }
     172              : 
     173              :         ~HashMap () {
     174     16601621 :                 clear ();
     175              :         }
     176              : 
     177              :         [Compact]
     178     38759698 :         private class Node<K,V> {
     179              :                 public K key;
     180              :                 public V value;
     181     38759698 :                 public Node<K,V> next;
     182              :                 public uint key_hash;
     183              : 
     184     38759710 :                 public Node (owned K k, owned V v, uint hash) {
     185     38759710 :                         key = (owned) k;
     186     38759710 :                         value = (owned) v;
     187     38759710 :                         key_hash = hash;
     188              :                 }
     189              :         }
     190              : 
     191      4914533 :         private class KeySet<K,V> : Set<K> {
     192              :                 public HashMap<K,V> map {
     193      9828792 :                         set { _map = value; }
     194              :                 }
     195              : 
     196      4913562 :                 private HashMap<K,V> _map;
     197              : 
     198     14740686 :                 public KeySet (HashMap<K,V> map) {
     199      4913562 :                         this.map = map;
     200              :                 }
     201              : 
     202            0 :                 public override Type get_element_type () {
     203            0 :                         return typeof (K);
     204              :                 }
     205              : 
     206      4913562 :                 public override Iterator<K> iterator () {
     207      4913562 :                         return new KeyIterator<K,V> (_map);
     208              :                 }
     209              : 
     210              :                 public override int size {
     211            0 :                         get { return _map.size; }
     212              :                 }
     213              : 
     214            0 :                 public override bool add (K key) {
     215            0 :                         assert_not_reached ();
     216              :                 }
     217              : 
     218            0 :                 public override void clear () {
     219            0 :                         assert_not_reached ();
     220              :                 }
     221              : 
     222            0 :                 public override bool remove (K key) {
     223            0 :                         assert_not_reached ();
     224              :                 }
     225              : 
     226            0 :                 public override bool contains (K key) {
     227            0 :                         return _map.contains (key);
     228              :                 }
     229              :         }
     230              : 
     231         3200 :         private class MapIterator<K,V> : Vala.MapIterator<K, V> {
     232              :                 public HashMap<K,V> map {
     233         1662 :                         set {
     234         3324 :                                 _map = value;
     235         1662 :                                 _stamp = _map._stamp;
     236              :                         }
     237              :                 }
     238              : 
     239         1662 :                 private HashMap<K,V> _map;
     240         1662 :                 private int _index = -1;
     241              :                 private weak Node<K,V> _node;
     242              : 
     243              :                 // concurrent modification protection
     244              :                 private int _stamp;
     245              : 
     246         4986 :                 public MapIterator (HashMap<K,V> map) {
     247         1662 :                         this.map = map;
     248              :                 }
     249              : 
     250         1666 :                 public override bool next () {
     251         1666 :                         if (_node != null) {
     252            4 :                                 _node = _node.next;
     253              :                         }
     254        19948 :                         while (_node == null && _index + 1 < _map._array_size) {
     255        18282 :                                 _index++;
     256        18282 :                                 _node = _map._nodes[_index];
     257              :                         }
     258         1666 :                         return (_node != null);
     259              :                 }
     260              : 
     261            4 :                 public override K get_key () {
     262            4 :                         assert (_stamp == _map._stamp);
     263            4 :                         assert (_node != null);
     264            4 :                         return _node.key;
     265              :                 }
     266              : 
     267            3 :                 public override V get_value () {
     268            3 :                         assert (_stamp == _map._stamp);
     269            3 :                         assert (_node != null);
     270            3 :                         return _node.value;
     271              :                 }
     272              :         }
     273              : 
     274      4914533 :         private class KeyIterator<K,V> : Iterator<K> {
     275              :                 public HashMap<K,V> map {
     276      4913562 :                         set {
     277      9827124 :                                 _map = value;
     278      4913562 :                                 _stamp = _map._stamp;
     279              :                         }
     280              :                 }
     281              : 
     282      4913562 :                 private HashMap<K,V> _map;
     283      4913562 :                 private int _index = -1;
     284              :                 private weak Node<K,V> _node;
     285              :                 private weak Node<K,V> _next;
     286              : 
     287              :                 // concurrent modification protection
     288              :                 private int _stamp;
     289              : 
     290     14740686 :                 public KeyIterator (HashMap<K,V> map) {
     291      4913562 :                         this.map = map;
     292              :                 }
     293              : 
     294     11800312 :                 public override bool next () {
     295     11800312 :                         assert (_stamp == _map._stamp);
     296     11800312 :                         if (!has_next ()) {
     297     11800312 :                                 return false;
     298              :                         }
     299      6894188 :                         _node = _next;
     300      6894188 :                         _next = null;
     301      6894188 :                         return (_node != null);
     302              :                 }
     303              : 
     304     11800312 :                 public override bool has_next () {
     305     11800312 :                         assert (_stamp == _map._stamp);
     306     11800312 :                         if (_next == null) {
     307     11800312 :                                 _next = _node;
     308     11800312 :                                 if (_next != null) {
     309      6886750 :                                         _next = _next.next;
     310              :                                 }
     311     65808300 :                                 while (_next == null && _index + 1 < _map._array_size) {
     312     54007988 :                                         _index++;
     313     54007988 :                                         _next = _map._nodes[_index];
     314              :                                 }
     315              :                         }
     316     11800312 :                         return (_next != null);
     317              :                 }
     318              : 
     319      6894188 :                 public override K? get () {
     320      6894188 :                         assert (_stamp == _map._stamp);
     321      6894188 :                         assert (_node != null);
     322      6894188 :                         return _node.key;
     323              :                 }
     324              : 
     325            0 :                 public override void remove () {
     326            0 :                         assert_not_reached ();
     327              :                 }
     328              : 
     329              :                 public override bool valid {
     330            0 :                         get {
     331            0 :                                 return _node != null;
     332              :                         }
     333              :                 }
     334              :         }
     335              : 
     336            6 :         private class ValueCollection<K,V> : Collection<V> {
     337              :                 public HashMap<K,V> map {
     338            6 :                         set { _map = value; }
     339              :                 }
     340              : 
     341            3 :                 private HashMap<K,V> _map;
     342              : 
     343            9 :                 public ValueCollection (HashMap<K,V> map) {
     344            3 :                         this.map = map;
     345              :                 }
     346              : 
     347            0 :                 public override Type get_element_type () {
     348            0 :                         return typeof (V);
     349              :                 }
     350              : 
     351            3 :                 public override Iterator<V> iterator () {
     352            3 :                         return new ValueIterator<K,V> (_map);
     353              :                 }
     354              : 
     355              :                 public override int size {
     356            0 :                         get { return _map.size; }
     357              :                 }
     358              : 
     359            0 :                 public override bool add (V value) {
     360            0 :                         assert_not_reached ();
     361              :                 }
     362              : 
     363            0 :                 public override void clear () {
     364            0 :                         assert_not_reached ();
     365              :                 }
     366              : 
     367            0 :                 public override bool remove (V value) {
     368            0 :                         assert_not_reached ();
     369              :                 }
     370              : 
     371            0 :                 public override bool contains (V value) {
     372            0 :                         Iterator<V> it = iterator ();
     373            0 :                         while (it.next ()) {
     374            0 :                                 if (_map._value_equal_func (it.get (), value)) {
     375            0 :                                         return true;
     376              :                                 }
     377              :                         }
     378            0 :                         return false;
     379              :                 }
     380              :         }
     381              : 
     382            6 :         private class ValueIterator<K,V> : Iterator<V> {
     383              :                 public HashMap<K,V> map {
     384            3 :                         set {
     385            6 :                                 _map = value;
     386            3 :                                 _stamp = _map._stamp;
     387              :                         }
     388              :                 }
     389              : 
     390            3 :                 private HashMap<K,V> _map;
     391            3 :                 private int _index = -1;
     392              :                 private weak Node<K,V> _node;
     393              :                 private weak Node<K,V> _next;
     394              : 
     395              :                 // concurrent modification protection
     396              :                 private int _stamp;
     397              : 
     398            9 :                 public ValueIterator (HashMap<K,V> map) {
     399            3 :                         this.map = map;
     400              :                 }
     401              : 
     402           61 :                 public override bool next () {
     403           61 :                         assert (_stamp == _map._stamp);
     404           61 :                         if (!has_next ()) {
     405           61 :                                 return false;
     406              :                         }
     407           58 :                         _node = _next;
     408           58 :                         _next = null;
     409           58 :                         return (_node != null);
     410              :                 }
     411              : 
     412           61 :                 public override bool has_next () {
     413           61 :                         assert (_stamp == _map._stamp);
     414           61 :                         if (_next == null) {
     415           61 :                                 _next = _node;
     416           61 :                                 if (_next != null) {
     417           58 :                                         _next = _next.next;
     418              :                                 }
     419          120 :                                 while (_next == null && _index + 1 < _map._array_size) {
     420           59 :                                         _index++;
     421           59 :                                         _next = _map._nodes[_index];
     422              :                                 }
     423              :                         }
     424           61 :                         return (_next != null);
     425              :                 }
     426              : 
     427           58 :                 public override V? get () {
     428           58 :                         assert (_stamp == _map._stamp);
     429           58 :                         assert (_node != null);
     430           58 :                         return _node.value;
     431              :                 }
     432              : 
     433            0 :                 public override void remove () {
     434            0 :                         assert_not_reached ();
     435              :                 }
     436              : 
     437              :                 public override bool valid {
     438            0 :                         get {
     439            0 :                                 return _node != null;
     440              :                         }
     441              :                 }
     442              :         }
     443              : }
     444              : 
        

Generated by: LCOV version 2.0-1