Add Contains(), at(), and a constructor with raw addresses to UniqueSet<T> and Unique<T>.

src/unique.h

 // Copyright 2013 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 46 matching lines @@
   explicit Unique(Handle<T> handle) {
     if (handle.is_null()) {
       raw_address_ = NULL;
     } else {
       raw_address_ = reinterpret_cast<Address>(*handle);
       ASSERT_NE(raw_address_, NULL);
     }
     handle_ = handle;
   }
 
+  // TODO(titzer): this is a hack to migrate to Unique<T> incrementally.
+  Unique(Address raw_address, Handle<T> handle)
+    : raw_address_(raw_address), handle_(handle) { }
+
   // Constructor for handling automatic up casting.
   // Ex. Unique<JSFunction> can be passed when Unique<Object> is expected.
   template <class S> Unique(Unique<S> uniq) {
 #ifdef DEBUG
     T* a = NULL;
     S* b = NULL;
     a = b;  // Fake assignment to enforce type checks.
     USE(a);
 #endif
     raw_address_ = uniq.raw_address_;
@@ skipping 54 matching lines @@
         size_++;
         return;
       }
     }
     // Append the element to the the end.
     Grow(size_ + 1, zone);
     array_[size_++] = uniq;
   }
 
   // Compare this set against another set. O(|this|).
-  bool Equals(UniqueSet<T>* that) {
+  bool Equals(UniqueSet<T>* that) const {
     if (that->size_ != this->size_) return false;
     for (int i = 0; i < this->size_; i++) {
       if (this->array_[i] != that->array_[i]) return false;
     }
     return true;
   }
 
+  template <typename U>
+  bool Contains(Unique<U> elem) const {
+    // TODO(titzer): use binary search for larger sets.

[Toon Verwaest, 2013/09/13 11:20:49]

Maybe you want to add an ASSERT that size_ <= 8; or some other low upper bound?

+    for (int i = 0; i < size_; i++) {
+      if (this->array_[i] == elem) return true;
+    }
+    return false;
+  }
+
   // Check if this set is a subset of the given set. O(|this| + |that|).
-  bool IsSubset(UniqueSet<T>* that) {
+  bool IsSubset(UniqueSet<T>* that) const {
     if (that->size_ < this->size_) return false;
     int j = 0;
     for (int i = 0; i < this->size_; i++) {
       Unique<T> sought = this->array_[i];
       while (true) {
         if (sought == that->array_[j++]) break;
         // Fail whenever there are more elements in {this} than {that}.
         if ((this->size_ - i) > (that->size_ - j)) return false;
       }
     }
     return true;
   }
 
   // Returns a new set representing the intersection of this set and the other.
   // O(|this| + |that|).
-  UniqueSet<T>* Intersect(UniqueSet<T>* that, Zone* zone) {
+  UniqueSet<T>* Intersect(UniqueSet<T>* that, Zone* zone) const {
     if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet<T>();
 
     UniqueSet<T>* out = new(zone) UniqueSet<T>();
     out->Grow(Min(this->size_, that->size_), zone);
 
     int i = 0, j = 0, k = 0;
     while (i < this->size_ && j < that->size_) {
       Unique<T> a = this->array_[i];
       Unique<T> b = that->array_[j];
       if (a == b) {
         out->array_[k++] = a;
         i++;
         j++;
       } else if (a.raw_address_ < b.raw_address_) {
         i++;
       } else {
         j++;
       }
     }
 
     out->size_ = k;
     return out;
   }
 
   // Returns a new set representing the union of this set and the other.
   // O(|this| + |that|).
-  UniqueSet<T>* Union(UniqueSet<T>* that, Zone* zone) {
+  UniqueSet<T>* Union(UniqueSet<T>* that, Zone* zone) const {
     if (that->size_ == 0) return this->Copy(zone);
     if (this->size_ == 0) return that->Copy(zone);
 
     UniqueSet<T>* out = new(zone) UniqueSet<T>();
     out->Grow(this->size_ + that->size_, zone);
 
     int i = 0, j = 0, k = 0;
     while (i < this->size_ && j < that->size_) {
       Unique<T> a = this->array_[i];
       Unique<T> b = that->array_[j];
@@ skipping 11 matching lines @@
     }
 
     while (i < this->size_) out->array_[k++] = this->array_[i++];
     while (j < that->size_) out->array_[k++] = that->array_[j++];
 
     out->size_ = k;
     return out;
   }
 
   // Makes an exact copy of this set. O(|this| + |that|).
-  UniqueSet<T>* Copy(Zone* zone) {
+  UniqueSet<T>* Copy(Zone* zone) const {
     UniqueSet<T>* copy = new(zone) UniqueSet<T>();
     copy->size_ = this->size_;
     copy->capacity_ = this->size_;
     copy->array_ = zone->NewArray<Unique<T> >(this->size_);
     memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique<T>));
     return copy;
   }
 
-  inline int size() {
+  inline int size() const {
     return size_;
   }
 
+  inline Unique<T> at(int index) const {
+    ASSERT(index >= 0 && index < size_);
+    return array_[index];
+  }
+
  private:
   // These sets should be small, since operations are implemented with simple
   // linear algorithms. Enforce a maximum size.
   static const int kMaxCapacity = 65535;
 
   uint16_t size_;
   uint16_t capacity_;
   Unique<T>* array_;
 
   // Grow the size of internal storage to be at least {size} elements.
   void Grow(int size, Zone* zone) {
     CHECK(size < kMaxCapacity);  // Enforce maximum size.
     if (capacity_ < size) {
       int new_capacity = 2 * capacity_ + size;
       if (new_capacity > kMaxCapacity) new_capacity = kMaxCapacity;
       Unique<T>* new_array = zone->NewArray<Unique<T> >(new_capacity);
       if (size_ > 0) {
         memcpy(new_array, array_, size_ * sizeof(Unique<T>));
       }
       capacity_ = new_capacity;
       array_ = new_array;
     }
   }
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_UNIQUE_H_