Debian Codegraph @

src/backend/access/nbtree/nbtcompare.c

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