1 /*-------------------------------------------------------------------------
2 *
3 * nbtcompare.c
4 * Comparison functions for btree access method.
5 *
6 * Portions Copyright (c) 1996-2021, 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/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
btboolcmp(PG_FUNCTION_ARGS)73 btboolcmp(PG_FUNCTION_ARGS)
74 {
75 bool a = PG_GETARG_BOOL(0);
76 bool b = PG_GETARG_BOOL(1);
77
78 PG_RETURN_INT32((int32) a - (int32) b);
79 }
80
81 Datum
btint2cmp(PG_FUNCTION_ARGS)82 btint2cmp(PG_FUNCTION_ARGS)
83 {
84 int16 a = PG_GETARG_INT16(0);
85 int16 b = PG_GETARG_INT16(1);
86
87 PG_RETURN_INT32((int32) a - (int32) b);
88 }
89
90 static int
btint2fastcmp(Datum x,Datum y,SortSupport ssup)91 btint2fastcmp(Datum x, Datum y, SortSupport ssup)
92 {
93 int16 a = DatumGetInt16(x);
94 int16 b = DatumGetInt16(y);
95
96 return (int) a - (int) b;
97 }
98
99 Datum
btint2sortsupport(PG_FUNCTION_ARGS)100 btint2sortsupport(PG_FUNCTION_ARGS)
101 {
102 SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
103
104 ssup->comparator = btint2fastcmp;
105 PG_RETURN_VOID();
106 }
107
108 Datum
btint4cmp(PG_FUNCTION_ARGS)109 btint4cmp(PG_FUNCTION_ARGS)
110 {
111 int32 a = PG_GETARG_INT32(0);
112 int32 b = PG_GETARG_INT32(1);
113
114 if (a > b)
115 PG_RETURN_INT32(A_GREATER_THAN_B);
116 else if (a == b)
117 PG_RETURN_INT32(0);
118 else
119 PG_RETURN_INT32(A_LESS_THAN_B);
120 }
121
122 static int
btint4fastcmp(Datum x,Datum y,SortSupport ssup)123 btint4fastcmp(Datum x, Datum y, SortSupport ssup)
124 {
125 int32 a = DatumGetInt32(x);
126 int32 b = DatumGetInt32(y);
127
128 if (a > b)
129 return A_GREATER_THAN_B;
130 else if (a == b)
131 return 0;
132 else
133 return A_LESS_THAN_B;
134 }
135
136 Datum
btint4sortsupport(PG_FUNCTION_ARGS)137 btint4sortsupport(PG_FUNCTION_ARGS)
138 {
139 SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
140
141 ssup->comparator = btint4fastcmp;
142 PG_RETURN_VOID();
143 }
144
145 Datum
btint8cmp(PG_FUNCTION_ARGS)146 btint8cmp(PG_FUNCTION_ARGS)
147 {
148 int64 a = PG_GETARG_INT64(0);
149 int64 b = PG_GETARG_INT64(1);
150
151 if (a > b)
152 PG_RETURN_INT32(A_GREATER_THAN_B);
153 else if (a == b)
154 PG_RETURN_INT32(0);
155 else
156 PG_RETURN_INT32(A_LESS_THAN_B);
157 }
158
159 static int
btint8fastcmp(Datum x,Datum y,SortSupport ssup)160 btint8fastcmp(Datum x, Datum y, SortSupport ssup)
161 {
162 int64 a = DatumGetInt64(x);
163 int64 b = DatumGetInt64(y);
164
165 if (a > b)
166 return A_GREATER_THAN_B;
167 else if (a == b)
168 return 0;
169 else
170 return A_LESS_THAN_B;
171 }
172
173 Datum
btint8sortsupport(PG_FUNCTION_ARGS)174 btint8sortsupport(PG_FUNCTION_ARGS)
175 {
176 SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
177
178 ssup->comparator = btint8fastcmp;
179 PG_RETURN_VOID();
180 }
181
182 Datum
btint48cmp(PG_FUNCTION_ARGS)183 btint48cmp(PG_FUNCTION_ARGS)
184 {
185 int32 a = PG_GETARG_INT32(0);
186 int64 b = PG_GETARG_INT64(1);
187
188 if (a > b)
189 PG_RETURN_INT32(A_GREATER_THAN_B);
190 else if (a == b)
191 PG_RETURN_INT32(0);
192 else
193 PG_RETURN_INT32(A_LESS_THAN_B);
194 }
195
196 Datum
btint84cmp(PG_FUNCTION_ARGS)197 btint84cmp(PG_FUNCTION_ARGS)
198 {
199 int64 a = PG_GETARG_INT64(0);
200 int32 b = PG_GETARG_INT32(1);
201
202 if (a > b)
203 PG_RETURN_INT32(A_GREATER_THAN_B);
204 else if (a == b)
205 PG_RETURN_INT32(0);
206 else
207 PG_RETURN_INT32(A_LESS_THAN_B);
208 }
209
210 Datum
btint24cmp(PG_FUNCTION_ARGS)211 btint24cmp(PG_FUNCTION_ARGS)
212 {
213 int16 a = PG_GETARG_INT16(0);
214 int32 b = PG_GETARG_INT32(1);
215
216 if (a > b)
217 PG_RETURN_INT32(A_GREATER_THAN_B);
218 else if (a == b)
219 PG_RETURN_INT32(0);
220 else
221 PG_RETURN_INT32(A_LESS_THAN_B);
222 }
223
224 Datum
btint42cmp(PG_FUNCTION_ARGS)225 btint42cmp(PG_FUNCTION_ARGS)
226 {
227 int32 a = PG_GETARG_INT32(0);
228 int16 b = PG_GETARG_INT16(1);
229
230 if (a > b)
231 PG_RETURN_INT32(A_GREATER_THAN_B);
232 else if (a == b)
233 PG_RETURN_INT32(0);
234 else
235 PG_RETURN_INT32(A_LESS_THAN_B);
236 }
237
238 Datum
btint28cmp(PG_FUNCTION_ARGS)239 btint28cmp(PG_FUNCTION_ARGS)
240 {
241 int16 a = PG_GETARG_INT16(0);
242 int64 b = PG_GETARG_INT64(1);
243
244 if (a > b)
245 PG_RETURN_INT32(A_GREATER_THAN_B);
246 else if (a == b)
247 PG_RETURN_INT32(0);
248 else
249 PG_RETURN_INT32(A_LESS_THAN_B);
250 }
251
252 Datum
btint82cmp(PG_FUNCTION_ARGS)253 btint82cmp(PG_FUNCTION_ARGS)
254 {
255 int64 a = PG_GETARG_INT64(0);
256 int16 b = PG_GETARG_INT16(1);
257
258 if (a > b)
259 PG_RETURN_INT32(A_GREATER_THAN_B);
260 else if (a == b)
261 PG_RETURN_INT32(0);
262 else
263 PG_RETURN_INT32(A_LESS_THAN_B);
264 }
265
266 Datum
btoidcmp(PG_FUNCTION_ARGS)267 btoidcmp(PG_FUNCTION_ARGS)
268 {
269 Oid a = PG_GETARG_OID(0);
270 Oid b = PG_GETARG_OID(1);
271
272 if (a > b)
273 PG_RETURN_INT32(A_GREATER_THAN_B);
274 else if (a == b)
275 PG_RETURN_INT32(0);
276 else
277 PG_RETURN_INT32(A_LESS_THAN_B);
278 }
279
280 static int
btoidfastcmp(Datum x,Datum y,SortSupport ssup)281 btoidfastcmp(Datum x, Datum y, SortSupport ssup)
282 {
283 Oid a = DatumGetObjectId(x);
284 Oid b = DatumGetObjectId(y);
285
286 if (a > b)
287 return A_GREATER_THAN_B;
288 else if (a == b)
289 return 0;
290 else
291 return A_LESS_THAN_B;
292 }
293
294 Datum
btoidsortsupport(PG_FUNCTION_ARGS)295 btoidsortsupport(PG_FUNCTION_ARGS)
296 {
297 SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
298
299 ssup->comparator = btoidfastcmp;
300 PG_RETURN_VOID();
301 }
302
303 Datum
btoidvectorcmp(PG_FUNCTION_ARGS)304 btoidvectorcmp(PG_FUNCTION_ARGS)
305 {
306 oidvector *a = (oidvector *) PG_GETARG_POINTER(0);
307 oidvector *b = (oidvector *) PG_GETARG_POINTER(1);
308 int i;
309
310 /* We arbitrarily choose to sort first by vector length */
311 if (a->dim1 != b->dim1)
312 PG_RETURN_INT32(a->dim1 - b->dim1);
313
314 for (i = 0; i < a->dim1; i++)
315 {
316 if (a->values[i] != b->values[i])
317 {
318 if (a->values[i] > b->values[i])
319 PG_RETURN_INT32(A_GREATER_THAN_B);
320 else
321 PG_RETURN_INT32(A_LESS_THAN_B);
322 }
323 }
324 PG_RETURN_INT32(0);
325 }
326
327 Datum
btcharcmp(PG_FUNCTION_ARGS)328 btcharcmp(PG_FUNCTION_ARGS)
329 {
330 char a = PG_GETARG_CHAR(0);
331 char b = PG_GETARG_CHAR(1);
332
333 /* Be careful to compare chars as unsigned */
334 PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
335 }
336