contrib/faiss/faiss/utils/ordered_key_value.h
Line | Count | Source |
1 | | /* |
2 | | * Copyright (c) Meta Platforms, Inc. and affiliates. |
3 | | * |
4 | | * This source code is licensed under the MIT license found in the |
5 | | * LICENSE file in the root directory of this source tree. |
6 | | */ |
7 | | |
8 | | #pragma once |
9 | | |
10 | | #include <climits> |
11 | | #include <cmath> |
12 | | |
13 | | #include <limits> |
14 | | |
15 | | namespace faiss { |
16 | | |
17 | | /******************************************************************* |
18 | | * C object: uniform handling of min and max heap |
19 | | *******************************************************************/ |
20 | | |
21 | | /** The C object gives the type T of the values of a key-value storage, the type |
22 | | * of the keys, TI and the comparison that is done: CMax for a decreasing |
23 | | * series and CMin for increasing series. In other words, for a given threshold |
24 | | * threshold, an incoming value x is kept if |
25 | | * |
26 | | * C::cmp(threshold, x) |
27 | | * |
28 | | * is true. |
29 | | */ |
30 | | |
31 | | template <typename T_, typename TI_> |
32 | | struct CMax; |
33 | | |
34 | | template <typename T> |
35 | | inline T cmin_nextafter(T x); |
36 | | template <typename T> |
37 | | inline T cmax_nextafter(T x); |
38 | | |
39 | | // traits of minheaps = heaps where the minimum value is stored on top |
40 | | // useful to find the *max* values of an array |
41 | | template <typename T_, typename TI_> |
42 | | struct CMin { |
43 | | typedef T_ T; |
44 | | typedef TI_ TI; |
45 | | typedef CMax<T_, TI_> Crev; // reference to reverse comparison |
46 | 114k | inline static bool cmp(T a, T b) { |
47 | 114k | return a < b; |
48 | 114k | } _ZN5faiss4CMinIflE3cmpEff Line | Count | Source | 46 | 114k | inline static bool cmp(T a, T b) { | 47 | 114k | return a < b; | 48 | 114k | } |
Unexecuted instantiation: _ZN5faiss4CMinItiE3cmpEtt Unexecuted instantiation: _ZN5faiss4CMinItlE3cmpEtt Unexecuted instantiation: _ZN5faiss4CMinIfiE3cmpEff Unexecuted instantiation: _ZN5faiss4CMinIilE3cmpEii |
49 | | // Similar to cmp(), but also breaks ties |
50 | | // by comparing the second pair of arguments. |
51 | 213 | inline static bool cmp2(T a1, T b1, TI a2, TI b2) { |
52 | 213 | return (a1 < b1) || ((a1 == b1) && (a2 < b2)); |
53 | 213 | } _ZN5faiss4CMinIflE4cmp2Effll Line | Count | Source | 51 | 213 | inline static bool cmp2(T a1, T b1, TI a2, TI b2) { | 52 | 213 | return (a1 < b1) || ((a1 == b1) && (a2 < b2)); | 53 | 213 | } |
Unexecuted instantiation: _ZN5faiss4CMinItiE4cmp2Ettii Unexecuted instantiation: _ZN5faiss4CMinItlE4cmp2Ettll Unexecuted instantiation: _ZN5faiss4CMinIilE4cmp2Eiill Unexecuted instantiation: _ZN5faiss4CMinIfiE4cmp2Effii Unexecuted instantiation: _ZN5faiss4CMinIiiE4cmp2Eiiii |
54 | 27.6k | inline static T neutral() { |
55 | 27.6k | return std::numeric_limits<T>::lowest(); |
56 | 27.6k | } _ZN5faiss4CMinIflE7neutralEv Line | Count | Source | 54 | 27.6k | inline static T neutral() { | 55 | 27.6k | return std::numeric_limits<T>::lowest(); | 56 | 27.6k | } |
Unexecuted instantiation: _ZN5faiss4CMinItiE7neutralEv Unexecuted instantiation: _ZN5faiss4CMinItlE7neutralEv Unexecuted instantiation: _ZN5faiss4CMinIilE7neutralEv Unexecuted instantiation: _ZN5faiss4CMinIfiE7neutralEv Unexecuted instantiation: _ZN5faiss4CMinIiiE7neutralEv |
57 | | static const bool is_max = false; |
58 | | |
59 | 0 | inline static T nextafter(T x) { |
60 | 0 | return cmin_nextafter(x); |
61 | 0 | } Unexecuted instantiation: _ZN5faiss4CMinIflE9nextafterEf Unexecuted instantiation: _ZN5faiss4CMinItlE9nextafterEt Unexecuted instantiation: _ZN5faiss4CMinItiE9nextafterEt |
62 | | }; |
63 | | |
64 | | template <typename T_, typename TI_> |
65 | | struct CMax { |
66 | | typedef T_ T; |
67 | | typedef TI_ TI; |
68 | | typedef CMin<T_, TI_> Crev; |
69 | 23.5k | inline static bool cmp(T a, T b) { |
70 | 23.5k | return a > b; |
71 | 23.5k | } _ZN5faiss4CMaxIflE3cmpEff Line | Count | Source | 69 | 23.5k | inline static bool cmp(T a, T b) { | 70 | 23.5k | return a > b; | 71 | 23.5k | } |
Unexecuted instantiation: _ZN5faiss4CMaxIfiE3cmpEff Unexecuted instantiation: _ZN5faiss4CMaxItiE3cmpEtt Unexecuted instantiation: _ZN5faiss4CMaxItlE3cmpEtt Unexecuted instantiation: _ZN5faiss4CMaxIilE3cmpEii |
72 | | // Similar to cmp(), but also breaks ties |
73 | | // by comparing the second pair of arguments. |
74 | 126k | inline static bool cmp2(T a1, T b1, TI a2, TI b2) { |
75 | 126k | return (a1 > b1) || ((a1 == b1) && (a2 > b2)); |
76 | 126k | } _ZN5faiss4CMaxIflE4cmp2Effll Line | Count | Source | 74 | 92.4k | inline static bool cmp2(T a1, T b1, TI a2, TI b2) { | 75 | 92.4k | return (a1 > b1) || ((a1 == b1) && (a2 > b2)); | 76 | 92.4k | } |
_ZN5faiss4CMaxIfiE4cmp2Effii Line | Count | Source | 74 | 34.2k | inline static bool cmp2(T a1, T b1, TI a2, TI b2) { | 75 | 34.2k | return (a1 > b1) || ((a1 == b1) && (a2 > b2)); | 76 | 34.2k | } |
Unexecuted instantiation: _ZN5faiss4CMaxItiE4cmp2Ettii Unexecuted instantiation: _ZN5faiss4CMaxItlE4cmp2Ettll Unexecuted instantiation: _ZN5faiss4CMaxIilE4cmp2Eiill Unexecuted instantiation: _ZN5faiss4CMaxIiiE4cmp2Eiiii |
77 | 18.8k | inline static T neutral() { |
78 | 18.8k | return std::numeric_limits<T>::max(); |
79 | 18.8k | } _ZN5faiss4CMaxIflE7neutralEv Line | Count | Source | 77 | 18.8k | inline static T neutral() { | 78 | 18.8k | return std::numeric_limits<T>::max(); | 79 | 18.8k | } |
Unexecuted instantiation: _ZN5faiss4CMaxItiE7neutralEv Unexecuted instantiation: _ZN5faiss4CMaxItlE7neutralEv Unexecuted instantiation: _ZN5faiss4CMaxIilE7neutralEv Unexecuted instantiation: _ZN5faiss4CMaxIfiE7neutralEv Unexecuted instantiation: _ZN5faiss4CMaxIiiE7neutralEv |
80 | | static const bool is_max = true; |
81 | 0 | inline static T nextafter(T x) { |
82 | 0 | return cmax_nextafter(x); |
83 | 0 | } Unexecuted instantiation: _ZN5faiss4CMaxIflE9nextafterEf Unexecuted instantiation: _ZN5faiss4CMaxItlE9nextafterEt Unexecuted instantiation: _ZN5faiss4CMaxItiE9nextafterEt |
84 | | }; |
85 | | |
86 | | template <> |
87 | 0 | inline float cmin_nextafter<float>(float x) { |
88 | 0 | return std::nextafterf(x, -HUGE_VALF); |
89 | 0 | } |
90 | | |
91 | | template <> |
92 | 0 | inline float cmax_nextafter<float>(float x) { |
93 | 0 | return std::nextafterf(x, HUGE_VALF); |
94 | 0 | } |
95 | | |
96 | | template <> |
97 | 0 | inline uint16_t cmin_nextafter<uint16_t>(uint16_t x) { |
98 | 0 | return x - 1; |
99 | 0 | } |
100 | | |
101 | | template <> |
102 | 0 | inline uint16_t cmax_nextafter<uint16_t>(uint16_t x) { |
103 | 0 | return x + 1; |
104 | 0 | } |
105 | | |
106 | | } // namespace faiss |