← Back to branch summary

~ubuntu-branches/ubuntu/lucid/postgresql-8.4/lucid-proposed

« back to all changes in this revision

Viewing changes to contrib/intarray/_int_tool.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-03-20 12:00:13 UTC
  • Revision ID: james.westby@ubuntu.com-20090320120013-hogj7egc5mjncc5g
Tags: upstream-8.4~0cvs20090328
Import upstream version 8.4~0cvs20090328

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/intarray/_int_tool.c
 
1
/*
 
2
 * $PostgreSQL:$ 
 
3
 */
 
4
#include "postgres.h"
 
5
 
 
6
#include "catalog/pg_type.h"
 
7
 
 
8
#include "_int.h"
 
9
 
 
10
 
 
11
bool
 
12
inner_int_contains(ArrayType *a, ArrayType *b)
 
13
{
 
14
        int                     na,
 
15
                                nb;
 
16
        int                     i,
 
17
                                j,
 
18
                                n;
 
19
        int                *da,
 
20
                           *db;
 
21
 
 
22
        CHECKARRVALID(a);
 
23
        CHECKARRVALID(b);
 
24
 
 
25
        if (ARRISVOID(a) || ARRISVOID(b))
 
26
                return FALSE;
 
27
 
 
28
        na = ARRNELEMS(a);
 
29
        nb = ARRNELEMS(b);
 
30
        da = ARRPTR(a);
 
31
        db = ARRPTR(b);
 
32
 
 
33
        i = j = n = 0;
 
34
        while (i < na && j < nb)
 
35
                if (da[i] < db[j])
 
36
                        i++;
 
37
                else if (da[i] == db[j])
 
38
                {
 
39
                        n++;
 
40
                        i++;
 
41
                        j++;
 
42
                }
 
43
                else
 
44
                        break;
 
45
 
 
46
        return (n == nb) ? TRUE : FALSE;
 
47
}
 
48
 
 
49
bool
 
50
inner_int_overlap(ArrayType *a, ArrayType *b)
 
51
{
 
52
        int                     na,
 
53
                                nb;
 
54
        int                     i,
 
55
                                j;
 
56
        int                *da,
 
57
                           *db;
 
58
 
 
59
        CHECKARRVALID(a);
 
60
        CHECKARRVALID(b);
 
61
 
 
62
        if (ARRISVOID(a) || ARRISVOID(b))
 
63
                return FALSE;
 
64
 
 
65
        na = ARRNELEMS(a);
 
66
        nb = ARRNELEMS(b);
 
67
        da = ARRPTR(a);
 
68
        db = ARRPTR(b);
 
69
 
 
70
        i = j = 0;
 
71
        while (i < na && j < nb)
 
72
                if (da[i] < db[j])
 
73
                        i++;
 
74
                else if (da[i] == db[j])
 
75
                        return TRUE;
 
76
                else
 
77
                        j++;
 
78
 
 
79
        return FALSE;
 
80
}
 
81
 
 
82
ArrayType *
 
83
inner_int_union(ArrayType *a, ArrayType *b)
 
84
{
 
85
        ArrayType  *r = NULL;
 
86
 
 
87
        CHECKARRVALID(a);
 
88
        CHECKARRVALID(b);
 
89
 
 
90
        if (ARRISVOID(a) && ARRISVOID(b))
 
91
                return new_intArrayType(0);
 
92
        if (ARRISVOID(a))
 
93
                r = copy_intArrayType(b);
 
94
        if (ARRISVOID(b))
 
95
                r = copy_intArrayType(a);
 
96
 
 
97
        if (!r)
 
98
        {
 
99
                int                     na = ARRNELEMS(a),
 
100
                                        nb = ARRNELEMS(b);
 
101
                int                *da = ARRPTR(a),
 
102
                                   *db = ARRPTR(b);
 
103
                int                     i,
 
104
                                        j,
 
105
                                   *dr;
 
106
 
 
107
                r = new_intArrayType(na + nb);
 
108
                dr = ARRPTR(r);
 
109
 
 
110
                /* union */
 
111
                i = j = 0;
 
112
                while (i < na && j < nb)
 
113
                {
 
114
                        if (da[i] == db[j])
 
115
                        {
 
116
                                *dr++ = da[i++];
 
117
                                j++;
 
118
                        }
 
119
                        else if (da[i] < db[j])
 
120
                                *dr++ = da[i++];
 
121
                        else
 
122
                                *dr++ = db[j++];
 
123
                }
 
124
 
 
125
                while (i < na)
 
126
                        *dr++ = da[i++];
 
127
                while (j < nb)
 
128
                        *dr++ = db[j++];
 
129
 
 
130
                r = resize_intArrayType(r, dr - ARRPTR(r));
 
131
        }
 
132
 
 
133
        if (ARRNELEMS(r) > 1)
 
134
                r = _int_unique(r);
 
135
 
 
136
        return r;
 
137
}
 
138
 
 
139
ArrayType *
 
140
inner_int_inter(ArrayType *a, ArrayType *b)
 
141
{
 
142
        ArrayType  *r;
 
143
        int                     na,
 
144
                                nb;
 
145
        int                *da,
 
146
                           *db,
 
147
                           *dr;
 
148
        int                     i,
 
149
                                j;
 
150
 
 
151
        CHECKARRVALID(a);
 
152
        CHECKARRVALID(b);
 
153
 
 
154
        if (ARRISVOID(a) || ARRISVOID(b))
 
155
                return new_intArrayType(0);
 
156
 
 
157
        na = ARRNELEMS(a);
 
158
        nb = ARRNELEMS(b);
 
159
        da = ARRPTR(a);
 
160
        db = ARRPTR(b);
 
161
        r = new_intArrayType(Min(na, nb));
 
162
        dr = ARRPTR(r);
 
163
 
 
164
        i = j = 0;
 
165
        while (i < na && j < nb)
 
166
                if (da[i] < db[j])
 
167
                        i++;
 
168
                else if (da[i] == db[j])
 
169
                {
 
170
                        if (i + j == 0 || (i + j > 0 && *(dr - 1) != db[j]))
 
171
                                *dr++ = db[j];
 
172
                        i++;
 
173
                        j++;
 
174
                }
 
175
                else
 
176
                        j++;
 
177
 
 
178
        if ((dr - ARRPTR(r)) == 0)
 
179
        {
 
180
                pfree(r);
 
181
                return new_intArrayType(0);
 
182
        }
 
183
        else
 
184
                return resize_intArrayType(r, dr - ARRPTR(r));
 
185
}
 
186
 
 
187
void
 
188
rt__int_size(ArrayType *a, float *size)
 
189
{
 
190
        *size = (float) ARRNELEMS(a);
 
191
 
 
192
        return;
 
193
}
 
194
 
 
195
 
 
196
/* len >= 2 */
 
197
bool
 
198
isort(int4 *a, int len)
 
199
{
 
200
        int4            tmp,
 
201
                                index;
 
202
        int4       *cur,
 
203
                           *end;
 
204
        bool            r = FALSE;
 
205
 
 
206
        end = a + len;
 
207
        do
 
208
        {
 
209
                index = 0;
 
210
                cur = a + 1;
 
211
                while (cur < end)
 
212
                {
 
213
                        if (*(cur - 1) > *cur)
 
214
                        {
 
215
                                tmp = *(cur - 1);
 
216
                                *(cur - 1) = *cur;
 
217
                                *cur = tmp;
 
218
                                index = 1;
 
219
                        }
 
220
                        else if (!r && *(cur - 1) == *cur)
 
221
                                r = TRUE;
 
222
                        cur++;
 
223
                }
 
224
        } while (index);
 
225
        return r;
 
226
}
 
227
 
 
228
ArrayType *
 
229
new_intArrayType(int num)
 
230
{
 
231
        ArrayType  *r;
 
232
        int                     nbytes = ARR_OVERHEAD_NONULLS(NDIM) + sizeof(int) * num;
 
233
 
 
234
        r = (ArrayType *) palloc0(nbytes);
 
235
 
 
236
        SET_VARSIZE(r, nbytes);
 
237
        ARR_NDIM(r) = NDIM;
 
238
        r->dataoffset = 0;                      /* marker for no null bitmap */
 
239
        ARR_ELEMTYPE(r) = INT4OID;
 
240
        *((int *) ARR_DIMS(r)) = num;
 
241
        *((int *) ARR_LBOUND(r)) = 1;
 
242
 
 
243
        return r;
 
244
}
 
245
 
 
246
ArrayType *
 
247
resize_intArrayType(ArrayType *a, int num)
 
248
{
 
249
        int                     nbytes = ARR_OVERHEAD_NONULLS(NDIM) + sizeof(int) * num;
 
250
 
 
251
        if (num == ARRNELEMS(a))
 
252
                return a;
 
253
 
 
254
        a = (ArrayType *) repalloc(a, nbytes);
 
255
 
 
256
        SET_VARSIZE(a, nbytes);
 
257
        *((int *) ARR_DIMS(a)) = num;
 
258
        return a;
 
259
}
 
260
 
 
261
ArrayType *
 
262
copy_intArrayType(ArrayType *a)
 
263
{
 
264
        ArrayType  *r;
 
265
 
 
266
        r = new_intArrayType(ARRNELEMS(a));
 
267
        memmove(r, a, VARSIZE(r));
 
268
        return r;
 
269
}
 
270
 
 
271
/* num for compressed key */
 
272
int
 
273
internal_size(int *a, int len)
 
274
{
 
275
        int                     i,
 
276
                                size = 0;
 
277
 
 
278
        for (i = 0; i < len; i += 2)
 
279
                if (!i || a[i] != a[i - 1])             /* do not count repeated range */
 
280
                        size += a[i + 1] - a[i] + 1;
 
281
 
 
282
        return size;
 
283
}
 
284
 
 
285
/* r is sorted and size of r > 1 */
 
286
ArrayType *
 
287
_int_unique(ArrayType *r)
 
288
{
 
289
        int                *tmp,
 
290
                           *dr,
 
291
                           *data;
 
292
        int                     num = ARRNELEMS(r);
 
293
 
 
294
        CHECKARRVALID(r);
 
295
 
 
296
        if (num < 2)
 
297
                return r;
 
298
 
 
299
        data = tmp = dr = ARRPTR(r);
 
300
        while (tmp - data < num)
 
301
                if (*tmp != *dr)
 
302
                        *(++dr) = *tmp++;
 
303
                else
 
304
                        tmp++;
 
305
        return resize_intArrayType(r, dr + 1 - ARRPTR(r));
 
306
}
 
307
 
 
308
void
 
309
gensign(BITVEC sign, int *a, int len)
 
310
{
 
311
        int                     i;
 
312
 
 
313
        /* we assume that the sign vector is previously zeroed */
 
314
        for (i = 0; i < len; i++)
 
315
        {
 
316
                HASH(sign, *a);
 
317
                a++;
 
318
        }
 
319
}
 
320
 
 
321
int32
 
322
intarray_match_first(ArrayType *a, int32 elem)
 
323
{
 
324
        int32      *aa,
 
325
                                c,
 
326
                                i;
 
327
 
 
328
        CHECKARRVALID(a);
 
329
        if (ARRISVOID(a))
 
330
                return 0;
 
331
        c = ARRNELEMS(a);
 
332
        aa = ARRPTR(a);
 
333
        for (i = 0; i < c; i++)
 
334
                if (aa[i] == elem)
 
335
                        return (i + 1);
 
336
        return 0;
 
337
}
 
338
 
 
339
ArrayType *
 
340
intarray_add_elem(ArrayType *a, int32 elem)
 
341
{
 
342
        ArrayType  *result;
 
343
        int32      *r;
 
344
        int32           c;
 
345
 
 
346
        CHECKARRVALID(a);
 
347
        c = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
 
348
        result = new_intArrayType(c + 1);
 
349
        r = ARRPTR(result);
 
350
        if (c > 0)
 
351
                memcpy(r, ARRPTR(a), c * sizeof(int32));
 
352
        r[c] = elem;
 
353
        return result;
 
354
}
 
355
 
 
356
ArrayType *
 
357
intarray_concat_arrays(ArrayType *a, ArrayType *b)
 
358
{
 
359
        ArrayType  *result;
 
360
        int32           ac = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
 
361
        int32           bc = (ARRISVOID(b)) ? 0 : ARRNELEMS(b);
 
362
 
 
363
        CHECKARRVALID(a);
 
364
        CHECKARRVALID(b);
 
365
        result = new_intArrayType(ac + bc);
 
366
        if (ac)
 
367
                memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
 
368
        if (bc)
 
369
                memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
 
370
        return result;
 
371
}
 
372
 
 
373
ArrayType *
 
374
int_to_intset(int32 n)
 
375
{
 
376
        ArrayType  *result;
 
377
        int32      *aa;
 
378
 
 
379
        result = new_intArrayType(1);
 
380
        aa = ARRPTR(result);
 
381
        aa[0] = n;
 
382
        return result;
 
383
}
 
384
 
 
385
int
 
386
compASC(const void *a, const void *b)
 
387
{
 
388
        if (*(int4 *) a == *(int4 *) b)
 
389
                return 0;
 
390
        return (*(int4 *) a > *(int4 *) b) ? 1 : -1;
 
391
}
 
392
 
 
393
int
 
394
compDESC(const void *a, const void *b)
 
395
{
 
396
        if (*(int4 *) a == *(int4 *) b)
 
397
                return 0;
 
398
        return (*(int4 *) a < *(int4 *) b) ? 1 : -1;
 
399
}