Mercurial > hg > graal-jvmci-8

comparison src/share/vm/utilities/growableArray.hpp @ 22549:f39ccee58e7a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
cleanup GrowableArray sorted find and insert
author Tom Rodriguez <tom.rodriguez@oracle.com>
date Thu, 10 Sep 2015 16:25:32 -0700
parents 7848fc12602b
children
comparison
equal deleted inserted replaced
22548:02fc27dc1da7 22549:f39ccee58e7a
375 375
376 // Binary search and insertion utility. Search array for element 376 // Binary search and insertion utility. Search array for element
377 // matching key according to the static compare function. Insert 377 // matching key according to the static compare function. Insert
378 // that element is not already in the list. Assumes the list is 378 // that element is not already in the list. Assumes the list is
379 // already sorted according to compare function. 379 // already sorted according to compare function.
380 template <int compare(E, E)> E find_insert_binary(E key) { 380 template <int compare(E&, E&)> E insert_sorted(E& key) {
381 bool found; 381 bool found;
382 int location = find_binary<E, compare>(key, found); 382 int location = find_sorted<E, compare>(key, found);
383 if (!found) { 383 if (!found) {
384 assert(location <= length(), "out of range"); 384 assert(location <= length(), "out of range");
385 insert_binary(location, key); 385 insert_before(location, key);
386 } 386 }
387 return at(location); 387 return at(location);
388 } 388 }
389 389
390 template <typename K, int compare(K, E)> int find_binary(K key, bool& found) { 390 template <typename K, int compare(K&, E&)> int find_sorted(K& key, bool& found) {
391 found = false; 391 found = false;
392 int min = 0; 392 int min = 0;
393 int max = length() - 1; 393 int max = length() - 1;
394 394
395 while (max >= min) { 395 while (max >= min) {
405 return mid; 405 return mid;
406 } 406 }
407 } 407 }
408 return min; 408 return min;
409 } 409 }
410
411 // Insert a new element at location, moving values as needed.
412 void insert_binary(int location, E element) {
413 int len = length();
414 if (len == location) {
415 append(element);
416 } else {
417 append(at(len-1));
418 int pos;
419 for (pos = len-2; pos >= location; pos--) {
420 at_put(pos+1, at(pos));
421 }
422 at_put(location, element);
423 }
424 }
425 }; 410 };
426 411
427 // Global GrowableArray methods (one instance in the library per each 'E' type). 412 // Global GrowableArray methods (one instance in the library per each 'E' type).
428 413
429 template<class E> void GrowableArray<E>::grow(int j) { 414 template<class E> void GrowableArray<E>::grow(int j) {