OLD | NEW |
1 // Copyright 2006-2009 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2009 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 7320 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7331 while (true) { | 7331 while (true) { |
7332 Object* element = KeyAt(entry); | 7332 Object* element = KeyAt(entry); |
7333 if (element->IsUndefined()) break; // Empty entry. | 7333 if (element->IsUndefined()) break; // Empty entry. |
7334 if (!element->IsNull() && Shape::IsMatch(key, element)) return entry; | 7334 if (!element->IsNull() && Shape::IsMatch(key, element)) return entry; |
7335 entry = NextProbe(entry, count++, capacity); | 7335 entry = NextProbe(entry, count++, capacity); |
7336 } | 7336 } |
7337 return kNotFound; | 7337 return kNotFound; |
7338 } | 7338 } |
7339 | 7339 |
7340 | 7340 |
| 7341 // Find entry for key otherwise return kNotFound. |
| 7342 int StringDictionary::FindEntry(String* key) { |
| 7343 if (!key->IsSymbol()) { |
| 7344 return HashTable<StringDictionaryShape, String*>::FindEntry(key); |
| 7345 } |
| 7346 |
| 7347 // Optimized for symbol key. Knowledge of the key type allows: |
| 7348 // 1. Move the check if the key is a symbol out of the loop. |
| 7349 // 2. Avoid comparing hash codes in symbol to symbol comparision. |
| 7350 // 3. Detect a case when a dictionary key is not a symbol but the key is. |
| 7351 // In case of positive result the dictionary key may be replaced by |
| 7352 // the symbol with minimal performance penalty. It gives a chance to |
| 7353 // perform further lookups in code stubs (and significant performance boost |
| 7354 // a certain style of code). |
| 7355 |
| 7356 // EnsureCapacity will guarantee the hash table is never full. |
| 7357 uint32_t capacity = Capacity(); |
| 7358 uint32_t entry = FirstProbe(key->Hash(), capacity); |
| 7359 uint32_t count = 1; |
| 7360 |
| 7361 while (true) { |
| 7362 int index = EntryToIndex(entry); |
| 7363 Object* element = get(index); |
| 7364 if (element->IsUndefined()) break; // Empty entry. |
| 7365 if (key == element) return entry; |
| 7366 if (!element->IsSymbol() && |
| 7367 !element->IsNull() && |
| 7368 String::cast(element)->Equals(key)) { |
| 7369 // Replace a non-symbol key by the equivalent symbol for faster further |
| 7370 // lookups. |
| 7371 set(index, key); |
| 7372 return entry; |
| 7373 } |
| 7374 ASSERT(element->IsNull() || !String::cast(element)->Equals(key)); |
| 7375 entry = NextProbe(entry, count++, capacity); |
| 7376 } |
| 7377 return kNotFound; |
| 7378 } |
| 7379 |
| 7380 |
7341 template<typename Shape, typename Key> | 7381 template<typename Shape, typename Key> |
7342 Object* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) { | 7382 Object* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) { |
7343 int capacity = Capacity(); | 7383 int capacity = Capacity(); |
7344 int nof = NumberOfElements() + n; | 7384 int nof = NumberOfElements() + n; |
7345 int nod = NumberOfDeletedElements(); | 7385 int nod = NumberOfDeletedElements(); |
7346 // Return if: | 7386 // Return if: |
7347 // 50% is still free after adding n elements and | 7387 // 50% is still free after adding n elements and |
7348 // at most 50% of the free elements are deleted elements. | 7388 // at most 50% of the free elements are deleted elements. |
7349 if (nod <= (capacity - nof) >> 1) { | 7389 if (nod <= (capacity - nof) >> 1) { |
7350 int needed_free = nof >> 1; | 7390 int needed_free = nof >> 1; |
(...skipping 1418 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
8769 if (break_point_objects()->IsUndefined()) return 0; | 8809 if (break_point_objects()->IsUndefined()) return 0; |
8770 // Single beak point. | 8810 // Single beak point. |
8771 if (!break_point_objects()->IsFixedArray()) return 1; | 8811 if (!break_point_objects()->IsFixedArray()) return 1; |
8772 // Multiple break points. | 8812 // Multiple break points. |
8773 return FixedArray::cast(break_point_objects())->length(); | 8813 return FixedArray::cast(break_point_objects())->length(); |
8774 } | 8814 } |
8775 #endif | 8815 #endif |
8776 | 8816 |
8777 | 8817 |
8778 } } // namespace v8::internal | 8818 } } // namespace v8::internal |
OLD | NEW |