Sketch for TraverseTransitionTree.

src/objects.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 4917 matching lines @@
 
 
 void Map::RemoveFromCodeCache(String* name, Code* code, int index) {
   // No GC is supposed to happen between a call to IndexInCodeCache and
   // RemoveFromCodeCache so the code cache must be there.
   ASSERT(!code_cache()->IsFixedArray());
   CodeCache::cast(code_cache())->RemoveByIndex(name, code, index);
 }
 
 
+class IntrusiveIterationState {
+ public:
+  IntrusiveIterationState(HeapObject* obj)
+      : obj_(obj) { }
+
+  Object* Get() {
+    return *HeapObject::RawField(obj_, HeapObject::kMapOffset);
+  }
+
+  void Set(Object* s) {
+    *HeapObject::RawField(obj_, HeapObject::kMapOffset) = s;
+  }
+
+ private:
+  HeapObject* obj_;
+};
+
+
+class IntrusiveFixedArrayIterator {
+ public:
+  IntrusiveFixedArrayIterator(FixedArray* array)
+      : state_(array) { }
+
+  bool IsIterating() {
+    return state_.Get()->IsSmi();
+  }
+
+  int GetIndex() {
+    return Smi::cast(state_.Get())->value();
+  }
+
+  void SetIndex(int index) {
+    state_.Set(Smi::FromInt(index));
+  }
+
+  void Stop() {
+    state_.Set(HEAP->fixed_array_map());
+  }
+
+ private:
+  IntrusiveIterationState state_;
+};
+
+
+class IntrusiveMapIterator {
+ public:
+  IntrusiveMapIterator(Map* map)
+      : current_(map) { }
+
+  void DescendInto(Map* child) {
+    Map* parent = Current();
+    SetCurrent(child);
+    ASSERT(Parent() == HEAP->meta_map());
+    SetParent(parent);
+  }
+
+  Map* Ascend() {
+    // We are done with the current map.
+    // Before ascending reset iteration state.
+    StopMapTransitionsIteration();
+    StopPrototypeTransitionsIteration();
+
+    Map* parent = Parent();
+    SetParent(HEAP->meta_map());
+
+    Map* current = Current();
+    SetCurrent(parent);
+
+    return current;
+  }
+
+  bool HasMore() {
+    return Current() != HEAP->meta_map();
+  }
+
+
+  Map* NextUnvisitedChild() {
+    Map* child = NULL;
+
+    child = NextUnvisitedMapTransition();
+    if (child != NULL) return child;
+
+    child = NextUnvisitedPrototypeTransition();
+    if (child != NULL) return child;
+
+    return NULL;
+  }
+
+ private:
+  Map* current_;
+
+  Map* Current() {
+    return current_;
+  }
+
+  void SetCurrent(Map* current) {
+    current_ = current;
+  }
+
+  Map* Parent() {
+    return reinterpret_cast<Map*>(IntrusiveIterationState(current_).Get());
+  }
+
+  void SetParent(Map* parent) {
+    IntrusiveIterationState(current_).Set(parent);
+  }
+
+  FixedArray* ContentArray() {
+    DescriptorArray* d = Current()->instance_descriptors();
+    return reinterpret_cast<FixedArray*>(
+        d->get(DescriptorArray::kContentArrayIndex));
+  }
+
+  bool HasContentArray() {
+    return !Current()->instance_descriptors()->IsEmpty();
+  }
+
+  void StopMapTransitionsIteration() {
+    if (HasContentArray()) {
+      IntrusiveFixedArrayIterator it(ContentArray());
+      it.Stop();
+    }
+  }
+
+  Map* NextUnvisitedMapTransition() {
+    if (HasContentArray()) {
+      FixedArray* content = ContentArray();
+
+      IntrusiveFixedArrayIterator it(content);
+      for (int i = it.IsIterating() ? it.GetIndex() : 0;
+           i < content->length();
+           i += 2) {
+        PropertyDetails details(Smi::cast(content->get(i + 1)));
+        if (details.IsTransition()) {
+          // Found a map in the transition array.  We record our progress in
+          // the transition array by recording the current map in the map field
+          // of the next map and recording the index in the transition array in
+          // the map field of the array.
+          Map* child = Map::cast(content->get(i));
+          it.SetIndex(i + 2);
+          return child;
+        }
+      }
+    }
+    return NULL;
+  }
+
+  void StopPrototypeTransitionsIteration() {
+    FixedArray* array = Current()->unchecked_prototype_transitions();
+    IntrusiveFixedArrayIterator it(array);
+    it.Stop();
+  }
+
+  Map* NextUnvisitedPrototypeTransition() {
+    FixedArray* array = Current()->unchecked_prototype_transitions();
+    IntrusiveFixedArrayIterator it(array);
+
+    static const int kFirstMapIndex =
+        (Map::kProtoTransitionHeaderSize + Map::kProtoTransitionMapOffset);
+
+    int index = it.IsIterating() ? it.GetIndex() : kFirstMapIndex;
+
+    if (index < array->length()) {
+      Object* child = array->get(index);
+      if (child->IsMap()) {
+        it.SetIndex(index + Map::kProtoTransitionElementsPerEntry);
+        return Map::cast(child);
+      }
+    }
+
+    return NULL;
+  }
+};
+
+
 void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
   // Traverse the transition tree without using a stack.  We do this by
   // reversing the pointers in the maps and descriptor arrays.
-  Map* current = this;
-  Map* meta_map = GetHeap()->meta_map();
-  Object** map_or_index_field = NULL;
-  while (current != meta_map) {
-    DescriptorArray* d = reinterpret_cast<DescriptorArray*>(
-        *RawField(current, Map::kInstanceDescriptorsOrBitField3Offset));
-    if (!d->IsEmpty()) {
-      FixedArray* contents = reinterpret_cast<FixedArray*>(
-          d->get(DescriptorArray::kContentArrayIndex));
-      map_or_index_field = RawField(contents, HeapObject::kMapOffset);
-      Object* map_or_index = *map_or_index_field;
-      bool map_done = true;  // Controls a nested continue statement.
-      for (int i = map_or_index->IsSmi() ? Smi::cast(map_or_index)->value() : 0;
-           i < contents->length();
-           i += 2) {
-        PropertyDetails details(Smi::cast(contents->get(i + 1)));
-        if (details.IsTransition()) {
-          // Found a map in the transition array.  We record our progress in
-          // the transition array by recording the current map in the map field
-          // of the next map and recording the index in the transition array in
-          // the map field of the array.
-          Map* next = Map::cast(contents->get(i));
-          next->set_map_no_write_barrier(current);
-          *map_or_index_field = Smi::FromInt(i + 2);
-          current = next;
-          map_done = false;
-          break;
-        }
-      }
-      if (!map_done) continue;
+  IntrusiveMapIterator it(this);
+  while (it.HasMore()) {
+    Map* child = it.NextUnvisitedChild();
+    if (child != NULL) {
+      it.DescendInto(child);
     } else {
-      map_or_index_field = NULL;
+      Map* map = it.Ascend();
+      callback(map, data);
     }
-    // That was the regular transitions, now for the prototype transitions.
-    FixedArray* prototype_transitions =
-        current->unchecked_prototype_transitions();
-    Object** proto_map_or_index_field =
-        RawField(prototype_transitions, HeapObject::kMapOffset);
-    Object* map_or_index = *proto_map_or_index_field;
-    const int start = kProtoTransitionHeaderSize + kProtoTransitionMapOffset;
-    int i = map_or_index->IsSmi() ? Smi::cast(map_or_index)->value() : start;
-    if (i < prototype_transitions->length()) {
-      // Found a map in the prototype transition array.  Record progress in
-      // an analogous way to the regular transitions array above.
-      Object* perhaps_map = prototype_transitions->get(i);
-      if (perhaps_map->IsMap()) {
-        Map* next = Map::cast(perhaps_map);
-        next->set_map_no_write_barrier(current);
-        *proto_map_or_index_field =
-            Smi::FromInt(i + kProtoTransitionElementsPerEntry);
-        current = next;
-        continue;
-      }
-    }
-    *proto_map_or_index_field = GetHeap()->fixed_array_map();
-    if (map_or_index_field != NULL) {
-      *map_or_index_field = GetHeap()->fixed_array_map();
-    }
-
-    // The callback expects a map to have a real map as its map, so we save
-    // the map field, which is being used to track the traversal and put the
-    // correct map (the meta_map) in place while we do the callback.
-    Map* prev = current->map();
-    current->set_map_no_write_barrier(meta_map);
-    callback(current, data);
-    current = prev;
   }
 }
 
 
 MaybeObject* CodeCache::Update(String* name, Code* code) {
   // The number of monomorphic stubs for normal load/store/call IC's can grow to
   // a large number and therefore they need to go into a hash table. They are
   // used to load global properties from cells.
   if (code->type() == NORMAL) {
     // Make sure that a hash table is allocated for the normal load code cache.
@@ skipping 7792 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single break point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif  // ENABLE_DEBUGGER_SUPPORT
 
 
 } }  // namespace v8::internal