Mercurial > hg > truffle
comparison src/share/vm/utilities/growableArray.hpp @ 17375:44b83285b645
Deduplicate constant oops during code installation
| author | Tom Rodriguez <tom.rodriguez@oracle.com> |
|---|---|
| date | Wed, 08 Oct 2014 11:50:00 -0700 |
| parents | 4ca6dc0799b6 |
| children | 89152779163c |
comparison
equal
deleted
inserted
replaced
| 17374:9928ad27a80e | 17375:44b83285b645 |
|---|---|
| 358 } | 358 } |
| 359 // sort by fixed-stride sub arrays: | 359 // sort by fixed-stride sub arrays: |
| 360 void sort(int f(E*,E*), int stride) { | 360 void sort(int f(E*,E*), int stride) { |
| 361 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f); | 361 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f); |
| 362 } | 362 } |
| 363 | |
| 364 // Binary search and insertion utility. Search array for element | |
| 365 // matching key according to the static compare function. Insert | |
| 366 // that element is not already in the list. Assumes the list is | |
| 367 // already sorted according to compare function. | |
| 368 template <int compare(E, E)> E find_insert_binary(E key) { | |
| 369 bool found; | |
| 370 int location = find_binary<E, compare>(key, found); | |
| 371 if (!found) { | |
| 372 assert(location <= length(), "out of range"); | |
| 373 insert_binary(location, key); | |
| 374 } | |
| 375 return at(location); | |
| 376 } | |
| 377 | |
| 378 template <typename K, int compare(K, E)> int find_binary(K key, bool& found) { | |
| 379 found = false; | |
| 380 int min = 0; | |
| 381 int max = length() - 1; | |
| 382 | |
| 383 while (max >= min) { | |
| 384 int mid = (max + min) / 2; | |
| 385 E value = at(mid); | |
| 386 int diff = compare(key, value); | |
| 387 if (diff > 0) { | |
| 388 min = mid + 1; | |
| 389 } else if (diff < 0) { | |
| 390 max = mid - 1; | |
| 391 } else { | |
| 392 found = true; | |
| 393 return mid; | |
| 394 } | |
| 395 } | |
| 396 return min; | |
| 397 } | |
| 398 | |
| 399 // Insert a new element at location, moving values as needed. | |
| 400 void insert_binary(int location, E element) { | |
| 401 int len = length(); | |
| 402 if (len == location) { | |
| 403 append(element); | |
| 404 } else { | |
| 405 append(at(len-1)); | |
| 406 int pos; | |
| 407 for (pos = len-2; pos >= location; pos--) { | |
| 408 at_put(pos+1, at(pos)); | |
| 409 } | |
| 410 at_put(location, element); | |
| 411 } | |
| 412 } | |
| 363 }; | 413 }; |
| 364 | 414 |
| 365 // Global GrowableArray methods (one instance in the library per each 'E' type). | 415 // Global GrowableArray methods (one instance in the library per each 'E' type). |
| 366 | 416 |
| 367 template<class E> void GrowableArray<E>::grow(int j) { | 417 template<class E> void GrowableArray<E>::grow(int j) { |