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 55806946 : btboolcmp(PG_FUNCTION_ARGS)
75 : {
76 55806946 : bool a = PG_GETARG_BOOL(0);
77 55806946 : bool b = PG_GETARG_BOOL(1);
78 :
79 55806946 : 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 12067654 : btint2cmp(PG_FUNCTION_ARGS)
129 : {
130 12067654 : int16 a = PG_GETARG_INT16(0);
131 12067654 : int16 b = PG_GETARG_INT16(1);
132 :
133 12067654 : PG_RETURN_INT32((int32) a - (int32) b);
134 : }
135 :
136 : static int
137 41001826 : btint2fastcmp(Datum x, Datum y, SortSupport ssup)
138 : {
139 41001826 : int16 a = DatumGetInt16(x);
140 41001826 : int16 b = DatumGetInt16(y);
141 :
142 41001826 : return (int) a - (int) b;
143 : }
144 :
145 : Datum
146 12134 : btint2sortsupport(PG_FUNCTION_ARGS)
147 : {
148 12134 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
149 :
150 12134 : ssup->comparator = btint2fastcmp;
151 12134 : 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 184 : btint2skipsupport(PG_FUNCTION_ARGS)
188 : {
189 184 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
190 :
191 184 : sksup->decrement = int2_decrement;
192 184 : sksup->increment = int2_increment;
193 184 : sksup->low_elem = Int16GetDatum(PG_INT16_MIN);
194 184 : sksup->high_elem = Int16GetDatum(PG_INT16_MAX);
195 :
196 184 : PG_RETURN_VOID();
197 : }
198 :
199 : Datum
200 98787666 : btint4cmp(PG_FUNCTION_ARGS)
201 : {
202 98787666 : int32 a = PG_GETARG_INT32(0);
203 98787666 : int32 b = PG_GETARG_INT32(1);
204 :
205 98787666 : if (a > b)
206 37992818 : PG_RETURN_INT32(A_GREATER_THAN_B);
207 60794848 : else if (a == b)
208 20415552 : PG_RETURN_INT32(0);
209 : else
210 40379296 : PG_RETURN_INT32(A_LESS_THAN_B);
211 : }
212 :
213 : Datum
214 173436 : btint4sortsupport(PG_FUNCTION_ARGS)
215 : {
216 173436 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
217 :
218 173436 : ssup->comparator = ssup_datum_int32_cmp;
219 173436 : 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 16636422 : btint8cmp(PG_FUNCTION_ARGS)
269 : {
270 16636422 : int64 a = PG_GETARG_INT64(0);
271 16636422 : int64 b = PG_GETARG_INT64(1);
272 :
273 16636422 : if (a > b)
274 9721434 : PG_RETURN_INT32(A_GREATER_THAN_B);
275 6914988 : else if (a == b)
276 844934 : PG_RETURN_INT32(0);
277 : else
278 6070054 : PG_RETURN_INT32(A_LESS_THAN_B);
279 : }
280 :
281 : #if SIZEOF_DATUM < 8
282 : static int
283 : btint8fastcmp(Datum x, Datum y, SortSupport ssup)
284 : {
285 : int64 a = DatumGetInt64(x);
286 : int64 b = DatumGetInt64(y);
287 :
288 : if (a > b)
289 : return A_GREATER_THAN_B;
290 : else if (a == b)
291 : return 0;
292 : else
293 : return A_LESS_THAN_B;
294 : }
295 : #endif
296 :
297 : Datum
298 3786 : btint8sortsupport(PG_FUNCTION_ARGS)
299 : {
300 3786 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
301 :
302 : #if SIZEOF_DATUM >= 8
303 3786 : ssup->comparator = ssup_datum_signed_cmp;
304 : #else
305 : ssup->comparator = btint8fastcmp;
306 : #endif
307 3786 : PG_RETURN_VOID();
308 : }
309 :
310 : static Datum
311 0 : int8_decrement(Relation rel, Datum existing, bool *underflow)
312 : {
313 0 : int64 iexisting = DatumGetInt64(existing);
314 :
315 0 : if (iexisting == PG_INT64_MIN)
316 : {
317 : /* return value is undefined */
318 0 : *underflow = true;
319 0 : return (Datum) 0;
320 : }
321 :
322 0 : *underflow = false;
323 0 : return Int64GetDatum(iexisting - 1);
324 : }
325 :
326 : static Datum
327 0 : int8_increment(Relation rel, Datum existing, bool *overflow)
328 : {
329 0 : int64 iexisting = DatumGetInt64(existing);
330 :
331 0 : if (iexisting == PG_INT64_MAX)
332 : {
333 : /* return value is undefined */
334 0 : *overflow = true;
335 0 : return (Datum) 0;
336 : }
337 :
338 0 : *overflow = false;
339 0 : return Int64GetDatum(iexisting + 1);
340 : }
341 :
342 : Datum
343 0 : btint8skipsupport(PG_FUNCTION_ARGS)
344 : {
345 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
346 :
347 0 : sksup->decrement = int8_decrement;
348 0 : sksup->increment = int8_increment;
349 0 : sksup->low_elem = Int64GetDatum(PG_INT64_MIN);
350 0 : sksup->high_elem = Int64GetDatum(PG_INT64_MAX);
351 :
352 0 : PG_RETURN_VOID();
353 : }
354 :
355 : Datum
356 1452 : btint48cmp(PG_FUNCTION_ARGS)
357 : {
358 1452 : int32 a = PG_GETARG_INT32(0);
359 1452 : int64 b = PG_GETARG_INT64(1);
360 :
361 1452 : if (a > b)
362 498 : PG_RETURN_INT32(A_GREATER_THAN_B);
363 954 : else if (a == b)
364 66 : PG_RETURN_INT32(0);
365 : else
366 888 : PG_RETURN_INT32(A_LESS_THAN_B);
367 : }
368 :
369 : Datum
370 102 : btint84cmp(PG_FUNCTION_ARGS)
371 : {
372 102 : int64 a = PG_GETARG_INT64(0);
373 102 : int32 b = PG_GETARG_INT32(1);
374 :
375 102 : if (a > b)
376 30 : PG_RETURN_INT32(A_GREATER_THAN_B);
377 72 : else if (a == b)
378 30 : PG_RETURN_INT32(0);
379 : else
380 42 : PG_RETURN_INT32(A_LESS_THAN_B);
381 : }
382 :
383 : Datum
384 52180 : btint24cmp(PG_FUNCTION_ARGS)
385 : {
386 52180 : int16 a = PG_GETARG_INT16(0);
387 52180 : int32 b = PG_GETARG_INT32(1);
388 :
389 52180 : if (a > b)
390 28242 : PG_RETURN_INT32(A_GREATER_THAN_B);
391 23938 : else if (a == b)
392 8060 : PG_RETURN_INT32(0);
393 : else
394 15878 : PG_RETURN_INT32(A_LESS_THAN_B);
395 : }
396 :
397 : Datum
398 1352 : btint42cmp(PG_FUNCTION_ARGS)
399 : {
400 1352 : int32 a = PG_GETARG_INT32(0);
401 1352 : int16 b = PG_GETARG_INT16(1);
402 :
403 1352 : if (a > b)
404 82 : PG_RETURN_INT32(A_GREATER_THAN_B);
405 1270 : else if (a == b)
406 300 : PG_RETURN_INT32(0);
407 : else
408 970 : PG_RETURN_INT32(A_LESS_THAN_B);
409 : }
410 :
411 : Datum
412 36 : btint28cmp(PG_FUNCTION_ARGS)
413 : {
414 36 : int16 a = PG_GETARG_INT16(0);
415 36 : int64 b = PG_GETARG_INT64(1);
416 :
417 36 : if (a > b)
418 0 : PG_RETURN_INT32(A_GREATER_THAN_B);
419 36 : else if (a == b)
420 0 : PG_RETURN_INT32(0);
421 : else
422 36 : PG_RETURN_INT32(A_LESS_THAN_B);
423 : }
424 :
425 : Datum
426 0 : btint82cmp(PG_FUNCTION_ARGS)
427 : {
428 0 : int64 a = PG_GETARG_INT64(0);
429 0 : int16 b = PG_GETARG_INT16(1);
430 :
431 0 : if (a > b)
432 0 : PG_RETURN_INT32(A_GREATER_THAN_B);
433 0 : else if (a == b)
434 0 : PG_RETURN_INT32(0);
435 : else
436 0 : PG_RETURN_INT32(A_LESS_THAN_B);
437 : }
438 :
439 : Datum
440 217207336 : btoidcmp(PG_FUNCTION_ARGS)
441 : {
442 217207336 : Oid a = PG_GETARG_OID(0);
443 217207336 : Oid b = PG_GETARG_OID(1);
444 :
445 217207336 : if (a > b)
446 58014898 : PG_RETURN_INT32(A_GREATER_THAN_B);
447 159192438 : else if (a == b)
448 51628762 : PG_RETURN_INT32(0);
449 : else
450 107563676 : PG_RETURN_INT32(A_LESS_THAN_B);
451 : }
452 :
453 : static int
454 267712030 : btoidfastcmp(Datum x, Datum y, SortSupport ssup)
455 : {
456 267712030 : Oid a = DatumGetObjectId(x);
457 267712030 : Oid b = DatumGetObjectId(y);
458 :
459 267712030 : if (a > b)
460 67427412 : return A_GREATER_THAN_B;
461 200284618 : else if (a == b)
462 135527190 : return 0;
463 : else
464 64757428 : return A_LESS_THAN_B;
465 : }
466 :
467 : Datum
468 125082 : btoidsortsupport(PG_FUNCTION_ARGS)
469 : {
470 125082 : SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
471 :
472 125082 : ssup->comparator = btoidfastcmp;
473 125082 : PG_RETURN_VOID();
474 : }
475 :
476 : static Datum
477 0 : oid_decrement(Relation rel, Datum existing, bool *underflow)
478 : {
479 0 : Oid oexisting = DatumGetObjectId(existing);
480 :
481 0 : if (oexisting == InvalidOid)
482 : {
483 : /* return value is undefined */
484 0 : *underflow = true;
485 0 : return (Datum) 0;
486 : }
487 :
488 0 : *underflow = false;
489 0 : return ObjectIdGetDatum(oexisting - 1);
490 : }
491 :
492 : static Datum
493 358 : oid_increment(Relation rel, Datum existing, bool *overflow)
494 : {
495 358 : Oid oexisting = DatumGetObjectId(existing);
496 :
497 358 : if (oexisting == OID_MAX)
498 : {
499 : /* return value is undefined */
500 0 : *overflow = true;
501 0 : return (Datum) 0;
502 : }
503 :
504 358 : *overflow = false;
505 358 : return ObjectIdGetDatum(oexisting + 1);
506 : }
507 :
508 : Datum
509 2828 : btoidskipsupport(PG_FUNCTION_ARGS)
510 : {
511 2828 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
512 :
513 2828 : sksup->decrement = oid_decrement;
514 2828 : sksup->increment = oid_increment;
515 2828 : sksup->low_elem = ObjectIdGetDatum(InvalidOid);
516 2828 : sksup->high_elem = ObjectIdGetDatum(OID_MAX);
517 :
518 2828 : PG_RETURN_VOID();
519 : }
520 :
521 : Datum
522 7565046 : btoidvectorcmp(PG_FUNCTION_ARGS)
523 : {
524 7565046 : oidvector *a = (oidvector *) PG_GETARG_POINTER(0);
525 7565046 : oidvector *b = (oidvector *) PG_GETARG_POINTER(1);
526 : int i;
527 :
528 : /* We arbitrarily choose to sort first by vector length */
529 7565046 : if (a->dim1 != b->dim1)
530 1276952 : PG_RETURN_INT32(a->dim1 - b->dim1);
531 :
532 11035144 : for (i = 0; i < a->dim1; i++)
533 : {
534 8410402 : if (a->values[i] != b->values[i])
535 : {
536 3663352 : if (a->values[i] > b->values[i])
537 1847652 : PG_RETURN_INT32(A_GREATER_THAN_B);
538 : else
539 1815700 : PG_RETURN_INT32(A_LESS_THAN_B);
540 : }
541 : }
542 2624742 : PG_RETURN_INT32(0);
543 : }
544 :
545 : Datum
546 57561274 : btcharcmp(PG_FUNCTION_ARGS)
547 : {
548 57561274 : char a = PG_GETARG_CHAR(0);
549 57561274 : char b = PG_GETARG_CHAR(1);
550 :
551 : /* Be careful to compare chars as unsigned */
552 57561274 : PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
553 : }
554 :
555 : static Datum
556 0 : char_decrement(Relation rel, Datum existing, bool *underflow)
557 : {
558 0 : uint8 cexisting = UInt8GetDatum(existing);
559 :
560 0 : if (cexisting == 0)
561 : {
562 : /* return value is undefined */
563 0 : *underflow = true;
564 0 : return (Datum) 0;
565 : }
566 :
567 0 : *underflow = false;
568 0 : return CharGetDatum((uint8) cexisting - 1);
569 : }
570 :
571 : static Datum
572 0 : char_increment(Relation rel, Datum existing, bool *overflow)
573 : {
574 0 : uint8 cexisting = UInt8GetDatum(existing);
575 :
576 0 : if (cexisting == UCHAR_MAX)
577 : {
578 : /* return value is undefined */
579 0 : *overflow = true;
580 0 : return (Datum) 0;
581 : }
582 :
583 0 : *overflow = false;
584 0 : return CharGetDatum((uint8) cexisting + 1);
585 : }
586 :
587 : Datum
588 0 : btcharskipsupport(PG_FUNCTION_ARGS)
589 : {
590 0 : SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
591 :
592 0 : sksup->decrement = char_decrement;
593 0 : sksup->increment = char_increment;
594 :
595 : /* btcharcmp compares chars as unsigned */
596 0 : sksup->low_elem = UInt8GetDatum(0);
597 0 : sksup->high_elem = UInt8GetDatum(UCHAR_MAX);
598 :
599 0 : PG_RETURN_VOID();
600 : }
|