Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * nbtcompare.c
4 : * Comparison functions for btree access method.
5 : *
6 : * Portions Copyright (c) 1996-2025, 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/skipsupport.h"
62 : #include "utils/sortsupport.h"
63 :
64 : #ifdef STRESS_SORT_INT_MIN
65 : #define A_LESS_THAN_B INT_MIN
66 : #define A_GREATER_THAN_B INT_MAX
67 : #else
68 : #define A_LESS_THAN_B (-1)
69 : #define A_GREATER_THAN_B 1
70 : #endif
71 :
72 :
73 : Datum
74 59584654 : btboolcmp(PG_FUNCTION_ARGS)
75 : {
76 59584654 : bool a = PG_GETARG_BOOL(0);
77 59584654 : bool b = PG_GETARG_BOOL(1);
78 :
79 59584654 : PG_RETURN_INT32((int32) a - (int32) b);
80 : }
81 :
82 : static Datum
83 0 : bool_decrement(Relation rel, Datum existing, bool *underflow)
84 : {
85 0 : bool bexisting = DatumGetBool(existing);
86 :
87 0 : if (bexisting == false)
88 : {
89 : /* return value is undefined */
90 0 : *underflow = true;
91 0 : return (Datum) 0;
92 : }
93 :
94 0 : *underflow = false;
95 0 : return BoolGetDatum(bexisting - 1);
96 : }
97 :
98 : static Datum
99 0 : bool_increment(Relation rel, Datum existing, bool *overflow)
100 : {
101 0 : bool bexisting = DatumGetBool(existing);
102 :
103 0 : if (bexisting == true)
104 : {
105 : /* return value is undefined */
106 0 : *overflow = true;
107 0 : return (Datum) 0;
108 : }
109 :
110 0 : *overflow = false;
111 0 : return BoolGetDatum(bexisting + 1);
112 : }
113 :
114 : Datum
115 0 : btboolskipsupport(PG_FUNCTION_ARGS)
116 : {
117 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
118 :
119 0 : sksup->decrement = bool_decrement;
120 0 : sksup->increment = bool_increment;
121 0 : sksup->low_elem = BoolGetDatum(false);
122 0 : sksup->high_elem = BoolGetDatum(true);
123 :
124 0 : PG_RETURN_VOID();
125 : }
126 :
127 : Datum
128 12336676 : btint2cmp(PG_FUNCTION_ARGS)
129 : {
130 12336676 : int16 a = PG_GETARG_INT16(0);
131 12336676 : int16 b = PG_GETARG_INT16(1);
132 :
133 12336676 : PG_RETURN_INT32((int32) a - (int32) b);
134 : }
135 :
136 : static int
137 44516528 : btint2fastcmp(Datum x, Datum y, SortSupport ssup)
138 : {
139 44516528 : int16 a = DatumGetInt16(x);
140 44516528 : int16 b = DatumGetInt16(y);
141 :
142 44516528 : return (int) a - (int) b;
143 : }
144 :
145 : Datum
146 11838 : btint2sortsupport(PG_FUNCTION_ARGS)
147 : {
148 11838 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
149 :
150 11838 : ssup->comparator = btint2fastcmp;
151 11838 : PG_RETURN_VOID();
152 : }
153 :
154 : static Datum
155 0 : int2_decrement(Relation rel, Datum existing, bool *underflow)
156 : {
157 0 : int16 iexisting = DatumGetInt16(existing);
158 :
159 0 : if (iexisting == PG_INT16_MIN)
160 : {
161 : /* return value is undefined */
162 0 : *underflow = true;
163 0 : return (Datum) 0;
164 : }
165 :
166 0 : *underflow = false;
167 0 : return Int16GetDatum(iexisting - 1);
168 : }
169 :
170 : static Datum
171 4 : int2_increment(Relation rel, Datum existing, bool *overflow)
172 : {
173 4 : int16 iexisting = DatumGetInt16(existing);
174 :
175 4 : if (iexisting == PG_INT16_MAX)
176 : {
177 : /* return value is undefined */
178 0 : *overflow = true;
179 0 : return (Datum) 0;
180 : }
181 :
182 4 : *overflow = false;
183 4 : return Int16GetDatum(iexisting + 1);
184 : }
185 :
186 : Datum
187 186 : btint2skipsupport(PG_FUNCTION_ARGS)
188 : {
189 186 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
190 :
191 186 : sksup->decrement = int2_decrement;
192 186 : sksup->increment = int2_increment;
193 186 : sksup->low_elem = Int16GetDatum(PG_INT16_MIN);
194 186 : sksup->high_elem = Int16GetDatum(PG_INT16_MAX);
195 :
196 186 : PG_RETURN_VOID();
197 : }
198 :
199 : Datum
200 97505124 : btint4cmp(PG_FUNCTION_ARGS)
201 : {
202 97505124 : int32 a = PG_GETARG_INT32(0);
203 97505124 : int32 b = PG_GETARG_INT32(1);
204 :
205 97505124 : if (a > b)
206 37180644 : PG_RETURN_INT32(A_GREATER_THAN_B);
207 60324480 : else if (a == b)
208 20256542 : PG_RETURN_INT32(0);
209 : else
210 40067938 : PG_RETURN_INT32(A_LESS_THAN_B);
211 : }
212 :
213 : Datum
214 171708 : btint4sortsupport(PG_FUNCTION_ARGS)
215 : {
216 171708 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
217 :
218 171708 : ssup->comparator = ssup_datum_int32_cmp;
219 171708 : PG_RETURN_VOID();
220 : }
221 :
222 : static Datum
223 3966 : int4_decrement(Relation rel, Datum existing, bool *underflow)
224 : {
225 3966 : int32 iexisting = DatumGetInt32(existing);
226 :
227 3966 : if (iexisting == PG_INT32_MIN)
228 : {
229 : /* return value is undefined */
230 0 : *underflow = true;
231 0 : return (Datum) 0;
232 : }
233 :
234 3966 : *underflow = false;
235 3966 : return Int32GetDatum(iexisting - 1);
236 : }
237 :
238 : static Datum
239 3822 : int4_increment(Relation rel, Datum existing, bool *overflow)
240 : {
241 3822 : int32 iexisting = DatumGetInt32(existing);
242 :
243 3822 : if (iexisting == PG_INT32_MAX)
244 : {
245 : /* return value is undefined */
246 30 : *overflow = true;
247 30 : return (Datum) 0;
248 : }
249 :
250 3792 : *overflow = false;
251 3792 : return Int32GetDatum(iexisting + 1);
252 : }
253 :
254 : Datum
255 246 : btint4skipsupport(PG_FUNCTION_ARGS)
256 : {
257 246 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
258 :
259 246 : sksup->decrement = int4_decrement;
260 246 : sksup->increment = int4_increment;
261 246 : sksup->low_elem = Int32GetDatum(PG_INT32_MIN);
262 246 : sksup->high_elem = Int32GetDatum(PG_INT32_MAX);
263 :
264 246 : PG_RETURN_VOID();
265 : }
266 :
267 : Datum
268 16637350 : btint8cmp(PG_FUNCTION_ARGS)
269 : {
270 16637350 : int64 a = PG_GETARG_INT64(0);
271 16637350 : int64 b = PG_GETARG_INT64(1);
272 :
273 16637350 : if (a > b)
274 9721748 : PG_RETURN_INT32(A_GREATER_THAN_B);
275 6915602 : else if (a == b)
276 845134 : PG_RETURN_INT32(0);
277 : else
278 6070468 : PG_RETURN_INT32(A_LESS_THAN_B);
279 : }
280 :
281 : Datum
282 3462 : btint8sortsupport(PG_FUNCTION_ARGS)
283 : {
284 3462 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
285 :
286 3462 : ssup->comparator = ssup_datum_signed_cmp;
287 3462 : PG_RETURN_VOID();
288 : }
289 :
290 : static Datum
291 0 : int8_decrement(Relation rel, Datum existing, bool *underflow)
292 : {
293 0 : int64 iexisting = DatumGetInt64(existing);
294 :
295 0 : if (iexisting == PG_INT64_MIN)
296 : {
297 : /* return value is undefined */
298 0 : *underflow = true;
299 0 : return (Datum) 0;
300 : }
301 :
302 0 : *underflow = false;
303 0 : return Int64GetDatum(iexisting - 1);
304 : }
305 :
306 : static Datum
307 0 : int8_increment(Relation rel, Datum existing, bool *overflow)
308 : {
309 0 : int64 iexisting = DatumGetInt64(existing);
310 :
311 0 : if (iexisting == PG_INT64_MAX)
312 : {
313 : /* return value is undefined */
314 0 : *overflow = true;
315 0 : return (Datum) 0;
316 : }
317 :
318 0 : *overflow = false;
319 0 : return Int64GetDatum(iexisting + 1);
320 : }
321 :
322 : Datum
323 0 : btint8skipsupport(PG_FUNCTION_ARGS)
324 : {
325 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
326 :
327 0 : sksup->decrement = int8_decrement;
328 0 : sksup->increment = int8_increment;
329 0 : sksup->low_elem = Int64GetDatum(PG_INT64_MIN);
330 0 : sksup->high_elem = Int64GetDatum(PG_INT64_MAX);
331 :
332 0 : PG_RETURN_VOID();
333 : }
334 :
335 : Datum
336 1486 : btint48cmp(PG_FUNCTION_ARGS)
337 : {
338 1486 : int32 a = PG_GETARG_INT32(0);
339 1486 : int64 b = PG_GETARG_INT64(1);
340 :
341 1486 : if (a > b)
342 510 : PG_RETURN_INT32(A_GREATER_THAN_B);
343 976 : else if (a == b)
344 76 : PG_RETURN_INT32(0);
345 : else
346 900 : PG_RETURN_INT32(A_LESS_THAN_B);
347 : }
348 :
349 : Datum
350 220 : btint84cmp(PG_FUNCTION_ARGS)
351 : {
352 220 : int64 a = PG_GETARG_INT64(0);
353 220 : int32 b = PG_GETARG_INT32(1);
354 :
355 220 : if (a > b)
356 78 : PG_RETURN_INT32(A_GREATER_THAN_B);
357 142 : else if (a == b)
358 58 : PG_RETURN_INT32(0);
359 : else
360 84 : PG_RETURN_INT32(A_LESS_THAN_B);
361 : }
362 :
363 : Datum
364 45760 : btint24cmp(PG_FUNCTION_ARGS)
365 : {
366 45760 : int16 a = PG_GETARG_INT16(0);
367 45760 : int32 b = PG_GETARG_INT32(1);
368 :
369 45760 : if (a > b)
370 25130 : PG_RETURN_INT32(A_GREATER_THAN_B);
371 20630 : else if (a == b)
372 6252 : PG_RETURN_INT32(0);
373 : else
374 14378 : PG_RETURN_INT32(A_LESS_THAN_B);
375 : }
376 :
377 : Datum
378 1516 : btint42cmp(PG_FUNCTION_ARGS)
379 : {
380 1516 : int32 a = PG_GETARG_INT32(0);
381 1516 : int16 b = PG_GETARG_INT16(1);
382 :
383 1516 : if (a > b)
384 166 : PG_RETURN_INT32(A_GREATER_THAN_B);
385 1350 : else if (a == b)
386 288 : PG_RETURN_INT32(0);
387 : else
388 1062 : PG_RETURN_INT32(A_LESS_THAN_B);
389 : }
390 :
391 : Datum
392 70 : btint28cmp(PG_FUNCTION_ARGS)
393 : {
394 70 : int16 a = PG_GETARG_INT16(0);
395 70 : int64 b = PG_GETARG_INT64(1);
396 :
397 70 : if (a > b)
398 12 : PG_RETURN_INT32(A_GREATER_THAN_B);
399 58 : else if (a == b)
400 10 : PG_RETURN_INT32(0);
401 : else
402 48 : PG_RETURN_INT32(A_LESS_THAN_B);
403 : }
404 :
405 : Datum
406 34 : btint82cmp(PG_FUNCTION_ARGS)
407 : {
408 34 : int64 a = PG_GETARG_INT64(0);
409 34 : int16 b = PG_GETARG_INT16(1);
410 :
411 34 : if (a > b)
412 12 : PG_RETURN_INT32(A_GREATER_THAN_B);
413 22 : else if (a == b)
414 10 : PG_RETURN_INT32(0);
415 : else
416 12 : PG_RETURN_INT32(A_LESS_THAN_B);
417 : }
418 :
419 : Datum
420 222604018 : btoidcmp(PG_FUNCTION_ARGS)
421 : {
422 222604018 : Oid a = PG_GETARG_OID(0);
423 222604018 : Oid b = PG_GETARG_OID(1);
424 :
425 222604018 : if (a > b)
426 61009348 : PG_RETURN_INT32(A_GREATER_THAN_B);
427 161594670 : else if (a == b)
428 52092562 : PG_RETURN_INT32(0);
429 : else
430 109502108 : PG_RETURN_INT32(A_LESS_THAN_B);
431 : }
432 :
433 : static int
434 257859836 : btoidfastcmp(Datum x, Datum y, SortSupport ssup)
435 : {
436 257859836 : Oid a = DatumGetObjectId(x);
437 257859836 : Oid b = DatumGetObjectId(y);
438 :
439 257859836 : if (a > b)
440 63654030 : return A_GREATER_THAN_B;
441 194205806 : else if (a == b)
442 131477970 : return 0;
443 : else
444 62727836 : return A_LESS_THAN_B;
445 : }
446 :
447 : Datum
448 120936 : btoidsortsupport(PG_FUNCTION_ARGS)
449 : {
450 120936 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
451 :
452 120936 : ssup->comparator = btoidfastcmp;
453 120936 : PG_RETURN_VOID();
454 : }
455 :
456 : static Datum
457 0 : oid_decrement(Relation rel, Datum existing, bool *underflow)
458 : {
459 0 : Oid oexisting = DatumGetObjectId(existing);
460 :
461 0 : if (oexisting == InvalidOid)
462 : {
463 : /* return value is undefined */
464 0 : *underflow = true;
465 0 : return (Datum) 0;
466 : }
467 :
468 0 : *underflow = false;
469 0 : return ObjectIdGetDatum(oexisting - 1);
470 : }
471 :
472 : static Datum
473 342 : oid_increment(Relation rel, Datum existing, bool *overflow)
474 : {
475 342 : Oid oexisting = DatumGetObjectId(existing);
476 :
477 342 : if (oexisting == OID_MAX)
478 : {
479 : /* return value is undefined */
480 0 : *overflow = true;
481 0 : return (Datum) 0;
482 : }
483 :
484 342 : *overflow = false;
485 342 : return ObjectIdGetDatum(oexisting + 1);
486 : }
487 :
488 : Datum
489 2864 : btoidskipsupport(PG_FUNCTION_ARGS)
490 : {
491 2864 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
492 :
493 2864 : sksup->decrement = oid_decrement;
494 2864 : sksup->increment = oid_increment;
495 2864 : sksup->low_elem = ObjectIdGetDatum(InvalidOid);
496 2864 : sksup->high_elem = ObjectIdGetDatum(OID_MAX);
497 :
498 2864 : PG_RETURN_VOID();
499 : }
500 :
501 : Datum
502 7800864 : btoidvectorcmp(PG_FUNCTION_ARGS)
503 : {
504 7800864 : oidvector *a = (oidvector *) PG_GETARG_POINTER(0);
505 7800864 : oidvector *b = (oidvector *) PG_GETARG_POINTER(1);
506 : int i;
507 :
508 : /* We arbitrarily choose to sort first by vector length */
509 7800864 : if (a->dim1 != b->dim1)
510 1408956 : PG_RETURN_INT32(a->dim1 - b->dim1);
511 :
512 11256354 : for (i = 0; i < a->dim1; i++)
513 : {
514 8582068 : if (a->values[i] != b->values[i])
515 : {
516 3717622 : if (a->values[i] > b->values[i])
517 1922324 : PG_RETURN_INT32(A_GREATER_THAN_B);
518 : else
519 1795298 : PG_RETURN_INT32(A_LESS_THAN_B);
520 : }
521 : }
522 2674286 : PG_RETURN_INT32(0);
523 : }
524 :
525 : Datum
526 61800878 : btcharcmp(PG_FUNCTION_ARGS)
527 : {
528 61800878 : char a = PG_GETARG_CHAR(0);
529 61800878 : char b = PG_GETARG_CHAR(1);
530 :
531 : /* Be careful to compare chars as unsigned */
532 61800878 : PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
533 : }
534 :
535 : static Datum
536 0 : char_decrement(Relation rel, Datum existing, bool *underflow)
537 : {
538 0 : uint8 cexisting = DatumGetUInt8(existing);
539 :
540 0 : if (cexisting == 0)
541 : {
542 : /* return value is undefined */
543 0 : *underflow = true;
544 0 : return (Datum) 0;
545 : }
546 :
547 0 : *underflow = false;
548 0 : return CharGetDatum((uint8) cexisting - 1);
549 : }
550 :
551 : static Datum
552 0 : char_increment(Relation rel, Datum existing, bool *overflow)
553 : {
554 0 : uint8 cexisting = DatumGetUInt8(existing);
555 :
556 0 : if (cexisting == UCHAR_MAX)
557 : {
558 : /* return value is undefined */
559 0 : *overflow = true;
560 0 : return (Datum) 0;
561 : }
562 :
563 0 : *overflow = false;
564 0 : return CharGetDatum((uint8) cexisting + 1);
565 : }
566 :
567 : Datum
568 0 : btcharskipsupport(PG_FUNCTION_ARGS)
569 : {
570 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
571 :
572 0 : sksup->decrement = char_decrement;
573 0 : sksup->increment = char_increment;
574 :
575 : /* btcharcmp compares chars as unsigned */
576 0 : sksup->low_elem = UInt8GetDatum(0);
577 0 : sksup->high_elem = UInt8GetDatum(UCHAR_MAX);
578 :
579 0 : PG_RETURN_VOID();
580 : }
|
