diff options
Diffstat (limited to 'src/db/db_sort_multiple.c')
| -rw-r--r-- | src/db/db_sort_multiple.c | 327 |
1 files changed, 327 insertions, 0 deletions
diff --git a/src/db/db_sort_multiple.c b/src/db/db_sort_multiple.c new file mode 100644 index 00000000..c5e2e941 --- /dev/null +++ b/src/db/db_sort_multiple.c @@ -0,0 +1,327 @@ +/*- + * See the file LICENSE for redistribution information. + * + * Copyright (c) 1996, 2012 Oracle and/or its affiliates. All rights reserved. + */ + +#include "db_config.h" + +#include "db_int.h" +#include "dbinc/db_page.h" +#include "dbinc/btree.h" + +static int __db_quicksort __P((DB *, DBT *, DBT *, u_int32_t *, u_int32_t *, + u_int32_t *, u_int32_t *, u_int32_t)); + +/* + * __db_compare_both -- + * Use the comparison functions from db to compare akey and bkey, and if + * DB_DUPSORT adata and bdata. + * + * PUBLIC: int __db_compare_both __P((DB *, const DBT *, const DBT *, + * PUBLIC: const DBT *, const DBT *)); + */ +int +__db_compare_both(db, akey, adata, bkey, bdata) + DB *db; + const DBT *akey; + const DBT *adata; + const DBT *bkey; + const DBT *bdata; +{ + BTREE *t; + int cmp; + + t = (BTREE *)db->bt_internal; + + cmp = t->bt_compare(db, akey, bkey); + if (cmp != 0) return cmp; + if (!F_ISSET(db, DB_AM_DUPSORT)) + return (0); + + if (adata == 0) return bdata == 0 ? 0 : -1; + if (bdata == 0) return 1; + +#ifdef HAVE_COMPRESSION + if (DB_IS_COMPRESSED(db)) + return t->compress_dup_compare(db, adata, bdata); +#endif + return db->dup_compare(db, adata, bdata); +} + +#define DB_SORT_SWAP(a, ad, b, bd) \ +do { \ + tmp = (a)[0]; (a)[0] = (b)[0]; (b)[0] = tmp; \ + tmp = (a)[-1]; (a)[-1] = (b)[-1]; (b)[-1] = tmp; \ + if (data != NULL) { \ + tmp = (ad)[0]; (ad)[0] = (bd)[0]; (bd)[0] = tmp; \ + tmp = (ad)[-1]; (ad)[-1] = (bd)[-1]; (bd)[-1] = tmp; \ + } \ +} while (0) + +#define DB_SORT_LOAD_DBT(a, ad, aptr, adptr) \ +do { \ + (a).data = (u_int8_t*)key->data + (aptr)[0]; \ + (a).size = (aptr)[-1]; \ + if (data != NULL) { \ + (ad).data = (u_int8_t*)data->data + (adptr)[0]; \ + (ad).size = (adptr)[-1]; \ + } \ +} while (0) + +#define DB_SORT_COMPARE(a, ad, b, bd) (data != NULL ? \ + __db_compare_both(db, &(a), &(ad), &(b), &(bd)) : \ + __db_compare_both(db, &(a), 0, &(b), 0)) + +#define DB_SORT_STACKSIZE 32 + +/* + * __db_quicksort -- + * The quicksort implementation for __db_sort_multiple() and + * __db_sort_multiple_key(). + */ +static int +__db_quicksort(db, key, data, kstart, kend, dstart, dend, size) + DB *db; + DBT *key, *data; + u_int32_t *kstart, *kend, *dstart, *dend; + u_int32_t size; +{ + int ret, cmp; + u_int32_t tmp, len; + u_int32_t *kptr, *dptr, *kl, *dl, *kr, *dr; + DBT a, ad, b, bd, m, md; + ENV *env; + + struct DB_SORT_quicksort_stack { + u_int32_t *kstart; + u_int32_t *kend; + u_int32_t *dstart; + u_int32_t *dend; + } stackbuf[DB_SORT_STACKSIZE], *stack; + u_int32_t soff, slen; + + ret = 0; + env = db->env; + + memset(&a, 0, sizeof(DBT)); + memset(&ad, 0, sizeof(DBT)); + memset(&b, 0, sizeof(DBT)); + memset(&bd, 0, sizeof(DBT)); + memset(&m, 0, sizeof(DBT)); + memset(&md, 0, sizeof(DBT)); + + /* NB end is smaller than start */ + + stack = stackbuf; + soff = 0; + slen = DB_SORT_STACKSIZE; + + start: + if (kend >= kstart) goto pop; + + /* If there's only one value, it's already sorted */ + len = (u_int32_t)(kstart - kend) / size; + if (len == 1) goto pop; + + DB_SORT_LOAD_DBT(a, ad, kstart, dstart); + DB_SORT_LOAD_DBT(b, bd, kend + size, dend + size); + + if (len == 2) { + /* Special case the sorting of two value sequences */ + if (DB_SORT_COMPARE(a, ad, b, bd) > 0) { + DB_SORT_SWAP(kstart, dstart, kend + size, + dend + size); + } + goto pop; + } + + kptr = kstart - (len / 2) * size; + dptr = dstart - (len / 2) * size; + DB_SORT_LOAD_DBT(m, md, kptr, dptr); + + /* Find the median of three */ + if (DB_SORT_COMPARE(a, ad, b, bd) < 0) { + if (DB_SORT_COMPARE(m, md, a, ad) < 0) { + /* m < a < b */ + if (len == 3) { + DB_SORT_SWAP(kstart, dstart, kptr, dptr); + goto pop; + } + DB_SORT_SWAP(kstart, dstart, kend + size, dend + size); + } else if (DB_SORT_COMPARE(m, md, b, bd) < 0) { + /* a <= m < b */ + if (len == 3) { + goto pop; + } + DB_SORT_SWAP(kptr, dptr, kend + size, dend + size); + } else { + /* a < b <= m */ + if (len == 3) { + DB_SORT_SWAP(kptr, dptr, kend + size, + dend + size); + goto pop; + } + /* Do nothing */ + } + } else { + if (DB_SORT_COMPARE(a, ad, m, md) < 0) { + /* b <= a < m */ + DB_SORT_SWAP(kstart, dstart, kend + size, + dend + size); + if (len == 3) { + DB_SORT_SWAP(kptr, dptr, kend + size, + dend + size); + goto pop; + } + } else if (DB_SORT_COMPARE(b, bd, m, md) < 0) { + /* b < m <= a */ + if (len == 3) { + DB_SORT_SWAP(kstart, dstart, kend + size, + dend + size); + goto pop; + } + DB_SORT_SWAP(kptr, dptr, kend + size, dend + size); + } else { + /* m <= b <= a */ + if (len == 3) { + DB_SORT_SWAP(kstart, dstart, kptr, dptr); + DB_SORT_SWAP(kptr, dptr, kend + size, + dend + size); + goto pop; + } + /* Do nothing */ + } + } + + /* partition */ + DB_SORT_LOAD_DBT(b, bd, kend + size, dend + size); + kl = kstart; + dl = dstart; + kr = kend + size; + dr = dend + size; + kptr = kstart; + dptr = dstart; + while (kptr >= kr) { + DB_SORT_LOAD_DBT(a, ad, kptr, dptr); + cmp = DB_SORT_COMPARE(a, ad, b, bd); + if (cmp < 0) { + DB_SORT_SWAP(kl, dl, kptr, dptr); + kl -= size; + dl -= size; + kptr -= size; + dptr -= size; + } else if (cmp > 0) { + DB_SORT_SWAP(kr, dr, kptr, dptr); + kr += size; + dr += size; + } else { + kptr -= size; + dptr -= size; + } + } + + if (soff == slen) { + /* Grow the stack */ + slen = slen * 2; + if (stack == stackbuf) { + ret = __os_malloc(env, slen * + sizeof(struct DB_SORT_quicksort_stack), &stack); + if (ret != 0) goto error; + memcpy(stack, stackbuf, soff * + sizeof(struct DB_SORT_quicksort_stack)); + } else { + ret = __os_realloc(env, slen * + sizeof(struct DB_SORT_quicksort_stack), &stack); + if (ret != 0) goto error; + } + } + + /* divide and conquer */ + stack[soff].kstart = kr - size; + stack[soff].kend = kend; + stack[soff].dstart = dr - size; + stack[soff].dend = dend; + ++soff; + + kend = kl; + dend = dl; + + goto start; + + pop: + if (soff != 0) { + --soff; + kstart = stack[soff].kstart; + kend = stack[soff].kend; + dstart = stack[soff].dstart; + dend = stack[soff].dend; + goto start; + } + + error: + if (stack != stackbuf) + __os_free(env, stack); + + return (ret); +} + +#undef DB_SORT_SWAP +#undef DB_SORT_LOAD_DBT + +/* + * __db_sort_multiple -- + * If flags == DB_MULTIPLE_KEY, sorts a DB_MULTIPLE_KEY format DBT using + * the BTree comparison function and duplicate comparison function. + * + * If flags == DB_MULTIPLE, sorts one or two DB_MULTIPLE format DBTs using + * the BTree comparison function and duplicate comparison function. Will + * assume key and data specifies pairs of key/data to sort together. If + * data is NULL, will just sort key according to the btree comparison + * function. + * + * Uses an in-place quicksort algorithm, with median of three for the pivot + * point. + * + * PUBLIC: int __db_sort_multiple __P((DB *, DBT *, DBT *, u_int32_t)); + */ +int +__db_sort_multiple(db, key, data, flags) + DB *db; + DBT *key, *data; + u_int32_t flags; +{ + u_int32_t *kstart, *kend, *dstart, *dend; + + /* TODO: sanity checks on the DBTs */ + /* DB_ILLEGAL_METHOD(db, DB_OK_BTREE); */ + + kstart = (u_int32_t*)((u_int8_t *)key->data + key->ulen) - 1; + + switch (flags) { + case DB_MULTIPLE: + if (data != NULL) + dstart = (u_int32_t*)((u_int8_t *)data->data + + data->ulen) - 1; + else + dstart = kstart; + + /* Find the end */ + for (kend = kstart, dend = dstart; + *kend != (u_int32_t)-1 && *dend != (u_int32_t)-1; + kend -= 2, dend -= 2) + ; + + return (__db_quicksort(db, key, data, kstart, kend, dstart, + dend, 2)); + case DB_MULTIPLE_KEY: + /* Find the end */ + for (kend = kstart; *kend != (u_int32_t)-1; kend -= 4) + ; + + return (__db_quicksort(db, key, key, kstart, kend, kstart - 2, + kend - 2, 4)); + default: + return (__db_ferr(db->env, "DB->sort_multiple", 0)); + } +} |