@@ -875,69 +875,37 @@ lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
875
875
Py_UNREACHABLE ();
876
876
}
877
877
878
- // Search non-Unicode key from Unicode table
879
- static Py_ssize_t
880
- unicodekeys_lookup_generic (PyDictObject * mp , PyDictKeysObject * dk , PyObject * key , Py_hash_t hash )
878
+ typedef void * (* generic_entries_func )(PyDictKeysObject * dk );
879
+
880
+ static inline Py_ALWAYS_INLINE Py_ssize_t
881
+ do_lookup (PyDictObject * mp , PyDictKeysObject * dk , PyObject * key , Py_hash_t hash ,
882
+ generic_entries_func entries ,
883
+ Py_ssize_t (* check_lookup )(PyDictObject * , PyDictKeysObject * , void * , Py_ssize_t ix , PyObject * key , Py_hash_t ))
881
884
{
882
- PyDictUnicodeEntry * ep0 = DK_UNICODE_ENTRIES (dk );
885
+ void * ep0 = entries (dk );
883
886
size_t mask = DK_MASK (dk );
884
887
size_t perturb = hash ;
885
888
size_t i = (size_t )hash & mask ;
886
889
Py_ssize_t ix ;
887
890
for (;;) {
888
891
ix = dictkeys_get_index (dk , i );
889
892
if (ix >= 0 ) {
890
- PyDictUnicodeEntry * ep = & ep0 [ix ];
891
- assert (ep -> me_key != NULL );
892
- assert (PyUnicode_CheckExact (ep -> me_key ));
893
- if (ep -> me_key == key ) {
893
+ ix = check_lookup (mp , dk , ep0 , ix , key , hash );
894
+ if (ix != DKIX_DUMMY ) {
894
895
return ix ;
895
896
}
896
- if (unicode_get_hash (ep -> me_key ) == hash ) {
897
- PyObject * startkey = ep -> me_key ;
898
- Py_INCREF (startkey );
899
- int cmp = PyObject_RichCompareBool (startkey , key , Py_EQ );
900
- Py_DECREF (startkey );
901
- if (cmp < 0 ) {
902
- return DKIX_ERROR ;
903
- }
904
- if (dk == mp -> ma_keys && ep -> me_key == startkey ) {
905
- if (cmp > 0 ) {
906
- return ix ;
907
- }
908
- }
909
- else {
910
- /* The dict was mutated, restart */
911
- return DKIX_KEY_CHANGED ;
912
- }
913
- }
914
897
}
915
898
else if (ix == DKIX_EMPTY ) {
916
899
return DKIX_EMPTY ;
917
900
}
918
901
perturb >>= PERTURB_SHIFT ;
919
902
i = mask & (i * 5 + perturb + 1 );
920
- }
921
- Py_UNREACHABLE ();
922
- }
923
903
924
- // Search Unicode key from Unicode table.
925
- static Py_ssize_t _Py_HOT_FUNCTION
926
- unicodekeys_lookup_unicode (PyDictKeysObject * dk , PyObject * key , Py_hash_t hash )
927
- {
928
- PyDictUnicodeEntry * ep0 = DK_UNICODE_ENTRIES (dk );
929
- size_t mask = DK_MASK (dk );
930
- size_t perturb = hash ;
931
- size_t i = (size_t )hash & mask ;
932
- Py_ssize_t ix ;
933
- for (;;) {
904
+ // Manual loop unrolling
934
905
ix = dictkeys_get_index (dk , i );
935
906
if (ix >= 0 ) {
936
- PyDictUnicodeEntry * ep = & ep0 [ix ];
937
- assert (ep -> me_key != NULL );
938
- assert (PyUnicode_CheckExact (ep -> me_key ));
939
- if (ep -> me_key == key ||
940
- (unicode_get_hash (ep -> me_key ) == hash && unicode_eq (ep -> me_key , key ))) {
907
+ ix = check_lookup (mp , dk , ep0 , ix , key , hash );
908
+ if (ix != DKIX_DUMMY ) {
941
909
return ix ;
942
910
}
943
911
}
@@ -946,69 +914,102 @@ unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
946
914
}
947
915
perturb >>= PERTURB_SHIFT ;
948
916
i = mask & (i * 5 + perturb + 1 );
949
- // Manual loop unrolling
950
- ix = dictkeys_get_index (dk , i );
951
- if (ix >= 0 ) {
952
- PyDictUnicodeEntry * ep = & ep0 [ix ];
953
- assert (ep -> me_key != NULL );
954
- assert (PyUnicode_CheckExact (ep -> me_key ));
955
- if (ep -> me_key == key ||
956
- (unicode_get_hash (ep -> me_key ) == hash && unicode_eq (ep -> me_key , key ))) {
917
+ }
918
+ Py_UNREACHABLE ();
919
+ }
920
+
921
+ static inline Py_ALWAYS_INLINE
922
+ Py_ssize_t compare_unicode_generic (PyDictObject * mp , PyDictKeysObject * dk ,
923
+ void * ep0 , Py_ssize_t ix , PyObject * key , Py_hash_t hash )
924
+ {
925
+ PyDictUnicodeEntry * ep = & ((PyDictUnicodeEntry * )ep0 )[ix ];
926
+ assert (ep -> me_key != NULL );
927
+ assert (PyUnicode_CheckExact (ep -> me_key ));
928
+ assert (!PyUnicode_CheckExact (key ));
929
+ // TODO: Thread safety
930
+
931
+ if (unicode_get_hash (ep -> me_key ) == hash ) {
932
+ PyObject * startkey = ep -> me_key ;
933
+ Py_INCREF (startkey );
934
+ int cmp = PyObject_RichCompareBool (startkey , key , Py_EQ );
935
+ Py_DECREF (startkey );
936
+ if (cmp < 0 ) {
937
+ return DKIX_ERROR ;
938
+ }
939
+ if (dk == mp -> ma_keys && ep -> me_key == startkey ) {
940
+ if (cmp > 0 ) {
957
941
return ix ;
958
942
}
959
943
}
960
- else if (ix == DKIX_EMPTY ) {
961
-
F438
return DKIX_EMPTY ;
944
+ else {
945
+ /* The dict was mutated, restart */
946
+ return DKIX_KEY_CHANGED ;
962
947
}
963
- perturb >>= PERTURB_SHIFT ;
964
- i = mask & (i * 5 + perturb + 1 );
965
948
}
966
- Py_UNREACHABLE () ;
949
+ return DKIX_DUMMY ;
967
950
}
968
951
969
- // Search key from Generic table.
952
+ // Search non-Unicode key from Unicode table
970
953
static Py_ssize_t
971
- dictkeys_generic_lookup (PyDictObject * mp , PyDictKeysObject * dk , PyObject * key , Py_hash_t hash )
954
+ unicodekeys_lookup_generic (PyDictObject * mp , PyDictKeysObject * dk , PyObject * key , Py_hash_t hash )
972
955
{
973
- PyDictKeyEntry * ep0 = DK_ENTRIES (dk );
974
- size_t mask = DK_MASK (dk );
975
- size_t perturb = hash ;
976
- size_t i = (size_t )hash & mask ;
977
- Py_ssize_t ix ;
978
- for (;;) {
979
- ix = dictkeys_get_index (dk , i );
980
- if (ix >= 0 ) {
981
- PyDictKeyEntry * ep = & ep0 [ix ];
982
- assert (ep -> me_key != NULL );
983
- if (ep -> me_key == key ) {
956
+ return do_lookup (mp , dk , key , hash , (generic_entries_func )DK_UNICODE_ENTRIES , compare_unicode_generic );
957
+ }
958
+
959
+ static inline Py_ALWAYS_INLINE
960
+ Py_ssize_t compare_unicode_unicode (PyDictObject * mp , PyDictKeysObject * dk ,
961
+ void * ep0 , Py_ssize_t ix , PyObject * key , Py_hash_t hash )
962
+ {
963
+ PyDictUnicodeEntry * ep = & ((PyDictUnicodeEntry * )ep0 )[ix ];
964
+ assert (ep -> me_key != NULL );
965
+ assert (PyUnicode_CheckExact (ep -> me_key ));
966
+ if (ep -> me_key == key ||
967
+ (unicode_get_hash (ep -> me_key ) == hash && unicode_eq (ep -> me_key , key ))) {
968
+ return ix ;
969
+ }
970
+ return DKIX_DUMMY ;
971
+ }
972
+
973
+ static Py_ssize_t _Py_HOT_FUNCTION
974
+ unicodekeys_lookup_unicode (PyDictKeysObject * dk , PyObject * key , Py_hash_t hash )
975
+ {
976
+ return do_lookup (NULL , dk , key , hash , (generic_entries_func )DK_UNICODE_ENTRIES , compare_unicode_unicode );
977
+ }
978
+
979
+ static inline Py_ALWAYS_INLINE
980
+ Py_ssize_t compare_generic (PyDictObject * mp , PyDictKeysObject * dk ,
981
+ void * ep0 , Py_ssize_t ix , PyObject * key , Py_hash_t hash )
982
+ {
983
+ PyDictKeyEntry * ep = & ((PyDictKeyEntry * )ep0 )[ix ];
984
+ assert (ep -> me_key != NULL );
985
+ if (ep -> me_key == key ) {
986
+ return ix ;
987
+ }
988
+ if (ep -> me_hash == hash ) {
989
+ PyObject * startkey = ep -> me_key ;
990
+ Py_INCREF (startkey );
991
+ int cmp = PyObject_RichCompareBool (startkey , key , Py_EQ );
992
+ Py_DECREF (startkey );
993
+ if (cmp < 0 ) {
994
+ return DKIX_ERROR ;
995
+ }
996
+ if (dk == mp -> ma_keys && ep -> me_key == startkey ) {
997
+ if (cmp > 0 ) {
984
998
return ix ;
985
999
}
986
- if (ep -> me_hash == hash ) {
987
- PyObject * startkey = ep -> me_key ;
988
- Py_INCREF (startkey );
989
- int cmp = PyObject_RichCompareBool (startkey , key , Py_EQ );
990
- Py_DECREF (startkey );
991
- if (cmp < 0 ) {
992
- return DKIX_ERROR ;
993
- }
994
- if (dk == mp -> ma_keys && ep -> me_key == startkey ) {
995
- if (cmp > 0 ) {
996
- return ix ;
997
- }
998
- }
999
- else {
1000
- /* The dict was mutated, restart */
1001
- return DKIX_KEY_CHANGED ;
1002
- }
1003
- }
1004
1000
}
1005
- else if (ix == DKIX_EMPTY ) {
1006
- return DKIX_EMPTY ;
1001
+ else {
1002
+ /* The dict was mutated, restart */
1003
+ return DKIX_KEY_CHANGED ;
1007
1004
}
1008
- perturb >>= PERTURB_SHIFT ;
1009
- i = mask & (i * 5 + perturb + 1 );
1010
1005
}
1011
- Py_UNREACHABLE ();
1006
+ return DKIX_DUMMY ;
1007
+ }
1008
+
1009
+ static Py_ssize_t
1010
+ dictkeys_generic_lookup (PyDictObject * mp , PyDictKeysObject * dk , PyObject * key , Py_hash_t hash )
1011
+ {
1012
+ return do_lookup (mp , dk , key , hash , (generic_entries_func )DK_ENTRIES , compare_generic );
1012
1013
}
1013
1014
1014
1015
/* Lookup a string in a (all unicode) dict keys.
0 commit comments