Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * nbtcompare.c
4 : : * Comparison functions for btree access method.
5 : : *
6 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/nbtree/nbtcompare.c
12 : : *
13 : : * NOTES
14 : : *
15 : : * These functions are stored in pg_amproc. For each operator class
16 : : * defined on btrees, they compute
17 : : *
18 : : * compare(a, b):
19 : : * < 0 if a < b,
20 : : * = 0 if a == b,
21 : : * > 0 if a > b.
22 : : *
23 : : * The result is always an int32 regardless of the input datatype.
24 : : *
25 : : * Although any negative int32 is acceptable for reporting "<",
26 : : * and any positive int32 is acceptable for reporting ">", routines
27 : : * that work on 32-bit or wider datatypes can't just return "a - b".
28 : : * That could overflow and give the wrong answer.
29 : : *
30 : : * NOTE: it is critical that the comparison function impose a total order
31 : : * on all non-NULL values of the data type, and that the datatype's
32 : : * boolean comparison operators (= < >= etc) yield results consistent
33 : : * with the comparison routine. Otherwise bad behavior may ensue.
34 : : * (For example, the comparison operators must NOT punt when faced with
35 : : * NAN or other funny values; you must devise some collation sequence for
36 : : * all such values.) If the datatype is not trivial, this is most
37 : : * reliably done by having the boolean operators invoke the same
38 : : * three-way comparison code that the btree function does. Therefore,
39 : : * this file contains only btree support for "trivial" datatypes ---
40 : : * all others are in the /utils/adt/ files that implement their datatypes.
41 : : *
42 : : * NOTE: these routines must not leak memory, since memory allocated
43 : : * during an index access won't be recovered till end of query. This
44 : : * primarily affects comparison routines for toastable datatypes;
45 : : * they have to be careful to free any detoasted copy of an input datum.
46 : : *
47 : : * NOTE: we used to forbid comparison functions from returning INT_MIN,
48 : : * but that proves to be too error-prone because some platforms' versions
49 : : * of memcmp() etc can return INT_MIN. As a means of stress-testing
50 : : * callers, this file can be compiled with STRESS_SORT_INT_MIN defined
51 : : * to cause many of these functions to return INT_MIN or INT_MAX instead of
52 : : * their customary -1/+1. For production, though, that's not a good idea
53 : : * since users or third-party code might expect the traditional results.
54 : : *-------------------------------------------------------------------------
55 : : */
56 : : #include "postgres.h"
57 : :
58 : : #include <limits.h>
59 : :
60 : : #include "utils/fmgrprotos.h"
61 : : #include "utils/sortsupport.h"
62 : :
63 : : #ifdef STRESS_SORT_INT_MIN
64 : : #define A_LESS_THAN_B INT_MIN
65 : : #define A_GREATER_THAN_B INT_MAX
66 : : #else
67 : : #define A_LESS_THAN_B (-1)
68 : : #define A_GREATER_THAN_B 1
69 : : #endif
70 : :
71 : :
72 : : Datum
8714 tgl@sss.pgh.pa.us 73 :CBC 22709442 : btboolcmp(PG_FUNCTION_ARGS)
74 : : {
75 : 22709442 : bool a = PG_GETARG_BOOL(0);
76 : 22709442 : bool b = PG_GETARG_BOOL(1);
77 : :
78 : 22709442 : PG_RETURN_INT32((int32) a - (int32) b);
79 : : }
80 : :
81 : : Datum
82 : 5050002 : btint2cmp(PG_FUNCTION_ARGS)
83 : : {
84 : 5050002 : int16 a = PG_GETARG_INT16(0);
85 : 5050002 : int16 b = PG_GETARG_INT16(1);
86 : :
87 : 5050002 : PG_RETURN_INT32((int32) a - (int32) b);
88 : : }
89 : :
90 : : static int
4512 91 : 15564887 : btint2fastcmp(Datum x, Datum y, SortSupport ssup)
92 : : {
93 : 15564887 : int16 a = DatumGetInt16(x);
94 : 15564887 : int16 b = DatumGetInt16(y);
95 : :
96 : 15564887 : return (int) a - (int) b;
97 : : }
98 : :
99 : : Datum
100 : 3762 : btint2sortsupport(PG_FUNCTION_ARGS)
101 : : {
4326 bruce@momjian.us 102 : 3762 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
103 : :
4512 tgl@sss.pgh.pa.us 104 : 3762 : ssup->comparator = btint2fastcmp;
105 : 3762 : PG_RETURN_VOID();
106 : : }
107 : :
108 : : Datum
8714 109 : 47720989 : btint4cmp(PG_FUNCTION_ARGS)
110 : : {
111 : 47720989 : int32 a = PG_GETARG_INT32(0);
112 : 47720989 : int32 b = PG_GETARG_INT32(1);
113 : :
8768 bruce@momjian.us 114 [ + + ]: 47720989 : if (a > b)
2018 tgl@sss.pgh.pa.us 115 : 18125327 : PG_RETURN_INT32(A_GREATER_THAN_B);
8768 bruce@momjian.us 116 [ + + ]: 29595662 : else if (a == b)
8714 tgl@sss.pgh.pa.us 117 : 9832144 : PG_RETURN_INT32(0);
118 : : else
2018 119 : 19763518 : PG_RETURN_INT32(A_LESS_THAN_B);
120 : : }
121 : :
122 : : Datum
4512 123 : 73192 : btint4sortsupport(PG_FUNCTION_ARGS)
124 : : {
4326 bruce@momjian.us 125 : 73192 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
126 : :
743 john.naylor@postgres 127 : 73192 : ssup->comparator = ssup_datum_int32_cmp;
4512 tgl@sss.pgh.pa.us 128 : 73192 : PG_RETURN_VOID();
129 : : }
130 : :
131 : : Datum
8714 132 : 8321000 : btint8cmp(PG_FUNCTION_ARGS)
133 : : {
134 : 8321000 : int64 a = PG_GETARG_INT64(0);
135 : 8321000 : int64 b = PG_GETARG_INT64(1);
136 : :
137 [ + + ]: 8321000 : if (a > b)
2018 138 : 4863647 : PG_RETURN_INT32(A_GREATER_THAN_B);
8714 139 [ + + ]: 3457353 : else if (a == b)
140 : 422410 : PG_RETURN_INT32(0);
141 : : else
2018 142 : 3034943 : PG_RETURN_INT32(A_LESS_THAN_B);
143 : : }
144 : :
145 : : #if SIZEOF_DATUM < 8
146 : : static int
147 : : btint8fastcmp(Datum x, Datum y, SortSupport ssup)
148 : : {
149 : : int64 a = DatumGetInt64(x);
150 : : int64 b = DatumGetInt64(y);
151 : :
152 : : if (a > b)
153 : : return A_GREATER_THAN_B;
154 : : else if (a == b)
155 : : return 0;
156 : : else
157 : : return A_LESS_THAN_B;
158 : : }
159 : : #endif
160 : :
161 : : Datum
4512 162 : 1483 : btint8sortsupport(PG_FUNCTION_ARGS)
163 : : {
4326 bruce@momjian.us 164 : 1483 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
165 : :
166 : : #if SIZEOF_DATUM >= 8
743 john.naylor@postgres 167 : 1483 : ssup->comparator = ssup_datum_signed_cmp;
168 : : #else
169 : : ssup->comparator = btint8fastcmp;
170 : : #endif
4512 tgl@sss.pgh.pa.us 171 : 1483 : PG_RETURN_VOID();
172 : : }
173 : :
174 : : Datum
7459 175 : 726 : btint48cmp(PG_FUNCTION_ARGS)
176 : : {
177 : 726 : int32 a = PG_GETARG_INT32(0);
178 : 726 : int64 b = PG_GETARG_INT64(1);
179 : :
180 [ + + ]: 726 : if (a > b)
2018 181 : 249 : PG_RETURN_INT32(A_GREATER_THAN_B);
7459 182 [ + + ]: 477 : else if (a == b)
183 : 33 : PG_RETURN_INT32(0);
184 : : else
2018 185 : 444 : PG_RETURN_INT32(A_LESS_THAN_B);
186 : : }
187 : :
188 : : Datum
7459 189 : 51 : btint84cmp(PG_FUNCTION_ARGS)
190 : : {
191 : 51 : int64 a = PG_GETARG_INT64(0);
192 : 51 : int32 b = PG_GETARG_INT32(1);
193 : :
194 [ + + ]: 51 : if (a > b)
2018 195 : 15 : PG_RETURN_INT32(A_GREATER_THAN_B);
7459 196 [ + + ]: 36 : else if (a == b)
197 : 15 : PG_RETURN_INT32(0);
198 : : else
2018 199 : 21 : PG_RETURN_INT32(A_LESS_THAN_B);
200 : : }
201 : :
202 : : Datum
7459 203 : 19110 : btint24cmp(PG_FUNCTION_ARGS)
204 : : {
205 : 19110 : int16 a = PG_GETARG_INT16(0);
206 : 19110 : int32 b = PG_GETARG_INT32(1);
207 : :
208 [ + + ]: 19110 : if (a > b)
2018 209 : 10969 : PG_RETURN_INT32(A_GREATER_THAN_B);
7459 210 [ + + ]: 8141 : else if (a == b)
211 : 2366 : PG_RETURN_INT32(0);
212 : : else
2018 213 : 5775 : PG_RETURN_INT32(A_LESS_THAN_B);
214 : : }
215 : :
216 : : Datum
7459 217 : 566 : btint42cmp(PG_FUNCTION_ARGS)
218 : : {
219 : 566 : int32 a = PG_GETARG_INT32(0);
220 : 566 : int16 b = PG_GETARG_INT16(1);
221 : :
222 [ + + ]: 566 : if (a > b)
2018 223 : 28 : PG_RETURN_INT32(A_GREATER_THAN_B);
7459 224 [ + + ]: 538 : else if (a == b)
225 : 129 : PG_RETURN_INT32(0);
226 : : else
2018 227 : 409 : PG_RETURN_INT32(A_LESS_THAN_B);
228 : : }
229 : :
230 : : Datum
7459 231 : 18 : btint28cmp(PG_FUNCTION_ARGS)
232 : : {
233 : 18 : int16 a = PG_GETARG_INT16(0);
234 : 18 : int64 b = PG_GETARG_INT64(1);
235 : :
236 [ - + ]: 18 : if (a > b)
2018 tgl@sss.pgh.pa.us 237 :UBC 0 : PG_RETURN_INT32(A_GREATER_THAN_B);
7459 tgl@sss.pgh.pa.us 238 [ - + ]:CBC 18 : else if (a == b)
7459 tgl@sss.pgh.pa.us 239 :UBC 0 : PG_RETURN_INT32(0);
240 : : else
2018 tgl@sss.pgh.pa.us 241 :CBC 18 : PG_RETURN_INT32(A_LESS_THAN_B);
242 : : }
243 : :
244 : : Datum
7459 tgl@sss.pgh.pa.us 245 :UBC 0 : btint82cmp(PG_FUNCTION_ARGS)
246 : : {
247 : 0 : int64 a = PG_GETARG_INT64(0);
248 : 0 : int16 b = PG_GETARG_INT16(1);
249 : :
250 [ # # ]: 0 : if (a > b)
2018 251 : 0 : PG_RETURN_INT32(A_GREATER_THAN_B);
7459 252 [ # # ]: 0 : else if (a == b)
253 : 0 : PG_RETURN_INT32(0);
254 : : else
2018 255 : 0 : PG_RETURN_INT32(A_LESS_THAN_B);
256 : : }
257 : :
258 : : Datum
8714 tgl@sss.pgh.pa.us 259 :CBC 94482887 : btoidcmp(PG_FUNCTION_ARGS)
260 : : {
261 : 94482887 : Oid a = PG_GETARG_OID(0);
262 : 94482887 : Oid b = PG_GETARG_OID(1);
263 : :
9716 bruce@momjian.us 264 [ + + ]: 94482887 : if (a > b)
2018 tgl@sss.pgh.pa.us 265 : 25434780 : PG_RETURN_INT32(A_GREATER_THAN_B);
9716 bruce@momjian.us 266 [ + + ]: 69048107 : else if (a == b)
8714 tgl@sss.pgh.pa.us 267 : 22506397 : PG_RETURN_INT32(0);
268 : : else
2018 269 : 46541710 : PG_RETURN_INT32(A_LESS_THAN_B);
270 : : }
271 : :
272 : : static int
4512 273 : 97174767 : btoidfastcmp(Datum x, Datum y, SortSupport ssup)
274 : : {
275 : 97174767 : Oid a = DatumGetObjectId(x);
276 : 97174767 : Oid b = DatumGetObjectId(y);
277 : :
278 [ + + ]: 97174767 : if (a > b)
2018 279 : 24070439 : return A_GREATER_THAN_B;
4512 280 [ + + ]: 73104328 : else if (a == b)
281 : 48480721 : return 0;
282 : : else
2018 283 : 24623607 : return A_LESS_THAN_B;
284 : : }
285 : :
286 : : Datum
4512 287 : 49032 : btoidsortsupport(PG_FUNCTION_ARGS)
288 : : {
4326 bruce@momjian.us 289 : 49032 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
290 : :
4512 tgl@sss.pgh.pa.us 291 : 49032 : ssup->comparator = btoidfastcmp;
292 : 49032 : PG_RETURN_VOID();
293 : : }
294 : :
295 : : Datum
8714 296 : 2868829 : btoidvectorcmp(PG_FUNCTION_ARGS)
297 : : {
6956 298 : 2868829 : oidvector *a = (oidvector *) PG_GETARG_POINTER(0);
299 : 2868829 : oidvector *b = (oidvector *) PG_GETARG_POINTER(1);
300 : : int i;
301 : :
302 : : /* We arbitrarily choose to sort first by vector length */
303 [ + + ]: 2868829 : if (a->dim1 != b->dim1)
304 : 418256 : PG_RETURN_INT32(a->dim1 - b->dim1);
305 : :
306 [ + + ]: 4284657 : for (i = 0; i < a->dim1; i++)
307 : : {
308 [ + + ]: 3286857 : if (a->values[i] != b->values[i])
309 : : {
310 [ + + ]: 1452773 : if (a->values[i] > b->values[i])
2018 311 : 757396 : PG_RETURN_INT32(A_GREATER_THAN_B);
312 : : else
313 : 695377 : PG_RETURN_INT32(A_LESS_THAN_B);
314 : : }
315 : : }
8714 316 : 997800 : PG_RETURN_INT32(0);
317 : : }
318 : :
319 : : Datum
320 : 22014890 : btcharcmp(PG_FUNCTION_ARGS)
321 : : {
322 : 22014890 : char a = PG_GETARG_CHAR(0);
323 : 22014890 : char b = PG_GETARG_CHAR(1);
324 : :
325 : : /* Be careful to compare chars as unsigned */
326 : 22014890 : PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
327 : : }
|
