js/src/jspropertytree.h

   1 /* -*- Mode: c++; c-basic-offset: 4; tab-width: 40; indent-tabs-mode: nil -*- */
   2 /* vim: set ts=40 sw=4 et tw=99: */
   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 the Mozilla SpiderMonkey property tree implementation
  17  *
  18  * The Initial Developer of the Original Code is
  19  *   Mozilla Foundation
  20  * Portions created by the Initial Developer are Copyright (C) 2002-2010
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Brendan Eich <brendan@mozilla.org>
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or 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 jspropertytree_h___
  41 #define jspropertytree_h___
  42
  43 #include "jsarena.h"
  44 #include "jshashtable.h"
  45 #include "jsprvtd.h"
  46
  47 namespace js {
  48
  49 struct ShapeHasher {
  50     typedef js::Shape *Key;
  51     typedef const js::Shape *Lookup;
  52
  53     static inline HashNumber hash(const Lookup l);
  54     static inline bool match(Key k, Lookup l);
  55 };
  56
  57 typedef HashSet<js::Shape *, ShapeHasher, SystemAllocPolicy> KidsHash;
  58
  59 class KidsPointer {
  60   private:
  61     enum {
  62         SHAPE = 0,
  63         HASH  = 1,
  64         TAG   = 1
  65     };
  66
  67     jsuword w;
  68
  69   public:
  70     bool isNull() const { return !w; }
  71     void setNull() { w = 0; }
  72
  73     bool isShape() const { return (w & TAG) == SHAPE && !isNull(); }
  74     js::Shape *toShape() const {
  75         JS_ASSERT(isShape());
  76         return reinterpret_cast<js::Shape *>(w & ~jsuword(TAG));
  77     }
  78     void setShape(js::Shape *shape) {
  79         JS_ASSERT(shape);
  80         JS_ASSERT((reinterpret_cast<jsuword>(shape) & TAG) == 0);
  81         w = reinterpret_cast<jsuword>(shape) | SHAPE;
  82     }
  83
  84     bool isHash() const { return (w & TAG) == HASH; }
  85     KidsHash *toHash() const {
  86         JS_ASSERT(isHash());
  87         return reinterpret_cast<KidsHash *>(w & ~jsuword(TAG));
  88     }
  89     void setHash(KidsHash *hash) {
  90         JS_ASSERT(hash);
  91         JS_ASSERT((reinterpret_cast<jsuword>(hash) & TAG) == 0);
  92         w = reinterpret_cast<jsuword>(hash) | HASH;
  93     }
  94
  95 #ifdef DEBUG
  96     void checkConsistency(const js::Shape *aKid) const;
  97 #endif
  98 };
  99
 100 class PropertyTree
 101 {
 102     friend struct ::JSFunction;
 103
 104     JSCompartment *compartment;
 105     JSArenaPool   arenaPool;
 106     js::Shape     *freeList;
 107
 108     bool insertChild(JSContext *cx, js::Shape *parent, js::Shape *child);
 109     void removeChild(js::Shape *child);
 110
 111     PropertyTree();
 112
 113   public:
 114     enum { MAX_HEIGHT = 128 };
 115
 116     PropertyTree(JSCompartment *comp)
 117         : compartment(comp), freeList(NULL)
 118     {
 119         PodZero(&arenaPool);
 120     }
 121
 122     bool init();
 123     void finish();
 124
 125     js::Shape *newShapeUnchecked();
 126     js::Shape *newShape(JSContext *cx);
 127     js::Shape *getChild(JSContext *cx, js::Shape *parent, const js::Shape &child);
 128
 129     void orphanChildren(js::Shape *shape);
 130     void sweepShapes(JSContext *cx);
 131     bool checkShapesAllUnmarked(JSContext *cx);
 132
 133     static void dumpShapes(JSContext *cx);
 134 #ifdef DEBUG
 135     static void meter(JSBasicStats *bs, js::Shape *node);
 136 #endif
 137 };
 138
 139 } /* namespace js */
 140
 141 #endif /* jspropertytree_h___ */