|
1 | | -/* Copyright (c) 2006, 2010, Oracle and/or its affiliates. All rights reserved. |
| 1 | +/* Copyright (c) 2006, 2015, Oracle and/or its affiliates. All rights reserved. |
2 | 2 |
|
3 | 3 | This program is free software; you can redistribute it and/or modify |
4 | 4 | it under the terms of the GNU General Public License as published by |
@@ -503,3 +503,187 @@ static int initialize_bucket(LF_HASH *hash, LF_SLIST * volatile *node, |
503 | 503 | */ |
504 | 504 | return 0; |
505 | 505 | } |
| 506 | + |
| 507 | +/** |
| 508 | + Search for list element satisfying condition specified by match |
| 509 | + function and position cursor on it. |
| 510 | +
|
| 511 | + @param head Head of the list to search in. |
| 512 | + @param first_hashnr Hash value to start search from. |
| 513 | + @param last_hashnr Hash value to stop search after. |
| 514 | + @param match Match function. |
| 515 | + @param cursor Cursor to be position. |
| 516 | + @param pins LF_PINS for the calling thread to be used during |
| 517 | + search for pinning result. |
| 518 | +
|
| 519 | + @retval 0 - not found |
| 520 | + @retval 1 - found |
| 521 | +*/ |
| 522 | + |
| 523 | +static int lfind_match(LF_SLIST * volatile *head, |
| 524 | + uint32 first_hashnr, uint32 last_hashnr, |
| 525 | + lf_hash_match_func *match, |
| 526 | + CURSOR *cursor, LF_PINS *pins) |
| 527 | +{ |
| 528 | + uint32 cur_hashnr; |
| 529 | + intptr link; |
| 530 | + |
| 531 | +retry: |
| 532 | + cursor->prev= (intptr *)head; |
| 533 | + do { /* PTR() isn't necessary below, head is a dummy node */ |
| 534 | + cursor->curr= (LF_SLIST *)(*cursor->prev); |
| 535 | + lf_pin(pins, 1, cursor->curr); |
| 536 | + } while (*cursor->prev != (intptr)cursor->curr && LF_BACKOFF); |
| 537 | + for (;;) |
| 538 | + { |
| 539 | + if (unlikely(!cursor->curr)) |
| 540 | + return 0; /* end of the list */ |
| 541 | + do { |
| 542 | + /* QQ: XXX or goto retry ? */ |
| 543 | + link= cursor->curr->link; |
| 544 | + cursor->next= PTR(link); |
| 545 | + lf_pin(pins, 0, cursor->next); |
| 546 | + } while (link != cursor->curr->link && LF_BACKOFF); |
| 547 | + cur_hashnr= cursor->curr->hashnr; |
| 548 | + if (*cursor->prev != (intptr)cursor->curr) |
| 549 | + { |
| 550 | + (void)LF_BACKOFF; |
| 551 | + goto retry; |
| 552 | + } |
| 553 | + if (!DELETED(link)) |
| 554 | + { |
| 555 | + if (cur_hashnr >= first_hashnr) |
| 556 | + { |
| 557 | + if (cur_hashnr > last_hashnr) |
| 558 | + return 0; |
| 559 | + |
| 560 | + if (cur_hashnr & 1) |
| 561 | + { |
| 562 | + /* Normal node. Check if element matches condition. */ |
| 563 | + if ((*match)((uchar *)(cursor->curr + 1))) |
| 564 | + return 1; |
| 565 | + } |
| 566 | + else |
| 567 | + { |
| 568 | + /* |
| 569 | + Dummy node. Nothing to check here. |
| 570 | +
|
| 571 | + Still thanks to the fact that dummy nodes are never deleted we |
| 572 | + can save it as a safe place to restart iteration if ever needed. |
| 573 | + */ |
| 574 | + head= (LF_SLIST * volatile *)&(cursor->curr->link); |
| 575 | + } |
| 576 | + } |
| 577 | + |
| 578 | + cursor->prev= &(cursor->curr->link); |
| 579 | + lf_pin(pins, 2, cursor->curr); |
| 580 | + } |
| 581 | + else |
| 582 | + { |
| 583 | + /* |
| 584 | + we found a deleted node - be nice, help the other thread |
| 585 | + and remove this deleted node |
| 586 | + */ |
| 587 | + if (my_atomic_casptr((void **)cursor->prev, |
| 588 | + (void **)&cursor->curr, cursor->next)) |
| 589 | + lf_pinbox_free(pins, cursor->curr); |
| 590 | + else |
| 591 | + { |
| 592 | + (void)LF_BACKOFF; |
| 593 | + goto retry; |
| 594 | + } |
| 595 | + } |
| 596 | + cursor->curr= cursor->next; |
| 597 | + lf_pin(pins, 1, cursor->curr); |
| 598 | + } |
| 599 | +} |
| 600 | + |
| 601 | +/** |
| 602 | + Find random hash element which satisfies condition specified by |
| 603 | + match function. |
| 604 | +
|
| 605 | + @param hash Hash to search element in. |
| 606 | + @param pin Pins for calling thread to be used during search |
| 607 | + and for pinning its result. |
| 608 | + @param match Pointer to match function. This function takes |
| 609 | + pointer to object stored in hash as parameter |
| 610 | + and returns 0 if object doesn't satisfy its |
| 611 | + condition (and non-0 value if it does). |
| 612 | + @param rand_val Random value to be used for selecting hash |
| 613 | + bucket from which search in sort-ordered |
| 614 | + list needs to be started. |
| 615 | +
|
| 616 | + @retval A pointer to a random element matching condition. |
| 617 | + @retval NULL - if nothing is found |
| 618 | + @retval MY_ERRPTR - OOM. |
| 619 | +
|
| 620 | + @note This function follows the same pinning protocol as lf_hash_search(), |
| 621 | + i.e. uses pins[0..2]. On return pins[0..1] are removed and pins[2] |
| 622 | + is used to pin object found. It is also not removed in case when |
| 623 | + object is not found/error occurs but its value is undefined in |
| 624 | + this case. |
| 625 | + So calling lf_hash_unpin() is mandatory after call to this function |
| 626 | + in case of both success and failure. |
| 627 | +*/ |
| 628 | + |
| 629 | +void *lf_hash_random_match(LF_HASH *hash, LF_PINS *pins, |
| 630 | + lf_hash_match_func *match, |
| 631 | + uint rand_val) |
| 632 | +{ |
| 633 | + /* Convert random value to valid hash value. */ |
| 634 | + uint hashnr= (rand_val & INT_MAX32); |
| 635 | + uint bucket; |
| 636 | + uint32 rev_hashnr; |
| 637 | + LF_SLIST * volatile *el; |
| 638 | + CURSOR cursor; |
| 639 | + int res; |
| 640 | + |
| 641 | + bucket= hashnr % hash->size; |
| 642 | + rev_hashnr= my_reverse_bits(hashnr); |
| 643 | + |
| 644 | + el= lf_dynarray_lvalue(&hash->array, bucket); |
| 645 | + if (unlikely(!el)) |
| 646 | + return MY_ERRPTR; |
| 647 | + /* |
| 648 | + Bucket might be totally empty if it has not been accessed since last |
| 649 | + time LF_HASH::size has been increased. In this case we initialize it |
| 650 | + by inserting dummy node for this bucket to the correct position in |
| 651 | + split-ordered list. This should help future lf_hash_* calls trying to |
| 652 | + access the same bucket. |
| 653 | + */ |
| 654 | + if (*el == NULL && unlikely(initialize_bucket(hash, el, bucket, pins))) |
| 655 | + return MY_ERRPTR; |
| 656 | + |
| 657 | + /* |
| 658 | + To avoid bias towards the first matching element in the bucket, we start |
| 659 | + looking for elements with inversed hash value greater or equal than |
| 660 | + inversed value of our random hash. |
| 661 | + */ |
| 662 | + res= lfind_match(el, rev_hashnr | 1, UINT_MAX32, match, &cursor, pins); |
| 663 | + |
| 664 | + if (! res && hashnr != 0) |
| 665 | + { |
| 666 | + /* |
| 667 | + We have not found matching element - probably we were too close to |
| 668 | + the tail of our split-ordered list. To avoid bias against elements |
| 669 | + at the head of the list we restart our search from its head. Unless |
| 670 | + we were already searching from it. |
| 671 | +
|
| 672 | + To avoid going through elements at which we have already looked |
| 673 | + twice we stop once we reach element from which we have begun our |
| 674 | + first search. |
| 675 | + */ |
| 676 | + el= lf_dynarray_lvalue(&hash->array, 0); |
| 677 | + if (unlikely(!el)) |
| 678 | + return MY_ERRPTR; |
| 679 | + res= lfind_match(el, 1, rev_hashnr, match, &cursor, pins); |
| 680 | + } |
| 681 | + |
| 682 | + if (res) |
| 683 | + lf_pin(pins, 2, cursor.curr); |
| 684 | + lf_unpin(pins, 0); |
| 685 | + lf_unpin(pins, 1); |
| 686 | + |
| 687 | + return res ? cursor.curr + 1 : 0; |
| 688 | +} |
| 689 | + |
0 commit comments