Redis GEO 源码注释

Redis 的 GEO 特性主要由 geo.hgeo.c 两个文件实现, 本文对这两个文件进行了详细的注释。

geo.h

#ifndef __GEO_H__
#define __GEO_H__

#include "server.h"

/* Structures used inside geo.c in order to represent points and array of
 * points on the earth. */
// 表示地理位置的结构
typedef struct geoPoint {

    // 经度
    double longitude;

    // 纬度
    double latitude;

    // 这个经纬度与另一个点之间的距离
    double dist;

    // 解码出经纬度的分值
    double score;

    // 分值对应的有序集合成员
    char *member;

} geoPoint;

// 用于储存多个地理位置的数组
typedef struct geoArray {

    // 数组本身
    struct geoPoint *array;

    // 数组可用的项数量
    size_t buckets;

    // 数组目前已用的项数量
    size_t used;

} geoArray;

#endif

geo.c

/*
 * Copyright (c) 2014, Matt Stancliff <matt@genges.com>.
 * Copyright (c) 2015, Salvatore Sanfilippo <antirez@gmail.com>.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "geo.h"
#include "geohash_helper.h"

/* Things exported from t_zset.c only for geo.c, since it is the only other
 * part of Redis that requires close zset introspection. */
unsigned char *zzlFirstInRange(unsigned char *zl, zrangespec *range);
int zslValueLteMax(double value, zrangespec *spec);

/* ====================================================================
 * This file implements the following commands:
 *
 *   - geoadd - add coordinates for value to geoset
 *   - georadius - search radius by coordinates in geoset
 *   - georadiusbymember - search radius based on geoset member position
 * ==================================================================== */

/* ====================================================================
 * geoArray implementation
 * ==================================================================== */

/* Create a new array of geoPoints. */
geoArray *geoArrayCreate(void) {

    geoArray *ga = zmalloc(sizeof(*ga));

    /* It gets allocated on first geoArrayAppend() call. */
    // 这个函数只创建一个空的数组,等到添加第一个项的时候再进行初始化
    ga->array = NULL;
    ga->buckets = 0;
    ga->used = 0;

    return ga;
}

/* Add a new entry and return its pointer so that the caller can populate
 * it with data. */
geoPoint *geoArrayAppend(geoArray *ga) {

    // 在数组空间已经用尽时,对数组进行扩展
    if (ga->used == ga->buckets) {
        // 空数组会分配 8 个项的空间
        // 而已有的数组则会分配目前多一倍空间
        ga->buckets = (ga->buckets == 0) ? 8 : ga->buckets*2;
        ga->array = zrealloc(ga->array,sizeof(geoPoint)*ga->buckets);
    }

    // 移动指针,指向下一个可用项
    geoPoint *gp = ga->array+ga->used;
    ga->used++;

    return gp;
}

/* Destroy a geoArray created with geoArrayCreate(). */
void geoArrayFree(geoArray *ga) {
    size_t i;
    for (i = 0; i < ga->used; i++) sdsfree(ga->array[i].member);
    zfree(ga->array);
    zfree(ga);
}

/* ====================================================================
 * Helpers
 * ==================================================================== */

// 从 bit 参数这个 geohash 里面解码出经度和纬度
// 然后分别将它们储存到 xy[0] 和 xy[1] 里面
int decodeGeohash(double bits, double *xy) {
    GeoHashBits hash = { .bits = (uint64_t)bits, .step = GEO_STEP_MAX };
    return geohashDecodeToLongLatWGS84(hash, xy);
}

/* Input Argument Helper */
/* Take a pointer to the latitude arg then use the next arg for longitude.
 * On parse error C_ERR is returned, otherwise C_OK. */
int extractLongLatOrReply(client *c, robj **argv,
                                        double *xy) {

    // 进行两次循环,第一次循环取出经度,第二次循环取出纬度
    for (int i = 0; i < 2; i++) {

        // 获取 double 格式的经度或者纬度
        if (getDoubleFromObjectOrReply(c, argv[i], xy + i, NULL) !=
            C_OK) {
            return C_ERR;
        }

        // 检查经纬度是否处于合法的范围之内
        if (xy[0] < GEO_LONG_MIN || xy[0] > GEO_LONG_MAX ||
            xy[1] < GEO_LAT_MIN  || xy[1] > GEO_LAT_MAX) {
            addReplySds(c, sdscatprintf(sdsempty(),
                "-ERR invalid longitude,latitude pair %f,%f\r\n",xy[0],xy[1]));
            return C_ERR;
        }
    }

    return C_OK;
}

/* Input Argument Helper */
/* Decode lat/long from a zset member's score.
 * Returns C_OK on successful decoding, otherwise C_ERR is returned. */
int longLatFromMember(robj *zobj, robj *member, double *xy) {
    double score = 0;

    // 从有序集合里面获取指定 member 对应的 score
    if (zsetScore(zobj, member, &score) == C_ERR) return C_ERR;

    // 从这个 score 里面解码出经度和纬度
    if (!decodeGeohash(score, xy)) return C_ERR;

    return C_OK;
}

/* Check that the unit argument matches one of the known units, and returns
 * the conversion factor to meters (you need to divide meters by the conversion
 * factor to convert to the right unit).
 *
 * If the unit is not valid, an error is reported to the client, and a value
 * less than zero is returned. */
// 获取用户指定的单位,并根据单位决定进行单位转换所需的乘法因子
double extractUnitOrReply(client *c, robj *unit) {
    char *u = unit->ptr;

    if (!strcmp(u, "m")) {
        return 1;
    } else if (!strcmp(u, "km")) {
        return 1000;
    } else if (!strcmp(u, "ft")) {
        return 0.3048;
    } else if (!strcmp(u, "mi")) {
        return 1609.34;
    } else {
        addReplyError(c,
            "unsupported unit provided. please use m, km, ft, mi");
        return -1;
    }
}

/* Input Argument Helper.
 * Extract the dinstance from the specified two arguments starting at 'argv'
 * that shouldbe in the form: <number> <unit> and return the dinstance in the
 * specified unit on success. *conversino is populated with the coefficient
 * to use in order to convert meters to the unit.
 *
 * On error a value less than zero is returned. */
// 从输入里面获取用户指定的范围值以及范围值的单位
double extractDistanceOrReply(client *c, robj **argv,
                                     double *conversion) {
    
    // 取出范围值
    double distance;
    if (getDoubleFromObjectOrReply(c, argv[0], &distance,
                                   "need numeric radius") != C_OK) {
        return -1;
    }

    // 取出单位
    double to_meters = extractUnitOrReply(c,argv[1]);
    if (to_meters < 0) return -1;

    // 单位默认为米,根据用户给定的单位对范围值进行转换
    if (conversion) *conversion = to_meters;
    return distance * to_meters;
}

/* The defailt addReplyDouble has too much accuracy.  We use this
 * for returning location distances. "5.2145 meters away" is nicer
 * than "5.2144992818115 meters away." We provide 4 digits after the dot
 * so that the returned value is decently accurate even when the unit is
 * the kilometer. */
// 向用户返回距离
void addReplyDoubleDistance(client *c, double d) {
    char dbuf[128];
    int dlen = snprintf(dbuf, sizeof(dbuf), "%.4f", d);
    addReplyBulkCBuffer(c, dbuf, dlen);
}

/* Helper function for geoGetPointsInRange(): given a sorted set score
 * representing a point, and another point (the center of our search) and
 * a radius, appends this entry as a geoPoint into the specified geoArray
 * only if the point is within the search area.
 *
 * returns C_OK if the point is included, or REIDS_ERR if it is outside. */
// 从给定的有序集合 score 中解码出一个经纬度
// 如果这个经纬度处于用户通过经纬度 lon 、lat 以及范围 radius 指定的范围之内
// 那么将这个经纬度、解码出经纬度的分值、分值对应的元素记录到 geoPoint 结构里面
// 然后将这个结构追加到数组的末尾
int geoAppendIfWithinRadius(geoArray *ga, double lon, double lat, double radius, double score, sds member) {
    double distance, xy[2];

    // 根据分值解码出经纬度
    if (!decodeGeohash(score,xy)) return C_ERR; /* Can't decode. */

    /* Note that geohashGetDistanceIfInRadiusWGS84() takes arguments in
     * reverse order: longitude first, latitude later. */
    // 如果 xy[2] 记录的经纬度处于 lon 、lat 以及 radius 所指定的范围之内
    // 那么将距离记录到 distance 里面
    if (!geohashGetDistanceIfInRadiusWGS84(lon,lat, xy[0], xy[1],
                                           radius, &distance))
    {
        return C_ERR;
    }

    /* Append the new element. */
    // 将处于范围内的经纬度信息记录到 geoPoint 结构
    // 并将结构追加到数组的末尾
    geoPoint *gp = geoArrayAppend(ga);
    gp->longitude = xy[0];
    gp->latitude = xy[1];
    gp->dist = distance;
    gp->member = member;
    gp->score = score;

    return C_OK;
}

/* Query a Redis sorted set to extract all the elements between 'min' and
 * 'max', appending them into the array of geoPoint structures 'gparray'.
 * The command returns the number of elements added to the array.
 *
 * 对有序集合进行查询,获取所有分值介于 min 和 max 之间的元素,
 * 并将它们追加到由 geoPoint 结构组成的 gparray 数组里面。
 * 这个函数返回数组的长度作为返回值。
 *
 * Elements which are farest than 'radius' from the specified 'x' and 'y'
 * coordinates are not included.
 *
 * 超出指定范围的元素不会被加入到数据里面,
 * 范围由坐标 x 和 y 指定。
 *
 * The ability of this function to append to an existing set of points is
 * important for good performances because querying by radius is performed
 * using multiple queries to the sorted set, that we later need to sort
 * via qsort. Similarly we need to be able to reject points outside the search
 * radius area ASAP in order to allocate and process more points than needed. 
 *
 * 为了提供良好的性能,这个函数提供了将坐标点添加到已有的坐标集合的功能,
 * 这对于需要对有序集合进行多次查询并在之后对其进行排序的这个操作来说是非常重要的。
 * 基于同样原因,这个函数会尽快地排除处于指定范围之外的元素,
 * 从而尽可能地为处理和分配坐标点提供条件。
 */
int geoGetPointsInRange(robj *zobj, double min, double max, double lon, double lat, double radius, geoArray *ga) {
    /* minex 0 = include min in range; maxex 1 = exclude max in range */
    /* That's: min <= val < max */
    zrangespec range = { .min = min, .max = max, .minex = 0, .maxex = 1 };
    // 记录此处查询之间,ga 数组已有的项数量
    size_t origincount = ga->used;
    sds member;

    // 在 ziplist 编码的有序集合里面进行查找
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *zl = zobj->ptr;
        unsigned char *eptr, *sptr;
        unsigned char *vstr = NULL;
        unsigned int vlen = 0;
        long long vlong = 0;
        double score = 0;

        if ((eptr = zzlFirstInRange(zl, &range)) == NULL) {
            /* Nothing exists starting at our min.  No results. */
            return 0;
        }

        // 指向分值处于范围之内的第一个元素
        sptr = ziplistNext(zl, eptr);

        // 遍历 ziplist ,查找所有分值位于范围之内的元素
        while (eptr) {

            // 取出分值
            score = zzlGetScore(sptr);

            /* If we fell out of range, break. */
            // 如果分值不再范围之内,那么跳出
            if (!zslValueLteMax(score, &range))
                break;

            /* We know the element exists. ziplistGet should always succeed */
            ziplistGet(eptr, &vstr, &vlen, &vlong);
            member = (vstr == NULL) ? sdsfromlonglong(vlong) :
                                      sdsnewlen(vstr,vlen);
            
            // 如果坐标位于范围之内,那么将它追加到数组 ga 的末尾
            if (geoAppendIfWithinRadius(ga,lon,lat,radius,score,member)
                == C_ERR) sdsfree(member);

            // 移动指针,准备继续遍历下个元素
            zzlNext(zl, &eptr, &sptr);
        }

    // 在跳跃表编码的有序集合里面进行查找
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        zskiplist *zsl = zs->zsl;
        zskiplistNode *ln;

        // 指向第一个位于范围之内的元素
        if ((ln = zslFirstInRange(zsl, &range)) == NULL) {
            /* Nothing exists starting at our min.  No results. */
            return 0;
        }

        while (ln) {
            robj *o = ln->obj;
            /* Abort when the node is no longer in range. */
            if (!zslValueLteMax(ln->score, &range))
                break;

            member = (o->encoding == OBJ_ENCODING_INT) ?
                        sdsfromlonglong((long)o->ptr) :
                        sdsdup(o->ptr);

            // 如果坐标位于范围之内,那么将它追加到数组 ga 的末尾
            if (geoAppendIfWithinRadius(ga,lon,lat,radius,ln->score,member)
                == C_ERR) sdsfree(member);

            // 移动指针,准备继续遍历下个元素
            ln = ln->level[0].forward;
        }
    }

    // 计算本次查询新添加的 ga 数组项数量,也即是本次查询到的位于范围之内的坐标数量
    return ga->used - origincount;
}

/* Compute the sorted set scores min (inclusive), max (exclusive) we should
 * query in order to retrieve all the elements inside the specified area
 * 'hash'. The two scores are returned by reference in *min and *max. */
// 计算出从有序集合里面查找指定范围内的所有位置所需的 min 值和 max 值。
void scoresOfGeoHashBox(GeoHashBits hash, GeoHashFix52Bits *min, GeoHashFix52Bits *max) {
    /* We want to compute the sorted set scores that will include all the
     * elements inside the specified Geohash 'hash', which has as many
     * bits as specified by hash.step * 2.
     *
     * So if step is, for example, 3, and the hash value in binary
     * is 101010, since our score is 52 bits we want every element which
     * is in binary: 101010?????????????????????????????????????????????
     * Where ? can be 0 or 1.
     *
     * To get the min score we just use the initial hash value left
     * shifted enough to get the 52 bit value. Later we increment the
     * 6 bit prefis (see the hash.bits++ statement), and get the new
     * prefix: 101011, which we align again to 52 bits to get the maximum
     * value (which is excluded from the search). So we get everything
     * between the two following scores (represented in binary):
     *
     * 1010100000000000000000000000000000000000000000000000 (included)
     * and
     * 1010110000000000000000000000000000000000000000000000 (excluded).
     */
    *min = geohashAlign52Bits(hash);
    hash.bits++;
    *max = geohashAlign52Bits(hash);
}

/* Obtain all members between the min/max of this geohash bounding box.
 * Populate a geoArray of GeoPoints by calling geoGetPointsInRange().
 * Return the number of points added to the array. */
int membersOfGeoHashBox(robj *zobj, GeoHashBits hash, geoArray *ga, double lon, double lat, double radius) {
    GeoHashFix52Bits min, max;

    // 计算出查找 hash 所指定范围内的所有位置所需的 min 值和 max 值
    scoresOfGeoHashBox(hash,&min,&max);

    // 根据 min 值和 max 值,在有序集合里面查找范围之内的元素
    return geoGetPointsInRange(zobj, min, max, lon, lat, radius, ga);
}

/* Search all eight neighbors + self geohash box */
int membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double lon, double lat, double radius, geoArray *ga) {
    GeoHashBits neighbors[9];
    unsigned int i, count = 0;

    // 中心点自身
    neighbors[0] = n.hash;
    // 中心点周围八个方向
    neighbors[1] = n.neighbors.north;
    neighbors[2] = n.neighbors.south;
    neighbors[3] = n.neighbors.east;
    neighbors[4] = n.neighbors.west;
    neighbors[5] = n.neighbors.north_east;
    neighbors[6] = n.neighbors.north_west;
    neighbors[7] = n.neighbors.south_east;
    neighbors[8] = n.neighbors.south_west;

    /* For each neighbor (*and* our own hashbox), get all the matching
     * members and add them to the potential result list. */
    // 遍历各个中心和各个方向,查找范围内的所有位置
    for (i = 0; i < sizeof(neighbors) / sizeof(*neighbors); i++) {

        // 跳过空位置
        if (HASHISZERO(neighbors[i]))
            continue;

        // 查找范围内的元素,并统计匹配元素的数量
        count += membersOfGeoHashBox(zobj, neighbors[i], ga, lon, lat, radius);
    }

    return count;
}

/* Sort comparators for qsort() */
static int sort_gp_asc(const void *a, const void *b) {
    const struct geoPoint *gpa = a, *gpb = b;
    /* We can't do adist - bdist because they are doubles and
     * the comparator returns an int. */
    if (gpa->dist > gpb->dist)
        return 1;
    else if (gpa->dist == gpb->dist)
        return 0;
    else
        return -1;
}

static int sort_gp_desc(const void *a, const void *b) {
    return -sort_gp_asc(a, b);
}

/* ====================================================================
 * Commands
 * ==================================================================== */

/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {

    // 参数合法性检查
    /* Check arguments number for sanity. */
    if ((c->argc - 2) % 3 != 0) {
        /* Need an odd number of arguments if we got this far... */
        addReplyError(c, "syntax error. Try GEOADD key [x1] [y1] [name1] "
                         "[x2] [y2] [name2] ... ");
        return;
    }

    // 提取用户输入的参数
    int elements = (c->argc - 2) / 3;
    int argc = 2+elements*2; /* ZADD key score ele ... */
    robj **argv = zcalloc(argc*sizeof(robj*));
    argv[0] = createRawStringObject("zadd",4);
    argv[1] = c->argv[1]; /* key */
    incrRefCount(argv[1]);

    /* Create the argument vector to call ZADD in order to add all
     * the score,value pairs to the requested zset, where score is actually
     * an encoded version of lat,long. */
    // 遍历用户输入,创建出有序集合元素
    int i;
    for (i = 0; i < elements; i++) {
        double xy[2];

        // 提取用户输入的经度和纬度
        if (extractLongLatOrReply(c, (c->argv+2)+(i*3),xy) == C_ERR) {
            for (i = 0; i < argc; i++)
                if (argv[i]) decrRefCount(argv[i]);
            zfree(argv);
            return;
        }

        /* Turn the coordinates into the score of the element. */
        // 根据坐标计算出 geohash 值
        GeoHashBits hash;
        geohashEncodeWGS84(xy[0], xy[1], GEO_STEP_MAX, &hash);
        // 将 geohash 值放到 52 个位上面
        GeoHashFix52Bits bits = geohashAlign52Bits(hash);
        // 将 52 位 geohash 作为分值记录到元素里面
        robj *score = createObject(OBJ_STRING, sdsfromlonglong(bits));
        robj *val = c->argv[2 + i * 3 + 2];
        // 设置有序集合元素的分值和名字
        argv[2+i*2] = score;
        argv[3+i*2] = val;
        incrRefCount(val);
    }

    /* Finally call ZADD that will do the work for us. */
    replaceClientCommandVector(c,argc,argv);
    
    // 将刚才创建的元素全部添加到有序集合里面
    zaddCommand(c);
}

// 指定范围查找时的排序方式
#define SORT_NONE 0
#define SORT_ASC 1
#define SORT_DESC 2

// 指定范围查找的类型
#define RADIUS_COORDS 1
#define RADIUS_MEMBER 2

/* GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC|DESC]
 *                               [COUNT count]
 * GEORADIUSBYMEMBER key member radius unit ... options ... */
void georadiusGeneric(client *c, int type) {
    robj *key = c->argv[1];

    /* Look up the requested zset */
    // 获取储存位置的有序集合
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, key, shared.emptymultibulk)) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }

    /* Find long/lat to use for radius search based on inquiry type */
    // 提取定义中心点的经纬度
    int base_args;
    double xy[2] = { 0 };
    if (type == RADIUS_COORDS) {
        // 使用用户输入的经纬度作为中心点
        base_args = 6;
        if (extractLongLatOrReply(c, c->argv + 2, xy) == C_ERR)
            return;
    } else if (type == RADIUS_MEMBER) {
        // 使用有序集合储存的经纬度作为中心点
        base_args = 5;
        robj *member = c->argv[2];
        if (longLatFromMember(zobj, member, xy) == C_ERR) {
            addReplyError(c, "could not decode requested zset member");
            return;
        }
    } else {
        addReplyError(c, "unknown georadius search type");
        return;
    }

    /* Extract radius and units from arguments */
    // 从参数中提取范围
    double radius_meters = 0, conversion = 1;
    if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2,
                                                &conversion)) < 0) {
        return;
    }

    /* Discover and populate all optional parameters. */
    // 提取所有可选参数
    int withdist = 0, withhash = 0, withcoords = 0;
    int sort = SORT_NONE;
    long long count = 0;
    if (c->argc > base_args) {
        int remaining = c->argc - base_args;
        for (int i = 0; i < remaining; i++) {
            char *arg = c->argv[base_args + i]->ptr;
            if (!strcasecmp(arg, "withdist")) {
                withdist = 1;
            } else if (!strcasecmp(arg, "withhash")) {
                withhash = 1;
            } else if (!strcasecmp(arg, "withcoord")) {
                withcoords = 1;
            } else if (!strcasecmp(arg, "asc")) {
                sort = SORT_ASC;
            } else if (!strcasecmp(arg, "desc")) {
                sort = SORT_DESC;
            } else if (!strcasecmp(arg, "count") && remaining > 0) {
                if (getLongLongFromObjectOrReply(c, c->argv[base_args+i+1],
                    &count, NULL) != C_OK) return;
                if (count <= 0) {
                    addReplyError(c,"COUNT must be > 0");
                    return;
                }
                i++;
            } else {
                addReply(c, shared.syntaxerr);
                return;
            }
        }
    }

    /* COUNT without ordering does not make much sense, force ASC
     * ordering if COUNT was specified but no sorting was requested. */
    // 指定排序方式
    if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;

    /* Get all neighbor geohash boxes for our radius search */
    // 定位中心点所处的范围
    GeoHashRadius georadius =
        geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);

    /* Search the zset for all matching points */
    geoArray *ga = geoArrayCreate();
    // 对中心点以及它的八个方向进行查找,找出所有范围内的元素
    membersOfAllNeighbors(zobj, georadius, xy[0], xy[1], radius_meters, ga);

    /* If no matching results, the user gets an empty reply. */
    // 没有匹配的位置,返回空列表
    if (ga->used == 0) {
        addReply(c, shared.emptymultibulk);
        geoArrayFree(ga);
        return;
    }

    // 有匹配的位置,继续执行以下动作……

    long result_length = ga->used;
    long option_length = 0;

    /* Our options are self-contained nested multibulk replies, so we
     * only need to track how many of those nested replies we return. */
    // 根据用户给定的可选项,计算数组中的每个子数组需要包含多少个项
    if (withdist)
        option_length++;

    if (withcoords)
        option_length++;

    if (withhash)
        option_length++;

    /* The multibulk len we send is exactly result_length. The result is either
     * all strings of just zset members  *or* a nested multi-bulk reply
     * containing the zset member string _and_ all the additional options the
     * user enabled for this request. */
    addReplyMultiBulkLen(c, (count == 0 || result_length < count) ?
                            result_length : count);

    /* Process [optional] requested sorting */
    // 对结果进行排序
    if (sort == SORT_ASC) {
        qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_asc);
    } else if (sort == SORT_DESC) {
        qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_desc);
    }

    /* Finally send results back to the caller */
    // 发送回复
    int i;
    for (i = 0; i < result_length; i++) {
        geoPoint *gp = ga->array+i;
        gp->dist /= conversion; /* Fix according to unit. */

        /* If we have options in option_length, return each sub-result
         * as a nested multi-bulk.  Add 1 to account for result value itself. */
        if (option_length)
            addReplyMultiBulkLen(c, option_length + 1);

        addReplyBulkSds(c,gp->member);
        gp->member = NULL;

        if (withdist)
            addReplyDoubleDistance(c, gp->dist);

        if (withhash)
            addReplyLongLong(c, gp->score);

        if (withcoords) {
            addReplyMultiBulkLen(c, 2);
            addReplyDouble(c, gp->longitude);
            addReplyDouble(c, gp->latitude);
        }

        /* Stop if COUNT was specified and we already provided the
         * specified number of elements. */
        if (count != 0 && count == i+1) break;
    }
    geoArrayFree(ga);
}

/* GEORADIUS wrapper function. */
void georadiusCommand(client *c) {
    georadiusGeneric(c, RADIUS_COORDS);
}

/* GEORADIUSBYMEMBER wrapper function. */
void georadiusByMemberCommand(client *c) {
    georadiusGeneric(c, RADIUS_MEMBER);
}

/* GEOHASH key ele1 ele2 ... eleN
 *
 * Returns an array with an 11 characters geohash representation of the
 * position of the specified elements. */
void geohashCommand(client *c) {
    char *geoalphabet= "0123456789bcdefghjkmnpqrstuvwxyz";
    int j;

    /* Look up the requested zset */
    // 获取储存位置的有序集合
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, c->argv[1], shared.emptymultibulk))
        == NULL || checkType(c, zobj, OBJ_ZSET)) return;

    /* Geohash elements one after the other, using a null bulk reply for
     * missing elements. */
    addReplyMultiBulkLen(c,c->argc-2);
    for (j = 2; j < c->argc; j++) {
        double score;
        if (zsetScore(zobj, c->argv[j], &score) == C_ERR) {
            // 位置不存在,直接返回空值
            addReply(c,shared.nullbulk);
        } else {
            /* The internal format we use for geocoding is a bit different
             * than the standard, since we use as initial latitude range
             * -85,85, while the normal geohashing algorithm uses -90,90.
             * So we have to decode our position and re-encode using the
             * standard ranges in order to output a valid geohash string. */

            /* Decode... */
            // 根据分值,解码出经度和纬度
            double xy[2];
            if (!decodeGeohash(score,xy)) {
                addReply(c,shared.nullbulk);
                continue;
            }

            /* Re-encode */
            // 重新编码出标准的 geohash
            GeoHashRange r[2];
            GeoHashBits hash;
            r[0].min = -180;
            r[0].max = 180;
            r[1].min = -90;
            r[1].max = 90;
            geohashEncode(&r[0],&r[1],xy[0],xy[1],26,&hash);

            char buf[12];
            int i;
            for (i = 0; i < 11; i++) {
                int idx = (hash.bits >> (52-((i+1)*5))) & 0x1f;
                buf[i] = geoalphabet[idx];
            }
            buf[11] = '\0';

            // 发送回复
            addReplyBulkCBuffer(c,buf,11);
        }
    }
}

/* GEOPOS key ele1 ele2 ... eleN
 *
 * Returns an array of two-items arrays representing the x,y position of each
 * element specified in the arguments. For missing elements NULL is returned. */
void geoposCommand(client *c) {
    int j;

    /* Look up the requested zset */
    // 获取位置集合对应的有序集合
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, c->argv[1], shared.emptymultibulk))
        == NULL || checkType(c, zobj, OBJ_ZSET)) return;

    /* Report elements one after the other, using a null bulk reply for
     * missing elements. */
    // 遍历所有输入的位置
    addReplyMultiBulkLen(c,c->argc-2);
    for (j = 2; j < c->argc; j++) {
        double score;
        if (zsetScore(zobj, c->argv[j], &score) == C_ERR) {
            // 元素没有分值(位置不存在),返回空值
            addReply(c,shared.nullmultibulk);
        } else {
            // 位置存在,根据它的分值解码出经纬度
            /* Decode... */
            double xy[2];
            if (!decodeGeohash(score,xy)) {
                addReply(c,shared.nullmultibulk);
                continue;
            }
            // 返回位置的经度和纬度
            addReplyMultiBulkLen(c,2);
            addReplyDouble(c,xy[0]);
            addReplyDouble(c,xy[1]);
        }
    }
}

/* GEODIST key ele1 ele2 [unit]
 *
 * Return the distance, in meters by default, otherwise accordig to "unit",
 * between points ele1 and ele2. If one or more elements are missing NULL
 * is returned. */
void geodistCommand(client *c) {
    double to_meter = 1;

    /* Check if there is the unit to extract, otherwise assume meters. */
    // 获取用户指定的单位
    if (c->argc == 5) {
        to_meter = extractUnitOrReply(c,c->argv[4]);
        if (to_meter < 0) return;
    } else if (c->argc > 5) {
        addReply(c,shared.syntaxerr);
        return;
    }

    /* Look up the requested zset */
    // 获取位置集合对应的有序集合
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, c->argv[1], shared.emptybulk))
        == NULL || checkType(c, zobj, OBJ_ZSET)) return;

    /* Get the scores. We need both otherwise NULL is returned. */
    // 获取两个坐标对应的分值,并在任意一个坐标不存在时返回空值
    double score1, score2, xyxy[4];
    if (zsetScore(zobj, c->argv[2], &score1) == C_ERR ||
        zsetScore(zobj, c->argv[3], &score2) == C_ERR)
    {
        addReply(c,shared.nullbulk);
        return;
    }

    /* Decode & compute the distance. */
    // 对两个分值进行解码,得出坐标
    if (!decodeGeohash(score1,xyxy) || !decodeGeohash(score2,xyxy+2))
        addReply(c,shared.nullbulk);
    else
        // 计算距离,并根据单位进行转换
        addReplyDouble(c,
            geohashGetDistance(xyxy[0],xyxy[1],xyxy[2],xyxy[3]) / to_meter);
}
黄健宏
2015.8.9