1import core/mem
2
3--- No live entry has the requested key.
4public missing: atom
5--- The insertion-order cursor has reached the end of the map.
6public end_of_entries: atom
7
8--- Equality evidence for keys. `eq` must define a consistent equivalence
9--- relation while the keys are stored.
10public equatable: type = concept (key: type)
11 --- Compare keys under a stable equivalence relation.
12 eq: (left: key, right: key) -> (same: bool)
13end equatable
14
15--- Hash evidence composing `equatable`. Equal keys must have equal hashes;
16--- key equality and hashes must remain stable while stored. Hashes are not
17--- cryptographic.
18---
19--- A hashable conformance composes equatable, but [1340] still requires a
20--- concrete key type to declare both conformances explicitly.
21public hashable: type = concept (key: type) is equatable
22 --- Return a stable hash; keys equal under eq must hash equally.
23 hash: (value: key) -> (result: u64)
24end hashable
25
26-- The compiler does not prove the semantic laws: eq must be an equivalence
27-- relation, equal keys must hash alike, and both answers must stay stable
28-- while a key is stored, including across mutation of anything a
29-- pointer/reference key reaches.
30
31-- Keys the library supplies evidence for: the integer scalars, bool and
32-- byte slices here, and utf8 in core/text. There is one register and no
33-- override [1280]; a program wanting another equality or hash for one of
34-- these wraps the key in a distinct type and declares evidence for that.
35-- Signed hashes are the two's-complement bits widened, computed without
36-- a narrowing conversion; byte slices use 64-bit FNV-1a.
37eq_u8: (left: u8, right: u8) -> (same: bool) =
38 same = left == right
39end eq_u8
40hash_u8: (value: u8) -> (result: u64) =
41 result = u64(value)
42end hash_u8
43eq_u16: (left: u16, right: u16) -> (same: bool) =
44 same = left == right
45end eq_u16
46hash_u16: (value: u16) -> (result: u64) =
47 result = u64(value)
48end hash_u16
49eq_u32: (left: u32, right: u32) -> (same: bool) =
50 same = left == right
51end eq_u32
52hash_u32: (value: u32) -> (result: u64) =
53 result = u64(value)
54end hash_u32
55eq_u64: (left: u64, right: u64) -> (same: bool) =
56 same = left == right
57end eq_u64
58hash_u64: (value: u64) -> (result: u64) =
59 result = u64(value)
60end hash_u64
61eq_usize: (left: usize, right: usize) -> (same: bool) =
62 same = left == right
63end eq_usize
64hash_usize: (value: usize) -> (result: u64) =
65 result = u64(value)
66end hash_usize
67eq_i8: (left: i8, right: i8) -> (same: bool) =
68 same = left == right
69end eq_i8
70hash_i8: (value: i8) -> (result: u64) =
71 if value >= 0 then
72 result = u64(value)
73 else
74 result = ~u64(0 - (value + 1))
75 end if
76end hash_i8
77eq_i16: (left: i16, right: i16) -> (same: bool) =
78 same = left == right
79end eq_i16
80hash_i16: (value: i16) -> (result: u64) =
81 if value >= 0 then
82 result = u64(value)
83 else
84 result = ~u64(0 - (value + 1))
85 end if
86end hash_i16
87eq_i32: (left: i32, right: i32) -> (same: bool) =
88 same = left == right
89end eq_i32
90hash_i32: (value: i32) -> (result: u64) =
91 if value >= 0 then
92 result = u64(value)
93 else
94 result = ~u64(0 - (value + 1))
95 end if
96end hash_i32
97eq_i64: (left: i64, right: i64) -> (same: bool) =
98 same = left == right
99end eq_i64
100hash_i64: (value: i64) -> (result: u64) =
101 if value >= 0 then
102 result = u64(value)
103 else
104 result = ~u64(0 - (value + 1))
105 end if
106end hash_i64
107eq_isize: (left: isize, right: isize) -> (same: bool) =
108 same = left == right
109end eq_isize
110hash_isize: (value: isize) -> (result: u64) =
111 if value >= 0 then
112 result = u64(value)
113 else
114 result = ~u64(0 - (value + 1))
115 end if
116end hash_isize
117eq_bool: (left: bool, right: bool) -> (same: bool) =
118 same = left == right
119end eq_bool
120hash_bool: (value: bool) -> (result: u64) =
121 result = if value then 1 else 0 end if
122end hash_bool
123eq_bytes: (left: []u8, right: []u8) -> (same: bool) =
124 if lenof left <> lenof right then
125 same = false
126 return
127 end if
128 mut index: usize = 0
129 while index < lenof left do
130 if left[index] <> right[index] then
131 same = false
132 return
133 end if
134 inc index
135 end while
136 same = true
137end eq_bytes
138hash_bytes: (value: []u8) -> (result: u64) =
139 mut hash: u64 = 14695981039346656037
140 mut index: usize = 0
141 while index < lenof value do
142 hash = (hash ^ u64(value[index])) *% 1099511628211
143 inc index
144 end while
145 result = hash
146end hash_bytes
147u8 is equatable (eq: eq_u8)
148u8 is hashable (hash: hash_u8)
149u16 is equatable (eq: eq_u16)
150u16 is hashable (hash: hash_u16)
151u32 is equatable (eq: eq_u32)
152u32 is hashable (hash: hash_u32)
153u64 is equatable (eq: eq_u64)
154u64 is hashable (hash: hash_u64)
155usize is equatable (eq: eq_usize)
156usize is hashable (hash: hash_usize)
157i8 is equatable (eq: eq_i8)
158i8 is hashable (hash: hash_i8)
159i16 is equatable (eq: eq_i16)
160i16 is hashable (hash: hash_i16)
161i32 is equatable (eq: eq_i32)
162i32 is hashable (hash: hash_i32)
163i64 is equatable (eq: eq_i64)
164i64 is hashable (hash: hash_i64)
165isize is equatable (eq: eq_isize)
166isize is hashable (hash: hash_isize)
167bool is equatable (eq: eq_bool)
168bool is hashable (hash: hash_bool)
169[]u8 is equatable (eq: eq_bytes)
170[]u8 is hashable (hash: hash_bytes)
171
172slot_free: u8 = 0
173slot_used: u8 = 1
174slot_dead: u8 = 2
175
176-- Buckets are always initialized. Keys and values occupy two independent
177-- dense initialized prefixes, and each used/dead bucket names its prefix
178-- position. Used buckets also form a doubly linked walk in insertion order;
179-- the map's capacity is the end marker for every link. Reusing a tombstone
180-- replaces its dense position and appends it to that walk.
181bucket: type = struct
182 state: u8
183 dense_index: usize
184 previous_used: usize
185 next_used: usize
186end bucket
187
188--- Insertion-ordered hash map with public composition of slot metadata and
189--- dense key/value prefixes. Keep those fields consistent by using the module
190--- operations. Providers are supplied per operation.
191---
192--- This is deliberately a public composition, not an encapsulated object.
193--- Callers can pass each storage to mem's public operations, can reach the
194--- initialized K/V prefixes (including removed dense entries), and can copy
195--- inferred whole bucket values despite bucket's private identity. They must
196--- preserve equal capacities, a fully initialized bucket array, paired K/V
197--- prefixes, one valid used/dead bucket per dense position, exact
198--- count/tombstone totals, and a linked walk of exactly the used buckets
199--- when composing below the map operations.
200public map: type (key: type is hashable, item: type) = struct
201 buckets: mem.storage(bucket)
202 keys: mem.storage(key)
203 values: mem.storage(item)
204 count: usize
205 tombstones: usize
206 first_used: usize
207 last_used: usize
208end map
209
210--- Position in an insertion-order entry walk. Start with `entries`; do not
211--- mutate the map during a walk.
212---
213--- Enumeration deliberately exposes ordinary public value shapes, matching
214--- map's public-composition boundary above. A cursor is a manual
215--- live-bucket position, not an ownership or snapshot token: it has no map
216--- identity or generation check and is not transferable between maps. Any mutation,
217--- including insert, remove, rehash, clear and release, invalidates an active
218--- walk; callers must discard its cursor and restart.
219public cursor: type = struct
220 next_slot: usize
221end cursor
222
223--- A copied key/value pair returned by `next_entry`. References inside either
224--- value still depend on their original backing.
225public entry: type (key: type, item: type) = struct
226 key: key
227 item: item
228end entry
229
230empty_storage: (value: type) -> (result: mem.storage(value)) =
231 result = mem.empty_storage(item: value)
232end empty_storage
233
234--- Create an empty map without allocating backing.
235public new: (key: type is hashable, item: type)
236 -> (result: map(key, item)) =
237 empty_buckets := empty_storage(value: bucket)
238 empty_keys := empty_storage(value: key)
239 empty_values := empty_storage(value: item)
240 result = (buckets: empty_buckets, keys: empty_keys,
241 values: empty_values, count: 0, tombstones: 0,
242 first_used: 0, last_used: 0)
243end new
244
245--- Return the number of live key/value entries.
246public length: (key: type is hashable, item: type,
247 value: map(key, item)) -> (count: usize) =
248 count = value.count
249end length
250
251--- Return the current hash-slot capacity. Hash-slot occupancy can require
252--- rebuilding before every slot is used.
253public capacity: (key: type is hashable, item: type,
254 value: map(key, item)) -> (count: usize) =
255 count = mem.capacity(value.buckets)
256end capacity
257
258--- Create a cursor positioned before the first entry. The walk follows
259--- current insertion order.
260public entries: () -> (position: cursor) =
261 -- This marker means "start at the map's head" on the first call. It is
262 -- distinct from every possible bucket capacity and from the exhausted
263 -- marker, which is the capacity of the map being walked.
264 position = (next_slot: 0 -% 1)
265end entries
266
267--- Copy the next live key/value pair and advance the cursor. Reports
268--- `end_of_entries` at the end; keep the map unchanged during the walk.
269---
270--- Each call follows one live link. Across an unmodified walk, every live
271--- entry is returned once in insertion order and the walk costs O(count),
272--- including the exhausted call. The result retains `from value` because K
273--- or V may hold references into the map's initialized storage.
274public next_entry: (key: type is hashable, item: type,
275 value: map(key, item), inout position: cursor)
276 -> (result: entry(key, item) from value) ! end_of_entries =
277 slots: usize = capacity(value)
278 if position.next_slot == 0 -% 1 then
279 position.next_slot = value.first_used
280 end if
281 fail end_of_entries when position.next_slot >= slots
282 record: bucket = (mem.get(value.buckets, position.next_slot)
283 else (problem)
284 _ = problem
285 fail end_of_entries
286 end)
287 fail end_of_entries when record.state <> slot_used
288 position.next_slot = record.next_used
289 found_key: key = (mem.get(value.keys, record.dense_index)
290 else (problem)
291 _ = problem
292 fail end_of_entries
293 end)
294 found_item: item = (mem.get(value.values, record.dense_index)
295 else (problem)
296 _ = problem
297 fail end_of_entries
298 end)
299 result = (key: found_key, item: found_item)
300end next_entry
301
302byte_extent: (value: type, slots: usize)
303 -> (extent: usize) ! mem.out_of_memory =
304 size: usize = sizeof value
305 if size == 0 then
306 extent = 0
307 return
308 end if
309 maximum: usize = 0 -% 1
310 fail mem.out_of_memory when slots > maximum / size
311 extent = slots * size
312end byte_extent
313
314drain: (value: type, inout storage: mem.storage(value)) -> none =
315 while mem.initialized(storage) > 0 do
316 discarded: value = mem.withdraw(storage) else (problem)
317 _ = problem
318 return
319 end
320 end while
321end drain
322
323free_empty: (value: type, provider: type is mem.allocator,
324 inout storage: mem.storage(value),
325 inout state: provider) -> none =
326 slots: usize = mem.capacity(storage)
327 return when slots == 0
328 extent: usize = slots * sizeof value
329 block: ptr mut u8 = mem.dispose(storage) else (problem)
330 _ = problem
331 return
332 end
333 provider.free(state, block, extent)
334end free_empty
335
336discard_storage: (value: type, provider: type is mem.allocator,
337 inout storage: mem.storage(value),
338 inout state: provider) -> none =
339 drain(storage)
340 free_empty(storage, state)
341end discard_storage
342
343replace_value: (value: type, inout storage: mem.storage(value),
344 index: usize, escaping replacement: value) -> (ok: bool) =
345 mem.replace(storage, index, replacement) else (problem)
346 _ = problem
347 ok = false
348 return
349 end
350 ok = true
351end replace_value
352
353index_of: (key: type is hashable, value: key, slots: usize)
354 -> (index: usize) =
355 -- Every library-created nonempty capacity is a power of two. Mask in
356 -- u64 before narrowing, so the same full-width reduction applies on a
357 -- 32-bit target. Publicly composed maps may have other capacities.
358 hash: u64 = key.hash(value)
359 if (slots & (slots - 1)) == 0 then
360 index = usize(hash & u64(slots - 1))
361 else
362 index = usize(hash % u64(slots))
363 end if
364end index_of
365
366next_index: (index: usize, slots: usize) -> (next: usize) =
367 if index == slots - 1 then
368 next = 0
369 else
370 next = index + 1
371 end if
372end next_index
373
374-- This is equivalent to `(count + tombstones + 1) * 4 > slots * 3`
375-- without overflowing either addition or multiplication. Corrupt counters
376-- conservatively report pressure rather than wrapping to "not crowded".
377-- Insert consults this only when no tombstones remain.
378crowded: (key: type is hashable, item: type,
379 value: map(key, item)) -> (yes: bool) =
380 slots: usize = capacity(value)
381 if slots == 0 then
382 yes = true
383 return
384 end if
385 if value.count > slots or value.tombstones > slots - value.count then
386 yes = true
387 return
388 end if
389 occupied: usize = value.count + value.tombstones
390 yes = occupied >= crowding_threshold(slots)
391end crowded
392
393-- Three quarters of the slots, computed without overflow.
394crowding_threshold: (slots: usize) -> (threshold: usize) =
395 quarter: usize = slots / 4
396 remainder: usize = slots % 4
397 threshold = quarter * 3 + (remainder * 3) / 4
398end crowding_threshold
399
400install_at: (key: type is hashable, item: type,
401 inout value: map(key, item), at: usize, was_dead: bool,
402 escaping added_key: key, escaping added_value: item)
403 -> (placed: bool) =
404 slots: usize = capacity(value)
405 mut dense: usize = 0
406 if was_dead then
407 record: bucket = (mem.get(value.buckets, at) else (problem)
408 _ = problem
409 placed = false
410 return
411 end)
412 dense = record.dense_index
413 if not replace_value(value.keys, dense, added_key) then
414 placed = false
415 return
416 end if
417 if not replace_value(value.values, dense, added_value) then
418 placed = false
419 return
420 end if
421 else
422 dense = (mem.admit(value.keys, added_key) else (problem)
423 _ = problem
424 placed = false
425 return
426 end)
427 value_dense: usize = (mem.admit(value.values, added_value)
428 else (problem)
429 _ = problem
430 discarded: key = (mem.withdraw(value.keys) else (release_problem)
431 _ = release_problem
432 placed = false
433 return
434 end)
435 placed = false
436 return
437 end)
438 if value_dense <> dense then
439 placed = false
440 return
441 end if
442 end if
443
444 replacement_bucket: bucket =
445 (state: slot_used, dense_index: dense,
446 previous_used: value.last_used, next_used: slots)
447 if not replace_value(value.buckets, at, replacement_bucket) then
448 placed = false
449 return
450 end if
451 if value.last_used < slots then
452 mut tail: bucket = (mem.get(value.buckets, value.last_used)
453 else (problem)
454 _ = problem
455 placed = false
456 return
457 end)
458 tail.next_used = at
459 if not replace_value(value.buckets, value.last_used, tail) then
460 placed = false
461 return
462 end if
463 else
464 value.first_used = at
465 end if
466 value.last_used = at
467 inc value.count
468 if was_dead then
469 dec value.tombstones
470 end if
471 placed = true
472end install_at
473
474-- Keep the absent key's placement position so insertion without a rebuild
475-- does not probe the same chain again. A dead bucket is usable only after
476-- checking the rest of the chain for an equal used key.
477insert_search: type = struct
478 updated: bool
479 slot_index: usize
480 was_dead: bool
481end insert_search
482
483search_for_insert: (key: type is hashable, item: type,
484 inout value: map(key, item), wanted: key,
485 escaping replacement: item)
486 -> (result: insert_search) ! mem.out_of_memory =
487 slots: usize = capacity(value)
488 if slots == 0 then
489 result = (updated: false, slot_index: slots, was_dead: false)
490 return
491 end if
492
493 mut at: usize = index_of(wanted, slots)
494 mut first_dead: usize = slots
495 mut probed: usize = 0
496 while probed < slots do
497 record: bucket = (mem.get(value.buckets, at) else (problem)
498 _ = problem
499 fail mem.out_of_memory
500 end)
501 if record.state == slot_free then
502 if first_dead < slots then
503 result = (updated: false, slot_index: first_dead,
504 was_dead: true)
505 else
506 result = (updated: false, slot_index: at, was_dead: false)
507 end if
508 return
509 end if
510 if record.state == slot_dead then
511 if first_dead == slots then
512 first_dead = at
513 end if
514 elsif record.state == slot_used then
515 existing: key = (mem.get(value.keys, record.dense_index)
516 else (problem)
517 _ = problem
518 fail mem.out_of_memory
519 end)
520 if key.eq(existing, wanted) then
521 if not replace_value(value.values, record.dense_index,
522 replacement)
523 then
524 fail mem.out_of_memory
525 end if
526 result = (updated: true, slot_index: at, was_dead: false)
527 return
528 end if
529 end if
530 at = next_index(at, slots)
531 inc probed
532 end while
533 result = (updated: false, slot_index: first_dead,
534 was_dead: first_dead < slots)
535end search_for_insert
536
537-- The caller has already proved this key absent. Probes are still bounded
538-- if no free bucket exists, and the first tombstone wins only after the
539-- search has reached a free bucket or exhausted the table.
540place_absent: (key: type is hashable, item: type,
541 inout value: map(key, item),
542 escaping added_key: key, escaping added_value: item)
543 -> (placed: bool) =
544 slots: usize = capacity(value)
545 if slots == 0 then
546 placed = false
547 return
548 end if
549
550 mut at: usize = index_of(added_key, slots)
551 mut first_dead: usize = slots
552 mut probed: usize = 0
553 while probed < slots do
554 record: bucket = (mem.get(value.buckets, at) else (problem)
555 _ = problem
556 placed = false
557 return
558 end)
559 if record.state == slot_dead then
560 if first_dead == slots then
561 first_dead = at
562 end if
563 elsif record.state == slot_free then
564 if first_dead < slots then
565 placed = install_at(value, first_dead, true,
566 added_key, added_value)
567 else
568 placed = install_at(value, at, false,
569 added_key, added_value)
570 end if
571 return
572 end if
573 at = next_index(at, slots)
574 inc probed
575 end while
576
577 if first_dead < slots then
578 placed = install_at(value, first_dead, true, added_key, added_value)
579 else
580 placed = false
581 end if
582end place_absent
583
584rehash: (key: type is hashable, item: type,
585 provider: type is mem.allocator,
586 inout value: map(key, item), inout state: provider, want: usize)
587 -> none ! mem.out_of_memory =
588 fail mem.out_of_memory when want == 0 or want < value.count
589
590 -- Preflight every byte product before the first provider effect.
591 bucket_extent: usize = try byte_extent(value: bucket, slots: want)
592 key_extent: usize = try byte_extent(value: key, slots: want)
593 value_extent: usize = try byte_extent(value: item, slots: want)
594
595 bucket_block: ptr mut u8 = try provider.alloc
596 (state, bucket_extent, alignof bucket)
597 mut new_buckets := mem.reserve
598 (item: bucket, base: bucket_block, slots: want)
599 undo discard_storage(new_buckets, state)
600
601 mut initialized: usize = 0
602 while initialized < want do
603 empty_bucket: bucket =
604 (state: slot_free, dense_index: 0,
605 previous_used: want, next_used: want)
606 admitted: usize = mem.admit
607 (new_buckets, empty_bucket)
608 else (problem)
609 _ = problem
610 fail mem.out_of_memory
611 end
612 _ = admitted
613 inc initialized
614 end while
615
616 key_block: ptr mut u8 = try provider.alloc
617 (state, key_extent, alignof key)
618 mut new_keys := mem.reserve(item: key, base: key_block, slots: want)
619 undo discard_storage(new_keys, state)
620
621 value_block: ptr mut u8 = try provider.alloc
622 (state, value_extent, alignof item)
623 mut new_values := mem.reserve(item: item, base: value_block, slots: want)
624 undo discard_storage(new_values, state)
625
626 old_slots: usize = capacity(value)
627 mut old_at: usize = value.first_used
628 mut migrated: usize = 0
629 mut new_first: usize = want
630 mut new_last: usize = want
631 while migrated < value.count do
632 fail mem.out_of_memory when old_at >= old_slots
633 old_bucket: bucket = (mem.get(value.buckets, old_at) else (problem)
634 _ = problem
635 fail mem.out_of_memory
636 end)
637 fail mem.out_of_memory when old_bucket.state <> slot_used
638 old_key: key = (mem.get(value.keys, old_bucket.dense_index)
639 else (problem)
640 _ = problem
641 fail mem.out_of_memory
642 end)
643 mut target: usize = index_of(old_key, want)
644 mut searched: usize = 0
645 while searched < want do
646 target_bucket: bucket = (mem.get(new_buckets, target)
647 else (problem)
648 _ = problem
649 fail mem.out_of_memory
650 end)
651 break when target_bucket.state == slot_free
652 target = next_index(target, want)
653 inc searched
654 end while
655 fail mem.out_of_memory when searched == want
656
657 key_dense: usize = (mem.transfer
658 (value.keys, old_bucket.dense_index, new_keys)
659 else (problem)
660 _ = problem
661 fail mem.out_of_memory
662 end)
663 value_dense: usize = (mem.transfer
664 (value.values, old_bucket.dense_index, new_values)
665 else (problem)
666 _ = problem
667 fail mem.out_of_memory
668 end)
669 fail mem.out_of_memory when key_dense <> value_dense
670 moved_bucket: bucket =
671 (state: slot_used, dense_index: key_dense,
672 previous_used: new_last, next_used: want)
673 if not replace_value(new_buckets, target, moved_bucket) then
674 fail mem.out_of_memory
675 end if
676 if new_last < want then
677 mut tail: bucket = (mem.get(new_buckets, new_last)
678 else (problem)
679 _ = problem
680 fail mem.out_of_memory
681 end)
682 tail.next_used = target
683 if not replace_value(new_buckets, new_last, tail) then
684 fail mem.out_of_memory
685 end if
686 else
687 new_first = target
688 end if
689 new_last = target
690 old_at = old_bucket.next_used
691 inc migrated
692 end while
693 fail mem.out_of_memory when old_at <> old_slots
694
695 -- Migration has succeeded. Everything below is infallible: retire all
696 -- three old extents exactly once and publish the replacement last.
697 discard_storage(value.values, state)
698 discard_storage(value.keys, state)
699 discard_storage(value.buckets, state)
700 value.buckets = new_buckets
701 value.keys = new_keys
702 value.values = new_values
703 value.count = migrated
704 value.tombstones = 0
705 value.first_used = new_first
706 value.last_used = new_last
707end rehash
708
709--- Insert a new key/value pair or replace the value of an equal key. New keys
710--- append in insertion order; replacement keeps its position. Allocation
711--- failure preserves the previous map. Growth can invalidate views.
712public insert: (key: type is hashable, item: type,
713 provider: type is mem.allocator,
714 inout value: map(key, item), inout state: provider,
715 escaping added_key: key, escaping added_value: item)
716 -> none ! mem.out_of_memory =
717 position: insert_search = try search_for_insert
718 (value, added_key, added_value)
719 return when position.updated
720
721 -- A dead bucket can be reused without extending either dense prefix.
722 -- Even at full physical occupancy, the bounded placement probe finds
723 -- one. Rebuilding on tombstone pressure would allocate three extents
724 -- for every steady-size remove/insert cycle on an arena.
725 if value.tombstones == 0 and crowded(value) then
726 old_capacity: usize = capacity(value)
727 mut want: usize = 8
728 if old_capacity > 0 then
729 maximum: usize = 0 -% 1
730 fail mem.out_of_memory when old_capacity > maximum / 2
731 want = old_capacity * 2
732 end if
733 try rehash(value, state, want)
734 inserted: bool = place_absent(value, added_key, added_value)
735 fail mem.out_of_memory when not inserted
736 return
737 end if
738 fail mem.out_of_memory when position.slot_index == capacity(value)
739 inserted: bool = install_at(value, position.slot_index, position.was_dead,
740 added_key, added_value)
741 fail mem.out_of_memory when not inserted
742end insert
743
744-- Where a present key lives: its bucket and its dense position.
745location: type = struct
746 slot: usize
747 dense: usize
748end location
749
750locate: (key: type is hashable, item: type,
751 value: map(key, item), wanted: key)
752 -> (found: location) ! missing =
753 fail missing when value.count == 0
754 slots: usize = capacity(value)
755 fail missing when slots == 0
756 mut slot: usize = index_of(wanted, slots)
757 mut probed: usize = 0
758 while probed < slots do
759 record: bucket = (mem.get(value.buckets, slot) else (problem)
760 _ = problem
761 fail missing
762 end)
763 fail missing when record.state == slot_free
764 if record.state == slot_used then
765 existing: key = (mem.get(value.keys, record.dense_index)
766 else (problem)
767 _ = problem
768 fail missing
769 end)
770 if key.eq(existing, wanted) then
771 found = (slot: slot, dense: record.dense_index)
772 return
773 end if
774 end if
775 slot = next_index(slot, slots)
776 inc probed
777 end while
778 fail missing
779end locate
780
781--- Copy the value associated with a key. Reports `missing` if absent;
782--- references inside the copy retain their origin.
783public get: (key: type is hashable, item: type,
784 value: map(key, item), wanted: key)
785 -> (result: item from value) ! missing =
786 found: location = try locate(value, wanted)
787 result = mem.get(value.values, found.dense) else (problem)
788 _ = problem
789 fail missing
790 end
791end get
792
793--- Lend a writable pointer to an existing value. Reports `missing` if absent.
794--- End the pointer before mutating the map's structure or releasing backing.
795---
796--- A writable slot for the present key's item, for in-place update. While
797--- the result lives the map binding may not be passed inout or sink
798--- [0800]; let it end before the next insert, remove or release.
799public at: (key: type is hashable, item: type,
800 inout value: map(key, item), wanted: key)
801 -> (slot: ptr mut item from value) ! missing =
802 found: location = try locate(value, wanted)
803 view: []mut item = mem.used(value.values)
804 fail missing when found.dense >= lenof view
805 slot = addr view[found.dense]
806end at
807
808--- Return whether a live entry has the requested key, without allocating.
809public contains: (key: type is hashable, item: type,
810 value: map(key, item), wanted: key) -> (yes: bool) =
811 _ = locate(value, wanted) else (problem)
812 _ = problem
813 yes = false
814 return
815 end
816 yes = true
817end contains
818
819--- Remove a key/value entry without returning it. Reports `missing` if
820--- absent; preserves the relative order of remaining entries. End existing
821--- value pointers and cursors before mutation.
822public remove: (key: type is hashable, item: type,
823 inout value: map(key, item), wanted: key)
824 -> none ! missing =
825 fail missing when value.count == 0
826 slots: usize = capacity(value)
827 fail missing when slots == 0
828 mut at: usize = index_of(wanted, slots)
829 mut probed: usize = 0
830 while probed < slots do
831 record: bucket = (mem.get(value.buckets, at) else (problem)
832 _ = problem
833 fail missing
834 end)
835 fail missing when record.state == slot_free
836 if record.state == slot_used then
837 existing: key = (mem.get(value.keys, record.dense_index)
838 else (problem)
839 _ = problem
840 fail missing
841 end)
842 if key.eq(existing, wanted) then
843 if record.previous_used < slots then
844 mut previous: bucket =
845 (mem.get(value.buckets, record.previous_used)
846 else (problem)
847 _ = problem
848 fail missing
849 end)
850 previous.next_used = record.next_used
851 if not replace_value(value.buckets,
852 record.previous_used, previous)
853 then
854 fail missing
855 end if
856 else
857 value.first_used = record.next_used
858 end if
859 if record.next_used < slots then
860 mut next: bucket =
861 (mem.get(value.buckets, record.next_used)
862 else (problem)
863 _ = problem
864 fail missing
865 end)
866 next.previous_used = record.previous_used
867 if not replace_value(value.buckets, record.next_used,
868 next)
869 then
870 fail missing
871 end if
872 else
873 value.last_used = record.previous_used
874 end if
875 dead_bucket: bucket =
876 (state: slot_dead, dense_index: record.dense_index,
877 previous_used: slots, next_used: slots)
878 if not replace_value(value.buckets, at, dead_bucket) then
879 fail missing
880 end if
881 dec value.count
882 inc value.tombstones
883 return
884 end if
885 end if
886 at = next_index(at, slots)
887 inc probed
888 end while
889 fail missing
890end remove
891
892--- Discard all entries, free the map's backing through its original provider
893--- and reset it. Nested resources referred to by keys or values are not freed
894--- automatically.
895public release: (key: type is hashable, item: type,
896 provider: type is mem.allocator,
897 inout value: map(key, item),
898 inout state: provider) -> none =
899 discard_storage(value.values, state)
900 discard_storage(value.keys, state)
901 discard_storage(value.buckets, state)
902 value = new(key: key, item: item)
903end release
904
905--- Discard all entries and tombstones while retaining allocations. End
906--- existing pointers and walks first; referenced resources remain the
907--- caller's responsibility.
908---
909--- Forget every entry but keep the bucket capacity. Every bucket is
910--- rewritten free and both dense prefixes are emptied; values in them are
911--- discarded, and resources they refer to remain the caller's.
912public clear: (key: type is hashable, item: type,
913 inout value: map(key, item)) -> none =
914 slots: usize = capacity(value)
915 mut slot: usize = 0
916 while slot < slots do
917 free_bucket: bucket = (state: slot_free, dense_index: 0,
918 previous_used: slots, next_used: slots)
919 return when not replace_value(value.buckets, slot, free_bucket)
920 inc slot
921 end while
922 mem.clear(value.keys)
923 mem.clear(value.values)
924 value.count = 0
925 value.tombstones = 0
926 value.first_used = slots
927 value.last_used = slots
928end clear
929
930--- Ensure capacity for at least `want` entries without adding any. Allocates
931--- replacement key, value and hash-slot storage before committing it. Any
932--- allocation failure frees the partial replacement and preserves all
933--- original entries and capacities. Success can invalidate pointers and
934--- cursors.
935---
936--- Room for `want` entries without a growth allocation: the capacity is
937--- doubled from eight until `want` sits below the crowding threshold, and
938--- the map is rebuilt once at that size. A map already that large is left
939--- alone, including its tombstones.
940public reserve: (key: type is hashable, item: type,
941 provider: type is mem.allocator,
942 inout value: map(key, item), inout state: provider,
943 want: usize) -> none ! mem.out_of_memory =
944 return when want == 0
945 maximum: usize = 0 -% 1
946 mut slots: usize = 8
947 while want >= crowding_threshold(slots) do
948 fail mem.out_of_memory when slots > maximum / 2
949 slots = slots * 2
950 end while
951 return when slots <= capacity(value)
952 try rehash(value, state, slots)
953end reserve