261 for (Node* next = bucket->first(); next != NULL ; next = next->next()) { |
261 for (Node* next = bucket->first(); next != NULL ; next = next->next()) { |
262 if (pref != NULL) { |
262 if (pref != NULL) { |
263 Prefetch::read(*pref->value(), 0); |
263 Prefetch::read(*pref->value(), 0); |
264 pref = pref->next(); |
264 pref = pref->next(); |
265 } |
265 } |
266 if (next->next() != NULL) { |
266 // Read next() Node* once. May be racing with a thread moving the next |
267 Prefetch::read(*next->next()->value(), 0); |
267 // pointers. |
|
268 Node* next_pref = next->next(); |
|
269 if (next_pref != NULL) { |
|
270 Prefetch::read(*next_pref->value(), 0); |
268 } |
271 } |
269 if (eval_f(next->value())) { |
272 if (eval_f(next->value())) { |
270 return true; |
273 return true; |
271 } |
274 } |
272 } |
275 } |
544 while (rem_n != NULL) { |
547 while (rem_n != NULL) { |
545 bool is_dead = false; |
548 bool is_dead = false; |
546 lookup_f.equals(rem_n->value(), &is_dead); |
549 lookup_f.equals(rem_n->value(), &is_dead); |
547 if (is_dead) { |
550 if (is_dead) { |
548 ndel[dels++] = rem_n; |
551 ndel[dels++] = rem_n; |
549 bucket->release_assign_node_ptr(rem_n_prev, rem_n->next()); |
552 Node* next_node = rem_n->next(); |
550 rem_n = rem_n->next(); |
553 bucket->release_assign_node_ptr(rem_n_prev, next_node); |
|
554 rem_n = next_node; |
551 if (dels == BULK_DELETE_LIMIT) { |
555 if (dels == BULK_DELETE_LIMIT) { |
552 break; |
556 break; |
553 } |
557 } |
554 } else { |
558 } else { |
555 rem_n_prev = rem_n->next_ptr(); |
559 rem_n_prev = rem_n->next_ptr(); |
652 Node* const volatile * even = new_table->get_bucket(even_index)->first_ptr(); |
656 Node* const volatile * even = new_table->get_bucket(even_index)->first_ptr(); |
653 Node* const volatile * odd = new_table->get_bucket(odd_index)->first_ptr(); |
657 Node* const volatile * odd = new_table->get_bucket(odd_index)->first_ptr(); |
654 while (aux != NULL) { |
658 while (aux != NULL) { |
655 bool dead_hash = false; |
659 bool dead_hash = false; |
656 size_t aux_hash = CONFIG::get_hash(*aux->value(), &dead_hash); |
660 size_t aux_hash = CONFIG::get_hash(*aux->value(), &dead_hash); |
|
661 Node* aux_next = aux->next(); |
657 if (dead_hash) { |
662 if (dead_hash) { |
658 delete_me = aux; |
663 delete_me = aux; |
659 // This item is dead, move both list to next |
664 // This item is dead, move both list to next |
660 new_table->get_bucket(odd_index)->release_assign_node_ptr(odd, |
665 new_table->get_bucket(odd_index)->release_assign_node_ptr(odd, |
661 aux->next()); |
666 aux_next); |
662 new_table->get_bucket(even_index)->release_assign_node_ptr(even, |
667 new_table->get_bucket(even_index)->release_assign_node_ptr(even, |
663 aux->next()); |
668 aux_next); |
664 } else { |
669 } else { |
665 size_t aux_index = bucket_idx_hash(new_table, aux_hash); |
670 size_t aux_index = bucket_idx_hash(new_table, aux_hash); |
666 if (aux_index == even_index) { |
671 if (aux_index == even_index) { |
667 // This is a even, so move odd to aux/even next |
672 // This is a even, so move odd to aux/even next |
668 new_table->get_bucket(odd_index)->release_assign_node_ptr(odd, |
673 new_table->get_bucket(odd_index)->release_assign_node_ptr(odd, |
669 aux->next()); |
674 aux_next); |
670 // Keep in even list |
675 // Keep in even list |
671 even = aux->next_ptr(); |
676 even = aux->next_ptr(); |
672 } else if (aux_index == odd_index) { |
677 } else if (aux_index == odd_index) { |
673 // This is a odd, so move odd to aux/odd next |
678 // This is a odd, so move odd to aux/odd next |
674 new_table->get_bucket(even_index)->release_assign_node_ptr(even, |
679 new_table->get_bucket(even_index)->release_assign_node_ptr(even, |
675 aux->next()); |
680 aux_next); |
676 // Keep in odd list |
681 // Keep in odd list |
677 odd = aux->next_ptr(); |
682 odd = aux->next_ptr(); |
678 } else { |
683 } else { |
679 fatal("aux_index does not match even or odd indices"); |
684 fatal("aux_index does not match even or odd indices"); |
680 } |
685 } |
681 } |
686 } |
682 aux = aux->next(); |
687 aux = aux_next; |
683 |
688 |
684 // We can only move 1 pointer otherwise a reader might be moved to the wrong |
689 // We can only move 1 pointer otherwise a reader might be moved to the wrong |
685 // chain. E.g. looking for even hash value but got moved to the odd bucket |
690 // chain. E.g. looking for even hash value but got moved to the odd bucket |
686 // chain. |
691 // chain. |
687 write_synchonize_on_visible_epoch(thread); |
692 write_synchonize_on_visible_epoch(thread); |
974 Node* const volatile * rem_n_prev = bucket->first_ptr(); |
979 Node* const volatile * rem_n_prev = bucket->first_ptr(); |
975 Node* rem_n = bucket->first(); |
980 Node* rem_n = bucket->first(); |
976 while (rem_n != NULL) { |
981 while (rem_n != NULL) { |
977 if (eval_f(rem_n->value())) { |
982 if (eval_f(rem_n->value())) { |
978 ndel[dels++] = rem_n; |
983 ndel[dels++] = rem_n; |
979 bucket->release_assign_node_ptr(rem_n_prev, rem_n->next()); |
984 Node* next_node = rem_n->next(); |
980 rem_n = rem_n->next(); |
985 bucket->release_assign_node_ptr(rem_n_prev, next_node); |
|
986 rem_n = next_node; |
981 if (dels == num_del) { |
987 if (dels == num_del) { |
982 break; |
988 break; |
983 } |
989 } |
984 } else { |
990 } else { |
985 rem_n_prev = rem_n->next_ptr(); |
991 rem_n_prev = rem_n->next_ptr(); |