Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 8bb71fe

Browse filesBrowse files
vstinnervstinner
committed
gh-111545: Add PyHash_Pointer() function
* Keep _Py_HashPointer() function as an alias to PyHash_Pointer(). * Add _Py_rotateright_uintptr() function with tests. * Add PyHash_Pointer() tests to test_capi.test_hash. * Remove _Py_HashPointerRaw() function: inline code in _Py_hashtable_hash_ptr().
1 parent d4f83e1 commit 8bb71fe
Copy full SHA for 8bb71fe

File tree

Expand file treeCollapse file tree

12 files changed

+181
-22
lines changed
Filter options
Expand file treeCollapse file tree

12 files changed

+181
-22
lines changed

‎Doc/c-api/hash.rst

Copy file name to clipboardExpand all lines: Doc/c-api/hash.rst
+9Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,3 +46,12 @@ See also the :c:member:`PyTypeObject.tp_hash` member.
4646
Get the hash function definition.
4747
4848
.. versionadded:: 3.4
49+
50+
51+
.. c:function:: Py_hash_t PyHash_Pointer(const void *ptr)
52+
53+
Hash a pointer.
54+
55+
The function cannot fail (cannot return ``-1``).
56+
57+
.. versionadded:: 3.13

‎Doc/whatsnew/3.13.rst

Copy file name to clipboardExpand all lines: Doc/whatsnew/3.13.rst
+3Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1181,6 +1181,9 @@ New Features
11811181
:exc:`KeyError` if the key missing.
11821182
(Contributed by Stefan Behnel and Victor Stinner in :gh:`111262`.)
11831183

1184+
* Add :c:func:`PyHash_Pointer` function to hash a pointer.
1185+
(Contributed by Victor Stinner in :gh:`111545`.)
1186+
11841187

11851188
Porting to Python 3.13
11861189
----------------------

‎Include/cpython/pyhash.h

Copy file name to clipboardExpand all lines: Include/cpython/pyhash.h
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,3 +11,5 @@ typedef struct {
1111
} PyHash_FuncDef;
1212

1313
PyAPI_FUNC(PyHash_FuncDef*) PyHash_GetFuncDef(void);
14+
15+
PyAPI_FUNC(Py_hash_t) PyHash_Pointer(const void *ptr);

‎Include/internal/pycore_bitutils.h

Copy file name to clipboardExpand all lines: Include/internal/pycore_bitutils.h
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -180,6 +180,22 @@ _Py_bit_length(unsigned long x)
180180
}
181181

182182

183+
// Rotate x bits to the right.
184+
// Function used by Py_HashPointer().
185+
static inline uintptr_t
186+
_Py_rotateright_uintptr(uintptr_t x, const unsigned int bits)
187+
{
188+
assert(bits < (8 * SIZEOF_UINTPTR_T));
189+
#if _Py__has_builtin(__builtin_rotateright64) && SIZEOF_UINTPTR_T == 8
190+
return __builtin_rotateright64(x, bits);
191+
#elif _Py__has_builtin(__builtin_rotateright32) && SIZEOF_UINTPTR_T == 4
192+
return __builtin_rotateright32(x, bits);
193+
#else
194+
return (x >> bits) | (x << (8 * SIZEOF_UINTPTR_T - bits));
195+
#endif
196+
}
197+
198+
183199
#ifdef __cplusplus
184200
}
185201
#endif

‎Include/internal/pycore_pyhash.h

Copy file name to clipboardExpand all lines: Include/internal/pycore_pyhash.h
+2-5Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -8,11 +8,8 @@
88
/* Helpers for hash functions */
99
extern Py_hash_t _Py_HashDouble(PyObject *, double);
1010

11-
// Export for '_decimal' shared extension
12-
PyAPI_FUNC(Py_hash_t) _Py_HashPointer(const void*);
13-
14-
// Similar to _Py_HashPointer(), but don't replace -1 with -2
15-
extern Py_hash_t _Py_HashPointerRaw(const void*);
11+
// Kept for backward compatibility
12+
#define _Py_HashPointer PyHash_Pointer
1613

1714
// Export for '_datetime' shared extension
1815
PyAPI_FUNC(Py_hash_t) _Py_HashBytes(const void*, Py_ssize_t);

‎Lib/test/test_capi/test_hash.py

Copy file name to clipboardExpand all lines: Lib/test/test_capi/test_hash.py
+27Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,3 +31,30 @@ def test_hash_getfuncdef(self):
3131
self.assertEqual(func_def.name, hash_info.algorithm)
3232
self.assertEqual(func_def.hash_bits, hash_info.hash_bits)
3333
self.assertEqual(func_def.seed_bits, hash_info.seed_bits)
34+
35+
def test_hash_pointer(self):
36+
# Test PyHash_Pointer()
37+
hash_pointer = _testcapi.hash_pointer
38+
39+
HASH_BITS = 8 * _testcapi.SIZEOF_VOID_P
40+
UHASH_T_MASK = ((2 ** HASH_BITS) - 1)
41+
HASH_T_MAX = (2 ** (HASH_BITS - 1) - 1)
42+
MAX_PTR = UHASH_T_MASK
43+
44+
def uhash_to_hash(x):
45+
# Convert unsigned Py_uhash_t to signed Py_hash_t
46+
if HASH_T_MAX < x:
47+
x = (~x) + 1
48+
x &= UHASH_T_MASK
49+
x = (~x) + 1
50+
return x
51+
52+
# Known values
53+
self.assertEqual(hash_pointer(0), 0)
54+
self.assertEqual(hash_pointer(MAX_PTR), -2)
55+
self.assertEqual(hash_pointer(0xABCDEF1234567890),
56+
0x0ABCDEF123456789)
57+
self.assertEqual(hash_pointer(0x1234567890ABCDEF),
58+
uhash_to_hash(0xF1234567890ABCDE))
59+
self.assertEqual(hash_pointer(0xFEE4ABEDD1CECA5E),
60+
uhash_to_hash(0xEFEE4ABEDD1CECA5))

‎Misc/NEWS.d/next/C API/2023-11-15-01-26-59.gh-issue-111545.iAoFtA.rst

Copy file name to clipboard
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
Add :c:func:`PyHash_Pointer` function to hash a pointer. Patch by Victor
2+
Stinner.

‎Modules/_testcapi/hash.c

Copy file name to clipboardExpand all lines: Modules/_testcapi/hash.c
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,8 +44,24 @@ hash_getfuncdef(PyObject *Py_UNUSED(module), PyObject *Py_UNUSED(args))
4444
return result;
4545
}
4646

47+
48+
static PyObject *
49+
hash_pointer(PyObject *Py_UNUSED(module), PyObject *arg)
50+
{
51+
void *ptr = PyLong_AsVoidPtr(arg);
52+
if (ptr == NULL && PyErr_Occurred()) {
53+
return NULL;
54+
}
55+
56+
Py_hash_t hash = PyHash_Pointer(ptr);
57+
Py_BUILD_ASSERT(sizeof(long long) >= sizeof(hash));
58+
return PyLong_FromLongLong(hash);
59+
}
60+
61+
4762
static PyMethodDef test_methods[] = {
4863
{"hash_getfuncdef", hash_getfuncdef, METH_NOARGS},
64+
{"hash_pointer", hash_pointer, METH_O},
4965
{NULL},
5066
};
5167

‎Modules/_testinternalcapi.c

Copy file name to clipboardExpand all lines: Modules/_testinternalcapi.c
+75Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -216,6 +216,80 @@ test_bit_length(PyObject *self, PyObject *Py_UNUSED(args))
216216
}
217217

218218

219+
static int
220+
check_rotateright_uintptr(uintptr_t ptr, unsigned int bits, uintptr_t expected)
221+
{
222+
#if SIZEOF_UINTPTR_T == 8
223+
# define FMT "0x%llx"
224+
#else
225+
# define FMT "0x%lx"
226+
#endif
227+
228+
// Use volatile to prevent the compiler to optimize out the whole test
229+
volatile uintptr_t x = ptr;
230+
uintptr_t y = _Py_rotateright_uintptr(x, bits);
231+
if (y != expected) {
232+
PyErr_Format(PyExc_AssertionError,
233+
"_Py_rotateright_uintptr(" FMT ", %u) returns " FMT ", expected " FMT,
234+
x, bits, y, expected);
235+
return -1;
236+
}
237+
return 0;
238+
239+
#undef FMT
240+
}
241+
242+
243+
static PyObject*
244+
test_rotateright_uintptr(PyObject *self, PyObject *Py_UNUSED(args))
245+
{
246+
#define CHECK(X, BITS, EXPECTED) \
247+
do { \
248+
if (check_rotateright_uintptr(X, BITS, EXPECTED) < 0) { \
249+
return NULL; \
250+
} \
251+
} while (0)
252+
253+
// Test _Py_rotateright_uintptr()
254+
#if SIZEOF_UINTPTR_T == 8
255+
CHECK(UINT64_C(0x1234567890ABCDEF), 4, UINT64_C(0xF1234567890ABCDE));
256+
CHECK(UINT64_C(0x1234567890ABCDEF), 8, UINT64_C(0xEF1234567890ABCD));
257+
CHECK(UINT64_C(0x1234567890ABCDEF), 12, UINT64_C(0xDEF1234567890ABC));
258+
CHECK(UINT64_C(0x1234567890ABCDEF), 16, UINT64_C(0xCDEF1234567890AB));
259+
CHECK(UINT64_C(0x1234567890ABCDEF), 20, UINT64_C(0xBCDEF1234567890A));
260+
CHECK(UINT64_C(0x1234567890ABCDEF), 24, UINT64_C(0xABCDEF1234567890));
261+
CHECK(UINT64_C(0x1234567890ABCDEF), 28, UINT64_C(0x0ABCDEF123456789));
262+
CHECK(UINT64_C(0x1234567890ABCDEF), 32, UINT64_C(0x90ABCDEF12345678));
263+
CHECK(UINT64_C(0x1234567890ABCDEF), 36, UINT64_C(0x890ABCDEF1234567));
264+
CHECK(UINT64_C(0x1234567890ABCDEF), 40, UINT64_C(0x7890ABCDEF123456));
265+
CHECK(UINT64_C(0x1234567890ABCDEF), 44, UINT64_C(0x67890ABCDEF12345));
266+
CHECK(UINT64_C(0x1234567890ABCDEF), 48, UINT64_C(0x567890ABCDEF1234));
267+
CHECK(UINT64_C(0x1234567890ABCDEF), 52, UINT64_C(0x4567890ABCDEF123));
268+
CHECK(UINT64_C(0x1234567890ABCDEF), 56, UINT64_C(0x34567890ABCDEF12));
269+
CHECK(UINT64_C(0x1234567890ABCDEF), 60, UINT64_C(0x234567890ABCDEF1));
270+
271+
CHECK(UINT64_C(0xFEE4ABEDD1CECA5E), 4, UINT64_C(0xEFEE4ABEDD1CECA5));
272+
CHECK(UINT64_C(0xFEE4ABEDD1CECA5E), 32, UINT64_C(0xD1CECA5EFEE4ABED));
273+
#elif SIZEOF_UINTPTR_T == 4
274+
CHECK(UINT32_C(0x12345678), 4, UINT32_C(0x81234567));
275+
CHECK(UINT32_C(0x12345678), 8, UINT32_C(0x78123456));
276+
CHECK(UINT32_C(0x12345678), 12, UINT32_C(0x67812345));
277+
CHECK(UINT32_C(0x12345678), 16, UINT32_C(0x56781234));
278+
CHECK(UINT32_C(0x12345678), 20, UINT32_C(0x45678123));
279+
CHECK(UINT32_C(0x12345678), 24, UINT32_C(0x34567812));
280+
CHECK(UINT32_C(0x12345678), 28, UINT32_C(0x23456781));
281+
282+
CHECK(UINT32_C(0xDEADCAFE), 4, UINT32_C(0xEDEADCAF));
283+
CHECK(UINT32_C(0xDEADCAFE), 16, UINT32_C(0xCAFEDEAD));
284+
#else
285+
# error "unsupported uintptr_t size"
286+
#endif
287+
Py_RETURN_NONE;
288+
289+
#undef CHECK
290+
}
291+
292+
219293
#define TO_PTR(ch) ((void*)(uintptr_t)ch)
220294
#define FROM_PTR(ptr) ((uintptr_t)ptr)
221295
#define VALUE(key) (1 + ((int)(key) - 'a'))
@@ -1614,6 +1688,7 @@ static PyMethodDef module_functions[] = {
16141688
{"test_bswap", test_bswap, METH_NOARGS},
16151689
{"test_popcount", test_popcount, METH_NOARGS},
16161690
{"test_bit_length", test_bit_length, METH_NOARGS},
1691+
{"test_rotateright_uintptr", test_rotateright_uintptr, METH_NOARGS},
16171692
{"test_hashtable", test_hashtable, METH_NOARGS},
16181693
{"get_config", test_get_config, METH_NOARGS},
16191694
{"set_config", test_set_config, METH_O},

‎PC/pyconfig.h

Copy file name to clipboardExpand all lines: PC/pyconfig.h
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -355,6 +355,8 @@ Py_NO_ENABLE_SHARED to find out. Also support MS_NO_COREDLL for b/w compat */
355355
# define ALIGNOF_MAX_ALIGN_T 8
356356
#endif
357357

358+
#define SIZEOF_UINTPTR_T SIZEOF_VOID_P
359+
358360
#ifdef _DEBUG
359361
# define Py_DEBUG
360362
#endif

‎Python/hashtable.c

Copy file name to clipboardExpand all lines: Python/hashtable.c
+14-3Lines changed: 14 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -45,8 +45,8 @@
4545
*/
4646

4747
#include "Python.h"
48-
#include "pycore_hashtable.h"
49-
#include "pycore_pyhash.h" // _Py_HashPointerRaw()
48+
#include "pycore_bitutils.h" // _Py_rotateright_uintptr()
49+
#include "pycore_hashtable.h" // export _Py_hashtable_new()
5050

5151
#define HASHTABLE_MIN_SIZE 16
5252
#define HASHTABLE_HIGH 0.50
@@ -89,10 +89,21 @@ _Py_slist_remove(_Py_slist_t *list, _Py_slist_item_t *previous,
8989
}
9090

9191

92+
// Similar to PyHash_Pointer() but avoid "if (x == -1) x = -2;" for best
93+
// performance. The value (Py_uhash_t)-1 is not special for
94+
// _Py_hashtable_t.hash_func function, there is no need to replace it with -2.
9295
Py_uhash_t
9396
_Py_hashtable_hash_ptr(const void *key)
9497
{
95-
return (Py_uhash_t)_Py_HashPointerRaw(key);
98+
uintptr_t x = (uintptr_t)key;
99+
Py_BUILD_ASSERT(sizeof(x) == sizeof(key));
100+
101+
// Bottom 3 or 4 bits are likely to be 0; rotate x by 4 to the right
102+
// to avoid excessive hash collisions.
103+
x = _Py_rotateright_uintptr(x, 4);
104+
105+
Py_BUILD_ASSERT(sizeof(x) == sizeof(Py_hash_t));
106+
return (Py_uhash_t)x;
96107
}
97108

98109

‎Python/pyhash.c

Copy file name to clipboardExpand all lines: Python/pyhash.c
+13-14Lines changed: 13 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
All the utility functions (_Py_Hash*()) return "-1" to signify an error.
55
*/
66
#include "Python.h"
7+
#include "pycore_bitutils.h" // _Py_rotateright_uintptr()
78
#include "pycore_pyhash.h" // _Py_HashSecret_t
89

910
#ifdef __APPLE__
@@ -132,23 +133,21 @@ _Py_HashDouble(PyObject *inst, double v)
132133
}
133134

134135
Py_hash_t
135-
_Py_HashPointerRaw(const void *p)
136+
PyHash_Pointer(const void *ptr)
136137
{
137-
size_t y = (size_t)p;
138-
/* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
139-
excessive hash collisions for dicts and sets */
140-
y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4));
141-
return (Py_hash_t)y;
142-
}
138+
uintptr_t x = (uintptr_t)ptr;
139+
Py_BUILD_ASSERT(sizeof(x) == sizeof(ptr));
143140

144-
Py_hash_t
145-
_Py_HashPointer(const void *p)
146-
{
147-
Py_hash_t x = _Py_HashPointerRaw(p);
148-
if (x == -1) {
149-
x = -2;
141+
// Bottom 3 or 4 bits are likely to be 0; rotate x by 4 to the right
142+
// to avoid excessive hash collisions for dicts and sets.
143+
x = _Py_rotateright_uintptr(x, 4);
144+
145+
Py_BUILD_ASSERT(sizeof(x) == sizeof(Py_hash_t));
146+
Py_hash_t result = (Py_hash_t)x;
147+
if (result == -1) {
148+
result = -2;
150149
}
151-
return x;
150+
return result;
152151
}
153152

154153
Py_hash_t

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.