874 } |
874 } |
875 |
875 |
876 template <typename VALUE, typename CONFIG, MEMFLAGS F> |
876 template <typename VALUE, typename CONFIG, MEMFLAGS F> |
877 template <typename LOOKUP_FUNC, typename VALUE_FUNC, typename CALLBACK_FUNC> |
877 template <typename LOOKUP_FUNC, typename VALUE_FUNC, typename CALLBACK_FUNC> |
878 inline bool ConcurrentHashTable<VALUE, CONFIG, F>:: |
878 inline bool ConcurrentHashTable<VALUE, CONFIG, F>:: |
879 internal_insert(Thread* thread, LOOKUP_FUNC& lookup_f, VALUE_FUNC& value_f, |
879 internal_get_insert(Thread* thread, LOOKUP_FUNC& lookup_f, VALUE_FUNC& value_f, |
880 CALLBACK_FUNC& callback, bool* grow_hint, bool* clean_hint) |
880 CALLBACK_FUNC& callback_f, bool* grow_hint, bool* clean_hint) |
881 { |
881 { |
882 bool ret = false; |
882 bool ret = false; |
883 bool clean = false; |
883 bool clean = false; |
884 bool locked; |
884 bool locked; |
885 size_t loops = 0; |
885 size_t loops = 0; |
899 new_node = Node::create_node(value_f(), first_at_start); |
899 new_node = Node::create_node(value_f(), first_at_start); |
900 } else { |
900 } else { |
901 new_node->set_next(first_at_start); |
901 new_node->set_next(first_at_start); |
902 } |
902 } |
903 if (bucket->cas_first(new_node, first_at_start)) { |
903 if (bucket->cas_first(new_node, first_at_start)) { |
904 callback(true, new_node->value()); |
904 callback_f(true, new_node->value()); |
905 new_node = NULL; |
905 new_node = NULL; |
906 ret = true; |
906 ret = true; |
907 break; /* leave critical section */ |
907 break; /* leave critical section */ |
908 } |
908 } |
909 // CAS failed we must leave critical section and retry. |
909 // CAS failed we must leave critical section and retry. |
910 locked = bucket->is_locked(); |
910 locked = bucket->is_locked(); |
911 } else { |
911 } else { |
912 // There is a duplicate. |
912 // There is a duplicate. |
913 callback(false, old->value()); |
913 callback_f(false, old->value()); |
914 break; /* leave critical section */ |
914 break; /* leave critical section */ |
915 } |
915 } |
916 } /* leave critical section */ |
916 } /* leave critical section */ |
917 i++; |
917 i++; |
918 if (locked) { |
918 if (locked) { |
929 // We only do cleaning on fast inserts. |
929 // We only do cleaning on fast inserts. |
930 Bucket* bucket = get_bucket_locked(thread, lookup_f.get_hash()); |
930 Bucket* bucket = get_bucket_locked(thread, lookup_f.get_hash()); |
931 delete_in_bucket(thread, bucket, lookup_f); |
931 delete_in_bucket(thread, bucket, lookup_f); |
932 bucket->unlock(); |
932 bucket->unlock(); |
933 |
933 |
|
934 clean = false; |
|
935 } |
|
936 |
|
937 if (grow_hint != NULL) { |
|
938 *grow_hint = loops > _grow_hint; |
|
939 } |
|
940 |
|
941 if (clean_hint != NULL) { |
|
942 *clean_hint = clean; |
|
943 } |
|
944 |
|
945 return ret; |
|
946 } |
|
947 |
|
948 template <typename VALUE, typename CONFIG, MEMFLAGS F> |
|
949 template <typename LOOKUP_FUNC> |
|
950 inline bool ConcurrentHashTable<VALUE, CONFIG, F>:: |
|
951 internal_insert(Thread* thread, LOOKUP_FUNC& lookup_f, const VALUE& value, |
|
952 bool* grow_hint, bool* clean_hint) |
|
953 { |
|
954 bool ret = false; |
|
955 bool clean = false; |
|
956 bool locked; |
|
957 size_t loops = 0; |
|
958 size_t i = 0; |
|
959 uintx hash = lookup_f.get_hash(); |
|
960 Node* new_node = Node::create_node(value, NULL); |
|
961 |
|
962 while (true) { |
|
963 { |
|
964 ScopedCS cs(thread, this); /* protected the table/bucket */ |
|
965 Bucket* bucket = get_bucket(hash); |
|
966 Node* first_at_start = bucket->first(); |
|
967 Node* old = get_node(bucket, lookup_f, &clean, &loops); |
|
968 if (old == NULL) { |
|
969 new_node->set_next(first_at_start); |
|
970 if (bucket->cas_first(new_node, first_at_start)) { |
|
971 new_node = NULL; |
|
972 ret = true; |
|
973 break; /* leave critical section */ |
|
974 } |
|
975 // CAS failed we must leave critical section and retry. |
|
976 locked = bucket->is_locked(); |
|
977 } else { |
|
978 // There is a duplicate. |
|
979 break; /* leave critical section */ |
|
980 } |
|
981 } /* leave critical section */ |
|
982 i++; |
|
983 if (locked) { |
|
984 os::naked_yield(); |
|
985 } else { |
|
986 SpinPause(); |
|
987 } |
|
988 } |
|
989 |
|
990 if (new_node != NULL) { |
|
991 // CAS failed and a duplicate was inserted, we must free this node. |
|
992 Node::destroy_node(new_node); |
|
993 } else if (i == 0 && clean) { |
|
994 // We only do cleaning on fast inserts. |
|
995 Bucket* bucket = get_bucket_locked(thread, lookup_f.get_hash()); |
|
996 delete_in_bucket(thread, bucket, lookup_f); |
|
997 bucket->unlock(); |
934 clean = false; |
998 clean = false; |
935 } |
999 } |
936 |
1000 |
937 if (grow_hint != NULL) { |
1001 if (grow_hint != NULL) { |
938 *grow_hint = loops > _grow_hint; |
1002 *grow_hint = loops > _grow_hint; |