diff options
Diffstat (limited to 'src/mongo/db/geo/hash.cpp')
| -rw-r--r-- | src/mongo/db/geo/hash.cpp | 105 |
1 files changed, 88 insertions, 17 deletions
diff --git a/src/mongo/db/geo/hash.cpp b/src/mongo/db/geo/hash.cpp index 5f922ba4c73..5715c2b5eca 100644 --- a/src/mongo/db/geo/hash.cpp +++ b/src/mongo/db/geo/hash.cpp @@ -26,7 +26,7 @@ * it in the license file. */ -#include "mongo/pch.h" +#include "mongo/db/field_parser.h" #include "mongo/db/jsobj.h" #include "mongo/db/geo/core.h" #include "mongo/db/geo/hash.h" @@ -59,9 +59,13 @@ namespace mongo { hashedToNormal[fixed] = i; } + // Generate all 32 + 1 all-on bit patterns by repeatedly shifting the next bit to the + // correct position + long long currAllX = 0, currAllY = 0; - for (int i = 0; i < 64; i++){ - long long thisBit = 1LL << (63 - i); + for (int i = 0; i < 64 + 2; i++){ + + long long thisBit = 1LL << (63 >= i ? 63 - i : 0); if (i % 2 == 0) { allX[i / 2] = currAllX; @@ -79,12 +83,13 @@ namespace mongo { // allX[1] = 8000000000000000 // allX[2] = a000000000000000 // allX[3] = a800000000000000 - long long allX[32]; + // Note that 32 + 1 entries are needed, since 0 and 32 are both valid numbers of bits. + long long allX[33]; // Same alternating bits but starting with one from the MSB: // allY[1] = 4000000000000000 // allY[2] = 5000000000000000 // allY[3] = 5400000000000000 - long long allY[32]; + long long allY[33]; unsigned hashedToNormal[256]; }; @@ -105,6 +110,13 @@ namespace mongo { return 1LL << (63 - i); } + // Binary data is stored in some particular byte ordering that requires this. + static void copyAndReverse(char *dst, const char *src) { + for (unsigned a = 0; a < 8; a++) { + dst[a] = src[7 - a]; + } + } + // Definition unsigned int const GeoHash::kMaxBits = 32; @@ -139,7 +151,7 @@ namespace mongo { _bits = bits; if (e.type() == BinData) { int len = 0; - _copyAndReverse((char*)&_hash, e.binData(len)); + copyAndReverse((char*)&_hash, e.binData(len)); verify(len == 8); } else { cout << "GeoHash bad element: " << e << endl; @@ -258,7 +270,7 @@ namespace mongo { // TODO(hk): Comment this. BSONObj GeoHash::wrap(const char* name) const { BSONObjBuilder b(20); - appendToBuilder(&b, name); + appendHashMin(&b, name); BSONObj o = b.obj(); if ('\0' == name[0]) verify(o.objsize() == 20); return o; @@ -365,7 +377,12 @@ namespace mongo { } bool GeoHash::operator<(const GeoHash& h) const { - if (_hash != h._hash) return _hash < h._hash; + + if (_hash != h._hash) { + return static_cast<unsigned long long>(_hash) < + static_cast<unsigned long long>(h._hash); + } + return _bits < h._bits; } @@ -410,11 +427,25 @@ namespace mongo { _hash &= mask; } - // Append the hash to the builder provided. - void GeoHash::appendToBuilder(BSONObjBuilder* b, const char * name) const { + static void appendHashToBuilder(long long hash, + BSONObjBuilder* builder, + const char* fieldName) { char buf[8]; - _copyAndReverse(buf, (char*)&_hash); - b->appendBinData(name, 8, bdtCustom, buf); + copyAndReverse(buf, (char*) &hash); + builder->appendBinData(fieldName, 8, bdtCustom, buf); + } + + void GeoHash::appendHashMin(BSONObjBuilder* builder, const char* fieldName) const { + // The min bound of a GeoHash region has all the unused suffix bits set to 0 + appendHashToBuilder(_hash, builder, fieldName); + } + + void GeoHash::appendHashMax(BSONObjBuilder* builder, const char* fieldName) const { + // The max bound of a GeoHash region has all the unused suffix bits set to 1 + long long suffixMax = ~(geoBitSets.allX[_bits] | geoBitSets.allY[_bits]); + long long hashMax = _hash | suffixMax; + + appendHashToBuilder(hashMax, builder, fieldName); } long long GeoHash::getHash() const { @@ -464,14 +495,54 @@ namespace mongo { return GeoHash(_hash, _bits - 1); } - // Binary data is stored in some particular byte ordering that requires this. - void GeoHash::_copyAndReverse(char *dst, const char *src) { - for (unsigned a = 0; a < 8; a++) { - dst[a] = src[7 - a]; + static BSONField<int> bitsField("bits", 26); + static BSONField<double> maxField("max", 180.0); + static BSONField<double> minField("min", -180.0); + + Status GeoHashConverter::parseParameters(const BSONObj& paramDoc, + GeoHashConverter::Parameters* params) { + + string errMsg; + + if (FieldParser::FIELD_INVALID + == FieldParser::extractNumber(paramDoc, bitsField, ¶ms->bits, &errMsg)) { + return Status(ErrorCodes::InvalidOptions, errMsg); + } + + if (FieldParser::FIELD_INVALID + == FieldParser::extractNumber(paramDoc, maxField, ¶ms->max, &errMsg)) { + return Status(ErrorCodes::InvalidOptions, errMsg); + } + + if (FieldParser::FIELD_INVALID + == FieldParser::extractNumber(paramDoc, minField, ¶ms->min, &errMsg)) { + return Status(ErrorCodes::InvalidOptions, errMsg); } + + if (params->bits < 1 || params->bits > 32) { + return Status(ErrorCodes::InvalidOptions, + str::stream() << "bits for hash must be > 0 and <= 32, " + << "but " << params->bits << " bits were specified"); + } + + if (params->min >= params->max) { + return Status(ErrorCodes::InvalidOptions, + str::stream() << "region for hash must be valid and have positive area, " + << "but [" << params->min << ", " << params->max << "]" + << "was specified"); + } + + double numBuckets = (1024 * 1024 * 1024 * 4.0); + params->scaling = numBuckets / (params->max - params->min); + + return Status::OK(); + } + + GeoHashConverter::GeoHashConverter(const Parameters& params) : _params(params) { + init(); } - GeoHashConverter::GeoHashConverter(const Parameters ¶ms) : _params(params) { + void GeoHashConverter::init() { // TODO(hk): What do we require of the values in params? // Compute how much error there is so it can be used as a fudge factor. |