/[eiffelstudio]/branches/eth/eve/Src/library/base/elks/structures/table/hash_table.e
ViewVC logotype

Contents of /branches/eth/eve/Src/library/base/elks/structures/table/hash_table.e

Parent Directory Parent Directory | Revision Log Revision Log


Revision 92964 - (show annotations)
Fri Sep 20 05:41:23 2013 UTC (6 years ago) by jasonw
File size: 47204 byte(s)
<<Merged from trunk#92963.>>
1 note
2 description: "Hash tables, used to store items identified by hashable keys"
3 library: "Free implementation of ELKS library"
4 legal: "See notice at end of class."
5 instructions: "See instructions at the end of the class."
6 warning: "[
7 Modifying an object used as a key by an item present in a table will
8 cause incorrect behavior. If you will be modifying key objects,
9 pass a clone, not the object itself, as key argument to
10 `put' and `replace_key'.
11 ]"
12
13 status: "See notice at end of class."
14 date: "$Date$"
15 revision: "$Revision$"
16
17 class HASH_TABLE [G, K -> detachable HASHABLE] inherit
18
19 UNBOUNDED [detachable G]
20 rename
21 has as has_item
22 redefine
23 has_item, copy, is_equal
24 end
25
26 TABLE [detachable G, K]
27 rename
28 has as has_item,
29 extend as collection_extend
30 export
31 {NONE} prune_all
32 redefine
33 copy, is_equal, wipe_out, has_item
34 end
35
36 TABLE_ITERABLE [G, K]
37 redefine
38 copy, is_equal
39 end
40
41 READABLE_INDEXABLE [G]
42 rename
43 item as iteration_item,
44 valid_index as valid_iteration_index,
45 index_set as iteration_index_set
46 redefine
47 copy, is_equal, new_cursor
48 end
49
50 MISMATCH_CORRECTOR
51 export
52 {NONE} all
53 {ANY} mismatch_information
54 undefine
55 copy, is_equal
56 redefine
57 correct_mismatch
58 end
59
60 create
61 make,
62 make_equal
63
64 feature -- Initialization
65
66 make (n: INTEGER)
67 -- Allocate hash table for at least `n' items.
68 -- The table will be resized automatically
69 -- if more than `n' items are inserted.
70 require
71 n_non_negative: n >= 0
72 local
73 clever: PRIMES
74 l_default_value: detachable G
75 l_default_key: detachable K
76 l_size: INTEGER
77 do
78 create clever
79 l_size := n.Max (minimum_capacity)
80 l_size := l_size + l_size // 2 + 1
81 l_size := clever.higher_prime (l_size)
82 capacity := l_size
83 -- Position `capacity' ignored by hash sequences,
84 -- used to store value for default key.
85 create content.make_empty (n + 1)
86 create keys.make_empty (n + 1)
87 create deleted_marks.make_filled (False, n + 1)
88 create indexes_map.make_filled (ht_impossible_position, l_size + 1)
89 iteration_position := n + 1
90 count := 0
91 deleted_item_position := ht_impossible_position
92 control := 0
93 found_item := l_default_value
94 has_default := False
95 item_position := 0
96 ht_lowest_deleted_position := ht_max_position
97 ht_deleted_item := l_default_value
98 ht_deleted_key := l_default_key
99 ensure
100 breathing_space: n < capacity
101 more_than_minimum: capacity > minimum_capacity
102 no_status: not special_status
103 end
104
105 make_equal (n: INTEGER)
106 -- Allocate hash table for at least `n' items.
107 -- The table will be resized automatically
108 -- if more than `n' items are inserted.
109 -- Use `~' to compare items.
110 require
111 n_non_negative: n >= 0
112 do
113 make (n)
114 compare_objects
115 ensure
116 breathing_space: n < capacity
117 more_than_minimum: capacity > minimum_capacity
118 no_status: not special_status
119 compare_objects: object_comparison
120 end
121
122 accommodate (n: INTEGER)
123 -- Reallocate table with enough space for `n' items;
124 -- keep all current items.
125 require
126 n >= 0
127 local
128 i, nb: INTEGER
129 new_table: like Current
130 l_content: like content
131 l_keys: like keys
132 do
133 from
134 new_table := empty_duplicate (keys.count.max (n))
135 l_content := content
136 l_keys := keys
137 nb := l_keys.count
138 until
139 i = nb
140 loop
141 if occupied (i) then
142 new_table.put (l_content.item (i), l_keys.item (i))
143 end
144 i := i + 1
145 end
146 if has_default then
147 i := indexes_map.item (capacity)
148 new_table.put (l_content.item (i), keys.item (i))
149 end
150
151 set_content (new_table.content)
152 set_keys (new_table.keys)
153 set_deleted_marks (new_table.deleted_marks)
154 set_indexes_map (new_table.indexes_map)
155 capacity := new_table.capacity
156 iteration_position := new_table.iteration_position
157 ensure
158 count_not_changed: count = old count
159 breathing_space: count < capacity
160 end
161
162 feature -- Access
163
164 found_item: detachable G
165 -- Item, if any, yielded by last search operation
166
167 item alias "[]", at alias "@" (key: K): detachable G assign force
168 -- Item associated with `key', if present
169 -- otherwise default value of type `G'.
170 note
171 option: stable
172 local
173 l_default_key: detachable K
174 hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER
175 l_first_deleted_position: INTEGER
176 stop: INTEGER
177 l_keys: like keys
178 l_indexes: like indexes_map
179 l_deleted_marks: like deleted_marks
180 l_key: K
181 do
182 l_first_deleted_position := ht_impossible_position
183 if key = l_default_key or key = Void then
184 if has_default then
185 Result := content.item (indexes_map.item (capacity))
186 end
187 else
188 from
189 l_keys := keys
190 l_indexes := indexes_map
191 l_deleted_marks := deleted_marks
192 l_capacity := capacity
193 stop := l_capacity
194 hash_value := hash_code_of (key)
195 increment := 1 + hash_value \\ (l_capacity - 1)
196 l_item_pos := (hash_value \\ l_capacity) - increment
197 until
198 stop = 0
199 loop
200 -- Go to next increment.
201 l_item_pos := (l_item_pos + increment) \\ l_capacity
202 l_pos := l_indexes [l_item_pos]
203 if l_pos >= 0 then
204 l_key := l_keys.item (l_pos)
205 debug ("detect_hash_table_catcall")
206 check
207 catcall_detected: l_key /= Void and then l_key.same_type (key)
208 end
209 end
210 if same_keys (l_key, key) then
211 -- We found our item
212 stop := 1
213 Result := content.item (l_pos)
214 end
215 elseif l_pos = ht_impossible_position then
216 stop := 1
217 elseif l_first_deleted_position = ht_impossible_position then
218 l_pos := -l_pos + ht_deleted_position
219 check l_pos_valid: l_pos < l_deleted_marks.count end
220 if not l_deleted_marks [l_pos] then
221 stop := 1
222 else
223 l_first_deleted_position := l_item_pos
224 end
225 end
226 stop := stop - 1
227 end
228 end
229 ensure then
230 default_value_if_not_present:
231 (not (has (key))) implies (Result = computed_default_value)
232 end
233
234 has (key: K): BOOLEAN
235 -- Is there an item in the table with key `key'?
236 local
237 l_default_key: detachable K
238 hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER
239 l_first_deleted_position: INTEGER
240 stop: INTEGER
241 l_keys: like keys
242 l_indexes: like indexes_map
243 l_deleted_marks: like deleted_marks
244 l_key: K
245 do
246 l_first_deleted_position := ht_impossible_position
247 if key = l_default_key or key = Void then
248 if has_default then
249 Result := True
250 end
251 else
252 from
253 l_keys := keys
254 l_indexes := indexes_map
255 l_deleted_marks := deleted_marks
256 l_capacity := capacity
257 stop := l_capacity
258 hash_value := hash_code_of (key)
259 increment := 1 + hash_value \\ (l_capacity - 1)
260 l_item_pos := (hash_value \\ l_capacity) - increment
261 until
262 stop = 0
263 loop
264 -- Go to next increment.
265 l_item_pos := (l_item_pos + increment) \\ l_capacity
266 l_pos := l_indexes [l_item_pos]
267 if l_pos >= 0 then
268 l_key := l_keys.item (l_pos)
269 debug ("detect_hash_table_catcall")
270 check
271 catcall_detected: l_key /= Void and then l_key.same_type (key)
272 end
273 end
274 if same_keys (l_key, key) then
275 -- We found our item
276 stop := 1
277 Result := True
278 end
279 elseif l_pos = ht_impossible_position then
280 stop := 1
281 elseif l_first_deleted_position = ht_impossible_position then
282 l_pos := -l_pos + ht_deleted_position
283 check l_pos_valid: l_pos < l_deleted_marks.count end
284 if not l_deleted_marks [l_pos] then
285 stop := 1
286 else
287 l_first_deleted_position := l_item_pos
288 end
289 end
290 stop := stop - 1
291 end
292 end
293 ensure then
294 default_case: (key = computed_default_key) implies (Result = has_default)
295 end
296
297 has_key (key: K): BOOLEAN
298 -- Is there an item in the table with key `key'? Set `found_item' to the found item.
299 local
300 old_position: INTEGER
301 l_default_value: detachable G
302 do
303 old_position := item_position
304 internal_search (key)
305 Result := found
306 if Result then
307 found_item := content.item (position)
308 else
309 found_item := l_default_value
310 end
311 item_position := old_position
312 ensure then
313 default_case: (key = computed_default_key) implies (Result = has_default)
314 found: Result = found
315 item_if_found: found implies (found_item = item (key))
316 end
317
318 has_item (v: detachable G): BOOLEAN
319 -- Does structure include `v'?
320 -- (Reference or object equality,
321 -- based on `object_comparison'.)
322 local
323 i, nb: INTEGER
324 l_content: like content
325 do
326 if has_default then
327 Result := (v = content.item (indexes_map.item (capacity)))
328 end
329 if not Result then
330 l_content := content
331 nb := l_content.count
332 if object_comparison then
333 from
334 until
335 i = nb or else Result
336 loop
337 Result := occupied (i) and then (v ~ l_content.item (i))
338 i := i + 1
339 end
340 else
341 from
342 until
343 i = nb or else Result
344 loop
345 Result := occupied (i) and then (v = l_content.item (i))
346 i := i + 1
347 end
348 end
349 end
350 end
351
352 current_keys: ARRAY [K]
353 -- New array containing actually used keys, from 1 to `count'
354 local
355 j: INTEGER
356 old_iteration_position: INTEGER
357 do
358 if is_empty then
359 create Result.make_empty
360 else
361 old_iteration_position := iteration_position
362 from
363 start
364 create Result.make_filled (key_for_iteration, 1, count)
365 j := 1
366 forth
367 until
368 off
369 loop
370 j := j + 1
371 Result.put (key_for_iteration, j)
372 forth
373 end
374 iteration_position := old_iteration_position
375 end
376 ensure
377 good_count: Result.count = count
378 end
379
380 item_for_iteration: G
381 -- Element at current iteration position
382 require
383 not_off: not off
384 do
385 Result := content.item (iteration_position)
386 end
387
388 key_for_iteration: K
389 -- Key at current iteration position
390 require
391 not_off: not off
392 do
393 Result := keys.item (iteration_position)
394 end
395
396 cursor: CURSOR
397 -- Current cursor position
398 do
399 create {HASH_TABLE_CURSOR} Result.make (iteration_position)
400 ensure
401 cursor_not_void: Result /= Void
402 end
403
404 new_cursor: HASH_TABLE_ITERATION_CURSOR [G, K]
405 -- <Precursor>
406 do
407 create Result.make (Current)
408 Result.start
409 end
410
411 iteration_item (i: INTEGER): G
412 -- <Precursor>
413 do
414 Result := content.item (i)
415 end
416
417 hash_code_of (a_key: attached K): INTEGER
418 -- Hash_code value associated to `a_key'.
419 do
420 -- Default implementation uses `{HASHABLE}.hash_code'.
421 Result := a_key.hash_code
422 ensure
423 non_negative: Result >= 0
424 end
425
426 feature -- Measurement
427
428 count: INTEGER
429 -- Number of items in table
430
431 capacity: INTEGER
432 -- Number of items that may be stored.
433
434 occurrences (v: detachable G): INTEGER
435 -- Number of table items equal to `v'.
436 local
437 old_iteration_position: INTEGER
438 do
439 old_iteration_position := iteration_position
440 if object_comparison then
441 from
442 start
443 until
444 off
445 loop
446 if item_for_iteration ~ v then
447 Result := Result + 1
448 end
449 forth
450 end
451 else
452 from
453 start
454 until
455 off
456 loop
457 if item_for_iteration = v then
458 Result := Result + 1
459 end
460 forth
461 end
462 end
463 iteration_position := old_iteration_position
464 end
465
466 iteration_index_set: INTEGER_INTERVAL
467 -- <Precursor>
468 do
469 create Result.make (next_iteration_position (-1), previous_iteration_position (keys.count))
470 end
471
472 feature -- Comparison
473
474 is_equal (other: like Current): BOOLEAN
475 -- Does table contain the same information as `other'?
476 do
477 if
478 count = other.count and then
479 object_comparison = other.object_comparison and then
480 has_default = other.has_default
481 then
482 Result := True
483 across
484 Current as l_c
485 until
486 not Result
487 loop
488 other.search (l_c.key)
489 if other.found then
490 if object_comparison then
491 Result := l_c.item ~ other.found_item
492 else
493 Result := l_c.item = other.found_item
494 end
495 else
496 Result := False
497 end
498 end
499 end
500 end
501
502 same_keys (a_search_key, a_key: K): BOOLEAN
503 -- Does `a_search_key' equal to `a_key'?
504 --| Default implementation is using ~.
505 require
506 valid_search_key: valid_key (a_search_key)
507 valid_key: valid_key (a_key)
508 do
509 Result := a_search_key ~ a_key
510 end
511
512 disjoint (other: HASH_TABLE [G, K]): BOOLEAN
513 -- Is `Current' and `other' disjoint on their keys?
514 -- Use `same_keys' for comparison.
515 do
516 -- If any of the tables are empty, it is clearly disjoint,
517 -- otherwise we check that no elements of `other' appears in Current.
518 Result := is_empty or else other.is_empty or else
519 not across other as o some has (o.key) end
520 end
521
522 feature -- Status report
523
524 full: BOOLEAN = False
525 -- Is structure filled to capacity?
526
527 extendible: BOOLEAN = False
528 -- May new items be added?
529
530 prunable: BOOLEAN
531 -- May items be removed?
532 do
533 Result := True
534 end
535
536 conflict: BOOLEAN
537 -- Did last operation cause a conflict?
538 do
539 Result := (control = conflict_constant)
540 end
541
542 inserted: BOOLEAN
543 -- Did last operation insert an item?
544 do
545 Result := (control = inserted_constant)
546 end
547
548 replaced: BOOLEAN
549 -- Did last operation replace an item?
550 do
551 Result := (control = replaced_constant)
552 end
553
554 removed: BOOLEAN
555 -- Did last operation remove an item?
556 do
557 Result := (control = removed_constant)
558 end
559
560 found: BOOLEAN
561 -- Did last operation find the item sought?
562 do
563 Result := (control = found_constant)
564 end
565
566 not_found: BOOLEAN
567 -- Did last operation fail to find the item sought?
568 do
569 Result := (control = not_found_constant)
570 end
571
572 after, off: BOOLEAN
573 -- Is cursor past last item?
574 do
575 Result := is_off_position (iteration_position)
576 end
577
578 valid_cursor (c: CURSOR): BOOLEAN
579 -- Can cursor be moved to position `c'?
580 require
581 c_not_void: c /= Void
582 local
583 i: INTEGER
584 do
585 if attached {HASH_TABLE_CURSOR} c as ht_cursor then
586 i := ht_cursor.position
587 Result := is_off_position (i) or else truly_occupied (i)
588 end
589 end
590
591 valid_key (k: K): BOOLEAN
592 -- Is `k' a valid key?
593 do
594 Result := True
595 debug ("prevent_hash_table_catcall")
596 -- If `K' is expanded then there will be no catcall.
597 -- If `K' is a reference, we make sure that the type of the object `k'
598 -- is the detachable version of `K' as objects have the detachable type by default.
599 if not ({K}).is_expanded and then attached k then
600 Result := k.generating_type ~ {detachable K}
601 end
602 end
603 end
604
605 valid_iteration_index (i: INTEGER): BOOLEAN
606 -- <Precursor>
607 do
608 Result := truly_occupied (i)
609 end
610
611 feature -- Cursor movement
612
613 start
614 -- Bring cursor to first position.
615 do
616 -- Get lower bound of iteration if any.
617 iteration_position := next_iteration_position (-1)
618 end
619
620 forth
621 -- Advance cursor to next occupied position,
622 -- or `off' if no such position remains.
623 require
624 not_off: not off
625 do
626 iteration_position := next_iteration_position (iteration_position)
627 end
628
629 go_to (c: CURSOR)
630 -- Move to position `c'.
631 require
632 c_not_void: c /= Void
633 valid_cursor: valid_cursor (c)
634 do
635 if attached {HASH_TABLE_CURSOR} c as ht_cursor then
636 iteration_position := ht_cursor.position
637 end
638 end
639
640 search (key: K)
641 -- Search for item of key `key'.
642 -- If found, set `found' to true, and set
643 -- `found_item' to item associated with `key'.
644 local
645 old_position: INTEGER
646 l_default_value: detachable G
647 do
648 old_position := item_position
649 internal_search (key)
650 if found then
651 found_item := content.item (position)
652 else
653 found_item := l_default_value
654 end
655 item_position := old_position
656 ensure
657 found_or_not_found: found or not_found
658 item_if_found: found implies (found_item = item (key))
659 end
660
661 search_item: detachable G
662 obsolete
663 "Use found_item instead."
664 do
665 Result := found_item
666 end
667
668 feature {HASH_TABLE_ITERATION_CURSOR} -- Cursor movement
669
670 next_iteration_position (a_position: like iteration_position): like iteration_position
671 -- Given an iteration position, advanced to the next one taking into account deleted
672 -- slots in the `content' and `keys' structures.
673 require
674 a_position_big_enough: a_position >= -1
675 a_position_small_enough: a_position < keys.count
676 local
677 l_deleted_marks: like deleted_marks
678 l_table_size: INTEGER
679 do
680 Result := a_position + 1
681 l_deleted_marks := deleted_marks
682 l_table_size := content.count
683 from
684 until
685 Result >= l_table_size or else not l_deleted_marks.item (Result)
686 loop
687 Result := Result + 1
688 end
689 end
690
691 previous_iteration_position (a_position: like iteration_position): like iteration_position
692 -- Given an iteration position, go to the previous one taking into account deleted
693 -- slots in the `content' and `keys' structures.
694 require
695 a_position_big_enough: a_position >= 0
696 a_position_small_enough: a_position <= keys.count
697 local
698 l_deleted_marks: like deleted_marks
699 l_table_size: INTEGER
700 do
701 Result := a_position - 1
702 l_deleted_marks := deleted_marks
703 l_table_size := content.count
704 from
705 until
706 Result <= 0 or else not l_deleted_marks.item (Result)
707 loop
708 Result := Result - 1
709 end
710 end
711
712 feature -- Element change
713
714 put (new: G; key: K)
715 -- Insert `new' with `key' if there is no other item
716 -- associated with the same key.
717 -- Set `inserted' if and only if an insertion has
718 -- been made (i.e. `key' was not present).
719 -- If so, set `position' to the insertion position.
720 -- If not, set `conflict'.
721 -- In either case, set `found_item' to the item
722 -- now associated with `key' (previous item if
723 -- there was one, `new' otherwise).
724 --
725 -- To choose between various insert/replace procedures,
726 -- see `instructions' in the Indexing clause.
727 local
728 l_default_key: detachable K
729 l_new_pos, l_new_index_pos: like position
730 do
731 internal_search (key)
732 if found then
733 set_conflict
734 found_item := content.item (position)
735 else
736 if soon_full then
737 add_space
738 internal_search (key)
739 check
740 -- The key didn't magically insert itself.
741 not_present: not found
742 end
743 end
744 if deleted_item_position /= ht_impossible_position then
745 l_new_pos := deleted_position (deleted_item_position)
746 l_new_index_pos := deleted_item_position
747 deleted_marks.force (False, l_new_pos)
748 else
749 l_new_pos := keys.count
750 l_new_index_pos := item_position
751 end
752 indexes_map.put (l_new_pos, l_new_index_pos)
753 content.force (new, l_new_pos)
754 keys.force (key, l_new_pos)
755 if key = l_default_key then
756 has_default := True
757 end
758 count := count + 1
759 found_item := new
760 control := inserted_constant
761 end
762 ensure then
763 conflict_or_inserted: conflict or inserted
764 insertion_done: inserted implies item (key) = new
765 now_present: inserted implies has (key)
766 one_more_if_inserted: inserted implies (count = old count + 1)
767 unchanged_if_conflict: conflict implies (count = old count)
768 same_item_if_conflict: conflict implies (item (key) = old (item (key)))
769 found_item_associated_with_key: found_item = item (key)
770 new_item_if_inserted: inserted implies (found_item = new)
771 old_item_if_conflict: conflict implies (found_item = old (item (key)))
772 default_property:
773 has_default =
774 ((inserted and (key = computed_default_key)) or
775 ((conflict or (key /= computed_default_key))
776 and (old has_default)))
777 end
778
779 force (new: G; key: K)
780 -- Update table so that `new' will be the item associated
781 -- with `key'.
782 -- If there was an item for that key, set `found'
783 -- and set `found_item' to that item.
784 -- If there was none, set `not_found' and set
785 -- `found_item' to the default value.
786 --
787 -- To choose between various insert/replace procedures,
788 -- see `instructions' in the Indexing clause.
789 local
790 l_default_key: detachable K
791 l_default_value: detachable G
792 l_new_pos, l_new_index_pos: like position
793 do
794 internal_search (key)
795 if not_found then
796 if soon_full then
797 add_space
798 internal_search (key)
799 end
800 if deleted_item_position /= ht_impossible_position then
801 l_new_pos := deleted_position (deleted_item_position)
802 l_new_index_pos := deleted_item_position
803 deleted_marks.force (False, l_new_pos)
804 else
805 l_new_pos := keys.count
806 l_new_index_pos := item_position
807 end
808 indexes_map.put (l_new_pos, l_new_index_pos)
809 keys.force (key, l_new_pos)
810 if key = l_default_key then
811 has_default := True
812 end
813 count := count + 1
814 found_item := l_default_value
815 else
816 l_new_pos := position
817 found_item := content.item (l_new_pos)
818 end
819 content.force (new, l_new_pos)
820 ensure then
821 insertion_done: item (key) = new
822 now_present: has (key)
823 found_or_not_found: found or not_found
824 not_found_if_was_not_present: not_found = not (old has (key))
825 same_count_or_one_more: (count = old count) or (count = old count + 1)
826 found_item_is_old_item: found implies (found_item = old (item (key)))
827 default_value_if_not_found:
828 not_found implies (found_item = computed_default_value)
829 -- The reverse is not true, as we can always insert
830 -- an item with the default value, for any key.
831
832 default_property:
833 has_default =
834 ((key = computed_default_key) or
835 ((key /= computed_default_key) and (old has_default)))
836 end
837
838 extend (new: G; key: K)
839 -- Assuming there is no item of key `key',
840 -- insert `new' with `key'.
841 -- Set `inserted'.
842 --
843 -- To choose between various insert/replace procedures,
844 -- see `instructions' in the Indexing clause.
845 require
846 not_present: not has (key)
847 local
848 l_default_key: detachable K
849 l_new_pos, l_new_index_pos: like position
850 do
851 search_for_insertion (key)
852 if soon_full then
853 add_space
854 search_for_insertion (key)
855 end
856 if deleted_item_position /= ht_impossible_position then
857 l_new_pos := deleted_position (deleted_item_position)
858 l_new_index_pos := deleted_item_position
859 deleted_marks.force (False, l_new_pos)
860 else
861 l_new_pos := keys.count
862 l_new_index_pos := item_position
863 end
864 indexes_map.put (l_new_pos, l_new_index_pos)
865 content.force (new, l_new_pos)
866 keys.force (key, l_new_pos)
867 if key = l_default_key then
868 has_default := True
869 end
870 count := count + 1
871 control := inserted_constant
872 ensure
873 inserted: inserted
874 insertion_done: item (key) = new
875 one_more: count = old count + 1
876 default_property:
877 has_default =
878 ((key = computed_default_key) or (old has_default))
879 end
880
881 replace (new: G; key: K)
882 -- Replace item at `key', if present,
883 -- with `new'; do not change associated key.
884 -- Set `replaced' if and only if a replacement has been made
885 -- (i.e. `key' was present); otherwise set `not_found'.
886 -- Set `found_item' to the item previously associated
887 -- with `key' (default value if there was none).
888 --
889 -- To choose between various insert/replace procedures,
890 -- see `instructions' in the Indexing clause.
891 local
892 l_default_item: detachable G
893 do
894 internal_search (key)
895 if found then
896 found_item := content.item (position)
897 content.put (new, position)
898 control := replaced_constant
899 else
900 found_item := l_default_item
901 end
902 ensure
903 replaced_or_not_found: replaced or not_found
904 insertion_done: replaced implies item (key) = new
905 no_change_if_not_found: not_found implies
906 item (key) = old (item (key))
907 found_item_is_old_item: found_item = old (item (key))
908 end
909
910 replace_key (new_key: K; old_key: K)
911 -- If there is an item of key `old_key' and no item of key
912 -- `new_key', replace the former's key by `new_key',
913 -- set `replaced', and set `found_item' to the item
914 -- previously associated with `old_key'.
915 -- Otherwise set `not_found' or `conflict' respectively.
916 -- If `conflict', set `found_item' to the item previously
917 -- associated with `new_key'.
918 --
919 -- To choose between various insert/replace procedures,
920 -- see `instructions' in the Indexing clause.
921 local
922 l_item: G
923 do
924 internal_search (new_key)
925 if not found then
926 internal_search (old_key)
927 if found then
928 l_item := content.item (position)
929 remove (old_key)
930 put (l_item, new_key)
931 control := replaced_constant
932 end
933 else
934 set_conflict
935 found_item := content.item (position)
936 end
937 ensure
938 same_count: count = old count
939 replaced_or_conflict_or_not_found: replaced or conflict or not_found
940 old_absent: (replaced and not same_keys (new_key, old_key)) implies (not has (old_key))
941 new_present: (replaced or conflict) = has (new_key)
942 new_item: replaced implies (item (new_key) = old (item (old_key)))
943 not_found_implies_no_old_key: not_found implies old (not has (old_key))
944 conflict_iff_already_present: conflict = old (has (new_key))
945 not_inserted_if_conflict: conflict implies
946 (item (new_key) = old (item (new_key)))
947 end
948
949 merge (other: HASH_TABLE [G, K])
950 -- Merge `other' into Current. If `other' has some elements
951 -- with same key as in `Current', replace them by one from
952 -- `other'.
953 require
954 other_not_void: other /= Void
955 do
956 from
957 other.start
958 until
959 other.after
960 loop
961 force (other.item_for_iteration, other.key_for_iteration)
962 other.forth
963 end
964 ensure
965 inserted: other.current_keys.linear_representation.for_all (agent has)
966 end
967
968 feature -- Removal
969
970 remove (key: K)
971 -- Remove item associated with `key', if present.
972 -- Set `removed' if and only if an item has been
973 -- removed (i.e. `key' was present);
974 -- if so, set `position' to index of removed element.
975 -- If not, set `not_found'.
976 -- Reset `found_item' to its default value if `removed'.
977 local
978 l_default_key: detachable K
979 l_default_value: detachable G
980 l_pos: like position
981 l_nb_removed_items: INTEGER
982 do
983 internal_search (key)
984 if found then
985 l_pos := position
986 if key = l_default_key then
987 has_default := False
988 end
989 deleted_marks.put (True, l_pos)
990 indexes_map.put (-l_pos + ht_deleted_position, item_position)
991 if iteration_position = l_pos then
992 forth
993 end
994 count := count - 1
995 -- For void-safety concerns and to avoid leaking too many objects,
996 -- we set all deleted positions to the same item and key when removing
997 -- on the inside of the SPECIALs, otherwise we simply shrink the SPECIALs.
998 ht_lowest_deleted_position := l_pos.min (ht_lowest_deleted_position)
999 if (ht_lowest_deleted_position = count) then
1000 -- We have removed all elements above `ht_lowest_deleted_position', we can
1001 -- shrink our SPECIALs.
1002 l_nb_removed_items := content.count - ht_lowest_deleted_position
1003 content.remove_tail (l_nb_removed_items)
1004 keys.remove_tail (l_nb_removed_items)
1005 -- All elements above `ht_lowest_deleted_position' of `deleted_marks' are reset
1006 -- to False. To be correct, we should also reset their corresponding indexes
1007 -- in `indexes_map' to `ht_impossible_position' however that would be too
1008 -- expensive to traverse the structure. Instead we leave items as they are but
1009 -- we cope with them in `internal_search'.
1010 deleted_marks.fill_with (False, ht_lowest_deleted_position, deleted_marks.count - 1)
1011 ht_deleted_item := l_default_value
1012 ht_deleted_key := l_default_key
1013 ht_lowest_deleted_position := ht_max_position
1014 elseif attached ht_deleted_item as l_item and attached ht_deleted_key as l_key then
1015 content.put (l_item, l_pos)
1016 keys.put (l_key, l_pos)
1017 else
1018 -- First time we actually remove an item from the table.
1019 ht_deleted_item := content.item (l_pos)
1020 ht_deleted_key := keys.item (l_pos)
1021 end
1022 control := removed_constant
1023 found_item := l_default_value
1024 end
1025 ensure
1026 removed_or_not_found: removed or not_found
1027 not_present: not has (key)
1028 one_less: found implies (count = old count - 1)
1029 default_case:
1030 (key = computed_default_key) implies (not has_default)
1031 non_default_case:
1032 (key /= computed_default_key) implies
1033 (has_default = old has_default)
1034 end
1035
1036 prune (v: detachable G)
1037 -- Remove first occurrence of `v', if any,
1038 -- after cursor position.
1039 -- Move cursor to right neighbor.
1040 -- (or after if no right neighbor or `v' does not occur)
1041 do
1042 -- No need to check if we are before because `iteration_position' is either
1043 -- a valid position or `off' (see invariant `valid_iteration_position').
1044 -- Thus we can start iterating right away.
1045 if object_comparison then
1046 from
1047 until
1048 after or else item_for_iteration ~ v
1049 loop
1050 forth
1051 end
1052 else
1053 from
1054 until
1055 after or else item_for_iteration = v
1056 loop
1057 forth
1058 end
1059 end
1060 if not after then
1061 remove (key_for_iteration)
1062 end
1063 end
1064
1065 wipe_out
1066 -- Reset all items to default values; reset status.
1067 local
1068 l_default_value: detachable G
1069 do
1070 content.wipe_out
1071 keys.wipe_out
1072 deleted_marks.fill_with (False, 0, deleted_marks.upper)
1073 indexes_map.fill_with (ht_impossible_position, 0, capacity)
1074 found_item := l_default_value
1075 count := 0
1076 item_position := 0
1077 iteration_position := keys.count
1078 control := 0
1079 has_default := False
1080 ensure then
1081 position_equal_to_zero: item_position = 0
1082 count_equal_to_zero: count = 0
1083 has_default_set: not has_default
1084 no_status: not special_status
1085 end
1086
1087 clear_all
1088 obsolete
1089 "Use `wipe_out' instead."
1090 do
1091 wipe_out
1092 end
1093
1094 feature -- Conversion
1095
1096 linear_representation: ARRAYED_LIST [G]
1097 -- Representation as a linear structure
1098 local
1099 old_iteration_position: INTEGER
1100 do
1101 old_iteration_position := iteration_position
1102 from
1103 create Result.make (count)
1104 start
1105 until
1106 off
1107 loop
1108 Result.extend (item_for_iteration)
1109 forth
1110 end
1111 iteration_position := old_iteration_position
1112 ensure then
1113 Result_exists: Result /= Void
1114 good_count: Result.count = count
1115 end
1116
1117 feature -- Duplication
1118
1119 copy (other: like Current)
1120 -- Re-initialize from `other'.
1121 do
1122 if other /= Current then
1123 standard_copy (other)
1124 set_content (other.content.twin)
1125 set_keys (other.keys.twin)
1126 set_deleted_marks (other.deleted_marks.twin)
1127 set_indexes_map (other.indexes_map.twin)
1128 end
1129 end
1130
1131 feature {NONE} -- Duplication
1132
1133 empty_duplicate (n: INTEGER): like Current
1134 -- Create an empty copy of Current that can accommodate `n' items
1135 require
1136 n_non_negative: n >= 0
1137 do
1138 create Result.make (n)
1139 if object_comparison then
1140 Result.compare_objects
1141 end
1142 ensure
1143 empty_duplicate_attached: Result /= Void
1144 end
1145
1146 feature {NONE} -- Transformation
1147
1148 correct_mismatch
1149 -- Attempt to correct object mismatch during retrieve using `mismatch_information'.
1150 local
1151 l_old_deleted_marks: detachable SPECIAL [BOOLEAN]
1152 i, l_capacity, l_count: INTEGER
1153 l_new_table: like Current
1154 l_default_item: like ht_deleted_item
1155 l_default_key: like ht_deleted_key
1156 do
1157 if not mismatch_information.has ("hash_table_version_64") then
1158 -- In version 5.1 and earlier, `content', `keys' and `deleted_marks'
1159 -- where of base class ARRAY. In 5.2 we changed it to be a SPECIAL for
1160 -- efficiency reasons. In order to retrieve an old HASH_TABLE we
1161 -- need to convert those ARRAY instances into SPECIAL instances.
1162
1163 -- Convert `content' from ARRAY to SPECIAL
1164 if attached {ARRAY [G]} mismatch_information.item ("content") as array_content then
1165 content := array_content.area
1166 end
1167
1168 -- Convert `keys' from ARRAY to SPECIAL
1169 if attached {ARRAY [K]} mismatch_information.item ("keys") as array_keys then
1170 keys := array_keys.area
1171 end
1172
1173 -- Convert `deleted_marks' from ARRAY to SPECIAL
1174 if attached {ARRAY [BOOLEAN]} mismatch_information.item ("deleted_marks") as array_marks then
1175 deleted_marks := array_marks.area
1176 end
1177
1178 -- In version 5.5 and later, `deleted_marks' had its size increased by 1 to take
1179 -- into account removal of default key, and therefore if we hit a 5.4 or earlier
1180 -- version, we need to resize `deleted_marks' to the new expected size.
1181 if deleted_marks /= Void and keys /= Void then
1182 if not mismatch_information.has ("hash_table_version_57") then
1183 -- Unfortunately this handling of the mismatch was added in 5.7 and
1184 -- therefore we might have stored a valid HASH_TABLE using 5.5 or 5.6.
1185 -- Fortunately enough we can simply compare the counts of
1186 -- `deleted_marks' and `keys'. If they are the same it is 5.5 or 5.6,
1187 -- otherwise it is 5.4 or older.
1188 if deleted_marks.count /= keys.count then
1189 l_old_deleted_marks := deleted_marks
1190 create deleted_marks.make_empty (keys.count)
1191 deleted_marks.copy_data (l_old_deleted_marks, 0, 0, l_old_deleted_marks.count)
1192 end
1193 end
1194 end
1195
1196 if attached {INTEGER} mismatch_information.item ("count") as l_retrieved_count then
1197 l_count := l_retrieved_count
1198 end
1199
1200 if content = Void or keys = Void or deleted_marks = Void then
1201 -- Could not retrieve old version of HASH_TABLE. We throw an exception.
1202 Precursor {MISMATCH_CORRECTOR}
1203 else
1204 -- Now we build the new HASH_TABLE from the old one.
1205 from
1206 l_capacity := keys.count
1207 l_new_table := empty_duplicate (l_count)
1208 until
1209 i = l_capacity
1210 loop
1211 if attached keys.item (i) as l_key_item and then l_key_item /= l_default_key then
1212 l_new_table.put (content.item (i), l_key_item)
1213 end
1214 i := i + 1
1215 end
1216 if attached {BOOLEAN} mismatch_information.item ("has_default") as l_bool and then l_bool then
1217 l_new_table.put (content.item (content.capacity - 1), keys.item (l_capacity - 1))
1218 end
1219
1220 set_content (l_new_table.content)
1221 set_keys (l_new_table.keys)
1222 set_deleted_marks (l_new_table.deleted_marks)
1223 set_indexes_map (l_new_table.indexes_map)
1224 capacity := l_new_table.capacity
1225 iteration_position := l_new_table.iteration_position
1226 deleted_item_position := l_new_table.deleted_item_position
1227 item_position := l_new_table.item_position
1228 -- We reset the following attributes to their default value
1229 ht_lowest_deleted_position := ht_max_position
1230 ht_deleted_item := l_default_item
1231 ht_deleted_key := l_default_key
1232 -- We don't change `object_comparison' from the value it was retrieved from.
1233 end
1234
1235 -- Reset `control' to an acceptable value.
1236 control := 0
1237 end
1238 end
1239
1240 hash_table_version_64: BOOLEAN
1241 -- Fake attribute for versioning purposes. Used in `correct_mismatch'.
1242
1243 feature {HASH_TABLE, HASH_TABLE_ITERATION_CURSOR} -- Implementation: content attributes and preservation
1244
1245 content: SPECIAL [G]
1246 -- Array of contents
1247
1248 keys: SPECIAL [K]
1249 -- Array of keys
1250
1251 feature {HASH_TABLE} -- Implementation: content attributes and preservation
1252
1253 indexes_map: SPECIAL [INTEGER]
1254 -- Indexes of items in `content', and `keys'.
1255 -- If item is not present, then it has `ht_mpossible_position'.
1256 -- If item is deleted, then it has `ht_deleted_position'.
1257
1258 deleted_marks: SPECIAL [BOOLEAN]
1259 -- Indexes of deleted positions in `content' and `keys'.
1260
1261 item_position: INTEGER
1262 -- Position in `indexes_map' for item at position `position'. Set by `internal_search'.
1263
1264 has_default: BOOLEAN
1265 -- Is the default key present?
1266
1267 feature {HASH_TABLE} -- Implementation: search attributes
1268
1269 iteration_position: INTEGER
1270 -- Cursor for iteration primitives
1271
1272 position: INTEGER
1273 -- Hash table cursor, updated after each operation:
1274 -- put, remove, has, replace, force, change_key...
1275 do
1276 Result := indexes_map.item (item_position)
1277 end
1278
1279 soon_full: BOOLEAN
1280 -- Is table close to being filled to current capacity?
1281 do
1282 Result := keys.count = keys.capacity
1283 ensure
1284 Result = (keys.count = keys.capacity)
1285 end
1286
1287 control: INTEGER
1288 -- Control code set by operations that may produce
1289 -- several possible conditions.
1290
1291 deleted_item_position: INTEGER
1292 -- Place where a deleted element was found during a search
1293
1294 feature {NONE} -- Implementation
1295
1296 ht_max_position: INTEGER = 0x7FFFFFFD
1297 -- Maximum possible position
1298
1299 ht_impossible_position: INTEGER = -1
1300 -- Position outside the array indices.
1301
1302 ht_deleted_position: INTEGER = -2
1303 -- Marked a deleted position.
1304
1305 ht_lowest_deleted_position: INTEGER
1306 -- Index of the lowest deleted position thus far.
1307
1308 ht_deleted_item: detachable G
1309 ht_deleted_key: detachable K
1310 -- Store the item and key that will be used to replace an element of the HASH_TABLE
1311 -- that will be removed. If elements being removed are at the end of `content' or `keys'
1312 -- then they are both Void. It is only used when removing an element at a position strictly
1313 -- less than `count'.
1314
1315 deleted_position (a_pos: INTEGER): INTEGER
1316 -- Given the position of a deleted item at `a_pos' gives the associated position
1317 -- in `content/keys'.
1318 require
1319 deleted: deleted (a_pos)
1320 do
1321 Result := -indexes_map.item (a_pos) + ht_deleted_position
1322 -- Sometime we shrink `keys' and `content' while removing items, as a result, some
1323 -- stored deleted position in `indexes_map' are beyond `keys' and `content'. In those
1324 -- cases, we simply return the location for the next insertion instead.
1325 Result := Result.min (keys.count)
1326 ensure
1327 deleted_position_non_negative: Result >= 0
1328 deleted_position_valid: Result <= keys.count and Result <= content.count
1329 end
1330
1331 occupied (i: INTEGER): BOOLEAN
1332 -- Is position `i' occupied by a non-default key and a value?
1333 require
1334 in_bounds: deleted_marks.valid_index (i)
1335 do
1336 if has_default then
1337 Result := i /= indexes_map.item (capacity) and then not deleted_marks.item (i)
1338 else
1339 Result := not deleted_marks.item (i)
1340 end
1341 end
1342
1343 truly_occupied (i: INTEGER): BOOLEAN
1344 -- Is position `i' occupied by a key and a value?
1345 do
1346 if i >= 0 and i < keys.count then
1347 Result := (has_default and i = indexes_map.item (capacity)) or else occupied (i)
1348 end
1349 ensure
1350 normal_key: (i >= 0 and i < keys.count and i /= indexes_map.item (capacity)) implies (occupied (i) implies Result)
1351 default_key: (i = indexes_map.item (capacity)) implies (Result = has_default)
1352 end
1353
1354 is_off_position (pos: INTEGER): BOOLEAN
1355 -- Is `pos' a cursor position outside the authorized range?
1356 do
1357 Result := pos < 0 or pos >= keys.count
1358 end
1359
1360 set_content (c: like content)
1361 -- Assign `c' to `content'.
1362 require
1363 c_attached: c /= Void
1364 do
1365 content := c
1366 ensure
1367 content_set: content = c
1368 end
1369
1370 deleted (i: INTEGER): BOOLEAN
1371 -- Is position `i' that of a deleted item?
1372 require
1373 in_bounds: i >= 0 and i <= capacity
1374 do
1375 Result := indexes_map.item (i) <= ht_deleted_position
1376 end
1377
1378 set_keys (c: like keys)
1379 -- Assign `c' to `keys'.
1380 require
1381 c_attached: c /= Void
1382 do
1383 keys := c
1384 ensure
1385 keys_set: keys = c
1386 end
1387
1388 set_deleted_marks (d: like deleted_marks)
1389 -- Assign `c' to `content'.
1390 require
1391 d_attached: d /= Void
1392 do
1393 deleted_marks := d
1394 ensure
1395 deleted_marks_set: deleted_marks = d
1396 end
1397
1398 set_indexes_map (v: like indexes_map )
1399 -- Assign `v' to `indexes_map'.
1400 do
1401 indexes_map := v
1402 ensure
1403 indexes_map_set: indexes_map = v
1404 end
1405
1406 default_key_value: G
1407 -- Value associated with the default key, if any
1408 require
1409 has_default: has_default
1410 do
1411 Result := content [indexes_map [capacity]]
1412 end
1413
1414 computed_default_key: detachable K
1415 -- Default key
1416 -- (For performance reasons, used only in assertions;
1417 -- elsewhere, see use of local entity `l_default_key'.)
1418 do
1419 -- No instructions necessary (returns default value of type K)
1420 end
1421
1422 computed_default_value: detachable G
1423 -- Default value of type G
1424 -- (For performance reasons, used only in assertions;
1425 -- elsewhere, see use of local entity `l_default_value'.)
1426 do
1427 -- No instructions necessary (returns default value of type G)
1428 end
1429
1430 internal_search (key: K)
1431 -- Search for item of key `key'.
1432 -- If successful, set `position' to index
1433 -- of item with this key (the same index as the key's index).
1434 -- If not, set `position' to possible position for insertion,
1435 -- and set status to `found' or `not_found'.
1436 local
1437 l_default_key: detachable K
1438 hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER
1439 l_first_deleted_position: INTEGER
1440 stop: INTEGER
1441 l_keys: like keys
1442 l_indexes: like indexes_map
1443 l_deleted_marks: like deleted_marks
1444 l_key: K
1445 do
1446 l_first_deleted_position := ht_impossible_position
1447 if key = l_default_key or key = Void then
1448 item_position := capacity
1449 if has_default then
1450 control := found_constant
1451 else
1452 control := not_found_constant
1453 end
1454 else
1455 from
1456 l_keys := keys
1457 l_indexes := indexes_map
1458 l_deleted_marks := deleted_marks
1459 l_capacity := capacity
1460 stop := l_capacity
1461 hash_value := hash_code_of (key)
1462 increment := 1 + hash_value \\ (l_capacity - 1)
1463 l_item_pos := (hash_value \\ l_capacity) - increment
1464 control := not_found_constant
1465 until
1466 stop = 0
1467 loop
1468 -- Go to next increment.
1469 l_item_pos := (l_item_pos + increment) \\ l_capacity
1470 l_pos := l_indexes [l_item_pos]
1471 if l_pos >= 0 then
1472 l_key := l_keys.item (l_pos)
1473 debug ("detect_hash_table_catcall")
1474 check
1475 catcall_detected: l_key /= Void and then l_key.same_type (key)
1476 end
1477 end
1478 if same_keys (l_key, key) then
1479 stop := 1
1480 control := found_constant
1481 end
1482 elseif l_pos = ht_impossible_position then
1483 stop := 1
1484 elseif l_first_deleted_position = ht_impossible_position then
1485 l_pos := -l_pos + ht_deleted_position
1486 check l_pos_valid: l_pos < l_deleted_marks.count end
1487 if not l_deleted_marks [l_pos] then
1488 stop := 1
1489 else
1490 l_first_deleted_position := l_item_pos
1491 end
1492 end
1493 stop := stop - 1
1494 end
1495 item_position := l_item_pos
1496 end
1497 deleted_item_position := l_first_deleted_position
1498 ensure
1499 found_or_not_found: found or not_found
1500 deleted_item_at_deleted_position:
1501 (deleted_item_position /= ht_impossible_position) implies (deleted (deleted_item_position))
1502 default_iff_at_capacity: (item_position = capacity) = (key = computed_default_key)
1503 end
1504
1505 search_for_insertion (key: K)
1506 -- Assuming there is no item of key `key', compute
1507 -- `position' at which to insert such an item.
1508 require
1509 not_present: not has (key)
1510 local
1511 l_default_key: detachable K
1512 hash_value, increment, l_pos, l_item_pos, l_capacity: INTEGER
1513 l_first_deleted_position: INTEGER
1514 stop: INTEGER
1515 l_keys: like keys
1516 l_indexes: like indexes_map
1517 l_deleted_marks: like deleted_marks
1518 do
1519 l_first_deleted_position := ht_impossible_position
1520 if key = l_default_key or key = Void then
1521 check
1522 -- Because of the precondition
1523 not has_default
1524 end
1525 item_position := capacity
1526 else
1527 from
1528 l_keys := keys
1529 l_indexes := indexes_map
1530 l_deleted_marks := deleted_marks
1531 l_capacity := capacity
1532 stop := l_capacity
1533 hash_value := hash_code_of (key)
1534 increment := 1 + hash_value \\ (l_capacity - 1)
1535 l_item_pos := (hash_value \\ l_capacity) - increment
1536 until
1537 stop = 0
1538 loop
1539 -- Go to next increment.
1540 l_item_pos := (l_item_pos + increment) \\ l_capacity
1541 l_pos := l_indexes [l_item_pos]
1542 if l_pos >= 0 then
1543 -- Because of precondition, we are sure there is no key corresponding to `key'.
1544 elseif l_pos = ht_impossible_position then
1545 stop := 1
1546 elseif l_first_deleted_position = ht_impossible_position then
1547 l_pos := -l_pos + ht_deleted_position
1548 check l_pos_valid: l_pos < l_deleted_marks.count end
1549 if not l_deleted_marks [l_pos] then
1550 stop := 1
1551 else
1552 l_first_deleted_position := l_item_pos
1553 end
1554 end
1555 stop := stop - 1
1556 end
1557 item_position := l_item_pos
1558 end
1559 deleted_item_position := l_first_deleted_position
1560 ensure
1561 deleted_item_at_deleted_position:
1562 (deleted_item_position /= ht_impossible_position) implies (deleted (deleted_item_position))
1563 default_iff_at_capacity: (item_position = capacity) = (key = computed_default_key)
1564 end
1565
1566 key_at (n: INTEGER): detachable K
1567 -- Key at position `n'
1568 do
1569 if keys.valid_index (n) then
1570 Result := keys.item (n)
1571 end
1572 end
1573
1574 initial_position (hash_value: INTEGER): INTEGER
1575 -- Initial position for an item of hash code `hash_value'
1576 do
1577 Result := (hash_value \\ capacity)
1578 end
1579
1580 position_increment (hash_value: INTEGER): INTEGER
1581 -- Distance between successive positions for hash code
1582 -- `hash_value' (computed for no cycle: `capacity' is prime)
1583 do
1584 Result := 1 + hash_value \\ (capacity - 1)
1585 end
1586
1587 conflict_constant: INTEGER = 1
1588 -- Could not insert an already existing key
1589
1590 set_conflict
1591 -- Set status to conflict.
1592 do
1593 control := conflict_constant
1594 ensure
1595 conflict: conflict
1596 end
1597
1598 found_constant: INTEGER = 2
1599 -- Key found
1600
1601 set_found
1602 -- Set status to found.
1603 do
1604 control := found_constant
1605 ensure
1606 found: found
1607 end
1608
1609 inserted_constant: INTEGER = 4
1610 -- Insertion successful
1611
1612 set_inserted
1613 -- Set status to inserted.
1614 do
1615 control := inserted_constant
1616 ensure
1617 inserted: inserted
1618 end
1619
1620 not_found_constant: INTEGER = 8
1621 -- Key not found
1622
1623 set_not_found
1624 -- Set status to not found.
1625 do
1626 control := not_found_constant
1627 ensure
1628 not_found: not_found
1629 end
1630
1631 set_no_status
1632 -- Set status to normal.
1633 do
1634 control := 0
1635 ensure
1636 default_status: not special_status
1637 end
1638
1639 removed_constant: INTEGER = 16
1640 -- Remove successful
1641
1642 set_removed
1643 -- Set status to removed.
1644 do
1645 control := removed_constant
1646 ensure
1647 removed: removed
1648 end
1649
1650 replaced_constant: INTEGER = 32
1651 -- Replaced value
1652
1653 set_replaced
1654 -- Set status to replaced.
1655 do
1656 control := replaced_constant
1657 ensure
1658 replaced: replaced
1659 end
1660
1661 special_status: BOOLEAN
1662 -- Has status been set to some non-default value?
1663 do
1664 Result := (control > 0)
1665 ensure
1666 Result = (control > 0)
1667 end
1668
1669 add_space
1670 -- Increase capacity.
1671 do
1672 -- Be pessimistic: plan for more growth by allocating 1.5 more than before
1673 accommodate (count + count // 2)
1674 ensure
1675 count_not_changed: count = old count
1676 breathing_space: count < capacity
1677 end
1678
1679 minimum_capacity: INTEGER = 2
1680
1681 feature {NONE} -- Inapplicable
1682
1683 collection_extend (v: detachable G)
1684 -- Insert a new occurrence of `v'.
1685 do
1686 end
1687
1688 invariant
1689
1690 keys_not_void: keys /= Void
1691 content_not_void: content /= Void
1692 keys_enough_capacity: keys.count <= capacity + 1
1693 content_enough_capacity: content.count <= capacity + 1
1694 valid_iteration_position: off or truly_occupied (iteration_position)
1695 control_non_negative: control >= 0
1696 special_status: special_status =
1697 (conflict or inserted or replaced or removed or found or not_found)
1698
1699 count_big_enough: 0 <= count
1700 count_small_enough: count <= capacity
1701 slot_count_big_enough: 0 <= count
1702
1703 note
1704 copyright: "Copyright (c) 1984-2013, Eiffel Software and others"
1705 license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
1706 source: "[
1707 Eiffel Software
1708 5949 Hollister Ave., Goleta, CA 93117 USA
1709 Telephone 805-685-1006, Fax 805-685-6869
1710 Website http://www.eiffel.com
1711 Customer support http://support.eiffel.com
1712 ]"
1713
1714 end

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision

  ViewVC Help
Powered by ViewVC 1.1.23