-
Notifications
You must be signed in to change notification settings - Fork 16
/
Copy pathDictionary.swift
107 lines (95 loc) · 5.74 KB
/
Dictionary.swift
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
//
// Dictionary.swift
// SwiftPointerDemo
//
// Created by jintao on 2019/7/31.
// Copyright © 2019 jintao. All rights reserved.
//
import Foundation
public extension Dictionary {
// struct Dictionary<K,V>
// +------------------------------------------------+
// | enum Dictionary<K,V>._Variant |
// | +--------------------------------------------+ |
// | | [struct _NativeDictionary<K,V> | |
// | +---|----------------------------------------+ |
// +----/-------------------------------------------+
// /
// |
// V
// class __RawDictionaryStorage
// +-----------------------------------------------------------------------+
// | var isa: UnsafeMutableRawPointer |
// | var refcount: Int |
// | var _count: Int // 16 byte offset |
// | var _capacity: Int |
// | var _scale: Int8 |
// | var _reservedScale: Int8 |
// | var _extra: Int16 |
// | var _age: Int32 |
// | var _seed: Int |
// | var _rawKeys: UnsafeMutableRawPointer // 48 byte offset -----------------------+
// | var _rawValues: UnsafeMutableRawPointer // 56 byte offset -----------------------+---------------+
// | var _bucketCount: Int | | |
// | var _metadata(get): UnsafeMutablePointer<_HashTable.Word> -----------------+ | |
// | var _hashTable(get): _HashTable | | | |
// +-----------------------------------------------------------------------+ | | |
// | | |
// | | |
// | | |
/* Dictionary | | |
| | | |
V | | |
+-------------------------------------+ | | |
| RawDictionaryStorage (MetaData) | | | |
| | | | |
+-------------------------------------+ <----------------------------------------------+ | |
| Word (Hash Offset) | | |
| | | |
+-------------------------------------+ <----------------------------------------------------+ |
| Keys | |
| | |
+-------------------------------------+ <--------------------------------------------------------------------+
| Values |
| |
+-------------------------------------+
Word (Hash Offset)
|
V 64(32) bits
/ \
if Word[0] = 0b1000000...0000000000100 => Keys[2] != nil and Keys[63] != nil
if Word[1] = 0b1000000...0000000000101 => Keys[64] != nil and Keys[66] != nil and ...
set: var bitOffset = hash(NewKey) & bucketCount
when bitOffset of Word is occupied(bit is 1) {
bitOffset += 1
}
set the bit of Word with bitOffset to 1
Keys[bitOffset] = NewKey
Values[bitOffset] = NewValue
get: var bitOffset = hash(Key) & bucketCount
when Keys[bitOffset] != Key {
bitOffset += 1
}
return Values[bitOffset]
*/
// count value of address
var countPointer: UnsafeMutablePointer<Int> {
get {
return unsafeBitCast(self, to: UnsafeMutableRawPointer.self).advanced(by: 16).assumingMemoryBound(to: Int.self)
}
}
// array of keys address
var keysPointer: UnsafeMutablePointer<Key> {
get {
let keysAddrValue = unsafeBitCast(self, to: UnsafeMutableRawPointer.self).advanced(by: 48).assumingMemoryBound(to: Int.self).pointee
return UnsafeMutableRawPointer(bitPattern: keysAddrValue)!.assumingMemoryBound(to: Key.self)
}
}
// array of values address
var valuesPointer: UnsafeMutablePointer<Value> {
get {
let valuesAddrValue = unsafeBitCast(self, to: UnsafeMutableRawPointer.self).advanced(by: 56).assumingMemoryBound(to: Int.self).pointee
return UnsafeMutableRawPointer(bitPattern: valuesAddrValue)!.assumingMemoryBound(to: Value.self)
}
}
}