_int_tool.c

Go to the documentation of this file.

/*
 * contrib/intarray/_int_tool.c
 */
#include "postgres.h"

#include <limits.h>

#include "_int.h"
#include "catalog/pg_type.h"
#include "lib/qunique.h"

/* arguments are assumed sorted & unique-ified */
bool
inner_int_contains(ArrayType *a, ArrayType *b)
{
    int         na,
                nb;
    int         i,
                j,
                n;
    int        *da,
               *db;

    na = ARRNELEMS(a);
    nb = ARRNELEMS(b);
    da = ARRPTR(a);
    db = ARRPTR(b);

    i = j = n = 0;
    while (i < na && j < nb)
    {
        if (da[i] < db[j])
            i++;
        else if (da[i] == db[j])
        {
            n++;
            i++;
            j++;
        }
        else
            break;              /* db[j] is not in da */
    }

    return (n == nb) ? true : false;
}

/* arguments are assumed sorted */
bool
inner_int_overlap(ArrayType *a, ArrayType *b)
{
    int         na,
                nb;
    int         i,
                j;
    int        *da,
               *db;

    na = ARRNELEMS(a);
    nb = ARRNELEMS(b);
    da = ARRPTR(a);
    db = ARRPTR(b);

    i = j = 0;
    while (i < na && j < nb)
    {
        if (da[i] < db[j])
            i++;
        else if (da[i] == db[j])
            return true;
        else
            j++;
    }

    return false;
}

ArrayType *
inner_int_union(ArrayType *a, ArrayType *b)
{
    ArrayType  *r = NULL;

    CHECKARRVALID(a);
    CHECKARRVALID(b);

    if (ARRISEMPTY(a) && ARRISEMPTY(b))
        return new_intArrayType(0);
    if (ARRISEMPTY(a))
        r = copy_intArrayType(b);
    if (ARRISEMPTY(b))
        r = copy_intArrayType(a);

    if (!r)
    {
        int         na = ARRNELEMS(a),
                    nb = ARRNELEMS(b);
        int        *da = ARRPTR(a),
                   *db = ARRPTR(b);
        int         i,
                    j,
                   *dr;

        r = new_intArrayType(na + nb);
        dr = ARRPTR(r);

        /* union */
        i = j = 0;
        while (i < na && j < nb)
        {
            if (da[i] == db[j])
            {
                *dr++ = da[i++];
                j++;
            }
            else if (da[i] < db[j])
                *dr++ = da[i++];
            else
                *dr++ = db[j++];
        }

        while (i < na)
            *dr++ = da[i++];
        while (j < nb)
            *dr++ = db[j++];

        r = resize_intArrayType(r, dr - ARRPTR(r));
    }

    if (ARRNELEMS(r) > 1)
        r = _int_unique(r);

    return r;
}

ArrayType *
inner_int_inter(ArrayType *a, ArrayType *b)
{
    ArrayType  *r;
    int         na,
                nb;
    int        *da,
               *db,
               *dr;
    int         i,
                j,
                k;

    if (ARRISEMPTY(a) || ARRISEMPTY(b))
        return new_intArrayType(0);

    na = ARRNELEMS(a);
    nb = ARRNELEMS(b);
    da = ARRPTR(a);
    db = ARRPTR(b);
    r = new_intArrayType(Min(na, nb));
    dr = ARRPTR(r);

    i = j = k = 0;
    while (i < na && j < nb)
    {
        if (da[i] < db[j])
            i++;
        else if (da[i] == db[j])
        {
            if (k == 0 || dr[k - 1] != db[j])
                dr[k++] = db[j];
            i++;
            j++;
        }
        else
            j++;
    }

    if (k == 0)
    {
        pfree(r);
        return new_intArrayType(0);
    }
    else
        return resize_intArrayType(r, k);
}

void
rt__int_size(ArrayType *a, float *size)
{
    *size = (float) ARRNELEMS(a);
}

/* qsort_arg comparison function for isort() */
static int
isort_cmp(const void *a, const void *b, void *arg)
{
    int32       aval = *((const int32 *) a);
    int32       bval = *((const int32 *) b);

    if (aval < bval)
        return -1;
    if (aval > bval)
        return 1;

    /*
     * Report if we have any duplicates.  If there are equal keys, qsort must
     * compare them at some point, else it wouldn't know whether one should go
     * before or after the other.
     */
    *((bool *) arg) = true;
    return 0;
}

/* Sort the given data (len >= 2).  Return true if any duplicates found */
bool
isort(int32 *a, int len)
{
    bool        r = false;

    qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
    return r;
}

/* Create a new int array with room for "num" elements */
ArrayType *
new_intArrayType(int num)
{
    ArrayType  *r;
    int         nbytes;

    /* if no elements, return a zero-dimensional array */
    if (num <= 0)
    {
        Assert(num == 0);
        r = construct_empty_array(INT4OID);
        return r;
    }

    nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;

    r = (ArrayType *) palloc0(nbytes);

    SET_VARSIZE(r, nbytes);
    ARR_NDIM(r) = 1;
    r->dataoffset = 0;          /* marker for no null bitmap */
    ARR_ELEMTYPE(r) = INT4OID;
    ARR_DIMS(r)[0] = num;
    ARR_LBOUND(r)[0] = 1;

    return r;
}

ArrayType *
resize_intArrayType(ArrayType *a, int num)
{
    int         nbytes;
    int         i;

    /* if no elements, return a zero-dimensional array */
    if (num <= 0)
    {
        Assert(num == 0);
        a = construct_empty_array(INT4OID);
        return a;
    }

    if (num == ARRNELEMS(a))
        return a;

    nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;

    a = (ArrayType *) repalloc(a, nbytes);

    SET_VARSIZE(a, nbytes);
    /* usually the array should be 1-D already, but just in case ... */
    for (i = 0; i < ARR_NDIM(a); i++)
    {
        ARR_DIMS(a)[i] = num;
        num = 1;
    }
    return a;
}

ArrayType *
copy_intArrayType(ArrayType *a)
{
    ArrayType  *r;
    int         n = ARRNELEMS(a);

    r = new_intArrayType(n);
    memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
    return r;
}

/* num for compressed key */
int
internal_size(int *a, int len)
{
    int         i;
    int64       size = 0;

    for (i = 0; i < len; i += 2)
    {
        if (!i || a[i] != a[i - 1]) /* do not count repeated range */
            size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
    }

    if (size > (int64) INT_MAX || size < (int64) INT_MIN)
        return -1;              /* overflow */
    return (int) size;
}

/* unique-ify elements of r in-place ... r must be sorted already */
ArrayType *
_int_unique(ArrayType *r)
{
    int         num = ARRNELEMS(r);
    bool        duplicates_found;   /* not used */

    num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
                      &duplicates_found);

    return resize_intArrayType(r, num);
}

void
gensign(BITVECP sign, int *a, int len, int siglen)
{
    int         i;

    /* we assume that the sign vector is previously zeroed */
    for (i = 0; i < len; i++)
    {
        HASH(sign, *a, siglen);
        a++;
    }
}

int32
intarray_match_first(ArrayType *a, int32 elem)
{
    int32      *aa,
                c,
                i;

    CHECKARRVALID(a);
    c = ARRNELEMS(a);
    aa = ARRPTR(a);
    for (i = 0; i < c; i++)
        if (aa[i] == elem)
            return (i + 1);
    return 0;
}

ArrayType *
intarray_add_elem(ArrayType *a, int32 elem)
{
    ArrayType  *result;
    int32      *r;
    int32       c;

    CHECKARRVALID(a);
    c = ARRNELEMS(a);
    result = new_intArrayType(c + 1);
    r = ARRPTR(result);
    if (c > 0)
        memcpy(r, ARRPTR(a), c * sizeof(int32));
    r[c] = elem;
    return result;
}

ArrayType *
intarray_concat_arrays(ArrayType *a, ArrayType *b)
{
    ArrayType  *result;
    int32       ac = ARRNELEMS(a);
    int32       bc = ARRNELEMS(b);

    CHECKARRVALID(a);
    CHECKARRVALID(b);
    result = new_intArrayType(ac + bc);
    if (ac)
        memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
    if (bc)
        memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
    return result;
}

ArrayType *
int_to_intset(int32 n)
{
    ArrayType  *result;
    int32      *aa;

    result = new_intArrayType(1);
    aa = ARRPTR(result);
    aa[0] = n;
    return result;
}

int
compASC(const void *a, const void *b)
{
    if (*(const int32 *) a == *(const int32 *) b)
        return 0;
    return (*(const int32 *) a > *(const int32 *) b) ? 1 : -1;
}

int
compDESC(const void *a, const void *b)
{
    if (*(const int32 *) a == *(const int32 *) b)
        return 0;
    return (*(const int32 *) a < *(const int32 *) b) ? 1 : -1;
}