/*
 * contrib/hstore/hstore_op.c
 */
#include "postgres.h"
#include "knl/knl_variable.h"

#include "access/hash.h"
#include "catalog/pg_type.h"
#include "funcapi.h"
#include "utils/builtins.h"
#include "utils/memutils.h"

#include "hstore.h"

/* old names for C functions */
HSTORE_POLLUTE(hstore_fetchval, fetchval);
HSTORE_POLLUTE(hstore_exists, exists);
HSTORE_POLLUTE(hstore_defined, defined);
HSTORE_POLLUTE(hstore_delete, hs_delete);
HSTORE_POLLUTE(hstore_concat, hs_concat);
HSTORE_POLLUTE(hstore_contains, hs_contains);
HSTORE_POLLUTE(hstore_contained, hs_contained);
HSTORE_POLLUTE(hstore_akeys, akeys);
HSTORE_POLLUTE(hstore_avals, avals);
HSTORE_POLLUTE(hstore_skeys, skeys);
HSTORE_POLLUTE(hstore_svals, svals);
HSTORE_POLLUTE(hstore_each, each);

/*
 * We're often finding a sequence of keys in ascending order. The
 * "lowbound" parameter is used to cache lower bounds of searches
 * between calls, based on this assumption. Pass NULL for it for
 * one-off or unordered searches.
 */
int hstoreFindKey(HStore* hs, int* lowbound, const char* key, uint32 keylen)
{
    NOT_NULL_HS(hs);
    HEntry* entries = ARRPTR(hs);
    int stopLow = lowbound ? *lowbound : 0;
    int stopHigh = HS_COUNT(hs);
    int stopMiddle;
    char* base = STRPTR(hs);

    while (stopLow < stopHigh) {
        int difference;

        stopMiddle = stopLow + (stopHigh - stopLow) / 2;

        if (HS_KEYLEN(entries, stopMiddle) == keylen)
            difference = memcmp(HS_KEY(entries, base, stopMiddle), key, keylen);
        else
            difference = (HS_KEYLEN(entries, stopMiddle) > keylen) ? 1 : -1;

        if (difference == 0) {
            if (lowbound != NULL)
                *lowbound = stopMiddle + 1;
            return stopMiddle;
        } else if (difference < 0)
            stopLow = stopMiddle + 1;
        else
            stopHigh = stopMiddle;
    }

    if (lowbound != NULL)
        *lowbound = stopLow;
    return -1;
}

Pairs* hstoreArrayToPairs(ArrayType* a, int* npairs)
{
    Datum* key_datums = NULL;
    bool* key_nulls = NULL;
    int key_count;
    Pairs* key_pairs = NULL;
    int bufsiz;
    int i, j;

    deconstruct_array(a, TEXTOID, -1, false, 'i', &key_datums, &key_nulls, &key_count);

    if (key_count == 0) {
        *npairs = 0;
        return NULL;
    }

    /*
     * A text array uses at least eight bytes per element, so any overflow in
     * "key_count * sizeof(Pairs)" is small enough for palloc() to catch.
     * However, credible improvements to the array format could invalidate
     * that assumption.  Therefore, use an explicit check rather than relying
     * on palloc() to complain.
     */
    if (key_count > int(MaxAllocSize / sizeof(Pairs)))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
                errmsg("number of pairs (%d) exceeds the maximum allowed (%d)",
                    key_count,
                    (int)(MaxAllocSize / sizeof(Pairs)))));

    key_pairs = (Pairs*)palloc(sizeof(Pairs) * key_count);

    for (i = 0, j = 0; i < key_count; i++) {
        if (!key_nulls[i]) {
            key_pairs[j].key = VARDATA(key_datums[i]);
            key_pairs[j].keylen = VARSIZE(key_datums[i]) - VARHDRSZ;
            key_pairs[j].val = NULL;
            key_pairs[j].vallen = 0;
            key_pairs[j].needfree = 0;
            key_pairs[j].isnull = 1;
            j++;
        }
    }

    *npairs = hstoreUniquePairs(key_pairs, j, &bufsiz);

    return key_pairs;
}

PG_FUNCTION_INFO_V1(hstore_fetchval);
extern "C" Datum hstore_fetchval(PG_FUNCTION_ARGS);
Datum hstore_fetchval(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    text* key = PG_GETARG_TEXT_PP(1);
    HEntry* entries = ARRPTR(hs);
    text* out = NULL;
    int idx = hstoreFindKey(hs, NULL, VARDATA_ANY(key), VARSIZE_ANY_EXHDR(key));

    if (idx < 0 || HS_VALISNULL(entries, idx))
        PG_RETURN_NULL();

    out = cstring_to_text_with_len(HS_VAL(entries, STRPTR(hs), idx), HS_VALLEN(entries, idx));

    PG_RETURN_TEXT_P(out);
}

PG_FUNCTION_INFO_V1(hstore_exists);
extern "C" Datum hstore_exists(PG_FUNCTION_ARGS);
Datum hstore_exists(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    text* key = PG_GETARG_TEXT_PP(1);
    int idx = hstoreFindKey(hs, NULL, VARDATA_ANY(key), VARSIZE_ANY_EXHDR(key));

    PG_RETURN_BOOL(idx >= 0);
}

PG_FUNCTION_INFO_V1(hstore_exists_any);
extern "C" Datum hstore_exists_any(PG_FUNCTION_ARGS);
Datum hstore_exists_any(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    ArrayType* keys = PG_GETARG_ARRAYTYPE_P(1);
    int nkeys;
    Pairs* key_pairs = hstoreArrayToPairs(keys, &nkeys);
    int i;
    int lowbound = 0;
    bool res = false;

    /*
     * we exploit the fact that the pairs list is already sorted into strictly
     * increasing order to narrow the hstoreFindKey search; each search can
     * start one entry past the previous "found" entry, or at the lower bound
     * of the last search.
     */
    for (i = 0; i < nkeys; i++) {
        int idx = hstoreFindKey(hs, &lowbound, key_pairs[i].key, key_pairs[i].keylen);

        if (idx >= 0) {
            res = true;
            break;
        }
    }

    PG_RETURN_BOOL(res);
}

PG_FUNCTION_INFO_V1(hstore_exists_all);
extern "C" Datum hstore_exists_all(PG_FUNCTION_ARGS);
Datum hstore_exists_all(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    ArrayType* keys = PG_GETARG_ARRAYTYPE_P(1);
    int nkeys;
    Pairs* key_pairs = hstoreArrayToPairs(keys, &nkeys);
    int i;
    int lowbound = 0;
    bool res = true;

    /*
     * we exploit the fact that the pairs list is already sorted into strictly
     * increasing order to narrow the hstoreFindKey search; each search can
     * start one entry past the previous "found" entry, or at the lower bound
     * of the last search.
     */
    for (i = 0; i < nkeys; i++) {
        int idx = hstoreFindKey(hs, &lowbound, key_pairs[i].key, key_pairs[i].keylen);

        if (idx < 0) {
            res = false;
            break;
        }
    }

    PG_RETURN_BOOL(res);
}

PG_FUNCTION_INFO_V1(hstore_defined);
extern "C" Datum hstore_defined(PG_FUNCTION_ARGS);
Datum hstore_defined(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    text* key = PG_GETARG_TEXT_PP(1);
    HEntry* entries = ARRPTR(hs);
    int idx = hstoreFindKey(hs, NULL, VARDATA_ANY(key), VARSIZE_ANY_EXHDR(key));
    bool res = (idx >= 0 && !HS_VALISNULL(entries, idx));

    PG_RETURN_BOOL(res);
}

PG_FUNCTION_INFO_V1(hstore_delete);
extern "C" Datum hstore_delete(PG_FUNCTION_ARGS);
Datum hstore_delete(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    NOT_NULL_HS(hs);
    text* key = PG_GETARG_TEXT_PP(1);
    char* keyptr = VARDATA_ANY(key);
    int keylen = VARSIZE_ANY_EXHDR(key);
    HStore* out = (HStore*)palloc(VARSIZE(hs));
    char *bufs = NULL, *bufd = NULL, *ptrd = NULL;
    HEntry *es = NULL, *ed = NULL;
    int i;
    int count = HS_COUNT(hs);
    uint32 outcount = 0;

    SET_VARSIZE(out, VARSIZE(hs));
    HS_SETCOUNT(out, count); /* temporary! */

    bufs = STRPTR(hs);
    es = ARRPTR(hs);
    bufd = ptrd = STRPTR(out);
    ed = ARRPTR(out);

    uint32 dlen = VARSIZE(hs) - HS_COUNT((HStore*)(out)) * 2;
    for (i = 0; i < count; ++i) {
        int len = HS_KEYLEN(es, i);
        char* ptrs = HS_KEY(es, bufs, i);

        if (!(len == keylen && memcmp(ptrs, keyptr, keylen) == 0)) {
            int vallen = HS_VALLEN(es, i);

            HS_COPYITEM(ed, bufd, ptrd, dlen, ptrs, len, vallen, HS_VALISNULL(es, i));
            ++outcount;
        }
    }

    HS_FINALIZE(out, VARSIZE(hs), outcount, bufd, ptrd);

    PG_RETURN_POINTER(out);
}

PG_FUNCTION_INFO_V1(hstore_delete_array);
extern "C" Datum hstore_delete_array(PG_FUNCTION_ARGS);
Datum hstore_delete_array(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    NOT_NULL_HS(hs);
    HStore* out = (HStore*)palloc(VARSIZE(hs));
    int hs_count = HS_COUNT(hs);
    char *ps = NULL, *bufd = NULL, *pd = NULL;
    HEntry *es = NULL, *ed = NULL;
    int i, j;
    uint32 outcount = 0;
    ArrayType* key_array = PG_GETARG_ARRAYTYPE_P(1);
    int nkeys;
    Pairs* key_pairs = hstoreArrayToPairs(key_array, &nkeys);

    SET_VARSIZE(out, VARSIZE(hs));
    HS_SETCOUNT(out, hs_count); /* temporary! */

    ps = STRPTR(hs);
    es = ARRPTR(hs);
    bufd = pd = STRPTR(out);
    ed = ARRPTR(out);

    if (nkeys == 0) {
        /* return a copy of the input, unchanged */
        errno_t rc = memcpy_s(out, VARSIZE(hs), hs, VARSIZE(hs));
        securec_check(rc, "", "");
        HS_FIXSIZE(out, hs_count);
        HS_SETCOUNT(out, hs_count);
        PG_RETURN_POINTER(out);
    }

    /*
     * this is in effect a merge between hs and key_pairs, both of which are
     * already sorted by (keylen,key); we take keys from hs only
     */
    uint32 dlen = VARSIZE(hs) - HS_COUNT((HStore*)(out)) * 2;
    for (i = j = 0; i < hs_count;) {
        int difference;

        if (j >= nkeys)
            difference = -1;
        else {
            uint32 skeylen = HS_KEYLEN(es, i);

            if (skeylen == key_pairs[j].keylen)
                difference = memcmp(HS_KEY(es, ps, i), key_pairs[j].key, key_pairs[j].keylen);
            else
                difference = (skeylen > key_pairs[j].keylen) ? 1 : -1;
        }

        if (difference > 0)
            ++j;
        else if (difference == 0)
            ++i, ++j;
        else {
            HS_COPYITEM(ed, bufd, pd, dlen, HS_KEY(es, ps, i), HS_KEYLEN(es, i), HS_VALLEN(es, i), HS_VALISNULL(es, i));
            ++outcount;
            ++i;
        }
    }

    HS_FINALIZE(out, VARSIZE(hs), outcount, bufd, pd);

    PG_RETURN_POINTER(out);
}

PG_FUNCTION_INFO_V1(hstore_delete_hstore);
extern "C" Datum hstore_delete_hstore(PG_FUNCTION_ARGS);
Datum hstore_delete_hstore(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    HStore* hs2 = PG_GETARG_HS(1);    
    NOT_NULL_HS(hs);
    NOT_NULL_HS(hs2);
    HStore* out = (HStore*)palloc(VARSIZE(hs));
    int hs_count = HS_COUNT(hs);
    int hs2_count = HS_COUNT(hs2);
    char *ps = NULL, *ps2 = NULL, *bufd = NULL, *pd = NULL;
    HEntry *es = NULL, *es2 = NULL, *ed = NULL;
    int i, j;
    uint32 outcount = 0;

    SET_VARSIZE(out, VARSIZE(hs));
    HS_SETCOUNT(out, hs_count); /* temporary! */

    ps = STRPTR(hs);
    es = ARRPTR(hs);
    ps2 = STRPTR(hs2);
    es2 = ARRPTR(hs2);
    bufd = pd = STRPTR(out);
    ed = ARRPTR(out);

    if (hs2_count == 0) {
        /* return a copy of the input, unchanged */
        errno_t rc = memcpy_s(out, VARSIZE(hs), hs, VARSIZE(hs));
        securec_check(rc, "", "");
        HS_FIXSIZE(out, hs_count);
        HS_SETCOUNT(out, hs_count);
        PG_RETURN_POINTER(out);
    }

    /*
     * this is in effect a merge between hs and hs2, both of which are already
     * sorted by (keylen,key); we take keys from hs only; for equal keys, we
     * take the value from hs unless the values are equal
     */
    uint32 dlen = VARSIZE(hs) - HS_COUNT((HStore*)(out)) * 2;
    for (i = j = 0; i < hs_count;) {
        int difference;

        if (j >= hs2_count)
            difference = -1;
        else {
            int skeylen = HS_KEYLEN(es, i);
            int s2keylen = HS_KEYLEN(es2, j);

            if (skeylen == s2keylen)
                difference = memcmp(HS_KEY(es, ps, i), HS_KEY(es2, ps2, j), skeylen);
            else
                difference = (skeylen > s2keylen) ? 1 : -1;
        }

        if (difference > 0)
            ++j;
        else if (difference == 0) {
            uint32 svallen = HS_VALLEN(es, i);
            int snullval = HS_VALISNULL(es, i);

            if (snullval != HS_VALISNULL(es2, j) ||
                (!snullval &&
                    (svallen != HS_VALLEN(es2, j) || memcmp(HS_VAL(es, ps, i), HS_VAL(es2, ps2, j), svallen) != 0))) {
                HS_COPYITEM(ed, bufd, pd, dlen, HS_KEY(es, ps, i), HS_KEYLEN(es, i), svallen, snullval);
                ++outcount;
            }
            ++i, ++j;
        } else {
            HS_COPYITEM(ed, bufd, pd, dlen, HS_KEY(es, ps, i), HS_KEYLEN(es, i), HS_VALLEN(es, i), HS_VALISNULL(es, i));
            ++outcount;
            ++i;
        }
    }

    HS_FINALIZE(out, VARSIZE(hs), outcount, bufd, pd);

    PG_RETURN_POINTER(out);
}

PG_FUNCTION_INFO_V1(hstore_concat);
extern "C" Datum hstore_concat(PG_FUNCTION_ARGS);
Datum hstore_concat(PG_FUNCTION_ARGS)
{
    HStore* s1 = PG_GETARG_HS(0);
    HStore* s2 = PG_GETARG_HS(1);

    if (NULL == s1 && NULL == s2) {
        PG_RETURN_NULL();
    }

    if (NULL == s1) {
        PG_RETURN_POINTER(s2);
    }

    if (NULL == s2) {
        PG_RETURN_POINTER(s1);
    }

    HStore* out = (HStore*)palloc(VARSIZE(s1) + VARSIZE(s2));
    char *ps1 = NULL, *ps2 = NULL, *bufd = NULL, *pd = NULL;
    HEntry *es1 = NULL, *es2 = NULL, *ed = NULL;
    int s1idx;
    int s2idx;
    int s1count = HS_COUNT(s1);
    int s2count = HS_COUNT(s2);
    uint32 outcount = 0;
    int rc = 0;

    SET_VARSIZE(out, VARSIZE(s1) + VARSIZE(s2) - HSHRDSIZE);
    HS_SETCOUNT(out, s1count + s2count);

    if (s1count == 0) {
        /* return a copy of the input, unchanged */
        rc = memcpy_s(out, VARSIZE(out), s2, VARSIZE(s2));    
        securec_check(rc, "", "");
        HS_FIXSIZE(out, s2count);
        HS_SETCOUNT(out, s2count);
        PG_RETURN_POINTER(out);
    }

    if (s2count == 0) {
        /* return a copy of the input, unchanged */
        rc = memcpy_s(out, VARSIZE(out), s1, VARSIZE(s1));    
        securec_check(rc, "", "");
        HS_FIXSIZE(out, s1count);
        HS_SETCOUNT(out, s1count);
        PG_RETURN_POINTER(out);
    }

    ps1 = STRPTR(s1);
    ps2 = STRPTR(s2);
    bufd = pd = STRPTR(out);
    es1 = ARRPTR(s1);
    es2 = ARRPTR(s2);
    ed = ARRPTR(out);

    /*
     * this is in effect a merge between s1 and s2, both of which are already
     * sorted by (keylen,key); we take s2 for equal keys
     */
    uint32 dlen = VARSIZE(s1) + VARSIZE(s2) - HSHRDSIZE - HS_COUNT((HStore*)(out)) * 2;
    for (s1idx = s2idx = 0; s1idx < s1count || s2idx < s2count; ++outcount) {
        int difference;

        if (s1idx >= s1count)
            difference = 1;
        else if (s2idx >= s2count)
            difference = -1;
        else {
            int s1keylen = HS_KEYLEN(es1, s1idx);
            int s2keylen = HS_KEYLEN(es2, s2idx);

            if (s1keylen == s2keylen)
                difference = memcmp(HS_KEY(es1, ps1, s1idx), HS_KEY(es2, ps2, s2idx), s1keylen);
            else
                difference = (s1keylen > s2keylen) ? 1 : -1;
        }

        if (difference >= 0) {
            HS_COPYITEM(ed,
                bufd,
                pd,
                dlen,
                HS_KEY(es2, ps2, s2idx),
                HS_KEYLEN(es2, s2idx),
                HS_VALLEN(es2, s2idx),
                HS_VALISNULL(es2, s2idx));
            ++s2idx;
            if (difference == 0)
                ++s1idx;
        } else {
            HS_COPYITEM(ed,
                bufd,
                pd,
                dlen,
                HS_KEY(es1, ps1, s1idx),
                HS_KEYLEN(es1, s1idx),
                HS_VALLEN(es1, s1idx),
                HS_VALISNULL(es1, s1idx));
            ++s1idx;
        }
    }

    HS_FINALIZE(out, VARSIZE(s1) + VARSIZE(s2) - HSHRDSIZE, outcount, bufd, pd);

    PG_RETURN_POINTER(out);
}

PG_FUNCTION_INFO_V1(hstore_slice_to_array);
extern "C" Datum hstore_slice_to_array(PG_FUNCTION_ARGS);
Datum hstore_slice_to_array(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    NOT_NULL_HS(hs);
    HEntry* entries = ARRPTR(hs);
    char* ptr = STRPTR(hs);
    ArrayType* key_array = PG_GETARG_ARRAYTYPE_P(1);
    ArrayType* aout = NULL;
    Datum* key_datums = NULL;
    bool* key_nulls = NULL;
    Datum* out_datums = NULL;
    bool* out_nulls = NULL;
    int key_count;
    int i;

    deconstruct_array(key_array, TEXTOID, -1, false, 'i', &key_datums, &key_nulls, &key_count);

    if (key_count == 0) {
        aout = construct_empty_array(TEXTOID);
        PG_RETURN_POINTER(aout);
    }

    out_datums = (Datum*)palloc(sizeof(Datum) * key_count);
    out_nulls = (bool*)palloc(sizeof(bool) * key_count);

    for (i = 0; i < key_count; ++i) {
        text* key = (text*)DatumGetPointer(key_datums[i]);
        int idx;

        if (key_nulls[i])
            idx = -1;
        else
            idx = hstoreFindKey(hs, NULL, VARDATA(key), VARSIZE(key) - VARHDRSZ);

        if (idx < 0 || HS_VALISNULL(entries, idx)) {
            out_nulls[i] = true;
            out_datums[i] = (Datum)0;
        } else {
            out_datums[i] =
                PointerGetDatum(cstring_to_text_with_len(HS_VAL(entries, ptr, idx), HS_VALLEN(entries, idx)));
            out_nulls[i] = false;
        }
    }

    aout = construct_md_array(out_datums,
        out_nulls,
        ARR_NDIM(key_array),
        ARR_DIMS(key_array),
        ARR_LBOUND(key_array),
        TEXTOID,
        -1,
        false,
        'i');

    PG_RETURN_POINTER(aout);
}

PG_FUNCTION_INFO_V1(hstore_slice_to_hstore);
extern "C" Datum hstore_slice_to_hstore(PG_FUNCTION_ARGS);
Datum hstore_slice_to_hstore(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    NOT_NULL_HS(hs);
    HEntry* entries = ARRPTR(hs);
    char* ptr = STRPTR(hs);
    ArrayType* key_array = PG_GETARG_ARRAYTYPE_P(1);
    HStore* out = NULL;
    int nkeys;
    Pairs* key_pairs = hstoreArrayToPairs(key_array, &nkeys);
    Pairs* out_pairs = NULL;
    int bufsiz;
    int lastidx = 0;
    int i;
    int out_count = 0;

    if (nkeys == 0) {
        out = hstorePairs(NULL, 0, 0);
        PG_RETURN_POINTER(out);
    }

    /* hstoreArrayToPairs() checked overflow */
    out_pairs = (Pairs*)palloc(sizeof(Pairs) * nkeys);
    bufsiz = 0;

    /*
     * we exploit the fact that the pairs list is already sorted into strictly
     * increasing order to narrow the hstoreFindKey search; each search can
     * start one entry past the previous "found" entry, or at the lower bound
     * of the last search.
     */

    for (i = 0; i < nkeys; ++i) {
        int idx = hstoreFindKey(hs, &lastidx, key_pairs[i].key, key_pairs[i].keylen);

        if (idx >= 0) {
            out_pairs[out_count].key = key_pairs[i].key;
            bufsiz += (out_pairs[out_count].keylen = key_pairs[i].keylen);
            out_pairs[out_count].val = HS_VAL(entries, ptr, idx);
            bufsiz += (out_pairs[out_count].vallen = HS_VALLEN(entries, idx));
            out_pairs[out_count].isnull = HS_VALISNULL(entries, idx);
            out_pairs[out_count].needfree = false;
            ++out_count;
        }
    }

    /*
     * we don't use uniquePairs here because we know that the pairs list is
     * already sorted and uniq'ed.
     */

    out = hstorePairs(out_pairs, out_count, bufsiz);

    PG_RETURN_POINTER(out);
}

PG_FUNCTION_INFO_V1(hstore_akeys);
extern "C" Datum hstore_akeys(PG_FUNCTION_ARGS);
Datum hstore_akeys(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    NOT_NULL_HS(hs);
    Datum* d = NULL;
    ArrayType* a = NULL;
    HEntry* entries = ARRPTR(hs);
    char* base = STRPTR(hs);
    int count = HS_COUNT(hs);
    int i;

    if (count == 0) {
        a = construct_empty_array(TEXTOID);
        PG_RETURN_POINTER(a);
    }

    d = (Datum*)palloc(sizeof(Datum) * count);

    for (i = 0; i < count; ++i) {
        text* item = cstring_to_text_with_len(HS_KEY(entries, base, i), HS_KEYLEN(entries, i));

        d[i] = PointerGetDatum(item);
    }

    a = construct_array(d, count, TEXTOID, -1, false, 'i');

    PG_RETURN_POINTER(a);
}

PG_FUNCTION_INFO_V1(hstore_avals);
extern "C" Datum hstore_avals(PG_FUNCTION_ARGS);
Datum hstore_avals(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    NOT_NULL_HS(hs);
    Datum* d = NULL;
    bool* nulls = NULL;
    ArrayType* a = NULL;
    HEntry* entries = ARRPTR(hs);
    char* base = STRPTR(hs);
    int count = HS_COUNT(hs);
    int lb = 1;
    int i;

    if (count == 0) {
        a = construct_empty_array(TEXTOID);
        PG_RETURN_POINTER(a);
    }

    d = (Datum*)palloc(sizeof(Datum) * count);
    nulls = (bool*)palloc(sizeof(bool) * count);

    for (i = 0; i < count; ++i) {
        if (HS_VALISNULL(entries, i)) {
            d[i] = (Datum)0;
            nulls[i] = true;
        } else {
            text* item = cstring_to_text_with_len(HS_VAL(entries, base, i), HS_VALLEN(entries, i));

            d[i] = PointerGetDatum(item);
            nulls[i] = false;
        }
    }

    a = construct_md_array(d, nulls, 1, &count, &lb, TEXTOID, -1, false, 'i');

    PG_RETURN_POINTER(a);
}

static ArrayType* hstore_to_array_internal(HStore* hs, int ndims)
{
    NOT_NULL_HS(hs);
    HEntry* entries = ARRPTR(hs);
    char* base = STRPTR(hs);
    int count = HS_COUNT(hs);
    int out_size[2] = {0, 2};
    int lb[2] = {1, 1};
    Datum* out_datums = NULL;
    bool* out_nulls = NULL;
    int i;

    Assert(ndims < 3);

    if (count == 0 || ndims == 0)
        return construct_empty_array(TEXTOID);

    out_size[0] = count * 2 / ndims;
    out_datums = (Datum*)palloc(sizeof(Datum) * count * 2);
    out_nulls = (bool*)palloc(sizeof(bool) * count * 2);

    for (i = 0; i < count; ++i) {
        text* key = cstring_to_text_with_len(HS_KEY(entries, base, i), HS_KEYLEN(entries, i));

        out_datums[i * 2] = PointerGetDatum(key);
        out_nulls[i * 2] = false;

        if (HS_VALISNULL(entries, i)) {
            out_datums[i * 2 + 1] = (Datum)0;
            out_nulls[i * 2 + 1] = true;
        } else {
            text* item = cstring_to_text_with_len(HS_VAL(entries, base, i), HS_VALLEN(entries, i));

            out_datums[i * 2 + 1] = PointerGetDatum(item);
            out_nulls[i * 2 + 1] = false;
        }
    }

    return construct_md_array(out_datums, out_nulls, ndims, out_size, lb, TEXTOID, -1, false, 'i');
}

PG_FUNCTION_INFO_V1(hstore_to_array);
extern "C" Datum hstore_to_array(PG_FUNCTION_ARGS);
Datum hstore_to_array(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    ArrayType* out = hstore_to_array_internal(hs, 1);

    PG_RETURN_POINTER(out);
}

PG_FUNCTION_INFO_V1(hstore_to_matrix);
extern "C" Datum hstore_to_matrix(PG_FUNCTION_ARGS);
Datum hstore_to_matrix(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    ArrayType* out = hstore_to_array_internal(hs, 2);

    PG_RETURN_POINTER(out);
}

/*
 * Common initialization function for the various set-returning
 * funcs. fcinfo is only passed if the function is to return a
 * composite; it will be used to look up the return tupledesc.
 * we stash a copy of the hstore in the multi-call context in
 * case it was originally toasted. (At least I assume that's why;
 * there was no explanatory comment in the original code. --AG)
 */

static void setup_firstcall(FuncCallContext* funcctx, HStore* hs, FunctionCallInfoData* fcinfo)
{
    MemoryContext oldcontext;
    HStore* st = NULL;
    NOT_NULL_HS(hs);
    oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);

    st = (HStore*)palloc(VARSIZE(hs));
    errno_t rc = memcpy_s(st, VARSIZE(hs), hs, VARSIZE(hs));
    securec_check(rc, "", "");

    funcctx->user_fctx = (void*)st;

    if (fcinfo != NULL) {
        TupleDesc tupdesc;

        /* Build a tuple descriptor for our result type */
        if (get_call_result_type(fcinfo, NULL, &tupdesc) != TYPEFUNC_COMPOSITE)
            elog(ERROR, "return type must be a row type");

        if (tupdesc != NULL) {
            funcctx->tuple_desc = BlessTupleDesc(tupdesc);
        }
    }

    MemoryContextSwitchTo(oldcontext);
}

PG_FUNCTION_INFO_V1(hstore_skeys);
extern "C" Datum hstore_skeys(PG_FUNCTION_ARGS);
Datum hstore_skeys(PG_FUNCTION_ARGS)
{
    FuncCallContext* funcctx = NULL;
    HStore* hs = NULL;
    uint32 i;

    if (SRF_IS_FIRSTCALL()) {
        hs = PG_GETARG_HS(0);
        funcctx = SRF_FIRSTCALL_INIT();
        setup_firstcall(funcctx, hs, NULL);
    }

    funcctx = SRF_PERCALL_SETUP();
    hs = (HStore*)funcctx->user_fctx;
    i = funcctx->call_cntr;

    if (i < HS_COUNT(hs)) {
        HEntry* entries = ARRPTR(hs);
        text* item = NULL;

        item = cstring_to_text_with_len(HS_KEY(entries, STRPTR(hs), i), HS_KEYLEN(entries, i));

        SRF_RETURN_NEXT(funcctx, PointerGetDatum(item));
    }

    SRF_RETURN_DONE(funcctx);
}

PG_FUNCTION_INFO_V1(hstore_svals);
extern "C" Datum hstore_svals(PG_FUNCTION_ARGS);
Datum hstore_svals(PG_FUNCTION_ARGS)
{
    FuncCallContext* funcctx = NULL;
    HStore* hs = NULL;
    uint32 i;

    if (SRF_IS_FIRSTCALL()) {
        hs = PG_GETARG_HS(0);
        funcctx = SRF_FIRSTCALL_INIT();
        setup_firstcall(funcctx, hs, NULL);
    }

    funcctx = SRF_PERCALL_SETUP();
    hs = (HStore*)funcctx->user_fctx;
    i = funcctx->call_cntr;

    if (i < HS_COUNT(hs)) {
        HEntry* entries = ARRPTR(hs);

        if (HS_VALISNULL(entries, i)) {
            ReturnSetInfo* rsi = NULL;

            /* ugly ugly ugly. why no macro for this? */
            (funcctx)->call_cntr++;
            rsi = (ReturnSetInfo*)fcinfo->resultinfo;
            rsi->isDone = ExprMultipleResult;
            PG_RETURN_NULL();
        } else {
            text* item = NULL;

            item = cstring_to_text_with_len(HS_VAL(entries, STRPTR(hs), i), HS_VALLEN(entries, i));

            SRF_RETURN_NEXT(funcctx, PointerGetDatum(item));
        }
    }

    SRF_RETURN_DONE(funcctx);
}

PG_FUNCTION_INFO_V1(hstore_contains);
extern "C" Datum hstore_contains(PG_FUNCTION_ARGS);
Datum hstore_contains(PG_FUNCTION_ARGS)
{
    HStore* val = PG_GETARG_HS(0);
    HStore* tmpl = PG_GETARG_HS(1);
    NOT_NULL_HS(val);
    NOT_NULL_HS(tmpl);
    bool res = true;
    HEntry* te = ARRPTR(tmpl);
    char* tstr = STRPTR(tmpl);
    HEntry* ve = ARRPTR(val);
    char* vstr = STRPTR(val);
    int tcount = HS_COUNT(tmpl);
    int lastidx = 0;
    int i;

    /*
     * we exploit the fact that keys in "tmpl" are in strictly increasing
     * order to narrow the hstoreFindKey search; each search can start one
     * entry past the previous "found" entry, or at the lower bound of the
     * search
     */

    for (i = 0; res && i < tcount; ++i) {
        int idx = hstoreFindKey(val, &lastidx, HS_KEY(te, tstr, i), HS_KEYLEN(te, i));

        if (idx >= 0) {
            bool nullval = HS_VALISNULL(te, i);
            uint32 vallen = HS_VALLEN(te, i);

            if (nullval != HS_VALISNULL(ve, idx) ||
                (!nullval &&
                    (vallen != HS_VALLEN(ve, idx) || memcmp(HS_VAL(te, tstr, i), HS_VAL(ve, vstr, idx), vallen))))
                res = false;
        } else
            res = false;
    }

    PG_RETURN_BOOL(res);
}

PG_FUNCTION_INFO_V1(hstore_contained);
extern "C" Datum hstore_contained(PG_FUNCTION_ARGS);
Datum hstore_contained(PG_FUNCTION_ARGS)
{
    PG_RETURN_DATUM(DirectFunctionCall2(hstore_contains, PG_GETARG_DATUM(1), PG_GETARG_DATUM(0)));
}

PG_FUNCTION_INFO_V1(hstore_each);
extern "C" Datum hstore_each(PG_FUNCTION_ARGS);
Datum hstore_each(PG_FUNCTION_ARGS)
{
    FuncCallContext* funcctx = NULL;
    HStore* hs = NULL;
    uint32 i;

    if (SRF_IS_FIRSTCALL()) {
        hs = PG_GETARG_HS(0);
        funcctx = SRF_FIRSTCALL_INIT();
        setup_firstcall(funcctx, hs, fcinfo);
    }

    funcctx = SRF_PERCALL_SETUP();
    hs = (HStore*)funcctx->user_fctx;
    i = funcctx->call_cntr;

    if (i < HS_COUNT(hs)) {
        HEntry* entries = ARRPTR(hs);
        char* ptr = STRPTR(hs);
        Datum res, dvalues[2];
        bool nulls[2] = {false, false};
        text* item = NULL;
        HeapTuple tuple;

        item = cstring_to_text_with_len(HS_KEY(entries, ptr, i), HS_KEYLEN(entries, i));
        dvalues[0] = PointerGetDatum(item);

        if (HS_VALISNULL(entries, i)) {
            dvalues[1] = (Datum)0;
            nulls[1] = true;
        } else {
            item = cstring_to_text_with_len(HS_VAL(entries, ptr, i), HS_VALLEN(entries, i));
            dvalues[1] = PointerGetDatum(item);
        }

        tuple = heap_form_tuple(funcctx->tuple_desc, dvalues, nulls);
        res = HeapTupleGetDatum(tuple);

        SRF_RETURN_NEXT(funcctx, PointerGetDatum(res));
    }

    SRF_RETURN_DONE(funcctx);
}

/*
 * btree sort order for hstores isn't intended to be useful; we really only
 * care about equality versus non-equality.  we compare the entire string
 * buffer first, then the entry pos array.
 */

PG_FUNCTION_INFO_V1(hstore_cmp);
extern "C" Datum hstore_cmp(PG_FUNCTION_ARGS);
Datum hstore_cmp(PG_FUNCTION_ARGS)
{
    HStore* hs1 = PG_GETARG_HS(0);
    HStore* hs2 = PG_GETARG_HS(1);
    NOT_NULL_HS(hs1);
    NOT_NULL_HS(hs2);
    int hcount1 = HS_COUNT(hs1);
    int hcount2 = HS_COUNT(hs2);
    int res = 0;

    if (hcount1 == 0 || hcount2 == 0) {
        /*
         * if either operand is empty, and the other is nonempty, the nonempty
         * one is larger. If both are empty they are equal.
         */
        if (hcount1 > 0)
            res = 1;
        else if (hcount2 > 0)
            res = -1;
    } else {
        /* here we know both operands are nonempty */
        char* str1 = STRPTR(hs1);
        char* str2 = STRPTR(hs2);
        HEntry* ent1 = ARRPTR(hs1);
        HEntry* ent2 = ARRPTR(hs2);
        size_t len1 = HSE_ENDPOS(ent1[2 * hcount1 - 1]);
        size_t len2 = HSE_ENDPOS(ent2[2 * hcount2 - 1]);

        res = memcmp(str1, str2, Min(len1, len2));

        if (res == 0) {
            if (len1 > len2)
                res = 1;
            else if (len1 < len2)
                res = -1;
            else if (hcount1 > hcount2)
                res = 1;
            else if (hcount2 > hcount1)
                res = -1;
            else {
                int count = hcount1 * 2;
                int i;

                for (i = 0; i < count; ++i)
                    if (HSE_ENDPOS(ent1[i]) != HSE_ENDPOS(ent2[i]) || HSE_ISNULL(ent1[i]) != HSE_ISNULL(ent2[i]))
                        break;
                if (i < count) {
                    if (HSE_ENDPOS(ent1[i]) < HSE_ENDPOS(ent2[i]))
                        res = -1;
                    else if (HSE_ENDPOS(ent1[i]) > HSE_ENDPOS(ent2[i]))
                        res = 1;
                    else if (HSE_ISNULL(ent1[i]))
                        res = 1;
                    else if (HSE_ISNULL(ent2[i]))
                        res = -1;
                }
            }
        } else {
            res = (res > 0) ? 1 : -1;
        }
    }

    /*
     * this is a btree support function; this is one of the few places where
     * memory needs to be explicitly freed.
     */
    PG_FREE_IF_COPY(hs1, 0);
    PG_FREE_IF_COPY(hs2, 1);
    PG_RETURN_INT32(res);
}

PG_FUNCTION_INFO_V1(hstore_eq);
extern "C" Datum hstore_eq(PG_FUNCTION_ARGS);
Datum hstore_eq(PG_FUNCTION_ARGS)
{
    int res = DatumGetInt32(DirectFunctionCall2(hstore_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));

    PG_RETURN_BOOL(res == 0);
}

PG_FUNCTION_INFO_V1(hstore_ne);
extern "C" Datum hstore_ne(PG_FUNCTION_ARGS);
Datum hstore_ne(PG_FUNCTION_ARGS)
{
    int res = DatumGetInt32(DirectFunctionCall2(hstore_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));

    PG_RETURN_BOOL(res != 0);
}

PG_FUNCTION_INFO_V1(hstore_gt);
extern "C" Datum hstore_gt(PG_FUNCTION_ARGS);
Datum hstore_gt(PG_FUNCTION_ARGS)
{
    int res = DatumGetInt32(DirectFunctionCall2(hstore_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));

    PG_RETURN_BOOL(res > 0);
}

PG_FUNCTION_INFO_V1(hstore_ge);
extern "C" Datum hstore_ge(PG_FUNCTION_ARGS);
Datum hstore_ge(PG_FUNCTION_ARGS)
{
    int res = DatumGetInt32(DirectFunctionCall2(hstore_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));

    PG_RETURN_BOOL(res >= 0);
}

PG_FUNCTION_INFO_V1(hstore_lt);
extern "C" Datum hstore_lt(PG_FUNCTION_ARGS);
Datum hstore_lt(PG_FUNCTION_ARGS)
{
    int res = DatumGetInt32(DirectFunctionCall2(hstore_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));

    PG_RETURN_BOOL(res < 0);
}

PG_FUNCTION_INFO_V1(hstore_le);
extern "C" Datum hstore_le(PG_FUNCTION_ARGS);
Datum hstore_le(PG_FUNCTION_ARGS)
{
    int res = DatumGetInt32(DirectFunctionCall2(hstore_cmp, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)));

    PG_RETURN_BOOL(res <= 0);
}

PG_FUNCTION_INFO_V1(hstore_hash);
extern "C" Datum hstore_hash(PG_FUNCTION_ARGS);
Datum hstore_hash(PG_FUNCTION_ARGS)
{
    HStore* hs = PG_GETARG_HS(0);
    NOT_NULL_HS(hs);
    Datum hval = hash_any((unsigned char*)VARDATA(hs), VARSIZE(hs) - VARHDRSZ);

    /*
     * this is the only place in the code that cares whether the overall
     * varlena size exactly matches the true data size; this assertion should
     * be maintained by all the other code, but we make it explicit here.
     */
    Assert(VARSIZE(hs) ==
           ((HS_COUNT(hs) != 0) ? CALCDATASIZE(HS_COUNT(hs), HSE_ENDPOS(ARRPTR(hs)[2 * HS_COUNT(hs) - 1])) : HSHRDSIZE));

    PG_FREE_IF_COPY(hs, 0);
    PG_RETURN_DATUM(hval);
}