Mercurial > hg > graal-jvmci-8
comparison src/share/vm/utilities/growableArray.hpp @ 22549:f39ccee58e7a
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) { |