1 /*******************************************************
2 
3    CoolReader Engine
4 
5    lvrefcache.h:  Referenced objects cache
6       allows to reuse objects with the same concents
7 
8    (c) Vadim Lopatin, 2000-2006
9    This source code is distributed under the terms of
10    GNU General Public License
11    See LICENSE file for details
12 
13 *******************************************************/
14 
15 #if !defined(__LV_REF_CACHE_H_INCLUDED__)
16 #define __LV_REF_CACHE_H_INCLUDED__
17 
18 #include "lvmemman.h"
19 #include "lvref.h"
20 #include "lvarray.h"
21 
22 /*
23     Object cache
24 
25     Requirements:
26        sz parameter of constructor should be power of 2
27        bool operator == (LVRef<T> & r1, LVRef<T> & r2 ) should be defined
28        lUInt32 calcHash( LVRef<T> & r1 ) should be defined
29 */
30 
31 template <class ref_t>
32 class LVRefCache {
33 
34     class LVRefCacheRec {
35         ref_t style;
36         lUInt32 hash;
37         LVRefCacheRec * next;
LVRefCacheRec(ref_t & s,lUInt32 h)38         LVRefCacheRec(ref_t & s, lUInt32 h)
39             : style(s), hash(h), next(NULL) { }
40         friend class LVRefCache< ref_t >;
41     };
42 
43 private:
44     int size;
45     LVRefCacheRec ** table;
46 
47 public:
48     // check whether equal object already exists if cache
49     // if found, replace reference with cached value
cacheIt(ref_t & style)50     void cacheIt(ref_t & style)
51     {
52         lUInt32 hash = calcHash( style );
53         lUInt32 index = hash & (size - 1);
54         LVRefCacheRec **rr;
55         rr = &table[index];
56         while ( *rr != NULL )
57         {
58             if ( *(*rr)->style.get() == *style.get() )
59             {
60                 style = (*rr)->style;
61                 return;
62             }
63             rr = &(*rr)->next;
64         }
65         *rr = new LVRefCacheRec( style, hash );
66     }
67     // garbage collector: remove unused entries
gc()68     void gc()
69     {
70         for (int index = 0; index < size; index++)
71         {
72             LVRefCacheRec **rr;
73             rr = &table[index];
74             while ( *rr != NULL )
75             {
76                 if ( (*rr)->style.getRefCount() == 1 )
77                 {
78                     LVRefCacheRec * r = (*rr);
79                     *rr = r->next;
80                     delete r;
81                 }
82                 else
83                 {
84                     rr = &(*rr)->next;
85                 }
86             }
87         }
88     }
LVRefCache(int sz)89     LVRefCache( int sz )
90     {
91         size = sz;
92         table = new LVRefCacheRec * [ sz ];
93         for( int i=0; i<sz; i++ )
94             table[i] = NULL;
95     }
~LVRefCache()96     ~LVRefCache()
97     {
98         LVRefCacheRec *r, *r2;
99         for ( int i=0; i < size; i++ )
100         {
101             for ( r = table[ i ]; r;  )
102             {
103                 r2 = r;
104                 r = r->next;
105                 delete r2;
106             }
107         }
108         delete[] table;
109     }
110 };
111 
112 template <class ref_t>
113 class LVIndexedRefCache {
114 
115     // hash table item
116     struct LVRefCacheRec {
117         int index;
118         ref_t style;
119         lUInt32 hash;
120         LVRefCacheRec * next;
LVRefCacheRecLVRefCacheRec121         LVRefCacheRec(ref_t & s, lUInt32 h)
122             : style(s), hash(h), next(NULL) { }
123     };
124 
125     // index item
126     struct LVRefCacheIndexRec {
127         LVRefCacheRec * item;
128         int refcount; // refcount, or next free index if item==NULL
129     };
130 
131 private:
132     int size;
133     LVRefCacheRec ** table;
134 
135     LVRefCacheIndexRec * index;
136     int indexsize;
137     int nextindex;
138     int freeindex;
139     int numitems;
140 
indexItem(LVRefCacheRec * rec)141     int indexItem( LVRefCacheRec * rec )
142     {
143         int n;
144         if ( freeindex ) {
145             n = freeindex;
146             freeindex = index[freeindex].refcount; // next free index
147         } else {
148             n = ++nextindex;
149         }
150         if ( n>=indexsize ) {
151             // resize
152             if ( indexsize==0 )
153                 indexsize = size/2;
154             else
155                 indexsize *= 2;
156             index = cr_realloc( index, indexsize );
157             for ( int i=nextindex+1; i<indexsize; i++ ) {
158                 index[i].item = NULL;
159                 index[i].refcount = 0;
160             }
161         }
162         rec->index = n;
163         index[n].item = rec;
164         index[n].refcount = 1;
165         return n;
166     }
167 
168     // remove item from hash table
removeItem(LVRefCacheRec * item)169     void removeItem( LVRefCacheRec * item )
170     {
171         lUInt32 hash = item->hash;
172         lUInt32 tindex = hash & (size - 1);
173         LVRefCacheRec **rr = &table[tindex];
174         for ( ; *rr; rr = &(*rr)->next ) {
175             if ( *rr == item ) {
176                 LVRefCacheRec * tmp = *rr;
177                 *rr = (*rr)->next;
178                 delete tmp;
179                 numitems--;
180                 return;
181             }
182         }
183         // not found!
184     }
185 
186 public:
187 
getIndex()188     LVArray<ref_t> * getIndex()
189     {
190         LVArray<ref_t> * list = new LVArray<ref_t>(indexsize, ref_t());
191         for ( int i=1; i<indexsize; i++ ) {
192             if ( index[i].item )
193                 list->set(i, index[i].item->style);
194         }
195         return list;
196     }
197 
length()198     int length()
199     {
200         return numitems;
201     }
202 
release(ref_t r)203     void release( ref_t r )
204     {
205         int i = find(r);
206         if (  i>0 )
207             release(i);
208     }
209 
release(int n)210     void release( int n )
211     {
212         if ( n<1 || n>nextindex )
213             return;
214         if ( index[n].item ) {
215             if ( (--index[n].refcount)<=0 ) {
216                 removeItem( index[n].item );
217                 // next free
218                 index[n].refcount = freeindex;
219                 index[n].item = NULL;
220                 freeindex = n;
221             }
222         }
223     }
224 
225     // get by index
get(int n)226     ref_t get( int n )
227     {
228         if ( n>0 && n<=nextindex && index[n].item )
229             return index[n].item->style;
230         return ref_t();
231     }
232 
233     // check whether equal object already exists if cache
234     // if found, replace reference with cached value
235     // returns index of item - use it to release reference
cache(lUInt16 & indexholder,ref_t & style)236     bool cache( lUInt16 &indexholder, ref_t & style)
237     {
238         int newindex = cache( style );
239         // printf("newindex: %d  /  provided indexholder: %d\n", newindex, (int)indexholder);
240         if ( indexholder != newindex ) {
241             release( indexholder );
242             indexholder = (lUInt16)newindex;
243             return true;
244         } else { // indexholder == newindex
245             // Here, we want to decrement the refcount that has been incremented
246             // by the above call "newindex = cache( style )", as it returned the
247             // same index as the already referenced one.
248             // In normal cases, when the item is already present in the cache
249             // and referenced once, we are here with refcount=2, and we want to
250             // put it back to refcount=1, as it should be.
251             // In rare cases for some yet undertermined reason or bug, we may
252             // have been called with a non-0 indexholder, but not previously
253             // present in the cache, and we get the same value for newindex:
254             // the cache item refcount is then 1. And we want it to stay 1 (as
255             // it's really referenced once) so the value/pointer are not freed,
256             // and some segmentation fault is avoided later.
257             // So, we just don't release it if the refcount is 1 (we were
258             // asked to cache something: so don't drop it!)
259             // printf("released: refcount for %d = %d\n", indexholder, this->index[indexholder].refcount);
260             if (this->index[indexholder].refcount > 1)
261                 release( indexholder );
262             return false;
263             // This returned boolean seems not used anywhere, so it's not
264             // clear whether we should return true or false when the
265             // item was not in the cache, and thus created - but the
266             // indexholder (although not existing) stayed unchanged.
267         }
268     }
269 
addIndexRef(lUInt16 n)270     bool addIndexRef( lUInt16 n )
271     {
272         if ( n>0 && n<=nextindex && index[n].item ) {
273             index[n].refcount++;
274             return true;
275         } else
276             return false;
277     }
278 
279     // check whether equal object already exists if cache
280     // if found, replace reference with cached value
281     // returns index of item - use it to release reference
cache(ref_t & style)282     int cache(ref_t & style)
283     {
284         lUInt32 hash = calcHash( style );
285         lUInt32 index = hash & (size - 1);
286         LVRefCacheRec **rr;
287         rr = &table[index];
288         while ( *rr != NULL )
289         {
290             if ( (*rr)->hash==hash && *(*rr)->style.get() == *style.get() )
291             {
292                 style = (*rr)->style;
293                 int n = (*rr)->index;
294                 this->index[n].refcount++;
295                 return n;
296             }
297             rr = &(*rr)->next;
298         }
299         *rr = new LVRefCacheRec( style, hash );
300         numitems++;
301         return indexItem( *rr );
302     }
303 
304     // check whether equal object already exists if cache
305     // if found, replace reference with cached value
306     // returns index of item - use it to release reference
find(ref_t & style)307     int find(ref_t & style)
308     {
309         lUInt32 hash = calcHash( style );
310         lUInt32 index = hash & (size - 1);
311         LVRefCacheRec **rr;
312         rr = &table[index];
313         while ( *rr != NULL )
314         {
315             if ( (*rr)->hash==hash && *(*rr)->style.get() == *style.get() )
316             {
317                 int n = (*rr)->index;
318                 return n;
319             }
320             rr = &(*rr)->next;
321         }
322         return 0;
323     }
324 
325     /// from index array
LVIndexedRefCache(LVArray<ref_t> & list)326     LVIndexedRefCache( LVArray<ref_t> &list )
327     : index(NULL)
328     , indexsize(0)
329     , nextindex(0)
330     , freeindex(0)
331     , numitems(0)
332     {
333         setIndex(list);
334     }
335 
nearestPowerOf2(int n)336     int nearestPowerOf2( int n )
337     {
338         int res;
339         for ( res = 1; res<n; res<<=1 )
340             ;
341         return res;
342     }
343 
344     /// init from index array
setIndex(LVArray<ref_t> & list)345     void setIndex( LVArray<ref_t> &list )
346     {
347         clear();
348         size = nearestPowerOf2(list.length()>0 ? list.length() : 32);
349         if ( table )
350             delete[] table;
351         table = new LVRefCacheRec * [ size ];
352         for( int i=0; i<size; i++ )
353             table[i] = NULL;
354         indexsize = list.length();
355         nextindex = indexsize > 0 ? indexsize-1 : 0;
356         if ( indexsize ) {
357             index = cr_realloc( index, indexsize );
358             index[0].item = NULL;
359             index[0].refcount=0;
360             for ( int i=1; i<indexsize; i++ ) {
361                 if ( list[i].isNull() ) {
362                     // add free node
363                     index[i].item = NULL;
364                     index[i].refcount = freeindex;
365                     freeindex = i;
366                 } else {
367                     // add item
368                     lUInt32 hash = calcHash( list[i] );
369                     lUInt32 hindex = hash & (size - 1);
370                     LVRefCacheRec * rec = new LVRefCacheRec(list[i], hash);
371                     rec->index = i;
372                     rec->next = table[hindex];
373                     table[hindex] = rec;
374                     index[i].item = rec;
375                     index[i].refcount = 1;
376                     numitems++;
377                 }
378             }
379         }
380     }
381 
LVIndexedRefCache(int sz)382     LVIndexedRefCache( int sz )
383     : index(NULL)
384     , indexsize(0)
385     , nextindex(0)
386     , freeindex(0)
387     , numitems(0)
388     {
389         size = sz;
390         table = new LVRefCacheRec * [ sz ];
391         for( int i=0; i<sz; i++ )
392             table[i] = NULL;
393     }
394     void clear( int sz = 0 )
395     {
396         if ( sz==-1 )
397             sz = size;
398         LVRefCacheRec *r, *r2;
399         for ( int i=0; i < size; i++ )
400         {
401             for ( r = table[ i ]; r;  )
402             {
403                 r2 = r;
404                 r = r->next;
405                 delete r2;
406             }
407             table[i] = NULL;
408         }
409         if (index) {
410             free( index );
411             index = NULL;
412             indexsize = 0;
413             nextindex = 0;
414             freeindex = 0;
415         }
416         numitems = 0;
417         if ( sz ) {
418             size = sz;
419             if ( table )
420                 delete[] table;
421             table = new LVRefCacheRec * [ sz ];
422             for( int i=0; i<sz; i++ )
423                 table[i] = NULL;
424         }
425     }
~LVIndexedRefCache()426     ~LVIndexedRefCache()
427     {
428         clear();
429         delete[] table;
430     }
431 };
432 
433 template <typename keyT, class dataT> class LVCacheMap
434 {
435 private:
436     class Pair {
437     public:
438         keyT key;
439         dataT data;
440         int lastAccess;
441     };
442     Pair * buf;
443     int size;
444     int orig_size;
445     int numitems;
446     int lastAccess;
checkOverflow(int oldestAccessTime)447     void checkOverflow( int oldestAccessTime )
448     {
449         int i;
450         if ( oldestAccessTime==-1 ) {
451             for ( i=0; i<size; i++ )
452                 if ( oldestAccessTime==-1 || buf[i].lastAccess>oldestAccessTime )
453                     oldestAccessTime = buf[i].lastAccess;
454         }
455         if ( oldestAccessTime>1000000000 ) {
456             int maxLastAccess = 0;
457             for ( i=0; i<size; i++ ) {
458                 buf[i].lastAccess -= 1000000000;
459                 if ( maxLastAccess==0 || buf[i].lastAccess>maxLastAccess )
460                     maxLastAccess = buf[i].lastAccess;
461             }
462             lastAccess = maxLastAccess+1;
463         }
464     }
465 public:
length()466     int length()
467     {
468         return numitems;
469     }
LVCacheMap(int maxSize)470     LVCacheMap( int maxSize )
471     : size(maxSize), orig_size(maxSize), numitems(0), lastAccess(1)
472     {
473         buf = new Pair[ size ];
474         clear();
475     }
reduceSize(int newSize)476     void reduceSize(int newSize)
477     {
478         if (newSize < orig_size) {
479             clear();
480             size = newSize;
481         }
482     }
restoreSize()483     void restoreSize()
484     {
485         size = orig_size;
486         clear();
487     }
clear()488     void clear()
489     {
490         for ( int i=0; i<size; i++ )
491         {
492             buf[i].key = keyT();
493             buf[i].data = dataT();
494             buf[i].lastAccess = 0;
495         }
496         numitems = 0;
497     }
get(keyT key,dataT & data)498     bool get( keyT key, dataT & data )
499     {
500         for ( int i=0; i<size; i++ ) {
501             if ( buf[i].key == key ) {
502                 data = buf[i].data;
503                 buf[i].lastAccess = ++lastAccess;
504                 if ( lastAccess>1000000000 )
505                     checkOverflow(-1);
506                 return true;
507             }
508         }
509         return false;
510     }
remove(keyT key)511     bool remove( keyT key )
512     {
513         for ( int i=0; i<size; i++ ) {
514             if ( buf[i].key == key ) {
515                 buf[i].key = keyT();
516                 buf[i].data = dataT();
517                 buf[i].lastAccess = 0;
518                 numitems--;
519                 return true;
520             }
521         }
522         return false;
523     }
set(keyT key,dataT data)524     void set( keyT key, dataT data )
525     {
526         int oldestAccessTime = -1;
527         int oldestIndex = 0;
528         for ( int i=0; i<size; i++ ) {
529             if ( buf[i].key == key ) {
530                 buf[i].data = data;
531                 buf[i].lastAccess = ++lastAccess;
532                 return;
533             }
534             int at = buf[i].lastAccess;
535             if ( at < oldestAccessTime || oldestAccessTime==-1 ) {
536                 oldestAccessTime = at;
537                 oldestIndex = i;
538             }
539         }
540         checkOverflow(oldestAccessTime);
541         if ( buf[oldestIndex].key==keyT() )
542             numitems++;
543         buf[oldestIndex].key = key;
544         buf[oldestIndex].data = data;
545         buf[oldestIndex].lastAccess = ++lastAccess;
546         return;
547     }
~LVCacheMap()548     ~LVCacheMap()
549     {
550         delete[] buf;
551     }
552 };
553 
554 #endif // __LV_REF_CACHE_H_INCLUDED__
555