src/share/vm/utilities/growableArray.hpp

@@ -166,10 +166,14 @@
   }
 
   GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
     : GenericGrowableArray(initial_size, 0, C_heap, F) {
     _data = (E*)raw_allocate(sizeof(E));
+// Needed for Visual Studio 2012 and older
+#ifdef _MSC_VER
+#pragma warning(suppress: 4345)
+#endif
     for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
   }
 
   GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
     : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {

@@ -370,10 +374,44 @@
   }
   // sort by fixed-stride sub arrays:
   void sort(int f(E*,E*), int stride) {
     qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
   }
+
+  // Binary search and insertion utility.  Search array for element
+  // matching key according to the static compare function.  Insert
+  // that element is not already in the list.  Assumes the list is
+  // already sorted according to compare function.
+  template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
+    bool found;
+    int location = find_sorted<E, compare>(key, found);
+    if (!found) {
+      insert_before(location, key);
+    }
+    return at(location);
+  }
+
+  template <typename K, int compare(const K&, const E&)> int find_sorted(const K& key, bool& found) {
+    found = false;
+    int min = 0;
+    int max = length() - 1;
+
+    while (max >= min) {
+      int mid = (int)(((uint)max + min) / 2);
+      E value = at(mid);
+      int diff = compare(key, value);
+      if (diff > 0) {
+        min = mid + 1;
+      } else if (diff < 0) {
+        max = mid - 1;
+      } else {
+        found = true;
+        return mid;
+      }
+    }
+    return min;
+  }
 };
 
 // Global GrowableArray methods (one instance in the library per each 'E' type).
 
 template<class E> void GrowableArray<E>::grow(int j) {

@@ -383,10 +421,14 @@
     while (j >= _max) _max = _max*2;
     // j < _max
     E* newData = (E*)raw_allocate(sizeof(E));
     int i = 0;
     for (     ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
+// Needed for Visual Studio 2012 and older
+#ifdef _MSC_VER
+#pragma warning(suppress: 4345)
+#endif
     for (     ; i < _max; i++) ::new ((void*)&newData[i]) E();
     for (i = 0; i < old_max; i++) _data[i].~E();
     if (on_C_heap() && _data != NULL) {
       FreeHeap(_data);
     }