Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * nbtcompare.c
4 : * Comparison functions for btree access method.
5 : *
6 : * Portions Copyright (c) 1996-2026, 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/builtins.h"
61 : #include "utils/fmgrprotos.h"
62 : #include "utils/skipsupport.h"
63 : #include "utils/sortsupport.h"
64 :
65 : #ifdef STRESS_SORT_INT_MIN
66 : #define A_LESS_THAN_B INT_MIN
67 : #define A_GREATER_THAN_B INT_MAX
68 : #else
69 : #define A_LESS_THAN_B (-1)
70 : #define A_GREATER_THAN_B 1
71 : #endif
72 :
73 :
74 : Datum
75 31353288 : btboolcmp(PG_FUNCTION_ARGS)
76 : {
77 31353288 : bool a = PG_GETARG_BOOL(0);
78 31353288 : bool b = PG_GETARG_BOOL(1);
79 :
80 31353288 : PG_RETURN_INT32((int32) a - (int32) b);
81 : }
82 :
83 : static Datum
84 0 : bool_decrement(Relation rel, Datum existing, bool *underflow)
85 : {
86 0 : bool bexisting = DatumGetBool(existing);
87 :
88 0 : if (bexisting == false)
89 : {
90 : /* return value is undefined */
91 0 : *underflow = true;
92 0 : return (Datum) 0;
93 : }
94 :
95 0 : *underflow = false;
96 0 : return BoolGetDatum(bexisting - 1);
97 : }
98 :
99 : static Datum
100 0 : bool_increment(Relation rel, Datum existing, bool *overflow)
101 : {
102 0 : bool bexisting = DatumGetBool(existing);
103 :
104 0 : if (bexisting == true)
105 : {
106 : /* return value is undefined */
107 0 : *overflow = true;
108 0 : return (Datum) 0;
109 : }
110 :
111 0 : *overflow = false;
112 0 : return BoolGetDatum(bexisting + 1);
113 : }
114 :
115 : Datum
116 0 : btboolskipsupport(PG_FUNCTION_ARGS)
117 : {
118 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
119 :
120 0 : sksup->decrement = bool_decrement;
121 0 : sksup->increment = bool_increment;
122 0 : sksup->low_elem = BoolGetDatum(false);
123 0 : sksup->high_elem = BoolGetDatum(true);
124 :
125 0 : PG_RETURN_VOID();
126 : }
127 :
128 : Datum
129 7077371 : btint2cmp(PG_FUNCTION_ARGS)
130 : {
131 7077371 : int16 a = PG_GETARG_INT16(0);
132 7077371 : int16 b = PG_GETARG_INT16(1);
133 :
134 7077371 : PG_RETURN_INT32((int32) a - (int32) b);
135 : }
136 :
137 : static int
138 23429244 : btint2fastcmp(Datum x, Datum y, SortSupport ssup)
139 : {
140 23429244 : int16 a = DatumGetInt16(x);
141 23429244 : int16 b = DatumGetInt16(y);
142 :
143 23429244 : return (int) a - (int) b;
144 : }
145 :
146 : Datum
147 6092 : btint2sortsupport(PG_FUNCTION_ARGS)
148 : {
149 6092 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
150 :
151 6092 : ssup->comparator = btint2fastcmp;
152 6092 : PG_RETURN_VOID();
153 : }
154 :
155 : static Datum
156 0 : int2_decrement(Relation rel, Datum existing, bool *underflow)
157 : {
158 0 : int16 iexisting = DatumGetInt16(existing);
159 :
160 0 : if (iexisting == PG_INT16_MIN)
161 : {
162 : /* return value is undefined */
163 0 : *underflow = true;
164 0 : return (Datum) 0;
165 : }
166 :
167 0 : *underflow = false;
168 0 : return Int16GetDatum(iexisting - 1);
169 : }
170 :
171 : static Datum
172 2 : int2_increment(Relation rel, Datum existing, bool *overflow)
173 : {
174 2 : int16 iexisting = DatumGetInt16(existing);
175 :
176 2 : if (iexisting == PG_INT16_MAX)
177 : {
178 : /* return value is undefined */
179 0 : *overflow = true;
180 0 : return (Datum) 0;
181 : }
182 :
183 2 : *overflow = false;
184 2 : return Int16GetDatum(iexisting + 1);
185 : }
186 :
187 : Datum
188 94 : btint2skipsupport(PG_FUNCTION_ARGS)
189 : {
190 94 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
191 :
192 94 : sksup->decrement = int2_decrement;
193 94 : sksup->increment = int2_increment;
194 94 : sksup->low_elem = Int16GetDatum(PG_INT16_MIN);
195 94 : sksup->high_elem = Int16GetDatum(PG_INT16_MAX);
196 :
197 94 : PG_RETURN_VOID();
198 : }
199 :
200 : Datum
201 48933793 : btint4cmp(PG_FUNCTION_ARGS)
202 : {
203 48933793 : int32 a = PG_GETARG_INT32(0);
204 48933793 : int32 b = PG_GETARG_INT32(1);
205 :
206 48933793 : if (a > b)
207 18621068 : PG_RETURN_INT32(A_GREATER_THAN_B);
208 30312725 : else if (a == b)
209 10164226 : PG_RETURN_INT32(0);
210 : else
211 20148499 : PG_RETURN_INT32(A_LESS_THAN_B);
212 : }
213 :
214 : Datum
215 88260 : btint4sortsupport(PG_FUNCTION_ARGS)
216 : {
217 88260 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
218 :
219 88260 : ssup->comparator = ssup_datum_int32_cmp;
220 88260 : PG_RETURN_VOID();
221 : }
222 :
223 : static Datum
224 1983 : int4_decrement(Relation rel, Datum existing, bool *underflow)
225 : {
226 1983 : int32 iexisting = DatumGetInt32(existing);
227 :
228 1983 : if (iexisting == PG_INT32_MIN)
229 : {
230 : /* return value is undefined */
231 0 : *underflow = true;
232 0 : return (Datum) 0;
233 : }
234 :
235 1983 : *underflow = false;
236 1983 : return Int32GetDatum(iexisting - 1);
237 : }
238 :
239 : static Datum
240 1911 : int4_increment(Relation rel, Datum existing, bool *overflow)
241 : {
242 1911 : int32 iexisting = DatumGetInt32(existing);
243 :
244 1911 : if (iexisting == PG_INT32_MAX)
245 : {
246 : /* return value is undefined */
247 15 : *overflow = true;
248 15 : return (Datum) 0;
249 : }
250 :
251 1896 : *overflow = false;
252 1896 : return Int32GetDatum(iexisting + 1);
253 : }
254 :
255 : Datum
256 123 : btint4skipsupport(PG_FUNCTION_ARGS)
257 : {
258 123 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
259 :
260 123 : sksup->decrement = int4_decrement;
261 123 : sksup->increment = int4_increment;
262 123 : sksup->low_elem = Int32GetDatum(PG_INT32_MIN);
263 123 : sksup->high_elem = Int32GetDatum(PG_INT32_MAX);
264 :
265 123 : PG_RETURN_VOID();
266 : }
267 :
268 : Datum
269 8318696 : btint8cmp(PG_FUNCTION_ARGS)
270 : {
271 8318696 : int64 a = PG_GETARG_INT64(0);
272 8318696 : int64 b = PG_GETARG_INT64(1);
273 :
274 8318696 : if (a > b)
275 4860883 : PG_RETURN_INT32(A_GREATER_THAN_B);
276 3457813 : else if (a == b)
277 422567 : PG_RETURN_INT32(0);
278 : else
279 3035246 : PG_RETURN_INT32(A_LESS_THAN_B);
280 : }
281 :
282 : Datum
283 1771 : btint8sortsupport(PG_FUNCTION_ARGS)
284 : {
285 1771 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
286 :
287 1771 : ssup->comparator = ssup_datum_signed_cmp;
288 1771 : PG_RETURN_VOID();
289 : }
290 :
291 : static Datum
292 0 : int8_decrement(Relation rel, Datum existing, bool *underflow)
293 : {
294 0 : int64 iexisting = DatumGetInt64(existing);
295 :
296 0 : if (iexisting == PG_INT64_MIN)
297 : {
298 : /* return value is undefined */
299 0 : *underflow = true;
300 0 : return (Datum) 0;
301 : }
302 :
303 0 : *underflow = false;
304 0 : return Int64GetDatum(iexisting - 1);
305 : }
306 :
307 : static Datum
308 0 : int8_increment(Relation rel, Datum existing, bool *overflow)
309 : {
310 0 : int64 iexisting = DatumGetInt64(existing);
311 :
312 0 : if (iexisting == PG_INT64_MAX)
313 : {
314 : /* return value is undefined */
315 0 : *overflow = true;
316 0 : return (Datum) 0;
317 : }
318 :
319 0 : *overflow = false;
320 0 : return Int64GetDatum(iexisting + 1);
321 : }
322 :
323 : Datum
324 0 : btint8skipsupport(PG_FUNCTION_ARGS)
325 : {
326 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
327 :
328 0 : sksup->decrement = int8_decrement;
329 0 : sksup->increment = int8_increment;
330 0 : sksup->low_elem = Int64GetDatum(PG_INT64_MIN);
331 0 : sksup->high_elem = Int64GetDatum(PG_INT64_MAX);
332 :
333 0 : PG_RETURN_VOID();
334 : }
335 :
336 : Datum
337 743 : btint48cmp(PG_FUNCTION_ARGS)
338 : {
339 743 : int32 a = PG_GETARG_INT32(0);
340 743 : int64 b = PG_GETARG_INT64(1);
341 :
342 743 : if (a > b)
343 255 : PG_RETURN_INT32(A_GREATER_THAN_B);
344 488 : else if (a == b)
345 38 : PG_RETURN_INT32(0);
346 : else
347 450 : PG_RETURN_INT32(A_LESS_THAN_B);
348 : }
349 :
350 : Datum
351 110 : btint84cmp(PG_FUNCTION_ARGS)
352 : {
353 110 : int64 a = PG_GETARG_INT64(0);
354 110 : int32 b = PG_GETARG_INT32(1);
355 :
356 110 : if (a > b)
357 39 : PG_RETURN_INT32(A_GREATER_THAN_B);
358 71 : else if (a == b)
359 29 : PG_RETURN_INT32(0);
360 : else
361 42 : PG_RETURN_INT32(A_LESS_THAN_B);
362 : }
363 :
364 : Datum
365 29544 : btint24cmp(PG_FUNCTION_ARGS)
366 : {
367 29544 : int16 a = PG_GETARG_INT16(0);
368 29544 : int32 b = PG_GETARG_INT32(1);
369 :
370 29544 : if (a > b)
371 16084 : PG_RETURN_INT32(A_GREATER_THAN_B);
372 13460 : else if (a == b)
373 4928 : PG_RETURN_INT32(0);
374 : else
375 8532 : PG_RETURN_INT32(A_LESS_THAN_B);
376 : }
377 :
378 : Datum
379 751 : btint42cmp(PG_FUNCTION_ARGS)
380 : {
381 751 : int32 a = PG_GETARG_INT32(0);
382 751 : int16 b = PG_GETARG_INT16(1);
383 :
384 751 : if (a > b)
385 64 : PG_RETURN_INT32(A_GREATER_THAN_B);
386 687 : else if (a == b)
387 157 : PG_RETURN_INT32(0);
388 : else
389 530 : PG_RETURN_INT32(A_LESS_THAN_B);
390 : }
391 :
392 : Datum
393 35 : btint28cmp(PG_FUNCTION_ARGS)
394 : {
395 35 : int16 a = PG_GETARG_INT16(0);
396 35 : int64 b = PG_GETARG_INT64(1);
397 :
398 35 : if (a > b)
399 6 : PG_RETURN_INT32(A_GREATER_THAN_B);
400 29 : else if (a == b)
401 5 : PG_RETURN_INT32(0);
402 : else
403 24 : PG_RETURN_INT32(A_LESS_THAN_B);
404 : }
405 :
406 : Datum
407 17 : btint82cmp(PG_FUNCTION_ARGS)
408 : {
409 17 : int64 a = PG_GETARG_INT64(0);
410 17 : int16 b = PG_GETARG_INT16(1);
411 :
412 17 : if (a > b)
413 6 : PG_RETURN_INT32(A_GREATER_THAN_B);
414 11 : else if (a == b)
415 5 : PG_RETURN_INT32(0);
416 : else
417 6 : PG_RETURN_INT32(A_LESS_THAN_B);
418 : }
419 :
420 : Datum
421 121214219 : btoidcmp(PG_FUNCTION_ARGS)
422 : {
423 121214219 : Oid a = PG_GETARG_OID(0);
424 121214219 : Oid b = PG_GETARG_OID(1);
425 :
426 121214219 : if (a > b)
427 33660829 : PG_RETURN_INT32(A_GREATER_THAN_B);
428 87553390 : else if (a == b)
429 28392956 : PG_RETURN_INT32(0);
430 : else
431 59160434 : PG_RETURN_INT32(A_LESS_THAN_B);
432 : }
433 :
434 : static int
435 143530267 : btoidfastcmp(Datum x, Datum y, SortSupport ssup)
436 : {
437 143530267 : Oid a = DatumGetObjectId(x);
438 143530267 : Oid b = DatumGetObjectId(y);
439 :
440 143530267 : if (a > b)
441 34711835 : return A_GREATER_THAN_B;
442 108818432 : else if (a == b)
443 72823184 : return 0;
444 : else
445 35995248 : return A_LESS_THAN_B;
446 : }
447 :
448 : Datum
449 64494 : btoidsortsupport(PG_FUNCTION_ARGS)
450 : {
451 64494 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
452 :
453 64494 : ssup->comparator = btoidfastcmp;
454 64494 : PG_RETURN_VOID();
455 : }
456 :
457 : static Datum
458 0 : oid_decrement(Relation rel, Datum existing, bool *underflow)
459 : {
460 0 : Oid oexisting = DatumGetObjectId(existing);
461 :
462 0 : if (oexisting == InvalidOid)
463 : {
464 : /* return value is undefined */
465 0 : *underflow = true;
466 0 : return (Datum) 0;
467 : }
468 :
469 0 : *underflow = false;
470 0 : return ObjectIdGetDatum(oexisting - 1);
471 : }
472 :
473 : static Datum
474 212 : oid_increment(Relation rel, Datum existing, bool *overflow)
475 : {
476 212 : Oid oexisting = DatumGetObjectId(existing);
477 :
478 212 : if (oexisting == OID_MAX)
479 : {
480 : /* return value is undefined */
481 0 : *overflow = true;
482 0 : return (Datum) 0;
483 : }
484 :
485 212 : *overflow = false;
486 212 : return ObjectIdGetDatum(oexisting + 1);
487 : }
488 :
489 : Datum
490 1603 : btoidskipsupport(PG_FUNCTION_ARGS)
491 : {
492 1603 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
493 :
494 1603 : sksup->decrement = oid_decrement;
495 1603 : sksup->increment = oid_increment;
496 1603 : sksup->low_elem = ObjectIdGetDatum(InvalidOid);
497 1603 : sksup->high_elem = ObjectIdGetDatum(OID_MAX);
498 :
499 1603 : PG_RETURN_VOID();
500 : }
501 :
502 : Datum
503 9 : btoid8cmp(PG_FUNCTION_ARGS)
504 : {
505 9 : Oid8 a = PG_GETARG_OID8(0);
506 9 : Oid8 b = PG_GETARG_OID8(1);
507 :
508 9 : if (a > b)
509 3 : PG_RETURN_INT32(A_GREATER_THAN_B);
510 6 : else if (a == b)
511 3 : PG_RETURN_INT32(0);
512 : else
513 3 : PG_RETURN_INT32(A_LESS_THAN_B);
514 : }
515 :
516 : static int
517 2187 : btoid8fastcmp(Datum x, Datum y, SortSupport ssup)
518 : {
519 2187 : Oid8 a = DatumGetObjectId8(x);
520 2187 : Oid8 b = DatumGetObjectId8(y);
521 :
522 2187 : if (a > b)
523 1317 : return A_GREATER_THAN_B;
524 870 : else if (a == b)
525 0 : return 0;
526 : else
527 870 : return A_LESS_THAN_B;
528 : }
529 :
530 : Datum
531 6 : btoid8sortsupport(PG_FUNCTION_ARGS)
532 : {
533 6 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
534 :
535 6 : ssup->comparator = btoid8fastcmp;
536 6 : PG_RETURN_VOID();
537 : }
538 :
539 : static Datum
540 0 : oid8_decrement(Relation rel, Datum existing, bool *underflow)
541 : {
542 0 : Oid8 oexisting = DatumGetObjectId8(existing);
543 :
544 0 : if (oexisting == InvalidOid8)
545 : {
546 : /* return value is undefined */
547 0 : *underflow = true;
548 0 : return (Datum) 0;
549 : }
550 :
551 0 : *underflow = false;
552 0 : return ObjectId8GetDatum(oexisting - 1);
553 : }
554 :
555 : static Datum
556 0 : oid8_increment(Relation rel, Datum existing, bool *overflow)
557 : {
558 0 : Oid8 oexisting = DatumGetObjectId8(existing);
559 :
560 0 : if (oexisting == OID8_MAX)
561 : {
562 : /* return value is undefined */
563 0 : *overflow = true;
564 0 : return (Datum) 0;
565 : }
566 :
567 0 : *overflow = false;
568 0 : return ObjectId8GetDatum(oexisting + 1);
569 : }
570 :
571 : Datum
572 0 : btoid8skipsupport(PG_FUNCTION_ARGS)
573 : {
574 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
575 :
576 0 : sksup->decrement = oid8_decrement;
577 0 : sksup->increment = oid8_increment;
578 0 : sksup->low_elem = ObjectId8GetDatum(InvalidOid8);
579 0 : sksup->high_elem = ObjectId8GetDatum(OID8_MAX);
580 :
581 0 : PG_RETURN_VOID();
582 : }
583 :
584 : Datum
585 3976609 : btoidvectorcmp(PG_FUNCTION_ARGS)
586 : {
587 3976609 : oidvector *a = (oidvector *) PG_GETARG_POINTER(0);
588 3976609 : oidvector *b = (oidvector *) PG_GETARG_POINTER(1);
589 : int i;
590 :
591 3976609 : check_valid_oidvector(a);
592 3976609 : check_valid_oidvector(b);
593 :
594 : /* We arbitrarily choose to sort first by vector length */
595 3976609 : if (a->dim1 != b->dim1)
596 654994 : PG_RETURN_INT32(a->dim1 - b->dim1);
597 :
598 5829293 : for (i = 0; i < a->dim1; i++)
599 : {
600 4465347 : if (a->values[i] != b->values[i])
601 : {
602 1957669 : if (a->values[i] > b->values[i])
603 1028245 : PG_RETURN_INT32(A_GREATER_THAN_B);
604 : else
605 929424 : PG_RETURN_INT32(A_LESS_THAN_B);
606 : }
607 : }
608 1363946 : PG_RETURN_INT32(0);
609 : }
610 :
611 : Datum
612 31602192 : btcharcmp(PG_FUNCTION_ARGS)
613 : {
614 31602192 : char a = PG_GETARG_CHAR(0);
615 31602192 : char b = PG_GETARG_CHAR(1);
616 :
617 : /* Be careful to compare chars as unsigned */
618 31602192 : PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
619 : }
620 :
621 : static Datum
622 0 : char_decrement(Relation rel, Datum existing, bool *underflow)
623 : {
624 0 : uint8 cexisting = DatumGetUInt8(existing);
625 :
626 0 : if (cexisting == 0)
627 : {
628 : /* return value is undefined */
629 0 : *underflow = true;
630 0 : return (Datum) 0;
631 : }
632 :
633 0 : *underflow = false;
634 0 : return CharGetDatum((uint8) cexisting - 1);
635 : }
636 :
637 : static Datum
638 0 : char_increment(Relation rel, Datum existing, bool *overflow)
639 : {
640 0 : uint8 cexisting = DatumGetUInt8(existing);
641 :
642 0 : if (cexisting == UCHAR_MAX)
643 : {
644 : /* return value is undefined */
645 0 : *overflow = true;
646 0 : return (Datum) 0;
647 : }
648 :
649 0 : *overflow = false;
650 0 : return CharGetDatum((uint8) cexisting + 1);
651 : }
652 :
653 : Datum
654 0 : btcharskipsupport(PG_FUNCTION_ARGS)
655 : {
656 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
657 :
658 0 : sksup->decrement = char_decrement;
659 0 : sksup->increment = char_increment;
660 :
661 : /* btcharcmp compares chars as unsigned */
662 0 : sksup->low_elem = UInt8GetDatum(0);
663 0 : sksup->high_elem = UInt8GetDatum(UCHAR_MAX);
664 :
665 0 : PG_RETURN_VOID();
666 : }
|
