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