-
-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
hash.cr
1990 lines (1774 loc) · 56.9 KB
/
hash.cr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
require "crystal/hasher"
# A `Hash` represents a collection of key-value mappings, similar to a dictionary.
#
# Main operations are storing a key-value mapping (`#[]=`) and
# querying the value associated to a key (`#[]`). Key-value mappings can also be
# deleted (`#delete`).
# Keys are unique within a hash. When adding a key-value mapping with a key that
# is already in use, the old value will be forgotten.
#
# ```
# # Create a new Hash for mapping String to Int32
# hash = Hash(String, Int32).new
# hash["one"] = 1
# hash["two"] = 2
# hash["one"] # => 1
# ```
#
# [Hash literals](https://crystal-lang.org/reference/syntax_and_semantics/literals/hash.html)
# can also be used to create a `Hash`:
#
# ```
# {"one" => 1, "two" => 2}
# ```
#
# Implementation is based on an open hash table.
# Two objects refer to the same hash key when their hash value (`Object#hash`)
# is identical and both objects are equal to each other (`Object#==`).
#
# Enumeration follows the order that the corresponding keys were inserted.
#
# NOTE: When using mutable data types as keys, changing the value of a key after
# it was inserted into the `Hash` may lead to undefined behaviour. This can be
# restored by re-indexing the hash with `#rehash`.
class Hash(K, V)
include Enumerable({K, V})
include Iterable({K, V})
# ===========================================================================
# Overall explanation of the algorithm
# ===========================================================================
#
# Hash implements an open addressing collision resolution method:
# https://en.wikipedia.org/wiki/Open_addressing
#
# The collision resolution is done using Linear Probing:
# https://en.wikipedia.org/wiki/Linear_probing
#
# The algorithm is partially based on Ruby's one but they are not exactly the same:
# https://github.com/ruby/ruby/blob/a4c09342a2219a8374240ef8d0ca86abe287f715/st.c#L1-L101
#
# There are two main data structures:
#
# - @entries:
# A contiguous buffer (Pointer) of hash entries (Entry) in the order
# they were inserted. This makes it possible for Hash to preserve
# order of insertion.
# An entry holds a key-value pair together with the key's hash code.
# An entry can also be marked as deleted. This is accomplished by using
# 0 as the hash code value. Because 0 is a valid hash code value, when
# computing the key's hash code if it's 0 then it's replaced by another
# value (UInt32::MAX). The alternative would be to use a boolean but
# that involves more memory allocated and worse performance.
# - @indices:
# A buffer of indices into the @entries buffer.
# An index might mean it's empty. We could use -1 for this but because
# of an optimization we'll explain later we use 0, and all other values
# represent indices which are 1 less than their actual value (so value
# 3 means index 2).
# When a key-value pair is inserted we first find the key's hash and
# then fit it (by modulo) into the indices buffer size. For example,
# assuming we are inserting a new key-value pair with key "hello",
# if the indices size is 128, the key is "hello" and its hash is
# 987 then fitting it into 128 is (987 % 128) gives 91. Lets also
# assume there are already 3 entries in @entries. We go ahead an add
# a new entry at index 3, and at position 91 in @indices we store 3
# (well, actually 4 because we store 1 more than the actual index
# because 0 means empty, as explained above).
#
# Open addressing means that if, in the example above, we go and try to
# insert another key with a hash that will be placed in the same position
# in indices (let's say, 91 again), because it's occupied we will insert
# it into the next non-empty slot. We try with 92. If it's empty we again
# go and insert it intro `@entries` and store the index at 92 (continuing
# with the previous example we would store the value 4).
#
# If we keep the size of @indices the same as @entries it means that in the worse
# case @indices is full and when finding a match we have to traverse it all,
# which is bad. That's why we always make the size of @indices at least twice
# as big as the size of @entries, so the non-empty indices will tend to be
# spread apart with empty indices in the middle.
#
# Also, we always keep the sizes of `@indices` and `@entries` (`indices_size` / 2)
# powers of 2, with the smallest size of `@indices` being 8 (and thus of
# `@entries` being 4).
#
# The size of `@indices` is stored as a number that has to be powered by 2 in
# `@indices_size_pow2`. For example if `@indices_size_pow2` is 3 then the actual
# size is 2**3 = 8.
#
# Next comes the optimizations.
#
# The first one is that for an empty hash we don't allocate `@entries`
# nor `@indices`, and there are a few checks against these when adding
# and fetching elements. Sometimes hashes are created empty and remain empty
# for some time or for the duration of the program when not used, and this
# helps save some memory.
#
# The second optimization is that for small hashes (less or equal to 16 elements)
# we don't allocate `@indices` and just perform a linear scan on `@entries`.
# This is an heuristic but in practice it's faster to search linearly in small
# hashes. There's another heuristic here: if we have less than or equal to 8
# elements we just compare values when doing the linear scan. If we have between
# 9 and 16 we first compute the hash code of the key and compare the hash codes
# first (at this point computing the hash code plus comparing them might become
# cheaper than doing a full comparison each time). This optimization also exists
# in the Ruby implementation (though it seems hash values are always compared).
#
# A third optimization is in the way `@indices` is allocated: when the number
# of entries is less than or equal to 128 (2 ** 8 / 2) the indexes values will range between
# 0 and 128. That means we can use `Pointer(UInt8)` as the type of `@indices`.
# (we can't do it for ranges between 0 and 256 because we need a value that means
# "empty"). Similarly, for ranges between 128 and 32768 (2 ** 16 / 2) we can use
# `Pointer(UInt16)`. This saves some memory (and the performance difference is
# noticeable). We store the bytesize of the `@indices` buffer in `@indices_bytesize`
# with values 1 (UInt8), 2 (UInt16) or 4 (UInt32). This optimization also exists
# in the Ruby implementation.
#
# Another optimization is, when fitting a value inside the range of `@indices`,
# to use masking (value & mask) instead of `remainder` or `%`, which apparently
# are much slower. This optimization also exists in the Ruby implementation.
#
# We also keep track of the number of deleted entries (`@deleted_count`). When an
# entry is deleted we just mark it as deleted by using the special hash value 0.
# Only when the hash needs to be resized we do something with this instance variable:
# if we have many deleted entries (at least as many as the number of non-deleted
# entries) we compact the map and avoid a resize. Otherwise we remove the non-deleted
# entries but also resize both the `@entries` and `@indices` buffer. This probably
# avoids an edge case where one deletes and inserts an element and there is a constant
# shift of the buffer (expensive).
#
# There might be other optimizations to try out, like not using Linear Probing,
# but for now this implementation is much faster than the old one which used
# linked lists (closed addressing).
#
# All methods that deal with this implementation come after the constructors.
# Then all other methods use the internal methods, usually using other high-level
# methods.
# The index of the first non-deleted entry in `@entries`.
# This is useful to support `shift`: instead of marking an entry
# as deleted and then always having to ignore it we just increment this
# variable and always start iterating from it.
# The invariant of `@first` always pointing to a non-deleted entry holds
# (unless `@size` is 0) and is guaranteed because of how
# `delete_and_update_counts` is implemented.
@first : Int32 = 0
# The buffer of entries.
# Might be null if the hash is empty at the very beginning.
# Has always the size of `indices_size` / 2.
@entries : Pointer(Entry(K, V))
# The buffer of indices into entries. Its size is given by `@indices_size_pow2`.
# Might be null if the hash is empty at the very beginning or when the hash
# size is less than or equal to 16.
# Could be a Slice but this way we might save a few bounds checking.
@indices : Pointer(UInt8)
# The number of actual entries in the hash.
# Exposed to the user via the `size` getter.
@size : Int32
# The number of deleted entries.
# Resets to zero when the hash resizes.
@deleted_count : Int32
# The actual type of `@indices`:
# - 1 means `Pointer(UInt8)`
# - 2 means `Pointer(UInt16)`
# - 4 means `Pointer(UInt32)`
@indices_bytesize : Int8
# The size of `@indices` given as a power of 2.
# For example if it's 4 it means 2**4 so size 16.
# Can be zero when hash is totally empty.
# Otherwise guaranteed to be at least 3.
@indices_size_pow2 : UInt8
# Whether to compare objects using `object_id`.
@compare_by_identity : Bool = false
# The optional block that triggers on non-existing keys.
@block : (self, K -> V)?
# Creates a new empty `Hash`.
def initialize
@entries = Pointer(Entry(K, V)).null
@indices = Pointer(UInt8).null
@indices_size_pow2 = 0
@size = 0
@deleted_count = 0
@block = nil
@indices_bytesize = 1
end
# Creates a new empty `Hash` with a *block* for handling missing keys.
#
# ```
# proc = ->(hash : Hash(String, Int32), key : String) { hash[key] = key.size }
# hash = Hash(String, Int32).new(proc)
#
# hash.size # => 0
# hash["foo"] # => 3
# hash.size # => 1
# hash["bar"] = 10
# hash["bar"] # => 10
# ```
#
# The *initial_capacity* is useful to avoid unnecessary reallocations
# of the internal buffer in case of growth. If the number of elements
# a hash will hold is known, the hash should be initialized with that
# capacity for improved performance. Otherwise, the default is 8.
# Inputs lower than 8 are ignored.
def initialize(block : (Hash(K, V), K -> V)? = nil, *, initial_capacity = nil)
initial_capacity = (initial_capacity || 0).to_i32
# Same as the empty hash case
# (but this constructor is a bit more expensive in terms of code execution).
if initial_capacity == 0
@entries = Pointer(Entry(K, V)).null
@indices = Pointer(UInt8).null
@indices_size_pow2 = 0
@indices_bytesize = 1
else
# Translate initial capacity to the nearest power of 2, but keep it a minimum of 8.
if initial_capacity < 8
initial_entries_size = 8
else
initial_entries_size = Math.pw2ceil(initial_capacity)
end
# Because we always keep indice_size >= entries_size * 2
initial_indices_size = initial_entries_size * 2
@entries = malloc_entries(initial_entries_size)
# Check if we can avoid allocating the `@indices` buffer for
# small hashes.
if initial_indices_size > MAX_INDICES_SIZE_LINEAR_SCAN
@indices_bytesize = compute_indices_bytesize(initial_indices_size)
@indices = malloc_indices(initial_indices_size)
else
@indices = Pointer(UInt8).null
@indices_bytesize = 1
end
@indices_size_pow2 = Math.log2(initial_indices_size).to_u8
end
@size = 0
@deleted_count = 0
@block = block
end
# Creates a new empty `Hash` with a *block* that handles missing keys.
#
# ```
# hash = Hash(String, Int32).new do |hash, key|
# hash[key] = key.size
# end
#
# hash.size # => 0
# hash["foo"] # => 3
# hash.size # => 1
# hash["bar"] = 10
# hash["bar"] # => 10
# ```
#
# The *initial_capacity* is useful to avoid unnecessary reallocations
# of the internal buffer in case of growth. If the number of elements
# a hash will hold is known, the hash should be initialized with that
# capacity for improved performance. Otherwise, the default is 8.
# Inputs lower than 8 are ignored.
def self.new(initial_capacity = nil, &block : (Hash(K, V), K -> V))
new block, initial_capacity: initial_capacity
end
# Creates a new empty `Hash` where the *default_value* is returned if a key is missing.
#
# ```
# inventory = Hash(String, Int32).new(0)
# inventory["socks"] = 3
# inventory["pickles"] # => 0
# ```
#
# NOTE: The default value is passed by reference:
# ```
# arr = [1, 2, 3]
# hash = Hash(String, Array(Int32)).new(arr)
# hash["3"][1] = 4
# arr # => [1, 4, 3]
# ```
#
# The *initial_capacity* is useful to avoid unnecessary reallocations
# of the internal buffer in case of growth. If the number of elements
# a hash will hold is known, the hash should be initialized with that
# capacity for improved performance. Otherwise, the default is 8.
# Inputs lower than 8 are ignored.
def self.new(default_value : V, initial_capacity = nil)
new(initial_capacity: initial_capacity) { default_value }
end
# ===========================================================================
# Internal implementation starts
# ===========================================================================
# Maximum number of `indices_size` for which we do a linear scan
# (maximum of 16 entries in `@entries`)
private MAX_INDICES_SIZE_LINEAR_SCAN = 32
# Maximum number of `indices_size` for which we can represent `@indices`
# as Pointer(UInt8).
private MAX_INDICES_BYTESIZE_1 = 256
# Maximum number of `indices_size` for which we can represent `@indices`
# as Pointer(UInt16).
private MAX_INDICES_BYTESIZE_2 = 65536
# Inserts or updates a key-value pair.
# Returns an `Entry` if it was updated, otherwise `nil`.
private def upsert(key, value) : Entry(K, V)?
# Empty hash table so only initialize entries for now
if @entries.null?
@indices_size_pow2 = 3
@entries = malloc_entries(4)
end
hash = key_hash(key)
# No indices allocated yet so try to do a linear scan
if @indices.null?
# Try to do an update by doing a linear scan
updated_entry = update_linear_scan(key, value, hash)
return updated_entry if updated_entry
# If we still have space, add an entry.
if !entries_full?
add_entry_and_increment_size(hash, key, value)
return nil
end
# No more space so we need to do a resize
resize
# Now, it could happen that we are still with less than 16 elements
# and so `@indices` will be null, in which case we only need to
# add the key-value pair at the end of the `@entries` buffer.
if @indices.null?
add_entry_and_increment_size(hash, key, value)
return nil
end
# Otherwise `@indices` became non-null which means we can't do
# a linear scan anymore.
end
# Fit the hash value into an index in `@indices`
index = fit_in_indices(hash)
while true
entry_index = get_index(index)
# If the index entry is empty...
if entry_index == -1
# If we reached the maximum in `@entries` it's time to resize
if entries_full?
resize
# We have to fit the hash into an index in `@indices` again, and try again
index = fit_in_indices(hash)
next
end
# We have free space: store the index and then insert the entry
set_index(index, entries_size)
add_entry_and_increment_size(hash, key, value)
return nil
end
# We found a non-empty slot, let's see if the key we have matches
entry = get_entry(entry_index)
if entry_matches?(entry, hash, key)
# If it does we just update the entry
set_entry(entry_index, Entry(K, V).new(hash, key, value))
return entry
else
# Otherwise we have to keep looking...
index = next_index(index)
end
end
end
# Tries to update a key-value-hash triplet by doing a linear scan.
# Returns an old `Entry` if it was updated, otherwise `nil`.
private def update_linear_scan(key, value, hash) : Entry(K, V)?
# Just do a linear scan...
each_entry_with_index do |entry, index|
if entry_matches?(entry, hash, key)
set_entry(index, Entry(K, V).new(entry.hash, entry.key, value))
return entry
end
end
nil
end
# Implementation of deleting a key.
# Returns the deleted Entry, if it existed, `nil` otherwise.
private def delete_impl(key) : Entry(K, V)?
# Empty hash table, nothing to do
if @indices_size_pow2 == 0
return nil
end
hash = key_hash(key)
# No indices allocated yet so do linear scan
if @indices.null?
return delete_linear_scan(key, hash)
end
# Fit hash into `@indices` size
index = fit_in_indices(hash)
while true
entry_index = get_index(index)
# If we find an empty index slot, there's no such key
if entry_index == -1
return nil
end
# We found a non-empty slot, let's see if the key we have matches
entry = get_entry(entry_index)
if entry_matches?(entry, hash, key)
delete_entry_and_update_counts(entry_index)
return entry
else
# If it doesn't, check the next index...
index = next_index(index)
end
end
end
# Delete by doing a linear scan over `@entries`.
# Returns the deleted Entry, if it existed, `nil` otherwise.
private def delete_linear_scan(key, hash) : Entry(K, V)?
each_entry_with_index do |entry, index|
if entry_matches?(entry, hash, key)
delete_entry_and_update_counts(index)
return entry
end
end
nil
end
# Finds an entry with the given key.
protected def find_entry(key) : Entry(K, V)?
# Empty hash table so there's no way it's there
if @indices_size_pow2 == 0
return nil
end
# No indices allocated yet so do linear scan
if @indices.null?
return find_entry_linear_scan(key)
end
hash = key_hash(key)
# Fit hash into `@indices` size
index = fit_in_indices(hash)
while true
entry_index = get_index(index)
# If we find an empty index slot, there's no such key
if entry_index == -1
return nil
end
# We found a non-empty slot, let's see if the key we have matches
entry = get_entry(entry_index)
if entry_matches?(entry, hash, key)
# It does!
return entry
else
# Nope, move on to the next slot
index = next_index(index)
end
end
end
# Finds an Entry with the given key by doing a linear scan.
private def find_entry_linear_scan(key) : Entry(K, V)?
# If we have less than 8 elements we avoid computing the hash
# code and directly compare the keys (might be cheaper than
# computing a hash code of a complex structure).
if entries_size <= 8
each_entry_with_index do |entry|
return entry if entry_matches?(entry, key)
end
else
hash = key_hash(key)
each_entry_with_index do |entry|
return entry if entry_matches?(entry, hash, key)
end
end
nil
end
# Tries to resize the hash table in the condition that there are
# no more available entries to add.
# Might not result in a resize if there are many entries marked as
# deleted. In that case the entries table is simply compacted.
# However, in case of a resize deleted entries are also compacted.
private def resize : Nil
# Only do an actual resize (grow `@entries` buffer) if we don't
# have many deleted elements.
if @deleted_count < @size
# First grow `@entries`
realloc_entries(indices_size)
double_indices_size
# If we didn't have `@indices` and we still don't have 16 entries
# we keep doing linear scans (not using `@indices`)
if @indices.null? && indices_size <= MAX_INDICES_SIZE_LINEAR_SCAN
return
end
# Otherwise, we must either start using `@indices`
# or grow the ones we had.
@indices_bytesize = compute_indices_bytesize(indices_size)
if @indices.null?
@indices = malloc_indices(indices_size)
else
@indices = realloc_indices(indices_size)
end
end
do_compaction
# After compaction we no longer have deleted entries
@deleted_count = 0
# And the first valid entry is the first one
@first = 0
end
# Compacts `@entries` (only keeps non-deleted ones) and rebuilds `@indices.`
# If `rehash` is `true` then hash values inside each `Entry` will be recomputed.
private def do_compaction(rehash : Bool = false) : Nil
# `@indices` might still be null if we are compacting in the case where
# we are still doing a linear scan (and we had many deleted elements)
if @indices.null?
has_indices = false
else
# If we do have indices we must clear them because we'll rebuild
# them from scratch
has_indices = true
clear_indices
end
# Here we traverse the `@entries` and compute their new index in `@indices`
# while moving non-deleted entries to the beginning (compaction).
new_entry_index = 0
each_entry_with_index do |entry, entry_index|
if rehash
# When rehashing we always have to copy the entry
entry_hash = key_hash(entry.key)
set_entry(new_entry_index, Entry(K, V).new(entry_hash, entry.key, entry.value))
else
# First we move the entry to its new index (if we need to do that)
entry_hash = entry.hash
set_entry(new_entry_index, entry) if entry_index != new_entry_index
end
if has_indices
# Then we try to find an empty index slot
# (we should find one now that we have more space)
index = fit_in_indices(entry_hash)
until get_index(index) == -1
index = next_index(index)
end
set_index(index, new_entry_index)
end
new_entry_index += 1
end
# We have to mark entries starting from the final new index
# as deleted so the GC can collect them.
entries_to_clear = entries_size - new_entry_index
if entries_to_clear > 0
(entries + new_entry_index).clear(entries_to_clear)
end
end
# After this it's 1 << 28, and with entries being Int32
# (4 bytes) it's 1 << 30 of actual bytesize and the
# next value would be 1 << 31 which overflows `Int32`.
private MAXIMUM_INDICES_SIZE = 1 << 28
# Doubles the value of `@indices_size` but first checks
# whether the maximum hash size is reached.
private def double_indices_size : Nil
if indices_size == MAXIMUM_INDICES_SIZE
raise "Maximum Hash size reached"
end
@indices_size_pow2 += 1
end
# Implementation of clearing the hash table.
private def clear_impl : Nil
# We _could_ set all buffers to null and start like in the
# empty case.
# However, it might happen that a user calls clear and then inserts
# elements in a loop. In that case each insert after clear will cause
# a new memory allocation and that's not good.
# Just clearing the buffers might retain some memory but it
# avoids a possible constant reallocation (which is slower).
clear_entries unless @entries.null?
clear_indices unless @indices.null?
@size = 0
@deleted_count = 0
@first = 0
end
# Initializes a `dup` copy from the contents of `other`.
protected def initialize_dup(other)
initialize_compare_by_identity(other)
return if other.empty?
initialize_dup_entries(other)
initialize_copy_non_entries_vars(other)
end
# Initializes a `clone` copy from the contents of `other`.
protected def initialize_clone(other)
initialize_compare_by_identity(other)
return if other.empty?
initialize_clone_entries(other)
initialize_copy_non_entries_vars(other)
end
private def initialize_compare_by_identity(other)
compare_by_identity if other.compare_by_identity?
end
# Initializes `@entries` for a dup copy.
# Here we only need to duplicate the buffer.
private def initialize_dup_entries(other)
return if other.@entries.null?
@entries = malloc_entries(other.entries_capacity)
# Note that we only need to copy `entries_size` which
# are the effective entries in use.
@entries.copy_from(other.@entries, other.entries_size)
end
# Initializes `@entries` for a clone copy.
# Here we need to copy entries while cloning their values.
private def initialize_clone_entries(other)
return if other.@entries.null?
@entries = malloc_entries(other.entries_capacity)
other.each_entry_with_index do |entry, index|
set_entry(index, entry.clone)
end
end
# Initializes all variables other than `@entries` for a copy.
private def initialize_copy_non_entries_vars(other)
@indices_bytesize = other.@indices_bytesize
@first = other.@first
@size = other.@size
@deleted_count = other.@deleted_count
@indices_size_pow2 = other.@indices_size_pow2
@block = other.@block
unless other.@indices.null?
@indices = malloc_indices(other.indices_size)
@indices.copy_from(other.@indices, indices_malloc_size(other.indices_size))
end
end
# Gets from `@indices` at the given `index`.
# Returns the index in `@entries` or `-1` if the slot is empty.
private def get_index(index : Int32) : Int32
# Check what we have: UInt8, Int16 or UInt32 buckets
value = case @indices_bytesize
when 1
@indices[index].to_i32!
when 2
@indices.as(UInt16*)[index].to_i32!
else
@indices.as(UInt32*)[index].to_i32!
end
# Because we increment the value by one when we store the value
# here we have to subtract one
value - 1
end
# Sets `@indices` at `index` with the given value.
private def set_index(index, value) : Nil
# We actually store 1 more than the value because 0 means empty.
value += 1
# We also have to see what we have: UInt8, UInt16 or UInt32 buckets.
case @indices_bytesize
when 1
@indices[index] = value.to_u8!
when 2
@indices.as(UInt16*)[index] = value.to_u16!
else
@indices.as(UInt32*)[index] = value.to_u32!
end
end
# Returns the capacity of `@indices`.
protected def indices_size
1 << @indices_size_pow2
end
# Computes what bytesize we'll store in `@indices` according to its size
private def compute_indices_bytesize(size) : Int8
case
when size <= MAX_INDICES_BYTESIZE_1
1_i8
when size <= MAX_INDICES_BYTESIZE_2
2_i8
else
4_i8
end
end
# Allocates `size` number of indices for `@indices`.
private def malloc_indices(size)
Pointer(UInt8).malloc(indices_malloc_size(size))
end
# The actual number of bytes needed to allocate `@indices`.
private def indices_malloc_size(size)
size * @indices_bytesize
end
# Reallocates `size` number of indices for `@indices`.
private def realloc_indices(size)
@indices.realloc(indices_malloc_size(size))
end
# Marks all existing indices as empty.
private def clear_indices : Nil
@indices.clear(indices_malloc_size(indices_size))
end
# Returns the entry in `@entries` at `index`.
private def get_entry(index) : Entry(K, V)
@entries[index]
end
# Sets the entry in `@entries` at `index`.
private def set_entry(index, value) : Nil
@entries[index] = value
end
# Adds an entry at the end and also increments this hash's size.
private def add_entry_and_increment_size(hash, key, value) : Nil
set_entry(entries_size, Entry(K, V).new(hash, key, value))
@size += 1
end
# Marks an entry in `@entries` at `index` as deleted
# *without* modifying any counters (`@size` and `@deleted_count`).
private def delete_entry(index) : Nil
set_entry(index, Entry(K, V).deleted)
end
# Marks an entry in `@entries` at `index` as deleted
# and updates the `@size` and `@deleted_count` counters.
private def delete_entry_and_update_counts(index) : Nil
delete_entry(index)
@size -= 1
@deleted_count += 1
# If we are deleting the first entry there are some
# more optimizations we can do
return if index != @first
# If the Hash is now empty then the first effective
# entry starts right after all the deleted ones.
if @size == 0
@first = @deleted_count
else
# Otherwise, we bump `@first` and keep bumping it
# until we find a non-deleted entry. It's guaranteed
# that this loop will end because `@size != 0` so
# there will be a non-deleted entry.
# It's better to skip the deleted entries once here
# and not every next time someone accesses the Hash.
# With this we also keep the invariant that `@first`
# always points to the first non-deleted entry.
@first += 1
while @entries[@first].deleted?
@first += 1
end
end
end
# Returns true if there's no place for new entries without doing a resize.
private def entries_full? : Bool
entries_size == entries_capacity
end
# Yields each non-deleted Entry with its index inside `@entries`.
protected def each_entry_with_index : Nil
return if @size == 0
@first.upto(entries_size - 1) do |i|
entry = get_entry(i)
yield entry, i unless entry.deleted?
end
end
# Allocates `size` number of entries for `@entries`.
private def malloc_entries(size)
Pointer(Entry(K, V)).malloc(size)
end
private def realloc_entries(size)
@entries = @entries.realloc(size)
end
# Marks all existing entries as deleted
private def clear_entries
@entries.clear(entries_capacity)
end
# Computes the next index in `@indices`, needed when an index is not empty.
private def next_index(index : Int32) : Int32
fit_in_indices(index + 1)
end
# Fits a value inside the range of `@indices`
private def fit_in_indices(value) : Int32
# We avoid doing modulo (`%` or `remainder`) because it's much
# slower than `<<` + `-` + `&`.
# For example if `@indices_size_pow2` is 8 then `indices_size`
# will be 256 (1 << 8) and the mask we use is 0xFF, which is 256 - 1.
(value & ((1_u32 << @indices_size_pow2) - 1)).to_i32!
end
# Returns the first `Entry` or `nil` if non exists.
private def first_entry?
# We always make sure that `@first` points to the first
# non-deleted entry, so `@entries[@first]` is guaranteed
# to be non-deleted.
@size == 0 ? nil : @entries[@first]
end
# Returns the first `Entry` or `nil` if non exists.
private def last_entry?
return nil if @size == 0
(entries_size - 1).downto(@first).each do |i|
entry = get_entry(i)
return entry unless entry.deleted?
end
# Might happen if the Hash is modified concurrently
nil
end
protected getter entries
# Returns the total number of existing entries, including
# deleted and non-deleted ones.
protected def entries_size
@size + @deleted_count
end
# Returns the capacity of `@entries`.
protected def entries_capacity
indices_size // 2
end
# Computes the hash of a key.
private def key_hash(key)
if @compare_by_identity && key.responds_to?(:object_id)
hash = key.object_id.hash.to_u32!
else
hash = key.hash.to_u32!
end
hash == 0 ? UInt32::MAX : hash
end
private def entry_matches?(entry, hash, key)
# Tiny optimization: for these primitive types it's faster to just
# compare the key instead of comparing the hash and the key.
# We still have to skip hashes with value 0 (means deleted).
{% if K == Bool ||
K == Char ||
K == Symbol ||
K < Int::Primitive ||
K < Float::Primitive ||
K < Enum %}
entry.key == key && entry.hash != 0_u32
{% else %}
entry.hash == hash && entry_matches?(entry, key)
{% end %}
end
private def entry_matches?(entry, key)
entry_key = entry.key
if @compare_by_identity
if entry_key.responds_to?(:object_id)
if key.responds_to?(:object_id)
entry_key.object_id == key.object_id
else
false
end
elsif key.responds_to?(:object_id)
# because entry_key doesn't respond to :object_id
false
else
entry_key == key
end
else
entry_key == key
end
end
# ===========================================================================
# Internal implementation ends
# ===========================================================================
# Returns the number of elements in this Hash.
getter size : Int32
# Makes this hash compare keys using their object identity (`object_id)`
# for types that define such method (`Reference` types, but also structs that
# might wrap other `Reference` types and delegate the `object_id` method to them).
#
# ```
# h1 = {"foo" => 1, "bar" => 2}
# h1["fo" + "o"]? # => 1
#
# h1.compare_by_identity
# h1.compare_by_identity? # => true
# h1["fo" + "o"]? # => nil # not the same String instance
# ```
def compare_by_identity
@compare_by_identity = true
rehash
self
end
# Returns `true` of this Hash is comparing keys by `object_id`.
#
# See `compare_by_identity`.
getter? compare_by_identity
# Sets the value of *key* to the given *value*.
#
# ```
# h = {} of String => String
# h["foo"] = "bar"
# h["foo"] # => "bar"
# ```
def []=(key : K, value : V)
upsert(key, value)
value
end
# Sets the value of *key* to the given *value*.
#
# If a value already exists for `key`, that (old) value is returned.
# Otherwise the given block is invoked with *key* and its value is returned.
#
# ```
# h = {} of Int32 => String
# h.put(1, "one") { "didn't exist" } # => "didn't exist"