Reviewed by Beth Dakin.
[WebKit-https.git] / WebKit / History / WebBackForwardList.m
1 /*
2  * Copyright (C) 2005 Apple Computer, Inc.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer. 
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution. 
13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission. 
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #import <JavaScriptCore/Assertions.h>
30 #import <WebKit/WebBackForwardList.h>
31 #import <WebKit/WebHistoryItemPrivate.h>
32 #import <WebKit/WebKitLogging.h>
33 #import <WebKit/WebNSObjectExtras.h>
34 #import <WebKit/WebPreferencesPrivate.h>
35 #import <WebKit/WebKitSystemBits.h>
36
37 #import "WebTypesInternal.h"
38
39 #define COMPUTE_DEFAULT_PAGE_CACHE_SIZE UINT_MAX
40
41 @interface WebBackForwardListPrivate : NSObject
42 {
43 @public
44     NSMutableArray *entries;
45     int current;
46     int maximumSize;
47     unsigned pageCacheSize;
48     BOOL closed;
49 }
50 @end
51
52 @implementation WebBackForwardListPrivate
53
54 - (void)dealloc
55 {
56     [entries release];
57     [super dealloc];
58 }
59 @end
60
61 @implementation WebBackForwardList
62
63 - (id)init
64 {
65     self = [super init];
66     if (!self) {
67         return nil;
68     }
69     
70     _private = [[WebBackForwardListPrivate alloc] init];
71     
72     _private->entries = [[NSMutableArray alloc] init];
73     _private->current = -1;
74     _private->maximumSize = 100; // typically set by browser app
75
76     _private->pageCacheSize = COMPUTE_DEFAULT_PAGE_CACHE_SIZE;
77     
78     return self;
79 }
80
81 - (void)dealloc
82 {
83     ASSERT(_private->closed);
84     [_private release];
85     [super dealloc];
86 }
87
88 - (void)finalize
89 {
90     ASSERT(_private->closed);
91     [super finalize];
92 }
93
94 - (void)_close
95 {
96     unsigned count = [_private->entries count];
97     unsigned i;
98     for (i = 0; i < count; i++){
99         WebHistoryItem *item = [_private->entries objectAtIndex: i];
100         [item setHasPageCache: NO]; 
101     }
102     _private->closed = YES;
103 }
104
105 - (void)addItem:(WebHistoryItem *)entry;
106 {
107     if (_private->maximumSize == 0)
108         return;
109     
110     // Toss anything in the forward list
111     int currSize = [_private->entries count];
112     if (_private->current != currSize-1 && _private->current != -1) {
113         NSRange forwardRange = NSMakeRange(_private->current+1, currSize-(_private->current+1));
114         NSArray *subarray;
115         subarray = [_private->entries subarrayWithRange:forwardRange];
116         unsigned i;
117         for (i = 0; i < [subarray count]; i++){
118             WebHistoryItem *item = [subarray objectAtIndex: i];
119             [item setHasPageCache: NO];            
120         }
121         [_private->entries removeObjectsInRange: forwardRange];
122         currSize -= forwardRange.length;
123     }
124
125     // Toss the first item if the list is getting too big, as long as we're not using it
126     if (currSize == _private->maximumSize && _private->current != 0) {
127         WebHistoryItem *item = [_private->entries objectAtIndex: 0];
128         [item setHasPageCache: NO];
129         [_private->entries removeObjectAtIndex:0];
130         currSize--;
131         _private->current--;
132     }
133
134     [_private->entries addObject:entry];
135     _private->current++;
136 }
137
138 - (void)removeItem:(WebHistoryItem *)item
139 {
140     if (!item)
141         return;
142     
143     WebNSUInteger itemIndex = [_private->entries indexOfObjectIdenticalTo:item];
144     ASSERT(itemIndex != (unsigned)_private->current);
145     
146     if (itemIndex != NSNotFound && itemIndex != (WebNSUInteger)_private->current) {
147         [_private->entries removeObjectAtIndex:itemIndex];
148     }
149 }
150
151 - (BOOL)containsItem:(WebHistoryItem *)entry
152 {
153     return [_private->entries indexOfObjectIdenticalTo:entry] != NSNotFound;
154 }
155
156
157 - (void)goBack
158 {
159     if(_private->current > 0)
160         _private->current--;
161     else
162         [NSException raise:NSInternalInconsistencyException format:@"%@: goBack called with empty back list", self];
163 }
164
165 - (void)goForward
166 {
167     if(_private->current < (int)[_private->entries count]-1)
168         _private->current++;
169     else
170         [NSException raise:NSInternalInconsistencyException format:@"%@: goForward called with empty forward list", self];
171 }
172
173 - (void)goToItem:(WebHistoryItem *)item
174 {
175     WebNSUInteger index = [_private->entries indexOfObjectIdenticalTo:item];
176     if (index != NSNotFound)
177         _private->current = index;
178     else
179         [NSException raise:NSInvalidArgumentException format:@"%@: %s:  invalid item", self, __FUNCTION__];
180 }
181
182 - (WebHistoryItem *)backItem
183 {
184     if (_private->current > 0) {
185         return [_private->entries objectAtIndex:_private->current-1];
186     } else {
187         return nil;
188     }
189 }
190
191 - (WebHistoryItem *)currentItem
192 {
193     if (_private->current >= 0) {
194         return [_private->entries objectAtIndex:_private->current];
195     } else {
196         return nil;
197     }
198 }
199
200 - (WebHistoryItem *)forwardItem
201 {
202     if (_private->current < (int)[_private->entries count]-1) {
203         return [_private->entries objectAtIndex:_private->current+1];
204     } else {
205         return nil;
206     }
207 }
208
209 - (NSArray *)backListWithLimit:(int)limit;
210 {
211     if (_private->current > 0) {
212         NSRange r;
213         r.location = MAX(_private->current-limit, 0);
214         r.length = _private->current - r.location;
215         return [_private->entries subarrayWithRange:r];
216     } else {
217         return nil;
218     }
219 }
220
221 - (NSArray *)forwardListWithLimit:(int)limit;
222 {
223     int lastEntry = (int)[_private->entries count]-1;
224     if (_private->current < lastEntry) {
225         NSRange r;
226         r.location = _private->current+1;
227         r.length =  MIN(_private->current+limit, lastEntry) - _private->current;
228         return [_private->entries subarrayWithRange:r];
229     } else {
230         return nil;
231     }
232 }
233
234 - (int)capacity
235 {
236     return _private->maximumSize;
237 }
238
239 - (void)setCapacity:(int)size
240 {
241     if (size < _private->maximumSize){
242         int currSize = [_private->entries count];
243         NSRange forwardRange = NSMakeRange(size, currSize-size);
244         NSArray *subarray;
245         subarray = [_private->entries subarrayWithRange:forwardRange];
246         unsigned i;
247         for (i = 0; i < [subarray count]; i++){
248             WebHistoryItem *item = [subarray objectAtIndex: i];
249             [item setHasPageCache: NO];
250         }
251         [_private->entries removeObjectsInRange: forwardRange];
252         currSize -= forwardRange.length;
253     }
254     if (_private->current > (int)([_private->entries count] - 1))
255         _private->current = [_private->entries count] - 1;
256         
257     _private->maximumSize = size;
258 }
259
260
261 -(NSString *)description
262 {
263     NSMutableString *result;
264     int i;
265     
266     result = [NSMutableString stringWithCapacity:512];
267     
268     [result appendString:@"\n--------------------------------------------\n"];    
269     [result appendString:@"WebBackForwardList:\n"];
270     
271     for (i = 0; i < (int)[_private->entries count]; i++) {
272         if (i == _private->current) {
273             [result appendString:@" >>>"]; 
274         }
275         else {
276             [result appendString:@"    "]; 
277         }   
278         [result appendFormat:@"%2d) ", i];
279         int currPos = [result length];
280         [result appendString:[[_private->entries objectAtIndex:i] description]];
281
282         // shift all the contents over.  a bit slow, but this is for debugging
283         NSRange replRange = {currPos, [result length]-currPos};
284         [result replaceOccurrencesOfString:@"\n" withString:@"\n        " options:0 range:replRange];
285         
286         [result appendString:@"\n"];
287     }
288
289     [result appendString:@"\n--------------------------------------------\n"];    
290
291     return result;
292 }
293
294 - (void)_clearPageCache
295 {
296     int i;
297     WebHistoryItem *currentItem = [self currentItem];
298     
299     for (i = 0; i < (int)[_private->entries count]; i++) {
300         WebHistoryItem *item;
301         // Don't clear the current item.  Objects are still in use.
302         item = [_private->entries objectAtIndex:i];
303         if (item != currentItem)
304             [item setHasPageCache:NO];
305     }
306     [WebHistoryItem _releaseAllPendingPageCaches];
307 }
308
309
310 - (void)setPageCacheSize: (unsigned)size
311 {
312     _private->pageCacheSize = size;
313     if (size == 0) {
314         [self _clearPageCache];
315     }
316 }
317
318 #ifndef NDEBUG
319 static BOOL loggedPageCacheSize = NO;
320 #endif
321
322 - (unsigned)pageCacheSize
323 {
324     if (_private->pageCacheSize == COMPUTE_DEFAULT_PAGE_CACHE_SIZE) {
325         unsigned s;
326         vm_size_t memSize = WebSystemMainMemory();
327         
328         s = [[WebPreferences standardPreferences] _pageCacheSize];
329         if (memSize >= 1024 * 1024 * 1024)
330             _private->pageCacheSize = s;
331         else if (memSize >= 512 * 1024 * 1024)
332             _private->pageCacheSize = s - 1;
333         else
334             _private->pageCacheSize = s - 2;
335
336 #ifndef NDEBUG
337         if (!loggedPageCacheSize){
338             LOG (CacheSizes, "Page cache size set to %d pages.", _private->pageCacheSize);
339             loggedPageCacheSize = YES;
340         }
341 #endif
342     }
343     
344     return _private->pageCacheSize;
345 }
346
347 - (BOOL)_usesPageCache
348 {
349     return _private->pageCacheSize != 0;
350 }
351
352 - (int)backListCount
353 {
354     return _private->current;
355 }
356
357 - (int)forwardListCount
358 {
359     return (int)[_private->entries count] - (_private->current + 1);
360 }
361
362 - (WebHistoryItem *)itemAtIndex:(int)index
363 {
364     // Do range checks without doing math on index to avoid overflow.
365     if (index < -_private->current) {
366         return nil;
367     }
368     if (index > [self forwardListCount]) {
369         return nil;
370     }
371     return [_private->entries objectAtIndex:index + _private->current];
372 }
373
374 - (NSMutableArray *)_entries
375 {
376     return _private->entries;
377 }
378
379 @end