Commit Graph
8 Commits
Author SHA1 Message Date
Franz Busch 3c373b900c Use the defines from traits directly
Package traits already pass defines with their trait name when building. Instead of adding our own conditional defines based on the traits we can use the trait provided defines directly. I observed that various tooling behaves better with the trait provided defines.
2026-05-06 07:41:02 -07:00
Karoy Lorentey fda65e149b [BasicContainers] Hashed containers: Make _checkInvariants() dump the hash table on failure 2026-03-11 00:31:37 -07:00
Karoy Lorentey 634a0ae766 [BasicContainers] Implement _checkInvariants on hashed containers 2026-03-10 23:04:49 -07:00
Karoy Lorentey 1c69635852 Add SPDX-License-Identifier tags 2026-03-05 19:39:24 -08:00
Karoy Lorentey ffdc48e67e [BasicContainers] Finalize requirements for hashed containers
- UnstableNoncopyableKeys → UnstableHashedContainers
- Delete the GeneralizedEquatable and GeneralizedHashable protocols, replacing them with the standard generalizations in the 6.4 stdlib
- Require Swift 6.4 for {Rigid,Unique}{Set,Dictionary}.
2026-03-03 16:01:45 -08:00
Karoy Lorentey 3941dab5b0 [BasicContainers] Implement removals on RigidSet and UniqueSet
Dictionaries are still to be done.
2026-02-20 18:19:51 -08:00
Karoy Lorentey 0cf34cc3a9 [BasicContainers] Improved debug output for hashed containers
- Allow bitmap visualization to be included/omitted as needed
- Visualize chain length distribution for both successful and unsuccessful lookups

Check out this sample test output for Robin Hood hashing:

```
⌗ large@11 1536/1792/2048, maxProbeLength: 11, totalProbeLength: 3712, maxOccupiedRun: 68
  ├╴[00000000] □□■■■■□□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□■■■■■■∙□□□■□■□□∙□□□■■□■■∙■■■■■■■■
  ├╴[00000064] □□■□□■■■∙■■■■□■□□∙□■■■■■■■∙■■■■■■■■∙■■□□□□■□∙■□■□■■■■∙■■■■■■□□∙■■■■■■■■
  ├╴[00000128] ■■■■■■■■∙■■■□□□■□∙■■□■□■■□∙□■■■■■□■∙■■■■■■■■∙□■■■■■■■∙■■■■□■□■∙■□■□□■□□
  ├╴[00000192] ■□■■□■■■∙■■■■□■□■∙□□□□□■■□∙■■■■■■■■∙■■■□■■□■∙□■□■■□□■∙■■■■■■■■∙■■■■■■■■
  ├╴[00000256] ■■■■■■□□∙■■■■■■■□∙□■■■■■■□∙□■■■■■■□∙□□■■□□■□∙□□□■■■■□∙□■■■■□■■∙■■■■■■■■
  ├╴[00000320] ■■■■■■■■∙□■■■■■■■∙■■■■■■■□∙□■■□□■□□∙□□□■■□□■∙■■■■■□■□∙■□■■■■■□∙■■■■■■■■
  ├╴[00000384] ■■■■■■■■∙■■■■■□□■∙□□■■■■□□∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙□■■□□■□■∙□□■■□■■■
  ├╴[00000448] ■■■■□■■■∙■■■□■■■□∙□□□■□■■■∙■■■□□■■■∙■■■□□□□□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■
  ├╴[00000512] ■■■■■□□□∙□□■■□■■■∙■■■□■■■■∙■■■■■■■■∙■■■■■■■□∙□■■■■□□■∙■■■■■■■■∙■■■■■■■■
  ├╴[00000576] □□□■■■□■∙■■■□■■■■∙■■■■■■■■∙■■■■■■■■∙■■□■■■■■∙■■■■■■■■∙■■□□■□□□∙■■■□□□■□
  ├╴[00000640] □■■□□■■□∙□□□□■■■■∙□■■□■■■□∙□■■□■■■■∙■■■■■■■■∙■□□■■■■■∙■■■■■□□□∙■■■■■■■□
  ├╴[00000704] ■■■■■■■□∙■■■■□□□■∙■■□■□■■■∙■■■■■■■■∙■■■■□■■■∙□□□■□■■■∙□□□■□□□□∙□□□■□■■■
  ├╴[00000768] □■■■■■□■∙□■■□□□■■∙■■■■■■■□∙■■■■■■■■∙■■■■■■■□∙□■■■□■■□∙■□■■□■■■∙■■■■□■□■
  ├╴[00000832] ■□□■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■□□∙□□■■■■■■∙□□■■■■■■∙■■■■■■■■∙□■□■■■■■
  ├╴[00000896] ■■■■■■■■∙■■■■■□□■∙■■■□□□□■∙■■□□■■■■∙■□□■■■■□∙■■■□□■■□∙□□■■□■■■∙□■□□■■■■
  ├╴[00000960] ■■■■■□■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■□∙□■□■■■■■∙■■■■□□■■
  ├╴[00001024] ■■■■■■□□∙■■■■□■■□∙■■■■■■■□∙□□□■■■□□∙■■■□■■□■∙■□■■□□□■∙■■■■■■■■∙□□□□□□□□
  ├╴[00001088] ■■□□□□■□∙■■□□□□□■∙■□□■■■■■∙■■■□□□□■∙■■■■■■■■∙■■■■■■■■∙■■■■□□□□∙■■□■□■■■
  ├╴[00001152] ■■■□□■■□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□■■□■■■∙■□■■□■■□∙□■■■■□■■
  ├╴[00001216] ■■■■■■■■∙■■□■□■■■∙■■■■■■■■∙□□■■□□□■∙□□□□□□□□∙□□■■■■■■∙■■■■■■■■∙■■■□□■■■
  ├╴[00001280] ■■■■■■■□∙■■□■■■■■∙■■■■■■□□∙■□□■■■■■∙■■■■■■■■∙■□□■□■□■∙■■■■■■■■∙■■■■■■■■
  ├╴[00001344] ■■■■■■■■∙■□■□■■□□∙■■■■□■□□∙□■■□■□□■∙□■□■■■■■∙■■■□■■■□∙□□■■■■■■∙■■■■■■■■
  ├╴[00001408] ■■■■■■■■∙■■■■■■■■∙■■■■■□□■∙■■■□■■■■∙■■□■■■■■∙■■■□■■■■∙■■□□■□□□∙■□■■■■■■
  ├╴[00001472] ■■■■■□■□∙■■□□□□□■∙□□□□□■■□∙■□□■■□■□∙■■■■■■■■∙■■■■■■■■∙□□□□■■■■∙■□■□□■■■
  ├╴[00001536] ■■■■■■■■∙□□□■■□■□∙□■■□■■□□∙□■□■■□□□∙■■■■■□□■∙■□■■■■■■∙■■■■■■■■∙■□□■□□□□
  ├╴[00001600] ■■■■■■■■∙■■■■□□■□∙□□■■□■■■∙■■■■■■■□∙□■□□■■□■∙■□■■■□■■∙■■■■■■■■∙□□■■■■■■
  ├╴[00001664] ■■■■■■■■∙□■■■□□■■∙■■■□■□■□∙■■■■■■□■∙■■■□■■■■∙■■■■■■■□∙□□□□■■■■∙■■■■□■■■
  ├╴[00001728] ■■■■■■■■∙■□□■■■■■∙■■□□■■□□∙■■■■■■■■∙■■■□□□■■∙□□■■■■■■∙■■■■■■■■∙■■■■■■■■
  ├╴[00001792] ■■■■■■■■∙■■■■■■■■∙■□□□■■□■∙□□■■□□□□∙□■■□■□□■∙□□■■■■□□∙■■■■■■■■∙■■■■■■■■
  ├╴[00001856] ■■■■■■■□∙■■■■■■■□∙□■□■□■■□∙■□□□■■■■∙■□■■□■■□∙□□■□■□■■∙■□□□□■■■∙■■■■■■■■
  ├╴[00001920] ■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□□■□■□□
  └╴[00001984] ■□□■□□■■∙□■■■■■■□∙□□□□■■■■∙■□□□■■■■∙■■■■■■■■∙■■□■□■■■∙■■■□■■□□∙■□□■■□■□
Chain length distribution (for successful lookups):
   AVG: 2.416
     1: **************************************************************************** 549
     2: ******************************************************** 408
     3: ************************************* 264
     4: ******************** 142
     5: ************** 96
     6: ******* 51
     7: *** 17
     8: * 4
     9: * 1
    10: * 3
    11: * 1
Chain length distribution (for unsuccessful lookups):
   AVG: 4.428
     0: **************************************************************************** 511
     1: **************************************** 269
     2: ***************************** 191
     3: ******************* 129
     4: ***************** 111
     5: ************** 94
     6: ************* 85
     7: *********** 70
     8: ********* 60
     9: ********* 55
    10: ******** 50
    11: ************************************************************** 422
```
2026-02-19 12:10:26 -08:00
Karoy Lorentey 099aa3b312 [BasicContainers] Add UniqueSet 2026-02-18 22:05:22 -08:00