diff options
| -rw-r--r-- | deps/geohash-int/geohash.c | 4 | ||||
| -rw-r--r-- | src/Makefile | 2 | ||||
| -rw-r--r-- | src/geo.c | 306 | ||||
| -rw-r--r-- | src/geo.h | 15 | ||||
| -rw-r--r-- | src/redis.h | 4 | ||||
| -rw-r--r-- | src/zset.c | 161 | ||||
| -rw-r--r-- | src/zset.h | 29 |
7 files changed, 190 insertions, 331 deletions
diff --git a/deps/geohash-int/geohash.c b/deps/geohash-int/geohash.c index e57434efd..66cff082c 100644 --- a/deps/geohash-int/geohash.c +++ b/deps/geohash-int/geohash.c @@ -183,10 +183,6 @@ int geohashDecodeToLatLongWGS84(const GeoHashBits hash, double *latlong) { return geohashDecodeToLatLongType(hash, latlong); } -int geohashDecodeToLatLongMercator(const GeoHashBits hash, double *latlong) { - return geohashDecodeToLatLongType(hash, latlong); -} - static void geohash_move_x(GeoHashBits *hash, int8_t d) { if (d == 0) return; diff --git a/src/Makefile b/src/Makefile index d61f8010f..650d438f7 100644 --- a/src/Makefile +++ b/src/Makefile @@ -117,7 +117,7 @@ endif REDIS_SERVER_NAME=redis-server REDIS_SENTINEL_NAME=redis-sentinel -REDIS_SERVER_OBJ=adlist.o quicklist.o ae.o anet.o dict.o redis.o sds.o zmalloc.o lzf_c.o lzf_d.o pqsort.o zipmap.o sha1.o ziplist.o release.o networking.o util.o object.o db.o replication.o rdb.o t_string.o t_list.o t_set.o t_zset.o t_hash.o config.o aof.o pubsub.o multi.o debug.o sort.o intset.o syncio.o cluster.o crc16.o endianconv.o slowlog.o scripting.o bio.o rio.o rand.o memtest.o crc64.o bitops.o sentinel.o notify.o setproctitle.o blocked.o hyperloglog.o latency.o sparkline.o redis-check-rdb.o geo.o zset.o +REDIS_SERVER_OBJ=adlist.o quicklist.o ae.o anet.o dict.o redis.o sds.o zmalloc.o lzf_c.o lzf_d.o pqsort.o zipmap.o sha1.o ziplist.o release.o networking.o util.o object.o db.o replication.o rdb.o t_string.o t_list.o t_set.o t_zset.o t_hash.o config.o aof.o pubsub.o multi.o debug.o sort.o intset.o syncio.o cluster.o crc16.o endianconv.o slowlog.o scripting.o bio.o rio.o rand.o memtest.o crc64.o bitops.o sentinel.o notify.o setproctitle.o blocked.o hyperloglog.o latency.o sparkline.o redis-check-rdb.o geo.o REDIS_GEOHASH_OBJ=../deps/geohash-int/geohash.o ../deps/geohash-int/geohash_helper.o REDIS_CLI_NAME=redis-cli REDIS_CLI_OBJ=anet.o sds.o adlist.o redis-cli.o zmalloc.o release.o anet.o ae.o crc64.o @@ -29,13 +29,15 @@ #include "geo.h" #include "geohash_helper.h" -#include "zset.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); /* ==================================================================== - * Redis Add-on Module: geo - * Provides commands: geoadd, georadius, georadiusbymember, - * geoencode, geodecode - * Behaviors: + * 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 @@ -44,6 +46,40 @@ * ==================================================================== */ /* ==================================================================== + * 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) { + 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 * ==================================================================== */ static inline int decodeGeohash(double bits, double *latlong) { @@ -65,16 +101,13 @@ static inline int extractLatLongOrReply(redisClient *c, robj **argv, } /* Input Argument Helper */ -/* Decode lat/long from a zset member's score */ +/* Decode lat/long from a zset member's score. + * Returns non-zero on successful decoding. */ static int latLongFromMember(robj *zobj, robj *member, double *latlong) { double score = 0; - if (!zsetScore(zobj, member, &score)) - return 0; - - if (!decodeGeohash(score, latlong)) - return 0; - + if (zsetScore(zobj, member, &score) == REDIS_ERR) return 0; + if (!decodeGeohash(score, latlong)) return 0; return 1; } @@ -120,25 +153,129 @@ static inline void addReplyDoubleDistance(redisClient *c, double d) { addReplyBulkCBuffer(c, dbuf, dlen); } -/* geohash range+zset access helper */ -/* Obtain all members between the min/max of this geohash bounding box. */ -/* Returns list of results. List must be listRelease()'d later. */ -static list *membersOfGeoHashBox(robj *zobj, GeoHashBits hash) { +/* 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 REDIS_OK if the point is included, or REIDS_ERR if it is outside. */ +int geoAppendIfWithinRadius(geoArray *ga, double x, double y, double radius, double score, sds member) { + GeoHashArea area = {{0,0},{0,0},{0,0}}; + GeoHashBits hash = { .bits = (uint64_t)score, .step = GEO_STEP_MAX }; + double distance; + + if (!geohashDecodeWGS84(hash, &area)) return REDIS_ERR; /* Can't decode. */ + + double neighbor_y = (area.latitude.min + area.latitude.max) / 2; + double neighbor_x = (area.longitude.min + area.longitude.max) / 2; + + if (!geohashGetDistanceIfInRadiusWGS84(x, y, neighbor_x, neighbor_y, + radius, &distance)) { + return REDIS_ERR; + } + + /* Append the new element. */ + geoPoint *gp = geoArrayAppend(ga); + gp->latitude = neighbor_y; + gp->longitude = neighbor_x; + gp->dist = distance; + gp->member = member; + gp->score = score; + return REDIS_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. + * + * Elements which are farest than 'radius' from the specified 'x' and 'y' + * coordinates are not included. + * + * 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 x, double y, 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 }; + size_t origincount = ga->used; + sds member; + + if (zobj->encoding == REDIS_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); + 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); + if (geoAppendIfWithinRadius(ga,x,y,radius,score,member) + == REDIS_ERR) sdsfree(member); + zzlNext(zl, &eptr, &sptr); + } + } else if (zobj->encoding == REDIS_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 == REDIS_ENCODING_INT) ? + sdsfromlonglong((long)o->ptr) : + sdsdup(o->ptr); + if (geoAppendIfWithinRadius(ga,x,y,radius,ln->score,member) + == REDIS_ERR) sdsfree(member); + ln = ln->level[0].forward; + } + } + return ga->used - origincount; +} + +/* 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 x, double y, double radius) { GeoHashFix52Bits min, max; min = geohashAlign52Bits(hash); hash.bits++; max = geohashAlign52Bits(hash); - return geozrangebyscore(zobj, min, max, -1); /* -1 = no limit */ + return geoGetPointsInRange(zobj, min, max, x, y, radius, ga); } /* Search all eight neighbors + self geohash box */ -static list *membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double x, - double y, double radius) { - list *l = NULL; +int membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double x, double y, double radius, geoArray *ga) { GeoHashBits neighbors[9]; - unsigned int i; + unsigned int i, count = 0; neighbors[0] = n.hash; neighbors[1] = n.neighbors.north; @@ -153,76 +290,11 @@ static list *membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double x, /* 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++) { - list *r; - if (HASHISZERO(neighbors[i])) continue; - - r = membersOfGeoHashBox(zobj, neighbors[i]); - if (!r) - continue; - - if (!l) { - l = r; - } else { - listJoin(l, r); - } - } - - /* if no results across any neighbors (*and* ourself, which is unlikely), - * then just give up. */ - if (!l) - return NULL; - - /* Iterate over all matching results in the combined 9-grid search area */ - /* Remove any results outside of our search radius. */ - listIter li; - listNode *ln; - listRewind(l, &li); - while ((ln = listNext(&li))) { - struct zipresult *zr = listNodeValue(ln); - GeoHashArea area = {{0,0},{0,0},{0,0}}; - GeoHashBits hash = { .bits = (uint64_t)zr->score, - .step = GEO_STEP_MAX }; - - if (!geohashDecodeWGS84(hash, &area)) { - /* Perhaps we should delete this node if the decode fails? */ - continue; - } - - double neighbor_y = (area.latitude.min + area.latitude.max) / 2; - double neighbor_x = (area.longitude.min + area.longitude.max) / 2; - - double distance; - if (!geohashGetDistanceIfInRadiusWGS84(x, y, neighbor_x, neighbor_y, - radius, &distance)) { - /* If result is in the grid, but not in our radius, remove it. */ - listDelNode(l, ln); -#ifdef DEBUG - fprintf(stderr, "No match for neighbor (%f, %f) within (%f, %f) at " - "distance %f\n", - neighbor_y, neighbor_x, y, x, distance); -#endif - } else { -/* Else: bueno. */ -#ifdef DEBUG - fprintf( - stderr, - "Matched neighbor (%f, %f) within (%f, %f) at distance %f\n", - neighbor_y, neighbor_x, y, x, distance); -#endif - zr->distance = distance; - } - } - - /* We found results, but rejected all of them as out of range. Clean up. */ - if (!listLength(l)) { - listRelease(l); - l = NULL; + count += membersOfGeoHashBox(zobj, neighbors[i], ga, x, y, radius); } - - /* Success! */ - return l; + return count; } /* Sort comparators for qsort() */ @@ -406,16 +478,17 @@ static void geoRadiusGeneric(redisClient *c, int type) { double x = latlong[1]; /* Search the zset for all matching points */ - list *found_matches = - membersOfAllNeighbors(zobj, georadius, x, y, radius_meters); + geoArray *ga = geoArrayCreate(); + membersOfAllNeighbors(zobj, georadius, x, y, radius_meters, ga); /* If no matching results, the user gets an empty reply. */ - if (!found_matches) { + if (ga->used == 0) { addReply(c, shared.emptymultibulk); + geoArrayFree(ga); return; } - long result_length = listLength(found_matches); + long result_length = ga->used; long option_length = 0; /* Our options are self-contained nested multibulk replies, so we @@ -435,63 +508,40 @@ static void geoRadiusGeneric(redisClient *c, int type) { * user enabled for this request. */ addReplyMultiBulkLen(c, result_length); - /* Iterate over results, populate struct used for sorting and result sending - */ - listIter li; - listRewind(found_matches, &li); - struct geoPoint gp[result_length]; - /* populate gp array from our results */ - for (int i = 0; i < result_length; i++) { - struct zipresult *zr = listNodeValue(listNext(&li)); - - gp[i].member = NULL; - gp[i].set = key->ptr; - gp[i].dist = zr->distance / conversion; - gp[i].userdata = zr; - - /* The layout of geoPoint allows us to pass the start offset - * of the struct directly to decodeGeohash. */ - decodeGeohash(zr->score, (double *)(gp + i)); - } - /* Process [optional] requested sorting */ if (sort == SORT_ASC) { - qsort(gp, result_length, sizeof(*gp), sort_gp_asc); + qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_asc); } else if (sort == SORT_DESC) { - qsort(gp, result_length, sizeof(*gp), sort_gp_desc); + qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_desc); } /* Finally send results back to the caller */ - for (int i = 0; i < result_length; i++) { - struct zipresult *zr = gp[i].userdata; + 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); - switch (zr->type) { - case ZR_LONG: - addReplyBulkLongLong(c, zr->val.v); - break; - case ZR_STRING: - addReplyBulkCBuffer(c, zr->val.s, sdslen(zr->val.s)); - break; - } + addReplyBulkSds(c,gp->member); + gp->member = NULL; if (withdist) - addReplyDoubleDistance(c, gp[i].dist); + addReplyDoubleDistance(c, gp->dist); if (withhash) - addReplyLongLong(c, zr->score); + addReplyLongLong(c, gp->score); if (withcoords) { addReplyMultiBulkLen(c, 2); - addReplyDouble(c, gp[i].latitude); - addReplyDouble(c, gp[i].longitude); + addReplyDouble(c, gp->latitude); + addReplyDouble(c, gp->longitude); } } - listRelease(found_matches); + geoArrayFree(ga); } void geoRadiusCommand(redisClient *c) { @@ -9,13 +9,20 @@ void geoRadiusByMemberCommand(redisClient *c); void geoRadiusCommand(redisClient *c); void geoAddCommand(redisClient *c); -struct geoPoint { +/* Structures used inside geo.c in order to represent points and array of + * points on the earth. */ +typedef struct geoPoint { double latitude; double longitude; double dist; - char *set; + double score; char *member; - void *userdata; -}; +} geoPoint; + +typedef struct geoArray { + struct geoPoint *array; + size_t buckets; + size_t used; +} geoArray; #endif diff --git a/src/redis.h b/src/redis.h index 3115689f5..7dd2137ac 100644 --- a/src/redis.h +++ b/src/redis.h @@ -1594,8 +1594,4 @@ void redisLogHexDump(int level, char *descr, void *value, size_t len); #define redisDebugMark() \ printf("-- MARK %s:%d --\n", __FILE__, __LINE__) -/***** TEMPORARY *******/ -#include "zset.h" -/***** END TEMPORARY *******/ - #endif diff --git a/src/zset.c b/src/zset.c deleted file mode 100644 index 7a80d3a47..000000000 --- a/src/zset.c +++ /dev/null @@ -1,161 +0,0 @@ -#include "zset.h" - -/* t_zset.c prototypes (there's no t_zset.h) */ -unsigned char *zzlFirstInRange(unsigned char *zl, zrangespec *range); -unsigned char *zzlFind(unsigned char *zl, robj *ele, double *score); -int zzlLexValueLteMax(unsigned char *p, zlexrangespec *spec); - -/* Converted from static in t_zset.c: */ -int zslValueLteMax(double value, zrangespec *spec); - -/* ==================================================================== - * Direct Redis DB Interaction - * ==================================================================== */ - -/* Largely extracted from genericZrangebyscoreCommand() in t_zset.c */ -/* The zrangebyscoreCommand expects to only operate on a live redisClient, - * but we need results returned to us, not sent over an async socket. */ -list *geozrangebyscore(robj *zobj, double min, double max, int limit) { - /* 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 }; - list *l = NULL; /* result list */ - - if (zobj->encoding == REDIS_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 NULL; - } - - l = listCreate(); - - sptr = ziplistNext(zl, eptr); - - while (eptr && limit--) { - 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); - if (vstr == NULL) { - listAddNodeTail(l, result_long(score, vlong)); - } else { - listAddNodeTail(l, result_str(score, vstr, vlen)); - } - zzlNext(zl, &eptr, &sptr); - } - } else if (zobj->encoding == REDIS_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 NULL; - } - - l = listCreate(); - - while (ln && limit--) { - robj *o = ln->obj; - /* Abort when the node is no longer in range. */ - if (!zslValueLteMax(ln->score, &range)) - break; - - if (o->encoding == REDIS_ENCODING_INT) { - listAddNodeTail(l, result_long(ln->score, (long)o->ptr)); - } else { - listAddNodeTail(l, - result_str(ln->score, o->ptr, sdslen(o->ptr))); - } - - ln = ln->level[0].forward; - } - } - if (l) { - listSetFreeMethod(l, (void (*)(void *ptr)) & free_zipresult); - } - - return l; -} - -/* ==================================================================== - * Helpers - * ==================================================================== */ - -/* join 'join' to 'join_to' and free 'join' container */ -void listJoin(list *join_to, list *join) { - /* If the current list has zero size, move join to become join_to. - * If not, append the new list to the current list. */ - if (join_to->len == 0) { - join_to->head = join->head; - } else { - join_to->tail->next = join->head; - join->head->prev = join_to->tail; - join_to->tail = join->tail; - } - - /* Update total element count */ - join_to->len += join->len; - - /* Release original list container. Internal nodes were transferred over. */ - zfree(join); -} - -/* A ziplist member may be either a long long or a string. We create the - * contents of our return zipresult based on what the ziplist contained. */ -static struct zipresult *result(double score, long long v, unsigned char *s, - int len) { - struct zipresult *r = zmalloc(sizeof(*r)); - - /* If string and length, become a string. */ - /* Else, if not string or no length, become a long. */ - if (s && len >= 0) - r->type = ZR_STRING; - else if (!s || len < 0) - r->type = ZR_LONG; - - r->score = score; - switch (r->type) { - case(ZR_LONG) : - r->val.v = v; - break; - case(ZR_STRING) : - r->val.s = sdsnewlen(s, len); - break; - } - return r; -} - -struct zipresult *result_long(double score, long long v) { - return result(score, v, NULL, -1); -} - -struct zipresult *result_str(double score, unsigned char *str, int len) { - return result(score, 0, str, len); -} - -void free_zipresult(struct zipresult *r) { - if (!r) - return; - - switch (r->type) { - case(ZR_LONG) : - break; - case(ZR_STRING) : - sdsfree(r->val.s); - break; - } - - zfree(r); -} diff --git a/src/zset.h b/src/zset.h deleted file mode 100644 index a861811e4..000000000 --- a/src/zset.h +++ /dev/null @@ -1,29 +0,0 @@ -#ifndef __ZSET_H__ -#define __ZSET_H__ - -#include "redis.h" - -#define ZR_LONG 1 -#define ZR_STRING 2 -struct zipresult { - double score; - union { - long long v; - sds s; - } val; - double distance; /* distance is in meters */ - char type; /* access type for the union */ -}; - -/* Redis DB Access */ -list *geozrangebyscore(robj *zobj, double min, double max, int limit); - -/* New list operation: append one list to another */ -void listJoin(list *join_to, list *join); - -/* Helpers for returning zrangebyscore results */ -struct zipresult *result_str(double score, unsigned char *str, int len); -struct zipresult *result_long(double score, long long v); -void free_zipresult(struct zipresult *r); - -#endif |