Redis高效檢索地理位置的原理解析

static void geohash_move_x(GeoHashBits *hash, int8_t d) {
    if (d == 0)
        return;

    uint64_t x = hash->bits  0xaaaaaaaaaaaaaaaaULL;
    uint64_t y = hash->bits  0x5555555555555555ULL;

    uint64_t zz = 0x5555555555555555ULL >> (64 - hash->step * 2);

    if (d > 0) {
        x = x + (zz + 1);
    } else {
        x = x | zz;
        x = x - (zz + 1);
    }

    x = (0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2));
    hash->bits = (x | y);
}

static void geohash_move_y(GeoHashBits *hash, int8_t d) {
    if (d == 0)
        return;

    uint64_t x = hash->bits  0xaaaaaaaaaaaaaaaaULL;
    uint64_t y = hash->bits  0x5555555555555555ULL;

    uint64_t zz = 0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2);
    if (d > 0) {
        y = y + (zz + 1);
    } else {
        y = y | zz;
        y = y - (zz + 1);
    }
    y = (0x5555555555555555ULL >> (64 - hash->step * 2));
    hash->bits = (x | y);
}

/* GEOADD key [CH] [NX|XX] long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
    int xx = 0, nx = 0, longidx = 2;
    int i;

    /* 解析可選參數(shù) */
    while (longidx  c->argc) {
        char *opt = c->argv[longidx]->ptr;
        if (!strcasecmp(opt,"nx")) nx = 1;
        else if (!strcasecmp(opt,"xx")) xx = 1;
        else if (!strcasecmp(opt,"ch")) {}
        else break;
        longidx++;
    }

    if ((c->argc - longidx) % 3 || (xx  nx)) {
        /* 解析所有的經(jīng)緯度值和member，并對其個數(shù)做校驗 */
            addReplyErrorObject(c,shared.syntaxerr);
        return;
    }

    /* 構建zadd的參數(shù)數(shù)組 */
    int elements = (c->argc - longidx) / 3;
    int argc = longidx+elements*2; /* ZADD key [CH] [NX|XX] score ele ... */
    robj **argv = zcalloc(argc*sizeof(robj*));
    argv[0] = createRawStringObject("zadd",4);
    for (i = 1; i  longidx; i++) {
        argv[i] = c->argv[i];
        incrRefCount(argv[i]);
    }

    /* 以3個參數(shù)為一組，將所有的經(jīng)緯度和member信息從參數(shù)列表里解析出來，并放到zadd的參數(shù)數(shù)組中 */
    for (i = 0; i  elements; i++) {
        double xy[2];

        if (extractLongLatOrReply(c, (c->argv+longidx)+(i*3),xy) == C_ERR) {
            for (i = 0; i  argc; i++)
                if (argv[i]) decrRefCount(argv[i]);
            zfree(argv);
            return;
        }

        /* 將經(jīng)緯度坐標轉(zhuǎn)化成score信息 */
        GeoHashBits hash;
        geohashEncodeWGS84(xy[0], xy[1], GEO_STEP_MAX, hash);
        GeoHashFix52Bits bits = geohashAlign52Bits(hash);
        robj *score = createObject(OBJ_STRING, sdsfromlonglong(bits));
        robj *val = c->argv[longidx + i * 3 + 2];
        argv[longidx+i*2] = score;
        argv[longidx+1+i*2] = val;
        incrRefCount(val);
    }

    /* 轉(zhuǎn)化成zadd命令所需要的參數(shù)格式*/
    replaceClientCommandVector(c,argc,argv);
    zaddCommand(c);
}

void georadiusGeneric(client *c, int srcKeyIndex, int flags) {
    robj *storekey = NULL;
    int storedist = 0; /* 0 for STORE, 1 for STOREDIST. */

    /* 根據(jù)key找找到對應的zojb */
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, c->argv[srcKeyIndex], shared.emptyarray)) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }

    /* 解析請求中的經(jīng)緯度值 */
    int base_args;
    GeoShape shape = {0};
    if (flags  RADIUS_COORDS) {
    /*
     * 各種必選參數(shù)的解析，省略細節(jié)代碼，主要是解析坐標點信息和半徑   
     */ 
    }

    /* 解析所有的可選參數(shù). */
    int withdist = 0, withhash = 0, withcoords = 0;
    int frommember = 0, fromloc = 0, byradius = 0, bybox = 0;
    int sort = SORT_NONE;
    int any = 0; /* any=1 means a limited search, stop as soon as enough results were found. */
    long long count = 0;  /* Max number of results to return. 0 means unlimited. */
    if (c->argc > base_args) {
    /*
     * 各種可選參數(shù)的解析，省略細節(jié)代碼   
     */ 
    }
    
    /* Get all neighbor geohash boxes for our radius search
     * 獲取到要查找范圍內(nèi)所有的9個geo鄰域 */
    GeoHashRadius georadius = geohashCalculateAreasByShapeWGS84(shape);

    /* 創(chuàng)建geoArray存儲結果列表 */
    geoArray *ga = geoArrayCreate();
    /* 掃描9個區(qū)域中是否有滿足條的點，有就放到geoArray中 */
    membersOfAllNeighbors(zobj, georadius, shape, ga, any ? count : 0);

    /* 如果沒有匹配結果，返回空對象 */
    if (ga->used == 0  storekey == NULL) {
        addReply(c,shared.emptyarray);
        geoArrayFree(ga);
        return;
    }

    long result_length = ga->used;
    long returned_items = (count == 0 || result_length  count) ?
                          result_length : count;
    long option_length = 0;

    /* 
     * 后續(xù)一些參數(shù)邏輯，比如處理排序，存儲……
     */
    // 釋放geoArray占用的空間 
    geoArrayFree(ga);
}