core/QCache.h

   1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
   2 /* vi: set ts=4 sw=4 expandtab: (add to ~/.vimrc: set modeline modelines=5) */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is [Open Source Virtual Machine.].
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Adobe System Incorporated.
  20  * Portions created by the Initial Developer are Copyright (C) 2008
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Adobe AS3 Team
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either the GNU General Public License Version 2 or later (the "GPL"), or
  28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #ifndef __avmplus_QCache__
  41 #define __avmplus_QCache__
  42
  43 #ifdef _DEBUG
  44     #define QCACHE_DEBUG
  45 #endif
  46
  47 #include "MathUtils.h"
  48
  49 /*
  50     QCache is a simple framework for maintaining a cache of items, with a random
  51     eviction policy. The cache is limited by count of items, which can be set arbitrarily
  52     (or allowed to grow to unlimited size).
  53
  54     The recommended use case is to split a a data structure split into a small, frequently-used
  55     chunk (owner), and a larger, less-frequently-used chunk (cacheditem) that can be reconstituted
  56     from compressed data; e.g., the slot-binding tables for Traits, which are kept in memory in
  57     a highly compressed form (the ABC bytecode), and expanded into convenient hashtable format
  58     as a cacheditem.
  59
  60     Important note: For proper use, the only "strong" ref to the cacheditem should be via
  61     the QCache itself; the owner should keep a reference to the cacheditem via a GCWeakRef, which
  62     will allow the cacheditem to be collected when it is evicted from the cache. (Naturally, the owner
  63     must check the GCWeakRef for null before using it.)
  64
  65     Cached items are stored in a singly-linked list; it's assumed that the cost
  66     of building a new item to add to the cache is likely to dwarf the cost of walking
  67     the list to evict an item (this is currently the case for all existing use cases).
  68 */
  69
  70 namespace avmplus
  71 {
  72     // QCachedItem is not meant to be instantiated as-is, but to be subclassed.
  73
  74     class GC_CPP_EXACT(QCachedItem, MMgc::GCTraceableObject)
  75     {
  76         friend class QCache;
  77     protected:
  78         inline QCachedItem() : next(NULL) { }
  79
  80     private:
  81         GC_DATA_BEGIN(QCachedItem)
  82
  83         QCachedItem*    GC_POINTER(next);   // written with explicit WB
  84
  85         GC_DATA_END(QCachedItem)
  86     };
  87
  88     class GC_CPP_EXACT(QCache, MMgc::GCFinalizedObject)
  89     {
  90     private:
  91         QCache(uint32_t _max, MMgc::GC* _gc);
  92     public:
  93         REALLY_INLINE static QCache* create(uint32_t max, MMgc::GC* gc)
  94         {
  95             return new (gc, MMgc::kExact) QCache(max, gc);
  96         }
  97
  98         ~QCache();
  99
 100         inline uint32_t count() const { return m_count; }
 101         inline uint32_t maxcount() const { return m_max; }  // sadly, "max" is a macro in some environments
 102         inline QCachedItem* first() const { return m_head; }
 103         inline QCachedItem* next(QCachedItem* gen) const { return gen->next; }
 104
 105         void flush();
 106         void resize(uint32_t _max);
 107
 108         QCachedItem* add(QCachedItem* gen);
 109
 110     private:
 111         #ifdef QCACHE_DEBUG
 112         void validate() const;
 113         #endif
 114
 115         GC_DATA_BEGIN(QCache)
 116
 117     private:
 118         MMgc::GC*               m_gc;
 119         QCachedItem*            GC_POINTER(m_head);
 120         uint32_t                m_count;
 121         uint32_t                m_max;
 122         TRandomFast             m_rand;
 123
 124         GC_DATA_END(QCache)
 125     };
 126 }
 127
 128 #endif /* __avmplus_QCache__ */