From 2cde97ae94d67405cec056839c766388ba0bc1f4 Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Mon, 5 Sep 2011 02:36:24 -0700 Subject: [PATCH] Use mdb_midl_append/sort instead of _insert --- libraries/libmdb/mdb.c | 15 ++++---- libraries/libmdb/midl.c | 78 +++++++++++++++++++++++++++++++++++++++++ libraries/libmdb/midl.h | 12 +++++++ 3 files changed, 98 insertions(+), 7 deletions(-) diff --git a/libraries/libmdb/mdb.c b/libraries/libmdb/mdb.c index a685241817..27f2387de2 100644 --- a/libraries/libmdb/mdb.c +++ b/libraries/libmdb/mdb.c @@ -578,7 +578,7 @@ mdb_dkey(MDB_val *key, char *buf) unsigned int i; if (key->mv_size > MAXKEYSIZE) return "MAXKEYSIZE"; -#if 0 +#if 1 for (i=0; imv_size; i++) ptr += sprintf(ptr, "%02x", *c++); #else @@ -744,7 +744,7 @@ mdb_touch(MDB_txn *txn, MDB_dbi dbi, MDB_pageparent *pp) return ENOMEM; DPRINTF("touched db %u page %lu -> %lu", dbi, mp->mp_pgno, dp->p.mp_pgno); assert(mp->mp_pgno != dp->p.mp_pgno); - mdb_midl_insert(txn->mt_free_pgs, mp->mp_pgno); + mdb_midl_append(txn->mt_free_pgs, mp->mp_pgno); pgno = dp->p.mp_pgno; memcpy(&dp->p, mp, txn->mt_env->me_psize); mp = &dp->p; @@ -1017,6 +1017,7 @@ mdb_txn_commit(MDB_txn *txn) mc.mc_snum = 0; mdb_search_page(txn, FREE_DBI, &key, &mc, 1, &mpp); + mdb_midl_sort(txn->mt_free_pgs); #if DEBUG > 1 { unsigned int i; @@ -3159,7 +3160,7 @@ mdb_cursor_del(MDB_cursor *mc, unsigned int flags) #endif { /* free it */ - mdb_midl_insert(mc->mc_txn->mt_free_pgs, pg); + mdb_midl_append(mc->mc_txn->mt_free_pgs, pg); } } rc = mdb_sibling(&mc->mc_xcursor->mx_cursor, 1); @@ -3178,7 +3179,7 @@ mdb_cursor_del(MDB_cursor *mc, unsigned int flags) #endif { /* free it */ - mdb_midl_insert(mc->mc_txn->mt_free_pgs, + mdb_midl_append(mc->mc_txn->mt_free_pgs, mc->mc_xcursor->mx_txn.mt_dbs[mc->mc_xcursor->mx_cursor.mc_dbi].md_root); } } @@ -3814,10 +3815,10 @@ mdb_rebalance(MDB_txn *txn, MDB_dbi dbi, MDB_pageparent *mpp) txn->mt_dbs[dbi].md_root = P_INVALID; txn->mt_dbs[dbi].md_depth = 0; txn->mt_dbs[dbi].md_leaf_pages = 0; - mdb_midl_insert(txn->mt_free_pgs, mpp->mp_page->mp_pgno); + mdb_midl_append(txn->mt_free_pgs, mpp->mp_page->mp_pgno); } else if (IS_BRANCH(mpp->mp_page) && NUMKEYS(mpp->mp_page) == 1) { DPUTS("collapsing root page!"); - mdb_midl_insert(txn->mt_free_pgs, mpp->mp_page->mp_pgno); + mdb_midl_append(txn->mt_free_pgs, mpp->mp_page->mp_pgno); txn->mt_dbs[dbi].md_root = NODEPGNO(NODEPTR(mpp->mp_page, 0)); if ((rc = mdb_get_page(txn, txn->mt_dbs[dbi].md_root, &root))) return rc; @@ -3895,7 +3896,7 @@ mdb_del0(MDB_cursor *mc, unsigned int ki, MDB_pageparent *mpp, MDB_node *leaf) ovpages = OVPAGES(NODEDSZ(leaf), mc->mc_txn->mt_env->me_psize); for (i=0; imc_txn->mt_free_pgs, pg); + mdb_midl_append(mc->mc_txn->mt_free_pgs, pg); pg++; } } diff --git a/libraries/libmdb/midl.c b/libraries/libmdb/midl.c index 0af517dbb5..17b6e51f97 100644 --- a/libraries/libmdb/midl.c +++ b/libraries/libmdb/midl.c @@ -28,6 +28,7 @@ */ #define CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) ) +#if 0 static unsigned mdb_midl_search( IDL ids, ID id ) { /* @@ -89,6 +90,7 @@ int mdb_midl_insert( IDL ids, ID id ) if ( x <= ids[0] && ids[x] == id ) { /* duplicate */ + assert(0); return -1; } @@ -112,6 +114,82 @@ int mdb_midl_insert( IDL ids, ID id ) return 0; } +#endif + +int mdb_midl_append( IDL ids, ID id ) +{ + /* Too big? */ + if (ids[0] >= MDB_IDL_UM_SIZE) + return -1; + ids[0]++; + ids[ids[0]] = id; + return 0; +} + +/* Quicksort + Insertion sort for small arrays */ + +#define SMALL 8 +#define SWAP(a,b) itmp=(a);(a)=(b);(b)=itmp + +void +mdb_midl_sort( ID *ids ) +{ + int istack[16*sizeof(int)]; + int i,j,k,l,ir,jstack; + ID a, itmp; + + ir = ids[0]; + l = 1; + jstack = 0; + for(;;) { + if (ir - l < SMALL) { /* Insertion sort */ + for (j=l+1;j<=ir;j++) { + a = ids[j]; + for (i=j-1;i>=1;i--) { + if (ids[i] >= a) break; + ids[i+1] = ids[i]; + } + ids[i+1] = a; + } + if (jstack == 0) break; + ir = istack[jstack--]; + l = istack[jstack--]; + } else { + k = (l + ir) >> 1; /* Choose median of left, center, right */ + SWAP(ids[k], ids[l+1]); + if (ids[l] < ids[ir]) { + SWAP(ids[l], ids[ir]); + } + if (ids[l+1] < ids[ir]) { + SWAP(ids[l+1], ids[ir]); + } + if (ids[l] < ids[l+1]) { + SWAP(ids[l], ids[l+1]); + } + i = l+1; + j = ir; + a = ids[l+1]; + for(;;) { + do i++; while(ids[i] > a); + do j--; while(ids[j] < a); + if (j < i) break; + SWAP(ids[i],ids[j]); + } + ids[l+1] = ids[j]; + ids[j] = a; + jstack += 2; + if (ir-i+1 >= j-1) { + istack[jstack] = ir; + istack[jstack-1] = i; + ir = j-1; + } else { + istack[jstack] = j-1; + istack[jstack-1] = l; + l = i; + } + } + } +} unsigned mdb_mid2l_search( ID2L ids, ID id ) { diff --git a/libraries/libmdb/midl.h b/libraries/libmdb/midl.h index 1e6c3c3843..8e4a6e3c1b 100644 --- a/libraries/libmdb/midl.h +++ b/libraries/libmdb/midl.h @@ -108,6 +108,18 @@ typedef ID *IDL; */ int mdb_midl_insert( IDL ids, ID id ); + /** Append an ID onto an IDL. + * @param[in,out] ids The IDL to append to. + * @param[in] id The ID to append. + * @return 0 on success, -2 if the IDL is too large. + */ +int mdb_midl_append( IDL ids, ID id ); + + /** Sort an IDL. + * @param[in,out] ids The IDL to sort. + */ +void mdb_midl_sort( IDL ids ); + /** An ID2 is an ID/pointer pair. */ typedef struct ID2 { -- 2.39.2