SameBoy | Accurate GB/GBC emulator |
| download: https://git.y1.nz/archives/sameboy.tar.gz | |
| README | Files | Log | Refs | LICENSE |
HexFiend/HFBTreeByteArray.m
1 //
2 // HFBTreeByteArray.m
3 // HexFiend_2
4 //
5 // Created by peter on 4/28/09.
6 // Copyright 2009 ridiculous_fish. All rights reserved.
7 //
8
9 #import <HexFiend/HFByteArray_Internal.h>
10 #import <HexFiend/HFByteSlice.h>
11 #import <HexFiend/HFBTreeByteArray.h>
12 #import <HexFiend/HFBTree.h>
13
14 @implementation HFBTreeByteArray
15
16 - (instancetype)init {
17 if ((self = [super init])) {
18 btree = [[HFBTree alloc] init];
19 }
20 return self;
21 }
22
23 - (void)dealloc {
24 [btree release];
25 [super dealloc];
26 }
27
28 - (unsigned long long)length {
29 return [btree length];
30 }
31
32 - (NSArray *)byteSlices {
33 return [btree allEntries];
34 }
35
36 - (NSEnumerator *)byteSliceEnumerator {
37 return [btree entryEnumerator];
38 }
39
40 - (NSString*)description {
41 NSMutableArray* result = [NSMutableArray array];
42 NSEnumerator *enumer = [self byteSliceEnumerator];
43 HFByteSlice *slice;
44 unsigned long long offset = 0;
45 while ((slice = [enumer nextObject])) {
46 unsigned long long length = [slice length];
47 [result addObject:[NSString stringWithFormat:@"{%llu - %llu}", offset, length]];
48 offset = HFSum(offset, length);
49 }
50 if (! [result count]) return @"(empty tree)";
51 return [NSString stringWithFormat:@"<%@: %p>: %@", [self class], self, [result componentsJoinedByString:@" "]];
52
53 }
54
55 struct HFBTreeByteArrayCopyInfo_t {
56 unsigned char *dst;
57 unsigned long long startingOffset;
58 NSUInteger remainingLength;
59 };
60
61 static BOOL copy_bytes(id entry, HFBTreeIndex offset, void *userInfo) {
62 struct HFBTreeByteArrayCopyInfo_t *info = userInfo;
63 HFByteSlice *slice = entry;
64 HFASSERT(slice != nil);
65 HFASSERT(info != NULL);
66 HFASSERT(offset <= info->startingOffset);
67
68 unsigned long long sliceLength = [slice length];
69 HFASSERT(sliceLength > 0);
70 unsigned long long offsetIntoSlice = info->startingOffset - offset;
71 HFASSERT(offsetIntoSlice < sliceLength);
72 NSUInteger amountToCopy = ll2l(MIN(info->remainingLength, sliceLength - offsetIntoSlice));
73 HFRange srcRange = HFRangeMake(info->startingOffset - offset, amountToCopy);
74 [slice copyBytes:info->dst range:srcRange];
75 info->dst += amountToCopy;
76 info->startingOffset = HFSum(info->startingOffset, amountToCopy);
77 info->remainingLength -= amountToCopy;
78 return info->remainingLength > 0;
79 }
80
81 - (void)copyBytes:(unsigned char *)dst range:(HFRange)range {
82 HFASSERT(range.length <= NSUIntegerMax);
83 HFASSERT(HFMaxRange(range) <= [self length]);
84 if (range.length > 0) {
85 struct HFBTreeByteArrayCopyInfo_t copyInfo = {.dst = dst, .remainingLength = ll2l(range.length), .startingOffset = range.location};
86 [btree applyFunction:copy_bytes toEntriesStartingAtOffset:range.location withUserInfo:©Info];
87 }
88 }
89
90 - (HFByteSlice *)sliceContainingByteAtIndex:(unsigned long long)offset beginningOffset:(unsigned long long *)actualOffset {
91 return [btree entryContainingOffset:offset beginningOffset:actualOffset];
92 }
93
94 /* Given a HFByteArray and a range contained within it, return the first byte slice containing that range, and the range within that slice. Modifies the given range to reflect what you get when the returned slice is removed. */
95 static inline HFByteSlice *findInitialSlice(HFBTree *btree, HFRange *inoutArrayRange, HFRange *outRangeWithinSlice) {
96 const HFRange arrayRange = *inoutArrayRange;
97 const unsigned long long arrayRangeEnd = HFMaxRange(arrayRange);
98
99 unsigned long long offsetIntoSlice, lengthFromOffsetIntoSlice;
100
101 unsigned long long beginningOffset;
102 HFByteSlice *slice = [btree entryContainingOffset:arrayRange.location beginningOffset:&beginningOffset];
103 const unsigned long long sliceLength = [slice length];
104 HFASSERT(beginningOffset <= arrayRange.location);
105 offsetIntoSlice = arrayRange.location - beginningOffset;
106 HFASSERT(offsetIntoSlice < sliceLength);
107
108 unsigned long long sliceEndInArray = HFSum(sliceLength, beginningOffset);
109 if (sliceEndInArray <= arrayRangeEnd) {
110 /* Our slice ends before or at the requested range end */
111 lengthFromOffsetIntoSlice = sliceLength - offsetIntoSlice;
112 }
113 else {
114 /* Our slice ends after the requested range end */
115 unsigned long long overflow = sliceEndInArray - arrayRangeEnd;
116 HFASSERT(HFSum(overflow, offsetIntoSlice) < sliceLength);
117 lengthFromOffsetIntoSlice = sliceLength - HFSum(overflow, offsetIntoSlice);
118 }
119
120 /* Set the out range to the input range minus the range consumed by the slice */
121 inoutArrayRange->location = MIN(sliceEndInArray, arrayRangeEnd);
122 inoutArrayRange->length = arrayRangeEnd - inoutArrayRange->location;
123
124 /* Set the out range within the slice to what we computed */
125 *outRangeWithinSlice = HFRangeMake(offsetIntoSlice, lengthFromOffsetIntoSlice);
126
127 return slice;
128 }
129
130 - (BOOL)fastPathInsertByteSlice:(HFByteSlice *)slice atOffset:(unsigned long long)offset {
131 HFASSERT(offset > 0);
132 unsigned long long priorSliceOffset;
133 HFByteSlice *priorSlice = [btree entryContainingOffset:offset - 1 beginningOffset:&priorSliceOffset];
134 HFByteSlice *appendedSlice = [priorSlice byteSliceByAppendingSlice:slice];
135 if (appendedSlice) {
136 [btree removeEntryAtOffset:priorSliceOffset];
137 [btree insertEntry:appendedSlice atOffset:priorSliceOffset];
138 return YES;
139 }
140 else {
141 return NO;
142 }
143 }
144
145 - (void)insertByteSlice:(HFByteSlice *)slice atOffset:(unsigned long long)offset {
146 [self incrementGenerationOrRaiseIfLockedForSelector:_cmd];
147
148 if (offset == 0) {
149 [btree insertEntry:slice atOffset:0];
150 }
151 else if (offset == [btree length]) {
152 if (! [self fastPathInsertByteSlice:slice atOffset:offset]) {
153 [btree insertEntry:slice atOffset:offset];
154 }
155 }
156 else {
157 unsigned long long beginningOffset;
158 HFByteSlice *overlappingSlice = [btree entryContainingOffset:offset beginningOffset:&beginningOffset];
159 if (beginningOffset == offset) {
160 if (! [self fastPathInsertByteSlice:slice atOffset:offset]) {
161 [btree insertEntry:slice atOffset:offset];
162 }
163 }
164 else {
165 HFASSERT(offset > beginningOffset);
166 unsigned long long offsetIntoSlice = offset - beginningOffset;
167 unsigned long long sliceLength = [overlappingSlice length];
168 HFASSERT(sliceLength > offsetIntoSlice);
169 HFByteSlice *left = [overlappingSlice subsliceWithRange:HFRangeMake(0, offsetIntoSlice)];
170 HFByteSlice *right = [overlappingSlice subsliceWithRange:HFRangeMake(offsetIntoSlice, sliceLength - offsetIntoSlice)];
171 [btree removeEntryAtOffset:beginningOffset];
172
173 [btree insertEntry:right atOffset:beginningOffset];
174
175 /* Try the fast appending path */
176 HFByteSlice *joinedSlice = [left byteSliceByAppendingSlice:slice];
177 if (joinedSlice) {
178 [btree insertEntry:joinedSlice atOffset:beginningOffset];
179 }
180 else {
181 [btree insertEntry:slice atOffset:beginningOffset];
182 [btree insertEntry:left atOffset:beginningOffset];
183 }
184 }
185 }
186 }
187
188 - (void)deleteBytesInRange:(HFRange)range {
189 [self incrementGenerationOrRaiseIfLockedForSelector:_cmd];
190 HFRange remainingRange = range;
191
192 HFASSERT(HFMaxRange(range) <= [self length]);
193 if (range.length == 0) return; //nothing to delete
194
195 //fast path for deleting everything
196 if (range.location == 0 && range.length == [self length]) {
197 [btree removeAllEntries];
198 return;
199 }
200
201 unsigned long long beforeLength = [self length];
202
203 unsigned long long rangeStartLocation = range.location;
204 HFByteSlice *beforeSlice = nil, *afterSlice = nil;
205 while (remainingRange.length > 0) {
206 HFRange rangeWithinSlice;
207 HFByteSlice *slice = findInitialSlice(btree, &remainingRange, &rangeWithinSlice);
208 const unsigned long long sliceLength = [slice length];
209 const unsigned long long rangeWithinSliceEnd = HFMaxRange(rangeWithinSlice);
210 HFRange lefty = HFRangeMake(0, rangeWithinSlice.location);
211 HFRange righty = HFRangeMake(rangeWithinSliceEnd, sliceLength - rangeWithinSliceEnd);
212 HFASSERT(lefty.length == 0 || beforeSlice == nil);
213 HFASSERT(righty.length == 0 || afterSlice == nil);
214
215 unsigned long long beginningOffset = remainingRange.location - HFMaxRange(rangeWithinSlice);
216
217 if (lefty.length > 0){
218 beforeSlice = [slice subsliceWithRange:lefty];
219 rangeStartLocation = beginningOffset;
220 }
221 if (righty.length > 0) afterSlice = [slice subsliceWithRange:righty];
222
223 [btree removeEntryAtOffset:beginningOffset];
224 remainingRange.location = beginningOffset;
225 }
226 if (afterSlice) {
227 [self insertByteSlice:afterSlice atOffset:rangeStartLocation];
228 }
229 if (beforeSlice) {
230 [self insertByteSlice:beforeSlice atOffset:rangeStartLocation];
231 }
232
233 unsigned long long afterLength = [self length];
234 HFASSERT(beforeLength - afterLength == range.length);
235 }
236
237 - (void)insertByteSlice:(HFByteSlice *)slice inRange:(HFRange)lrange {
238 [self incrementGenerationOrRaiseIfLockedForSelector:_cmd];
239
240 if (lrange.length > 0) {
241 [self deleteBytesInRange:lrange];
242 }
243 if ([slice length] > 0) {
244 [self insertByteSlice:slice atOffset:lrange.location];
245 }
246 }
247
248 - (id)mutableCopyWithZone:(NSZone *)zone {
249 USE(zone);
250 HFBTreeByteArray *result = [[[self class] alloc] init];
251 [result->btree release];
252 result->btree = [btree mutableCopy];
253 return result;
254 }
255
256 - (id)subarrayWithRange:(HFRange)range {
257 if (range.location == 0 && range.length == [self length]) {
258 return [[self mutableCopy] autorelease];
259 }
260 HFBTreeByteArray *result = [[[[self class] alloc] init] autorelease];
261 HFRange remainingRange = range;
262 unsigned long long offsetInResult = 0;
263 while (remainingRange.length > 0) {
264 HFRange rangeWithinSlice;
265 HFByteSlice *slice = findInitialSlice(btree, &remainingRange, &rangeWithinSlice);
266 HFByteSlice *subslice;
267 if (rangeWithinSlice.location == 0 && rangeWithinSlice.length == [slice length]) {
268 subslice = slice;
269 }
270 else {
271 subslice = [slice subsliceWithRange:rangeWithinSlice];
272 }
273 [result insertByteSlice:subslice atOffset:offsetInResult];
274 offsetInResult = HFSum(offsetInResult, rangeWithinSlice.length);
275 }
276 return result;
277 }
278
279 @end
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.