Imported Upstream version 2.0.0

16 files changed, 863 insertions, 238 deletions

diff --git a/bson/bson-inl.h b/bson/bson-inl.h
index 5b4c490..b86d667 100644
--- a/bson/bson-inl.h
+++ b/bson/bson-inl.h
@@ -1,4 +1,7 @@
-// bsoninlines.h
+/** @file bsoninlines.h
+          a goal here is that the most common bson methods can be used inline-only, a la boost.
+          thus some things are inline that wouldn't necessarily be otherwise.
+*/
 
 /*    Copyright 2009 10gen Inc.
  *
@@ -18,18 +21,158 @@
 #pragma once
 
 #include <map>
-#include "util/atomic_int.h"
-#include "util/misc.h"
-#include "../util/hex.h"
+#include <limits>
+
+#if defined(_WIN32)
+#undef max
+#undef min
+#endif
 
 namespace mongo {
 
-    inline BSONObjIterator BSONObj::begin() {
+    inline bool isNaN(double d) { 
+        return d != d;
+    }
+
+    /* must be same type when called, unless both sides are #s 
+       this large function is in header to facilitate inline-only use of bson
+    */
+    inline int compareElementValues(const BSONElement& l, const BSONElement& r) {
+        int f;
+
+        switch ( l.type() ) {
+        case EOO:
+        case Undefined: // EOO and Undefined are same canonicalType
+        case jstNULL:
+        case MaxKey:
+        case MinKey:
+            f = l.canonicalType() - r.canonicalType();
+            if ( f<0 ) return -1;
+            return f==0 ? 0 : 1;
+        case Bool:
+            return *l.value() - *r.value();
+        case Timestamp:
+            // unsigned compare for timestamps - note they are not really dates but (ordinal + time_t)
+            if ( l.date() < r.date() )
+                return -1;
+            return l.date() == r.date() ? 0 : 1;
+        case Date:
+            {
+                long long a = (long long) l.Date().millis;
+                long long b = (long long) r.Date().millis;
+                if( a < b ) 
+                    return -1;
+                return a == b ? 0 : 1;
+            }
+        case NumberLong:
+            if( r.type() == NumberLong ) {
+                long long L = l._numberLong();
+                long long R = r._numberLong();
+                if( L < R ) return -1;
+                if( L == R ) return 0;
+                return 1;
+            }
+            goto dodouble;
+        case NumberInt:
+            if( r.type() == NumberInt ) {
+                int L = l._numberInt();
+                int R = r._numberInt();
+                if( L < R ) return -1;
+                return L == R ? 0 : 1;
+            }
+            // else fall through
+        case NumberDouble: 
+dodouble:
+            {
+                double left = l.number();
+                double right = r.number();
+                if( left < right ) 
+                    return -1;
+                if( left == right )
+                    return 0;
+                if( isNaN(left) )
+                    return isNaN(right) ? 0 : -1;
+                return 1;
+            }
+        case jstOID:
+            return memcmp(l.value(), r.value(), 12);
+        case Code:
+        case Symbol:
+        case String:
+            /* todo: a utf sort order version one day... */
+            {
+                // we use memcmp as we allow zeros in UTF8 strings
+                int lsz = l.valuestrsize();
+                int rsz = r.valuestrsize();
+                int common = min(lsz, rsz);
+                int res = memcmp(l.valuestr(), r.valuestr(), common);
+                if( res ) 
+                    return res;
+                // longer string is the greater one
+                return lsz-rsz;
+            }
+        case Object:
+        case Array:
+            return l.embeddedObject().woCompare( r.embeddedObject() );
+        case DBRef: {
+            int lsz = l.valuesize();
+            int rsz = r.valuesize();
+            if ( lsz - rsz != 0 ) return lsz - rsz;
+            return memcmp(l.value(), r.value(), lsz);
+        }
+        case BinData: {
+            int lsz = l.objsize(); // our bin data size in bytes, not including the subtype byte
+            int rsz = r.objsize();
+            if ( lsz - rsz != 0 ) return lsz - rsz;
+            return memcmp(l.value()+4, r.value()+4, lsz+1);
+        }
+        case RegEx: {
+            int c = strcmp(l.regex(), r.regex());
+            if ( c )
+                return c;
+            return strcmp(l.regexFlags(), r.regexFlags());
+        }
+        case CodeWScope : {
+            f = l.canonicalType() - r.canonicalType();
+            if ( f )
+                return f;
+            f = strcmp( l.codeWScopeCode() , r.codeWScopeCode() );
+            if ( f )
+                return f;
+            f = strcmp( l.codeWScopeScopeData() , r.codeWScopeScopeData() );
+            if ( f )
+                return f;
+            return 0;
+        }
+        default:
+            assert( false);
+        }
+        return -1;
+    }
+
+    /* wo = "well ordered" */
+    inline int BSONElement::woCompare( const BSONElement &e,
+                                bool considerFieldName ) const {
+        int lt = (int) canonicalType();
+        int rt = (int) e.canonicalType();
+        int x = lt - rt;
+        if( x != 0 && (!isNumber() || !e.isNumber()) )
+            return x;
+        if ( considerFieldName ) {
+            x = strcmp(fieldName(), e.fieldName());
+            if ( x != 0 )
+                return x;
+        }
+        x = compareElementValues(*this, e);
+        return x;
+    }
+
+    inline BSONObjIterator BSONObj::begin() const {
         return BSONObjIterator(*this);
     }
 
     inline BSONObj BSONElement::embeddedObjectUserCheck() const {
-        if ( isABSONObj() )
+        if ( MONGO_likely(isABSONObj()) )
             return BSONObj(value());
         stringstream ss;
         ss << "invalid parameter: expected an object (" << fieldName() << ")";
@@ -48,6 +191,21 @@ namespace mongo {
         return BSONObj( value() + 4 + 4 + strSizeWNull );
     }
 
+    // deep (full) equality
+    inline bool BSONObj::equal(const BSONObj &rhs) const {
+        BSONObjIterator i(*this);
+        BSONObjIterator j(rhs);
+        BSONElement l,r;
+        do {
+            // so far, equal...
+            l = i.next();
+            r = j.next();
+            if ( l.eoo() )
+                return r.eoo();
+        } while( l == r );
+        return false;
+    }
+
     inline NOINLINE_DECL void BSONObj::_assertInvalid() const {
         StringBuilder ss;
         int os = objsize();
@@ -64,9 +222,10 @@ namespace mongo {
        getOwned() method.  the presumption being that is better.
     */
     inline NOINLINE_DECL BSONObj BSONObj::copy() const {
-        char *p = (char*) malloc(objsize());
-        memcpy(p, objdata(), objsize());
-        return BSONObj(p, true);
+        Holder *h = (Holder*) malloc(objsize() + sizeof(unsigned));
+        h->zero();
+        memcpy(h->data, objdata(), objsize());
+        return BSONObj(h);
     }
 
     inline BSONObj BSONObj::getOwned() const {
@@ -88,16 +247,18 @@ namespace mongo {
         return b.obj();
     }
 
-    inline bool BSONObj::hasElement(const char *name) const {
-        if ( !isEmpty() ) {
-            BSONObjIterator it(*this);
-            while ( it.moreWithEOO() ) {
-                BSONElement e = it.next();
-                if ( strcmp(name, e.fieldName()) == 0 )
-                    return true;
+    inline void BSONObj::getFields(unsigned n, const char **fieldNames, BSONElement *fields) const { 
+        BSONObjIterator i(*this);
+        while ( i.more() ) {
+            BSONElement e = i.next();
+            const char *p = e.fieldName();
+            for( unsigned i = 0; i < n; i++ ) {
+                if( strcmp(p, fieldNames[i]) == 0 ) {
+                    fields[i] = e;
+                    break;
+                }
             }
         }
-        return false;
     }
 
     inline BSONElement BSONObj::getField(const StringData& name) const {
@@ -110,6 +271,21 @@ namespace mongo {
         return BSONElement();
     }
 
+    inline int BSONObj::getIntField(const char *name) const {
+        BSONElement e = getField(name);
+        return e.isNumber() ? (int) e.number() : std::numeric_limits< int >::min();
+    }
+
+    inline bool BSONObj::getBoolField(const char *name) const {
+        BSONElement e = getField(name);
+        return e.type() == Bool ? e.boolean() : false;
+    }
+
+    inline const char * BSONObj::getStringField(const char *name) const {
+        BSONElement e = getField(name);
+        return e.type() == String ? e.valuestr() : "";
+    }
+
     /* add all the fields from the object specified to this object */
     inline BSONObjBuilder& BSONObjBuilder::appendElements(BSONObj x) {
         BSONObjIterator it(x);
@@ -141,7 +317,7 @@ namespace mongo {
     }
 
 
-    inline bool BSONObj::isValid() {
+    inline bool BSONObj::isValid() const {
         int x = objsize();
         return x > 0 && x <= BSONObjMaxInternalSize;
     }
@@ -302,8 +478,6 @@ namespace mongo {
         s << ( isArray ? " ]" : " }" );
     }
 
-    extern unsigned getRandomNumber();
-
     inline void BSONElement::validate() const {
         const BSONType t = type();
 
@@ -398,7 +572,7 @@ namespace mongo {
             break;
         case RegEx: {
             const char *p = value();
-            size_t len1 = ( maxLen == -1 ) ? strlen( p ) : mongo::strnlen( p, remain );
+            size_t len1 = ( maxLen == -1 ) ? strlen( p ) : (size_t)mongo::strnlen( p, remain );
             //massert( 10318 ,  "Invalid regex string", len1 != -1 ); // ERH - 4/28/10 - don't think this does anything
             p = p + len1 + 1;
             size_t len2;
@@ -417,7 +591,7 @@ namespace mongo {
             StringBuilder ss;
             ss << "BSONElement: bad type " << (int) type();
             string msg = ss.str();
-            massert( 10320 , msg.c_str(),false);
+            massert( 13655 , msg.c_str(),false);
         }
         }
         totalSize =  x + fieldNameSize() + 1; // BSONType
@@ -425,6 +599,72 @@ namespace mongo {
         return totalSize;
     }
 
+    inline int BSONElement::size() const {
+        if ( totalSize >= 0 )
+            return totalSize;
+
+        int x = 0;
+        switch ( type() ) {
+        case EOO:
+        case Undefined:
+        case jstNULL:
+        case MaxKey:
+        case MinKey:
+            break;
+        case mongo::Bool:
+            x = 1;
+            break;
+        case NumberInt:
+            x = 4;
+            break;
+        case Timestamp:
+        case mongo::Date:
+        case NumberDouble:
+        case NumberLong:
+            x = 8;
+            break;
+        case jstOID:
+            x = 12;
+            break;
+        case Symbol:
+        case Code:
+        case mongo::String:
+            x = valuestrsize() + 4;
+            break;
+        case DBRef:
+            x = valuestrsize() + 4 + 12;
+            break;
+        case CodeWScope:
+        case Object:
+        case mongo::Array:
+            x = objsize();
+            break;
+        case BinData:
+            x = valuestrsize() + 4 + 1/*subtype*/;
+            break;
+        case RegEx: 
+            {
+                const char *p = value();
+                size_t len1 = strlen(p);
+                p = p + len1 + 1;
+                size_t len2;
+                len2 = strlen( p );
+                x = (int) (len1 + 1 + len2 + 1);
+            }
+            break;
+        default: 
+            {
+                StringBuilder ss;
+                ss << "BSONElement: bad type " << (int) type();
+                string msg = ss.str();
+                massert(10320 , msg.c_str(),false);
+            }
+        }
+        totalSize =  x + fieldNameSize() + 1; // BSONType
+
+        return totalSize;
+    }
+
     inline string BSONElement::toString( bool includeFieldName, bool full ) const {
         StringBuilder s;
         toString(s, includeFieldName, full);
@@ -438,7 +678,7 @@ namespace mongo {
             s << "EOO";
             break;
         case mongo::Date:
-            s << "new Date(" << date() << ')';
+            s << "new Date(" << (long long) date() << ')';
             break;
         case RegEx: {
             s << "/" << regex() << '/';
@@ -492,8 +732,8 @@ namespace mongo {
         case Symbol:
         case mongo::String:
             s << '"';
-            if ( !full &&  valuestrsize() > 80 ) {
-                s.write(valuestr(), 70);
+            if ( !full &&  valuestrsize() > 160 ) {
+                s.write(valuestr(), 150);
                 s << "...\"";
             }
             else {
@@ -662,4 +902,87 @@ namespace mongo {
         b.append( q , t );
         return BSONFieldValue<BSONObj>( _name , b.obj() );
     }
+
+    // used by jsonString()
+    inline string escape( string s , bool escape_slash=false) {
+        StringBuilder ret;
+        for ( string::iterator i = s.begin(); i != s.end(); ++i ) {
+            switch ( *i ) {
+            case '"':
+                ret << "\\\"";
+                break;
+            case '\\':
+                ret << "\\\\";
+                break;
+            case '/':
+                ret << (escape_slash ? "\\/" : "/");
+                break;
+            case '\b':
+                ret << "\\b";
+                break;
+            case '\f':
+                ret << "\\f";
+                break;
+            case '\n':
+                ret << "\\n";
+                break;
+            case '\r':
+                ret << "\\r";
+                break;
+            case '\t':
+                ret << "\\t";
+                break;
+            default:
+                if ( *i >= 0 && *i <= 0x1f ) {
+                    //TODO: these should be utf16 code-units not bytes
+                    char c = *i;
+                    ret << "\\u00" << toHexLower(&c, 1);
+                }
+                else {
+                    ret << *i;
+                }
+            }
+        }
+        return ret.str();
+    }
+
+    inline string BSONObj::hexDump() const {
+        stringstream ss;
+        const char *d = objdata();
+        int size = objsize();
+        for( int i = 0; i < size; ++i ) {
+            ss.width( 2 );
+            ss.fill( '0' );
+            ss << hex << (unsigned)(unsigned char)( d[ i ] ) << dec;
+            if ( ( d[ i ] >= '0' && d[ i ] <= '9' ) || ( d[ i ] >= 'A' && d[ i ] <= 'z' ) )
+                ss << '\'' << d[ i ] << '\'';
+            if ( i != size - 1 )
+                ss << ' ';
+        }
+        return ss.str();
+    }
+
+    inline void BSONObjBuilder::appendKeys( const BSONObj& keyPattern , const BSONObj& values ) {
+        BSONObjIterator i(keyPattern);
+        BSONObjIterator j(values);
+
+        while ( i.more() && j.more() ) {
+            appendAs( j.next() , i.next().fieldName() );
+        }
+
+        assert( ! i.more() );
+        assert( ! j.more() );
+    }
+
+    inline BSONObj BSONObj::removeField(const StringData& name) const { 
+        BSONObjBuilder b;
+        BSONObjIterator i(*this);
+        while ( i.more() ) {
+            BSONElement e = i.next();
+            const char *fname = e.fieldName();
+            if( strcmp(name.data(), fname) )
+                b.append(e);
+        }
+        return b.obj();
+    }
 }
diff --git a/bson/bson.h b/bson/bson.h
index ba1b751..9515adf 100644
--- a/bson/bson.h
+++ b/bson/bson.h
@@ -1,11 +1,9 @@
-/* NOTE: Standalone bson header for when not using MongoDB.
-   See also: bsondemo.
+/** @file bson.h
 
-   MongoDB includes ../db/jsobj.h instead. This file, however, pulls in much less code / dependencies.
-*/
+    Main bson include file for mongodb c++ clients. MongoDB includes ../db/jsobj.h instead. 
+    This file, however, pulls in much less code / dependencies.
 
-/** @file bson.h
-    BSON classes
+    @see bsondemo
 */
 
 /*
@@ -25,7 +23,7 @@
  */
 
 /**
-   bo and its helpers
+   Main include file for C++ BSON module when using standalone (sans MongoDB client).
 
    "BSON" stands for "binary JSON" -- ie a binary way to represent objects that would be
    represented in JSON (plus a few extensions useful for databases & other languages).
@@ -42,10 +40,11 @@
    */
 #endif
 
+#include <cstdlib>
+#include <memory>
 #include <iostream>
 #include <sstream>
 #include <boost/utility.hpp>
-#include "util/builder.h"
 
 namespace bson {
 
@@ -56,7 +55,7 @@ namespace bson {
     public:
         assertion( unsigned u , const string& s )
             : id( u ) , msg( s ) {
-            mongo::StringBuilder ss;
+            stringstream ss;
             ss << "BsonAssertion id: " << u << " " << s;
             full = ss.str();
         }
@@ -101,23 +100,11 @@ namespace mongo {
 #endif
 }
 
-#include "../bson/bsontypes.h"
-#include "../bson/oid.h"
-#include "../bson/bsonelement.h"
-#include "../bson/bsonobj.h"
-#include "../bson/bsonmisc.h"
-#include "../bson/bsonobjbuilder.h"
-#include "../bson/bsonobjiterator.h"
-#include "../bson/bson-inl.h"
-
-namespace mongo {
-
-    inline unsigned getRandomNumber() {
-#if defined(_WIN32)
-        return rand();
-#else
-        return random();
-#endif
-    }
-
-}
+#include "util/builder.h"
+#include "bsontypes.h"
+#include "oid.h"
+#include "bsonelement.h"
+#include "bsonobj.h"
+#include "bsonobjbuilder.h"
+#include "bsonobjiterator.h"
+#include "bson-inl.h"
diff --git a/bson/bsondemo/bsondemo.cpp b/bson/bsondemo/bsondemo.cpp
index ec83f5e..b53a7b3 100644
--- a/bson/bsondemo/bsondemo.cpp
+++ b/bson/bsondemo/bsondemo.cpp
@@ -4,6 +4,12 @@
 
     Requires boost (headers only).
     Works headers only (the parts actually exercised herein that is - some functions require .cpp files).
+
+    To build and run:
+      g++ -o bsondemo bsondemo.cpp
+      ./bsondemo
+
+    Windows: project files are available in this directory for bsondemo.cpp for use with Visual Studio.
 */
 
 /*
diff --git a/bson/bsondemo/bsondemo.vcxproj b/bson/bsondemo/bsondemo.vcxproj
index bb82a50..2ad5389 100644
--- a/bson/bsondemo/bsondemo.vcxproj
+++ b/bson/bsondemo/bsondemo.vcxproj
@@ -89,7 +89,7 @@
     <ClCompile>

       <Optimization>Disabled</Optimization>

       <AdditionalIncludeDirectories>c:\boost;\boost</AdditionalIncludeDirectories>

-      <PreprocessorDefinitions>WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

+      <PreprocessorDefinitions>_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

       <MinimalRebuild>No</MinimalRebuild>

       <BasicRuntimeChecks>EnableFastChecks</BasicRuntimeChecks>

       <RuntimeLibrary>MultiThreadedDebugDLL</RuntimeLibrary>

@@ -109,7 +109,7 @@
     <ClCompile>

       <Optimization>Disabled</Optimization>

       <AdditionalIncludeDirectories>c:\boost;\boost</AdditionalIncludeDirectories>

-      <PreprocessorDefinitions>WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

+      <PreprocessorDefinitions>_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

       <BasicRuntimeChecks>EnableFastChecks</BasicRuntimeChecks>

       <RuntimeLibrary>MultiThreadedDebugDLL</RuntimeLibrary>

       <PrecompiledHeader>

@@ -128,7 +128,7 @@
     <ClCompile>

       <Optimization>MaxSpeed</Optimization>

       <IntrinsicFunctions>true</IntrinsicFunctions>

-      <PreprocessorDefinitions>WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

+      <PreprocessorDefinitions>NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

       <RuntimeLibrary>MultiThreadedDLL</RuntimeLibrary>

       <FunctionLevelLinking>true</FunctionLevelLinking>

       <PrecompiledHeader>

@@ -151,7 +151,7 @@
     <ClCompile>

       <Optimization>MaxSpeed</Optimization>

       <IntrinsicFunctions>true</IntrinsicFunctions>

-      <PreprocessorDefinitions>WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

+      <PreprocessorDefinitions>NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>

       <RuntimeLibrary>MultiThreadedDLL</RuntimeLibrary>

       <FunctionLevelLinking>true</FunctionLevelLinking>

       <PrecompiledHeader>

diff --git a/bson/bsonelement.h b/bson/bsonelement.h
index 23d59fa..5487d8d 100644
--- a/bson/bsonelement.h
+++ b/bson/bsonelement.h
@@ -20,6 +20,14 @@
 #include <vector>
 #include <string.h>
 #include "util/builder.h"
+#include "bsontypes.h"
+
+namespace mongo {
+    class OpTime;
+    class BSONObj;
+    class BSONElement;
+    class BSONObjBuilder;
+}
 
 namespace bson {
     typedef mongo::BSONElement be;
@@ -29,9 +37,6 @@ namespace bson {
 
 namespace mongo {
 
-    class OpTime;
-    class BSONElement;
-
     /* l and r MUST have same type when called: check that first. */
     int compareElementValues(const BSONElement& l, const BSONElement& r);
 
@@ -120,7 +125,8 @@ namespace mongo {
         /** Size of the element.
             @param maxLen If maxLen is specified, don't scan more than maxLen bytes to calculate size.
         */
-        int size( int maxLen = -1 ) const;
+        int size( int maxLen ) const;
+        int size() const;
 
         /** Wrap this element up as a singleton object. */
         BSONObj wrap() const;
@@ -155,15 +161,18 @@ namespace mongo {
             return *value() ? true : false;
         }
 
+        bool booleanSafe() const { return isBoolean() && boolean(); }
+
         /** Retrieve a java style date value from the element.
             Ensure element is of type Date before calling.
+            @see Bool(), trueValue()
         */
         Date_t date() const {
             return *reinterpret_cast< const Date_t* >( value() );
         }
 
         /** Convert the value to boolean, regardless of its type, in a javascript-like fashion
-            (i.e., treat zero and null as false).
+            (i.e., treats zero and null and eoo as false).
         */
         bool trueValue() const;
 
@@ -203,7 +212,9 @@ namespace mongo {
         }
 
         /** Size (length) of a string element.
-            You must assure of type String first.  */
+            You must assure of type String first.  
+            @return string size including terminating null
+        */
         int valuestrsize() const {
             return *reinterpret_cast< const int* >( value() );
         }
@@ -359,6 +370,7 @@ namespace mongo {
             return *reinterpret_cast< const mongo::OID* >( start );
         }
 
+        /** this does not use fieldName in the comparison, just the value */
         bool operator<( const BSONElement& other ) const {
             int x = (int)canonicalType() - (int)other.canonicalType();
             if ( x < 0 ) return true;
@@ -366,19 +378,30 @@ namespace mongo {
             return compareElementValues(*this,other) < 0;
         }
 
-        // If maxLen is specified, don't scan more than maxLen bytes.
-        explicit BSONElement(const char *d, int maxLen = -1) : data(d) {
-            fieldNameSize_ = -1;
-            if ( eoo() )
+        // @param maxLen don't scan more than maxLen bytes
+        explicit BSONElement(const char *d, int maxLen) : data(d) {
+            if ( eoo() ) {
+                totalSize = 1;
                 fieldNameSize_ = 0;
+            }
             else {
+                totalSize = -1;
+                fieldNameSize_ = -1;
                 if ( maxLen != -1 ) {
                     int size = (int) strnlen( fieldName(), maxLen - 1 );
                     massert( 10333 ,  "Invalid field name", size != -1 );
                     fieldNameSize_ = size + 1;
                 }
             }
+        }
+
+        explicit BSONElement(const char *d) : data(d) {
+            fieldNameSize_ = -1;
             totalSize = -1;
+            if ( eoo() ) {
+                fieldNameSize_ = 0;
+                totalSize = 1;
+            }
         }
 
         string _asCode() const;
@@ -399,7 +422,10 @@ namespace mongo {
         const BSONElement& chk(int t) const {
             if ( t != type() ) {
                 StringBuilder ss;
-                ss << "wrong type for BSONElement (" << fieldName() << ") " << type() << " != " << t;
+                if( eoo() )
+                    ss << "field not found, expected type " << t;
+                else
+                    ss << "wrong type for field (" << fieldName() << ") " << type() << " != " << t;
                 uasserted(13111, ss.str() );
             }
             return *this;
@@ -477,7 +503,7 @@ namespace mongo {
         return true;
     }
 
-    /** True if element is of a numeric type. */
+    /** @return true if element is of a numeric type. */
     inline bool BSONElement::isNumber() const {
         switch( type() ) {
         case NumberLong:
diff --git a/bson/bsonmisc.h b/bson/bsonmisc.h
index 96be12a..8abb487 100644
--- a/bson/bsonmisc.h
+++ b/bson/bsonmisc.h
@@ -29,20 +29,16 @@ namespace mongo {
 
     class BSONObjCmp {
     public:
-        BSONObjCmp( const BSONObj &_order = BSONObj() ) : order( _order ) {}
+        BSONObjCmp( const BSONObj &order = BSONObj() ) : _order( order ) {}
         bool operator()( const BSONObj &l, const BSONObj &r ) const {
-            return l.woCompare( r, order ) < 0;
+            return l.woCompare( r, _order ) < 0;
         }
+        BSONObj order() const { return _order; }
     private:
-        BSONObj order;
+        BSONObj _order;
     };
 
-    class BSONObjCmpDefaultOrder : public BSONObjCmp {
-    public:
-        BSONObjCmpDefaultOrder() : BSONObjCmp( BSONObj() ) {}
-    };
-
-    typedef set< BSONObj, BSONObjCmpDefaultOrder > BSONObjSetDefaultOrder;
+    typedef set<BSONObj,BSONObjCmp> BSONObjSet;
 
     enum FieldCompareResult {
         LEFT_SUBFIELD = -2,
@@ -202,4 +198,6 @@ namespace mongo {
         int _sizes[SIZE];
     };
 
+    // considers order
+    bool fieldsMatch(const BSONObj& lhs, const BSONObj& rhs);
 }
diff --git a/bson/bsonobj.h b/bson/bsonobj.h
index 3ca6b8c..9e948f3 100644
--- a/bson/bsonobj.h
+++ b/bson/bsonobj.h
@@ -17,15 +17,18 @@
 
 #pragma once
 
+#include <boost/intrusive_ptr.hpp>
 #include <set>
 #include <list>
 #include <vector>
+#include "util/atomic_int.h"
 #include "util/builder.h"
 #include "stringdata.h"
 
 namespace mongo {
 
     typedef set< BSONElement, BSONElementCmpWithoutField > BSONElementSet;
+    typedef multiset< BSONElement, BSONElementCmpWithoutField > BSONElementMSet;
 
     /**
        C++ representation of a "BSON" object -- that is, an extended JSON-style
@@ -69,11 +72,19 @@ namespace mongo {
     public:
 
         /** Construct a BSONObj from data in the proper format.
-            @param ifree true if the BSONObj should free() the msgdata when
-            it destructs.
+         *  Use this constructor when something else owns msgdata's buffer
         */
-        explicit BSONObj(const char *msgdata, bool ifree = false) {
-            init(msgdata, ifree);
+        explicit BSONObj(const char *msgdata) {
+            init(msgdata);
+        }
+
+        /** Construct a BSONObj from data in the proper format.
+         *  Use this constructor when you want BSONObj to free(holder) when it is no longer needed
+         *  BSONObj::Holder has an extra 4 bytes for a ref-count before the start of the object
+        */
+        class Holder;
+        explicit BSONObj(Holder* holder) {
+            init(holder);
         }
 
         explicit BSONObj(const Record *r);
@@ -81,7 +92,9 @@ namespace mongo {
         /** Construct an empty BSONObj -- that is, {}. */
         BSONObj();
 
-        ~BSONObj() { /*defensive:*/ _objdata = 0; }
+        ~BSONObj() { 
+            _objdata = 0; // defensive
+        }
 
         /**
            A BSONObj can use a buffer it "owns" or one it does not.
@@ -113,7 +126,9 @@ namespace mongo {
         */
         bool isOwned() const { return _holder.get() != 0; }
 
-        /* make sure the data buffer is under the control of this BSONObj and not a remote buffer */
+        /** assure the data buffer is under the control of this BSONObj and not a remote buffer 
+            @see isOwned()
+        */
         BSONObj getOwned() const;
 
         /** @return a new full (and owned) copy of the object. */
@@ -133,6 +148,11 @@ namespace mongo {
         /** note: addFields always adds _id even if not specified */
         int addFields(BSONObj& from, set<string>& fields); /* returns n added */
 
+        /** remove specified field and return a new object with the remaining fields.
+            slowish as builds a full new object
+         */
+        BSONObj removeField(const StringData& name) const;
+
         /** returns # of top level fields in the object
            note: iterates to count the fields
         */
@@ -141,20 +161,26 @@ namespace mongo {
         /** adds the field names to the fields set.  does NOT clear it (appends). */
         int getFieldNames(set<string>& fields) const;
 
-        /** return has eoo() true if no match
-           supports "." notation to reach into embedded objects
+        /** @return the specified element.  element.eoo() will be true if not found.
+            @param name field to find. supports dot (".") notation to reach into embedded objects.
+             for example "x.y" means "in the nested object in field x, retrieve field y"
         */
         BSONElement getFieldDotted(const char *name) const;
-        /** return has eoo() true if no match
-           supports "." notation to reach into embedded objects
+        /** @return the specified element.  element.eoo() will be true if not found.
+            @param name field to find. supports dot (".") notation to reach into embedded objects.
+             for example "x.y" means "in the nested object in field x, retrieve field y"
         */
         BSONElement getFieldDotted(const string& name) const {
             return getFieldDotted( name.c_str() );
         }
 
-        /** Like getFieldDotted(), but expands multikey arrays and returns all matching objects
+        /** Like getFieldDotted(), but expands arrays and returns all matching objects.
+         *  Turning off expandLastArray allows you to retrieve nested array objects instead of
+         *  their contents.
          */
-        void getFieldsDotted(const StringData& name, BSONElementSet &ret ) const;
+        void getFieldsDotted(const StringData& name, BSONElementSet &ret, bool expandLastArray = true ) const;
+        void getFieldsDotted(const StringData& name, BSONElementMSet &ret, bool expandLastArray = true ) const;
+
         /** Like getFieldDotted(), but returns first array encountered while traversing the
             dotted fields of name.  The name variable is updated to represent field
             names with respect to the returned element. */
@@ -165,6 +191,14 @@ namespace mongo {
         */
         BSONElement getField(const StringData& name) const;
 
+        /** Get several fields at once. This is faster than separate getField() calls as the size of 
+            elements iterated can then be calculated only once each.
+            @param n number of fieldNames, and number of elements in the fields array
+            @param fields if a field is found its element is stored in its corresponding position in this array.
+                   if not found the array element is unchanged.
+         */
+        void getFields(unsigned n, const char **fieldNames, BSONElement *fields) const;
+
         /** Get the field of the specified name. eoo() is true on the returned
             element if not found.
         */
@@ -184,7 +218,9 @@ namespace mongo {
         }
 
         /** @return true if field exists */
-        bool hasField( const char * name ) const { return ! getField( name ).eoo(); }
+        bool hasField( const char * name ) const { return !getField(name).eoo(); }
+        /** @return true if field exists */
+        bool hasElement(const char *name) const { return hasField(name); }
 
         /** @return "" if DNE or wrong type */
         const char * getStringField(const char *name) const;
@@ -195,7 +231,9 @@ namespace mongo {
         /** @return INT_MIN if not present - does some type conversions */
         int getIntField(const char *name) const;
 
-        /** @return false if not present */
+        /** @return false if not present 
+            @see BSONElement::trueValue()
+         */
         bool getBoolField(const char *name) const;
 
         /**
@@ -224,7 +262,7 @@ namespace mongo {
         int objsize() const { return *(reinterpret_cast<const int*>(objdata())); }
 
         /** performs a cursory check on the object's size only. */
-        bool isValid();
+        bool isValid() const;
 
         /** @return if the user is a valid user doc
             criter: isValid() no . or $ field names
@@ -255,7 +293,6 @@ namespace mongo {
         int woCompare(const BSONObj& r, const BSONObj &ordering = BSONObj(),
                       bool considerFieldName=true) const;
 
-
         bool operator<( const BSONObj& other ) const { return woCompare( other ) < 0; }
         bool operator<=( const BSONObj& other ) const { return woCompare( other ) <= 0; }
         bool operator>( const BSONObj& other ) const { return woCompare( other ) > 0; }
@@ -266,10 +303,12 @@ namespace mongo {
          */
         int woSortOrder( const BSONObj& r , const BSONObj& sortKey , bool useDotted=false ) const;
 
+        bool equal(const BSONObj& r) const;
+
         /** This is "shallow equality" -- ints and doubles won't match.  for a
            deep equality test use woCompare (which is slower).
         */
-        bool woEqual(const BSONObj& r) const {
+        bool binaryEqual(const BSONObj& r) const {
             int os = objsize();
             if ( os == r.objsize() ) {
                 return (os == 0 || memcmp(objdata(),r.objdata(),os)==0);
@@ -280,8 +319,13 @@ namespace mongo {
         /** @return first field of the object */
         BSONElement firstElement() const { return BSONElement(objdata() + 4); }
 
-        /** @return true if field exists in the object */
-        bool hasElement(const char *name) const;
+        /** faster than firstElement().fieldName() - for the first element we can easily find the fieldname without 
+            computing the element size.
+        */
+        const char * firstElementFieldName() const { 
+            const char *p = objdata() + 4;
+            return *p == EOO ? "" : p+1;
+        }
 
         /** Get the _id field from the object.  For good performance drivers should
             assure that _id is the first element of the object; however, correct operation
@@ -315,9 +359,7 @@ namespace mongo {
         /** @return an md5 value for this object. */
         string md5() const;
 
-        bool operator==( const BSONObj& other ) const {
-            return woCompare( other ) == 0;
-        }
+        bool operator==( const BSONObj& other ) const { return equal( other ); }
 
         enum MatchType {
             Equality = 0,
@@ -376,34 +418,52 @@ namespace mongo {
                 ...
             }
         */
-        BSONObjIterator begin();
+        BSONObjIterator begin() const;
 
         void appendSelfToBufBuilder(BufBuilder& b) const {
             assert( objsize() );
             b.appendBuf(reinterpret_cast<const void *>( objdata() ), objsize());
         }
 
-    private:
-        class Holder {
+#pragma pack(1)
+        class Holder : boost::noncopyable {
+        private:
+            Holder(); // this class should never be explicitly created
+            AtomicUInt refCount;
         public:
-            Holder( const char *objdata ) :
-                _objdata( objdata ) {
-            }
-            ~Holder() {
-                free((void *)_objdata);
-                _objdata = 0;
+            char data[4]; // start of object
+
+            void zero() { refCount.zero(); }
+
+            // these are called automatically by boost::intrusive_ptr
+            friend void intrusive_ptr_add_ref(Holder* h) { h->refCount++; }
+            friend void intrusive_ptr_release(Holder* h) {
+#if defined(_DEBUG) // cant use dassert or DEV here
+                assert((int)h->refCount > 0); // make sure we haven't already freed the buffer
+#endif
+                if(--(h->refCount) == 0){
+#if defined(_DEBUG)
+                    unsigned sz = (unsigned&) *h->data;
+                    assert(sz < BSONObjMaxInternalSize * 3);
+                    memset(h->data, 0xdd, sz);
+#endif
+                    free(h);
+                }
             }
-        private:
-            const char *_objdata;
         };
+#pragma pack()
 
+    private:
         const char *_objdata;
-        boost::shared_ptr< Holder > _holder;
+        boost::intrusive_ptr< Holder > _holder;
 
         void _assertInvalid() const;
-        void init(const char *data, bool ifree) {
-            if ( ifree )
-                _holder.reset( new Holder( data ) );
+
+        void init(Holder *holder) {
+            _holder = holder; // holder is now managed by intrusive_ptr
+            init(holder->data);
+        }
+        void init(const char *data) {
             _objdata = data;
             if ( !isValid() )
                 _assertInvalid();
diff --git a/bson/bsonobjbuilder.h b/bson/bsonobjbuilder.h
index a39b529..86a52ac 100644
--- a/bson/bsonobjbuilder.h
+++ b/bson/bsonobjbuilder.h
@@ -24,10 +24,15 @@
 
 #include <limits>
 #include <cmath>
-using namespace std;
+#include <boost/static_assert.hpp>
+#include "bsonelement.h"
+#include "bsonobj.h"
+#include "bsonmisc.h"
 
 namespace mongo {
 
+    using namespace std;
+
 #if defined(_WIN32)
 // warning: 'this' : used in base member initializer list
 #pragma warning( disable : 4355 )
@@ -81,18 +86,21 @@ namespace mongo {
     class BSONObjBuilder : boost::noncopyable {
     public:
         /** @param initsize this is just a hint as to the final size of the object */
-        BSONObjBuilder(int initsize=512) : _b(_buf), _buf(initsize), _offset( 0 ), _s( this ) , _tracker(0) , _doneCalled(false) {
-            _b.skip(4); /*leave room for size field*/
+        BSONObjBuilder(int initsize=512) : _b(_buf), _buf(initsize + sizeof(unsigned)), _offset( sizeof(unsigned) ), _s( this ) , _tracker(0) , _doneCalled(false) {
+            _b.appendNum((unsigned)0); // ref-count
+            _b.skip(4); /*leave room for size field and ref-count*/
         }
 
-        /* dm why do we have this/need this? not clear to me, comment please tx. */
-        /** @param baseBuilder construct a BSONObjBuilder using an existing BufBuilder */
+        /** @param baseBuilder construct a BSONObjBuilder using an existing BufBuilder
+         *  This is for more efficient adding of subobjects/arrays. See docs for subobjStart for example.
+         */
         BSONObjBuilder( BufBuilder &baseBuilder ) : _b( baseBuilder ), _buf( 0 ), _offset( baseBuilder.len() ), _s( this ) , _tracker(0) , _doneCalled(false) {
             _b.skip( 4 );
         }
 
-        BSONObjBuilder( const BSONSizeTracker & tracker ) : _b(_buf) , _buf(tracker.getSize() ), _offset(0), _s( this ) , _tracker( (BSONSizeTracker*)(&tracker) ) , _doneCalled(false) {
-            _b.skip( 4 );
+        BSONObjBuilder( const BSONSizeTracker & tracker ) : _b(_buf) , _buf(tracker.getSize() + sizeof(unsigned) ), _offset( sizeof(unsigned) ), _s( this ) , _tracker( (BSONSizeTracker*)(&tracker) ) , _doneCalled(false) {
+            _b.appendNum((unsigned)0); // ref-count
+            _b.skip(4);
         }
 
         ~BSONObjBuilder() {
@@ -146,9 +154,17 @@ namespace mongo {
             return *this;
         }
 
-
         /** add header for a new subobject and return bufbuilder for writing to
-            the subobject's body */
+         *  the subobject's body
+         *
+         *  example:
+         *
+         *  BSONObjBuilder b;
+         *  BSONObjBuilder sub (b.subobjStart("fieldName"));
+         *  // use sub
+         *  sub.done()
+         *  // use b and convert to object
+         */
         BufBuilder &subobjStart(const StringData& fieldName) {
             _b.appendNum((char) Object);
             _b.appendStr(fieldName);
@@ -218,7 +234,7 @@ namespace mongo {
             long long x = n;
             if ( x < 0 )
                 x = x * -1;
-            if ( x < ( numeric_limits<int>::max() / 2 ) )
+            if ( x < ( (numeric_limits<int>::max)() / 2 ) ) // extra () to avoid max macro on windows
                 append( fieldName , (int)n );
             else
                 append( fieldName , n );
@@ -247,14 +263,13 @@ namespace mongo {
             return *this;
         }
 
-
         BSONObjBuilder& appendNumber( const StringData& fieldName , long long l ) {
             static long long maxInt = (int)pow( 2.0 , 30.0 );
             static long long maxDouble = (long long)pow( 2.0 , 40.0 );
-
-            if ( l < maxInt )
+            long long x = l >= 0 ? l : -l;
+            if ( x < maxInt )
                 append( fieldName , (int)l );
-            else if ( l < maxDouble )
+            else if ( x < maxDouble )
                 append( fieldName , (double)l );
             else
                 append( fieldName , l );
@@ -366,12 +381,13 @@ namespace mongo {
             return *this;
         }
 
-        /** Append a string element. len DOES include terminating nul */
-        BSONObjBuilder& append(const StringData& fieldName, const char *str, int len) {
+        /** Append a string element. 
+            @param sz size includes terminating null character */
+        BSONObjBuilder& append(const StringData& fieldName, const char *str, int sz) {
             _b.appendNum((char) String);
             _b.appendStr(fieldName);
-            _b.appendNum((int)len);
-            _b.appendBuf(str, len);
+            _b.appendNum((int)sz);
+            _b.appendBuf(str, sz);
             return *this;
         }
         /** Append a string element */
@@ -517,6 +533,10 @@ namespace mongo {
         template < class T >
         BSONObjBuilder& append( const StringData& fieldName, const list< T >& vals );
 
+        /** Append a set of values. */
+        template < class T >
+        BSONObjBuilder& append( const StringData& fieldName, const set< T >& vals );
+
         /**
          * destructive
          * The returned BSONObj will free the buffer when it is finished.
@@ -525,8 +545,10 @@ namespace mongo {
         BSONObj obj() {
             bool own = owned();
             massert( 10335 , "builder does not own memory", own );
-            int l;
-            return BSONObj(decouple(l), true);
+            doneFast();
+            BSONObj::Holder* h = (BSONObj::Holder*)_b.buf();
+            decouple(); // sets _b.buf() to NULL
+            return BSONObj(h);
         }
 
         /** Fetch the object we have built.
@@ -535,7 +557,7 @@ namespace mongo {
             would like the BSONObj to last longer than the builder.
         */
         BSONObj done() {
-            return BSONObj(_done(), /*ifree*/false);
+            return BSONObj(_done());
         }
 
         // Like 'done' above, but does not construct a BSONObj to return to the caller.
@@ -569,7 +591,7 @@ namespace mongo {
         void appendKeys( const BSONObj& keyPattern , const BSONObj& values );
 
         static string numStr( int i ) {
-            if (i>=0 && i<100)
+            if (i>=0 && i<100 && numStrsReady)
                 return numStrs[i];
             StringBuilder o;
             o << i;
@@ -623,6 +645,8 @@ namespace mongo {
 
         int len() const { return _b.len(); }
 
+        BufBuilder& bb() { return _b; }
+
     private:
         char* _done() {
             if ( _doneCalled )
@@ -647,6 +671,7 @@ namespace mongo {
         bool _doneCalled;
 
         static const string numStrs[100]; // cache of 0 to 99 inclusive
+        static bool numStrsReady; // for static init safety. see comments in db/jsobj.cpp
     };
 
     class BSONArrayBuilder : boost::noncopyable {
@@ -692,7 +717,23 @@ namespace mongo {
             return *this;
         }
 
-        BufBuilder &subobjStart( const StringData& name = "0" ) {
+        // These two just use next position
+        BufBuilder &subobjStart() { return _b.subobjStart( num() ); }
+        BufBuilder &subarrayStart() { return _b.subarrayStart( num() ); }
+
+        // These fill missing entries up to pos. if pos is < next pos is ignored
+        BufBuilder &subobjStart(int pos) {
+            fill(pos);
+            return _b.subobjStart( num() );
+        }
+        BufBuilder &subarrayStart(int pos) {
+            fill(pos);
+            return _b.subarrayStart( num() );
+        }
+
+        // These should only be used where you really need interface compatability with BSONObjBuilder
+        // Currently they are only used by update.cpp and it should probably stay that way
+        BufBuilder &subobjStart( const StringData& name ) {
             fill( name );
             return _b.subobjStart( num() );
         }
@@ -720,7 +761,16 @@ namespace mongo {
             long int n = strtol( name.data(), &r, 10 );
             if ( *r )
                 uasserted( 13048, (string)"can't append to array using string field name [" + name.data() + "]" );
-            while( _i < n )
+            fill(n);
+        }
+
+        void fill (int upTo){
+            // if this is changed make sure to update error message and jstests/set7.js
+            const int maxElems = 1500000;
+            BOOST_STATIC_ASSERT(maxElems < (BSONObjMaxUserSize/10));
+            uassert(15891, "can't backfill array to larger than 1,500,000 elements", upTo <= maxElems);
+
+            while( _i < upTo )
                 append( nullElt() );
         }
 
@@ -749,16 +799,27 @@ namespace mongo {
         return *this;
     }
 
-    template < class T >
-    inline BSONObjBuilder& BSONObjBuilder::append( const StringData& fieldName, const list< T >& vals ) {
+    template < class L >
+    inline BSONObjBuilder& _appendIt( BSONObjBuilder& _this, const StringData& fieldName, const L& vals ) {
         BSONObjBuilder arrBuilder;
         int n = 0;
-        for( typename list< T >::const_iterator i = vals.begin(); i != vals.end(); i++ )
-            arrBuilder.append( numStr(n++), *i );
-        appendArray( fieldName, arrBuilder.done() );
-        return *this;
+        for( typename L::const_iterator i = vals.begin(); i != vals.end(); i++ )
+            arrBuilder.append( BSONObjBuilder::numStr(n++), *i );
+        _this.appendArray( fieldName, arrBuilder.done() );
+        return _this;
     }
 
+    template < class T >
+    inline BSONObjBuilder& BSONObjBuilder::append( const StringData& fieldName, const list< T >& vals ) {
+        return _appendIt< list< T > >( *this, fieldName, vals );
+    }
+
+    template < class T >
+    inline BSONObjBuilder& BSONObjBuilder::append( const StringData& fieldName, const set< T >& vals ) {
+        return _appendIt< set< T > >( *this, fieldName, vals );
+    }
+
+
     // $or helper: OR(BSON("x" << GT << 7), BSON("y" << LT 6));
     inline BSONObj OR(const BSONObj& a, const BSONObj& b)
     { return BSON( "$or" << BSON_ARRAY(a << b) ); }
diff --git a/bson/bsonobjiterator.h b/bson/bsonobjiterator.h
index 6e6a69e..39ae24d 100644
--- a/bson/bsonobjiterator.h
+++ b/bson/bsonobjiterator.h
@@ -26,6 +26,8 @@ namespace mongo {
        Note each BSONObj ends with an EOO element: so you will get more() on an empty
        object, although next().eoo() will be true.
 
+       The BSONObj must stay in scope for the duration of the iterator's execution.
+
        todo: we may want to make a more stl-like iterator interface for this
              with things like begin() and end()
     */
@@ -35,39 +37,44 @@ namespace mongo {
         */
         BSONObjIterator(const BSONObj& jso) {
             int sz = jso.objsize();
-            if ( sz == 0 ) {
+            if ( MONGO_unlikely(sz == 0) ) {
                 _pos = _theend = 0;
                 return;
             }
             _pos = jso.objdata() + 4;
-            _theend = jso.objdata() + sz;
+            _theend = jso.objdata() + sz - 1;
         }
 
         BSONObjIterator( const char * start , const char * end ) {
             _pos = start + 4;
-            _theend = end;
+            _theend = end - 1;
         }
 
         /** @return true if more elements exist to be enumerated. */
-        bool more() { return _pos < _theend && _pos[0]; }
+        bool more() { return _pos < _theend; }
 
         /** @return true if more elements exist to be enumerated INCLUDING the EOO element which is always at the end. */
-        bool moreWithEOO() { return _pos < _theend; }
+        bool moreWithEOO() { return _pos <= _theend; }
 
         /** @return the next element in the object. For the final element, element.eoo() will be true. */
-        BSONElement next( bool checkEnd = false ) {
-            assert( _pos < _theend );
-            BSONElement e( _pos, checkEnd ? (int)(_theend - _pos) : -1 );
-            _pos += e.size( checkEnd ? (int)(_theend - _pos) : -1 );
+        BSONElement next( bool checkEnd ) {
+            assert( _pos <= _theend );
+            BSONElement e( _pos, checkEnd ? (int)(_theend + 1 - _pos) : -1 );
+            _pos += e.size( checkEnd ? (int)(_theend + 1 - _pos) : -1 );
+            return e;
+        }
+        BSONElement next() {
+            assert( _pos <= _theend );
+            BSONElement e(_pos);
+            _pos += e.size();
             return e;
         }
-
         void operator++() { next(); }
         void operator++(int) { next(); }
 
         BSONElement operator*() {
-            assert( _pos < _theend );
-            return BSONElement(_pos, -1);
+            assert( _pos <= _theend );
+            return BSONElement(_pos);
         }
 
     private:
@@ -102,6 +109,29 @@ namespace mongo {
         int _cur;
     };
 
+    /** transform a BSON array into a vector of BSONElements.
+        we match array # positions with their vector position, and ignore
+        any fields with non-numeric field names.
+        */
+    inline vector<BSONElement> BSONElement::Array() const {
+        chk(mongo::Array);
+        vector<BSONElement> v;
+        BSONObjIterator i(Obj());
+        while( i.more() ) {
+            BSONElement e = i.next();
+            const char *f = e.fieldName();
+            try {
+                unsigned u = stringToNum(f);
+                assert( u < 1000000 );
+                if( u >= v.size() )
+                    v.resize(u+1);
+                v[u] = e;
+            }
+            catch(unsigned) { }
+        }
+        return v;
+    }
+
     /** Similar to BOOST_FOREACH
      *
      *  because the iterator is defined outside of the for, you must use {} around
diff --git a/bson/inline_decls.h b/bson/inline_decls.h
index 1605611..30da9b4 100644
--- a/bson/inline_decls.h
+++ b/bson/inline_decls.h
@@ -1,20 +1,19 @@
-// inline.h
-
-/**
-*    Copyright (C) 2010 10gen Inc.
-*
-*    This program is free software: you can redistribute it and/or  modify
-*    it under the terms of the GNU Affero General Public License, version 3,
-*    as published by the Free Software Foundation.
-*
-*    This program is distributed in the hope that it will be useful,
-*    but WITHOUT ANY WARRANTY; without even the implied warranty of
-*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-*    GNU Affero General Public License for more details.
-*
-*    You should have received a copy of the GNU Affero General Public License
-*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
-*/
+// inline_decls.h
+
+/*    Copyright 2010 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
 
 #pragma once
 
@@ -31,3 +30,39 @@
 #define NOINLINE_DECL
 
 #endif
+
+namespace mongo {
+
+/* Note: do not clutter code with these -- ONLY use in hot spots / significant loops. */
+
+#if !defined(__GNUC__)
+
+// branch prediction.  indicate we expect to be true
+# define MONGO_likely(x) ((bool)(x))
+
+// branch prediction.  indicate we expect to be false
+# define MONGO_unlikely(x) ((bool)(x))
+
+# if defined(_WIN32)
+    // prefetch data from memory
+    inline void prefetch(const void *p) { 
+#if defined(_MM_HINT_T0)
+        _mm_prefetch((char *) p, _MM_HINT_T0);
+#endif
+    }
+#else
+    inline void prefetch(void *p) { }
+#endif
+
+#else
+
+# define MONGO_likely(x) ( __builtin_expect((bool)(x), 1) )
+# define MONGO_unlikely(x) ( __builtin_expect((bool)(x), 0) )
+
+    inline void prefetch(void *p) { 
+        __builtin_prefetch(p);
+    }
+
+#endif
+
+}
diff --git a/bson/oid.cpp b/bson/oid.cpp
index 6aa0730..3aee14a 100644
--- a/bson/oid.cpp
+++ b/bson/oid.cpp
@@ -19,6 +19,7 @@
 #include "oid.h"
 #include "util/atomic_int.h"
 #include "../db/nonce.h"
+#include "bsonobjbuilder.h"
 
 BOOST_STATIC_ASSERT( sizeof(mongo::OID) == 12 );
 
@@ -34,7 +35,7 @@ namespace mongo {
 #elif defined(__linux__) || defined(__APPLE__) || defined(__sunos__)
         pid = (unsigned short) getpid();
 #else
-        pid = (unsigned short) security.getNonce();
+        pid = (unsigned short) Security::getNonce();
 #endif
         return pid;
     }
@@ -53,13 +54,13 @@ namespace mongo {
         // this is not called often, so the following is not expensive, and gives us some
         // testing that nonce generation is working right and that our OIDs are (perhaps) ok.
         {
-            nonce a = security.getNonce();
-            nonce b = security.getNonce();
-            nonce c = security.getNonce();
+            nonce64 a = Security::getNonceDuringInit();
+            nonce64 b = Security::getNonceDuringInit();
+            nonce64 c = Security::getNonceDuringInit();
             assert( !(a==b && b==c) );
         }
 
-        unsigned long long n = security.getNonce();
+        unsigned long long n = Security::getNonceDuringInit();
         OID::MachineAndPid x = ourMachine = (OID::MachineAndPid&) n;
         foldInPid(x);
         return x;
@@ -96,7 +97,7 @@ namespace mongo {
     }
 
     void OID::init() {
-        static AtomicUInt inc = (unsigned) security.getNonce();
+        static AtomicUInt inc = (unsigned) Security::getNonce();
 
         {
             unsigned t = (unsigned) time(0);
@@ -151,4 +152,22 @@ namespace mongo {
         return time;
     }
 
+    const string BSONObjBuilder::numStrs[] = {
+        "0",  "1",  "2",  "3",  "4",  "5",  "6",  "7",  "8",  "9",
+        "10", "11", "12", "13", "14", "15", "16", "17", "18", "19",
+        "20", "21", "22", "23", "24", "25", "26", "27", "28", "29",
+        "30", "31", "32", "33", "34", "35", "36", "37", "38", "39",
+        "40", "41", "42", "43", "44", "45", "46", "47", "48", "49",
+        "50", "51", "52", "53", "54", "55", "56", "57", "58", "59",
+        "60", "61", "62", "63", "64", "65", "66", "67", "68", "69",
+        "70", "71", "72", "73", "74", "75", "76", "77", "78", "79",
+        "80", "81", "82", "83", "84", "85", "86", "87", "88", "89",
+        "90", "91", "92", "93", "94", "95", "96", "97", "98", "99",
+    };
+
+    // This is to ensure that BSONObjBuilder doesn't try to use numStrs before the strings have been constructed
+    // I've tested just making numStrs a char[][], but the overhead of constructing the strings each time was too high
+    // numStrsReady will be 0 until after numStrs is initialized because it is a static variable
+    bool BSONObjBuilder::numStrsReady = (numStrs[0].size() > 0);
+
 }
diff --git a/bson/ordering.h b/bson/ordering.h
index 749e20d..bca3296 100644
--- a/bson/ordering.h
+++ b/bson/ordering.h
@@ -19,15 +19,22 @@
 
 namespace mongo {
 
-    /** A precomputation of a BSON key pattern.
+    // todo: ideally move to db/ instead of bson/, but elim any dependencies first
+
+    /** A precomputation of a BSON index or sort key pattern.  That is something like: 
+           { a : 1, b : -1 }
         The constructor is private to make conversion more explicit so we notice where we call make().
         Over time we should push this up higher and higher.
-        */
+    */
     class Ordering {
-        const unsigned bits;
-        const unsigned nkeys;
-        Ordering(unsigned b,unsigned n) : bits(b),nkeys(n) { }
+        unsigned bits;
+        Ordering(unsigned b) : bits(b) { }
     public:
+        Ordering(const Ordering& r) : bits(r.bits) { }
+        void operator=(const Ordering& r) {
+            bits = r.bits;
+        }
+
         /** so, for key pattern { a : 1, b : -1 }
             get(0) == 1
             get(1) == -1
@@ -39,12 +46,12 @@ namespace mongo {
         // for woCompare...
         unsigned descending(unsigned mask) const { return bits & mask; }
 
-        operator string() const {
+        /*operator string() const {
             StringBuilder buf(32);
             for ( unsigned i=0; i<nkeys; i++)
                 buf.append( get(i) > 0 ? "+" : "-" );
             return buf.str();
-        }
+        }*/
 
         static Ordering make(const BSONObj& obj) {
             unsigned b = 0;
@@ -59,7 +66,7 @@ namespace mongo {
                     b |= (1 << n);
                 n++;
             }
-            return Ordering(b,n);
+            return Ordering(b);
         }
     };
 
diff --git a/bson/stringdata.h b/bson/stringdata.h
index 46cdb7a..352dc51 100644
--- a/bson/stringdata.h
+++ b/bson/stringdata.h
@@ -15,8 +15,7 @@
  *    limitations under the License.
  */
 
-#ifndef BSON_STRINDATA_HEADER
-#define BSON_STRINDATA_HEADER
+#pragma once
 
 #include <string>
 #include <cstring>
@@ -25,29 +24,31 @@ namespace mongo {
 
     using std::string;
 
-    // A StringData object wraps a 'const string&' or a 'const char*' without
-    // copying its contents. The most common usage is as a function argument that
-    // takes any of the two forms of strings above. Fundamentally, this class tries
-    // go around the fact that string literals in C++ are char[N]'s.
-    //
-    // Note that the object StringData wraps around must be alive while the StringDAta
-    // is.
-
+    /** A StringData object wraps a 'const string&' or a 'const char*' without
+     * copying its contents. The most common usage is as a function argument that
+     * takes any of the two forms of strings above. Fundamentally, this class tries
+     * go around the fact that string literals in C++ are char[N]'s.
+     *
+     * Note that the object StringData wraps around must be alive while the StringData
+     * is.
+    */
     class StringData {
     public:
-        // Construct a StringData explicilty, for the case where the lenght of
-        // string is not known. 'c' must be a pointer to a null-terminated string.
+        /** Construct a StringData, for the case where the length of
+         * string is not known. 'c' must be a pointer to a null-terminated string.
+         */
         StringData( const char* c )
             : _data(c), _size((unsigned) strlen(c)) {}
 
-        // Construct a StringData explicitly, for the case where the length of the string
-        // is already known. 'c' must be a pointer to a null-terminated string, and strlenOfc
-        // must be the length that std::strlen(c) would return, a.k.a the index of the
-        // terminator in c.
-        StringData( const char* c, size_t strlenOfc )
-            : _data(c), _size((unsigned) strlenOfc) {}
+        /** Construct a StringData explicitly, for the case where the length of the string
+         * is already known. 'c' must be a pointer to a null-terminated string, and strlenOfc
+         * must be the length that std::strlen(c) would return, a.k.a the index of the
+         * terminator in c.
+         */
+        StringData( const char* c, unsigned len )
+            : _data(c), _size(len) {}
 
-        // Construct a StringData explicitly, for the case of a std::string.
+        /** Construct a StringData, for the case of a std::string. */
         StringData( const string& s )
             : _data(s.c_str()), _size((unsigned) s.size()) {}
 
@@ -59,19 +60,12 @@ namespace mongo {
             : _data(&val[0]), _size(N-1) {}
 
         // accessors
-
-        const char* const data() const { return _data; }
+        const char* data() const { return _data; }
         const unsigned size() const { return _size; }
 
     private:
-        // There are two assumptions we use bellow.
-        // '_data' *always* finishes with a null terminator
-        // 'size' does *not* account for the null terminator
-        // These assumptions may make it easier to minimize changes to existing code.
-        const char* const _data;
-        const unsigned    _size;
+        const char* const _data;  // is always null terminated
+        const unsigned    _size;  // 'size' does not include the null terminator
     };
 
 } // namespace mongo
-
-#endif  // BSON_STRINGDATA_HEADER
diff --git a/bson/util/atomic_int.h b/bson/util/atomic_int.h
index 1573552..e85a023 100644
--- a/bson/util/atomic_int.h
+++ b/bson/util/atomic_int.h
@@ -36,15 +36,17 @@ namespace mongo {
         inline AtomicUInt operator--(); // --prefix
         inline AtomicUInt operator--(int); // postfix--
 
-        inline void zero() { x = 0; } // TODO: this isn't thread safe
+        inline void zero();
 
         volatile unsigned x;
     };
 
 #if defined(_WIN32)
+    void AtomicUInt::zero() { 
+        InterlockedExchange((volatile long*)&x, 0);
+    }
     AtomicUInt AtomicUInt::operator++() {
-        // InterlockedIncrement returns the new value
-        return InterlockedIncrement((volatile long*)&x); //long is 32bits in Win64
+        return InterlockedIncrement((volatile long*)&x);
     }
     AtomicUInt AtomicUInt::operator++(int) {
         return InterlockedIncrement((volatile long*)&x)-1;
@@ -57,6 +59,7 @@ namespace mongo {
     }
 #elif defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_4)
     // this is in GCC >= 4.1
+    inline void AtomicUInt::zero() { x = 0; } // TODO: this isn't thread safe - maybe
     AtomicUInt AtomicUInt::operator++() {
         return __sync_add_and_fetch(&x, 1);
     }
@@ -70,8 +73,8 @@ namespace mongo {
         return __sync_fetch_and_add(&x, -1);
     }
 #elif defined(__GNUC__)  && (defined(__i386__) || defined(__x86_64__))
+    inline void AtomicUInt::zero() { x = 0; } // TODO: this isn't thread safe
     // from boost 1.39 interprocess/detail/atomic.hpp
-
     inline unsigned atomic_int_helper(volatile unsigned *x, int val) {
         int r;
         asm volatile
diff --git a/bson/util/builder.h b/bson/util/builder.h
index 6f4ff9e..710c2d4 100644
--- a/bson/util/builder.h
+++ b/bson/util/builder.h
@@ -20,8 +20,6 @@
 #include <string>
 #include <string.h>
 #include <stdio.h>
-#include <boost/shared_ptr.hpp>
-
 #include "../inline_decls.h"
 #include "../stringdata.h"
 
@@ -49,11 +47,47 @@ namespace mongo {
 
     void msgasserted(int msgid, const char *msg);
 
-    class BufBuilder {
+    class TrivialAllocator { 
+    public:
+        void* Malloc(size_t sz) { return malloc(sz); }
+        void* Realloc(void *p, size_t sz) { return realloc(p, sz); }
+        void Free(void *p) { free(p); }
+    };
+
+    class StackAllocator {
+    public:
+        enum { SZ = 512 };
+        void* Malloc(size_t sz) {
+            if( sz <= SZ ) return buf;
+            return malloc(sz); 
+        }
+        void* Realloc(void *p, size_t sz) { 
+            if( p == buf ) {
+                if( sz <= SZ ) return buf;
+                void *d = malloc(sz);
+                memcpy(d, p, SZ);
+                return d;
+            }
+            return realloc(p, sz); 
+        }
+        void Free(void *p) { 
+            if( p != buf )
+                free(p); 
+        }
+    private:
+        char buf[SZ];
+    };
+
+    template< class Allocator >
+    class _BufBuilder {
+        // non-copyable, non-assignable
+        _BufBuilder( const _BufBuilder& );
+        _BufBuilder& operator=( const _BufBuilder& );
+        Allocator al;
     public:
-        BufBuilder(int initsize = 512) : size(initsize) {
+        _BufBuilder(int initsize = 512) : size(initsize) {
             if ( size > 0 ) {
-                data = (char *) malloc(size);
+                data = (char *) al.Malloc(size);
                 if( data == 0 )
                     msgasserted(10000, "out of memory BufBuilder");
             }
@@ -62,22 +96,23 @@ namespace mongo {
             }
             l = 0;
         }
-        ~BufBuilder() {
-            kill();
-        }
+        ~_BufBuilder() { kill(); }
 
         void kill() {
             if ( data ) {
-                free(data);
+                al.Free(data);
                 data = 0;
             }
         }
 
-        void reset( int maxSize = 0 ) {
+        void reset() {
+            l = 0;
+        }
+        void reset( int maxSize ) {
             l = 0;
             if ( maxSize && size > maxSize ) {
-                free(data);
-                data = (char*)malloc(maxSize);
+                al.Free(data);
+                data = (char*)al.Malloc(maxSize);
                 size = maxSize;
             }
         }
@@ -94,6 +129,9 @@ namespace mongo {
         /* assume ownership of the buffer - you must then free() it */
         void decouple() { data = 0; }
 
+        void appendUChar(unsigned char j) {
+            *((unsigned char*)grow(sizeof(unsigned char))) = j;
+        }
         void appendChar(char j) {
             *((char*)grow(sizeof(char))) = j;
         }
@@ -131,13 +169,15 @@ namespace mongo {
             appendBuf(&s, sizeof(T));
         }
 
-        void appendStr(const StringData &str , bool includeEOO = true ) {
-            const int len = str.size() + ( includeEOO ? 1 : 0 );
+        void appendStr(const StringData &str , bool includeEndingNull = true ) {
+            const int len = str.size() + ( includeEndingNull ? 1 : 0 );
             memcpy(grow(len), str.data(), len);
         }
 
+        /** @return length of current string */
         int len() const { return l; }
         void setlen( int newLen ) { l = newLen; }
+        /** @return size of the buffer */
         int getSize() const { return size; }
 
         /* returns the pre-grow write position */
@@ -160,7 +200,7 @@ namespace mongo {
                 a = l + 16 * 1024;
             if ( a > BufferMaxSize )
                 msgasserted(13548, "BufBuilder grow() > 64MB");
-            data = (char *) realloc(data, a);
+            data = (char *) al.Realloc(data, a);
             size= a;
         }
 
@@ -171,6 +211,21 @@ namespace mongo {
         friend class StringBuilder;
     };
 
+    typedef _BufBuilder<TrivialAllocator> BufBuilder;
+
+    /** The StackBufBuilder builds smaller datasets on the stack instead of using malloc.
+          this can be significantly faster for small bufs.  However, you can not decouple() the 
+          buffer with StackBufBuilder.
+        While designed to be a variable on the stack, if you were to dynamically allocate one, 
+          nothing bad would happen.  In fact in some circumstances this might make sense, say, 
+          embedded in some other object.
+    */
+    class StackBufBuilder : public _BufBuilder<StackAllocator> { 
+    public:
+        StackBufBuilder() : _BufBuilder<StackAllocator>(StackAllocator::SZ) { }
+        void decouple(); // not allowed. not implemented.
+    };
+
 #if defined(_WIN32)
 #pragma warning( push )
 // warning C4996: 'sprintf': This function or variable may be unsafe. Consider using sprintf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS.
@@ -236,6 +291,8 @@ namespace mongo {
         void reset( int maxSize = 0 ) { _buf.reset( maxSize ); }
 
         std::string str() const { return std::string(_buf.data, _buf.l); }
+        
+        int len() const { return _buf.l; }
 
     private:
         BufBuilder _buf;
diff --git a/bson/util/misc.h b/bson/util/misc.h
index b31f36f..33764e3 100644
--- a/bson/util/misc.h
+++ b/bson/util/misc.h
@@ -1,4 +1,4 @@
-/* @file util.h
+/* @file misc.h 
 */
 
 /*
@@ -91,4 +91,23 @@ namespace mongo {
                 return i;
         return -1;
     }
+
+    inline bool isNumber( char c ) {
+        return c >= '0' && c <= '9';
+    }
+
+    inline unsigned stringToNum(const char *str) {
+        unsigned x = 0;
+        const char *p = str;
+        while( 1 ) {
+            if( !isNumber(*p) ) {
+                if( *p == 0 && p != str )
+                    break;
+                throw 0;
+            }
+            x = x * 10 + *p++ - '0';
+        }
+        return x;
+    }
+
 }