summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--deps/Makefile7
-rw-r--r--deps/geohash-int/Makefile23
-rw-r--r--deps/geohash-int/geohash.c290
-rw-r--r--deps/geohash-int/geohash.h120
-rw-r--r--deps/geohash-int/geohash_helper.c279
-rw-r--r--deps/geohash-int/geohash_helper.h78
-rw-r--r--src/Makefile11
-rw-r--r--src/geo.c749
-rw-r--r--src/geo.h12
-rw-r--r--src/geojson.c265
-rw-r--r--src/geojson.h54
-rw-r--r--src/redis.c5
-rw-r--r--src/redis.h9
-rw-r--r--src/t_zset.c2
-rw-r--r--src/zset.c185
-rw-r--r--src/zset.h31
-rw-r--r--tests/unit/geo.tcl53
17 files changed, 2167 insertions, 6 deletions
diff --git a/deps/Makefile b/deps/Makefile
index 71f6d3a2c..10ae6e790 100644
--- a/deps/Makefile
+++ b/deps/Makefile
@@ -36,6 +36,7 @@ distclean:
-(cd hiredis && $(MAKE) clean) > /dev/null || true
-(cd linenoise && $(MAKE) clean) > /dev/null || true
-(cd lua && $(MAKE) clean) > /dev/null || true
+ -(cd geohash-int && $(MAKE) clean) > /dev/null || true
-(cd jemalloc && [ -f Makefile ] && $(MAKE) distclean) > /dev/null || true
-(rm -f .make-*)
@@ -81,3 +82,9 @@ jemalloc: .make-prerequisites
cd jemalloc && $(MAKE) CFLAGS="$(JEMALLOC_CFLAGS)" LDFLAGS="$(JEMALLOC_LDFLAGS)" lib/libjemalloc.a
.PHONY: jemalloc
+
+geohash-int: .make-prerequisites
+ @printf '%b %b\n' $(MAKECOLOR)MAKE$(ENDCOLOR) $(BINCOLOR)$@$(ENDCOLOR)
+ cd geohash-int && $(MAKE)
+
+.PHONY: geohash-int
diff --git a/deps/geohash-int/Makefile b/deps/geohash-int/Makefile
new file mode 100644
index 000000000..bf9eaebb8
--- /dev/null
+++ b/deps/geohash-int/Makefile
@@ -0,0 +1,23 @@
+STD=
+WARN= -Wall
+OPT= -Ofast
+
+R_CFLAGS= $(STD) $(WARN) $(OPT) $(DEBUG) $(CFLAGS)
+R_LDFLAGS= $(LDFLAGS)
+DEBUG= -g
+
+R_CC=$(CC) $(R_CFLAGS)
+R_LD=$(CC) $(R_LDFLAGS)
+
+all: geohash.o geohash_helper.o
+
+.PHONY: all
+
+geohash.o: geohash.h geohash.c
+geohash_helper.o: geohash.h geohash_helper.h geohash_helper.c
+
+.c.o:
+ $(R_CC) -c $<
+
+clean:
+ rm -f *.o
diff --git a/deps/geohash-int/geohash.c b/deps/geohash-int/geohash.c
new file mode 100644
index 000000000..9212736bf
--- /dev/null
+++ b/deps/geohash-int/geohash.c
@@ -0,0 +1,290 @@
+/*
+ * Copyright (c) 2013-2014, yinqiwen <yinqiwen@gmail.com>
+ * Copyright (c) 2014, Matt Stancliff <matt@genges.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 "geohash.h"
+
+/**
+ * Hashing works like this:
+ * Divide the world into 4 buckets. Label each one as such:
+ * -----------------
+ * | | |
+ * | | |
+ * | 0,1 | 1,1 |
+ * -----------------
+ * | | |
+ * | | |
+ * | 0,0 | 1,0 |
+ * -----------------
+ */
+
+bool geohashGetCoordRange(uint8_t coord_type, GeoHashRange *lat_range,
+ GeoHashRange *long_range) {
+ switch (coord_type) {
+ case GEO_WGS84_TYPE: {
+ /* These are constraints from EPSG:900913 / EPSG:3785 / OSGEO:41001 */
+ /* We can't geocode at the north/south pole. */
+ lat_range->max = 85.05112878;
+ lat_range->min = -85.05112878;
+ long_range->max = 180.0;
+ long_range->min = -180.0;
+ break;
+ }
+ case GEO_MERCATOR_TYPE: {
+ lat_range->max = 20037726.37;
+ lat_range->min = -20037726.37;
+ long_range->max = 20037726.37;
+ long_range->min = -20037726.37;
+ break;
+ }
+ default: { return false; }
+ }
+ return true;
+}
+
+bool geohashEncode(GeoHashRange *lat_range, GeoHashRange *long_range,
+ double latitude, double longitude, uint8_t step,
+ GeoHashBits *hash) {
+ uint8_t i;
+
+ if (NULL == hash || step > 32 || step == 0 || RANGEPISZERO(lat_range) ||
+ RANGEPISZERO(long_range)) {
+ return false;
+ }
+
+ hash->bits = 0;
+ hash->step = step;
+
+ if (latitude < lat_range->min || latitude > lat_range->max ||
+ longitude < long_range->min || longitude > long_range->max) {
+ return false;
+ }
+
+ for (i = 0; i < step; i++) {
+ uint8_t lat_bit, long_bit;
+
+ if (lat_range->max - latitude >= latitude - lat_range->min) {
+ lat_bit = 0;
+ lat_range->max = (lat_range->max + lat_range->min) / 2;
+ } else {
+ lat_bit = 1;
+ lat_range->min = (lat_range->max + lat_range->min) / 2;
+ }
+ if (long_range->max - longitude >= longitude - long_range->min) {
+ long_bit = 0;
+ long_range->max = (long_range->max + long_range->min) / 2;
+ } else {
+ long_bit = 1;
+ long_range->min = (long_range->max + long_range->min) / 2;
+ }
+
+ hash->bits <<= 1;
+ hash->bits += long_bit;
+ hash->bits <<= 1;
+ hash->bits += lat_bit;
+ }
+ return true;
+}
+
+bool geohashEncodeType(uint8_t coord_type, double latitude, double longitude,
+ uint8_t step, GeoHashBits *hash) {
+ GeoHashRange r[2] = { { 0 } };
+ geohashGetCoordRange(coord_type, &r[0], &r[1]);
+ return geohashEncode(&r[0], &r[1], latitude, longitude, step, hash);
+}
+
+bool geohashEncodeWGS84(double latitude, double longitude, uint8_t step,
+ GeoHashBits *hash) {
+ return geohashEncodeType(GEO_WGS84_TYPE, latitude, longitude, step, hash);
+}
+
+bool geohashEncodeMercator(double latitude, double longitude, uint8_t step,
+ GeoHashBits *hash) {
+ return geohashEncodeType(GEO_MERCATOR_TYPE, latitude, longitude, step,
+ hash);
+}
+
+static inline uint8_t get_bit(uint64_t bits, uint8_t pos) {
+ return (bits >> pos) & 0x01;
+}
+
+bool geohashDecode(const GeoHashRange lat_range, const GeoHashRange long_range,
+ const GeoHashBits hash, GeoHashArea *area) {
+ uint8_t i;
+
+ if (HASHISZERO(hash) || NULL == area || RANGEISZERO(lat_range) ||
+ RANGEISZERO(long_range)) {
+ return false;
+ }
+
+ area->hash = hash;
+ area->latitude.min = lat_range.min;
+ area->latitude.max = lat_range.max;
+ area->longitude.min = long_range.min;
+ area->longitude.max = long_range.max;
+
+ for (i = 0; i < hash.step; i++) {
+ uint8_t lat_bit, long_bit;
+
+ long_bit = get_bit(hash.bits, (hash.step - i) * 2 - 1);
+ lat_bit = get_bit(hash.bits, (hash.step - i) * 2 - 2);
+
+ if (lat_bit == 0) {
+ area->latitude.max = (area->latitude.max + area->latitude.min) / 2;
+ } else {
+ area->latitude.min = (area->latitude.max + area->latitude.min) / 2;
+ }
+
+ if (long_bit == 0) {
+ area->longitude.max =
+ (area->longitude.max + area->longitude.min) / 2;
+ } else {
+ area->longitude.min =
+ (area->longitude.max + area->longitude.min) / 2;
+ }
+ }
+ return true;
+}
+
+bool geohashDecodeType(uint8_t coord_type, const GeoHashBits hash,
+ GeoHashArea *area) {
+ GeoHashRange r[2] = { { 0 } };
+ geohashGetCoordRange(coord_type, &r[0], &r[1]);
+ return geohashDecode(r[0], r[1], hash, area);
+}
+
+bool geohashDecodeWGS84(const GeoHashBits hash, GeoHashArea *area) {
+ return geohashDecodeType(GEO_WGS84_TYPE, hash, area);
+}
+
+bool geohashDecodeMercator(const GeoHashBits hash, GeoHashArea *area) {
+ return geohashDecodeType(GEO_MERCATOR_TYPE, hash, area);
+}
+
+bool geohashDecodeAreaToLatLong(const GeoHashArea *area, double *latlong) {
+ double y, x;
+
+ if (!latlong)
+ return false;
+
+ y = (area->latitude.min + area->latitude.max) / 2;
+ x = (area->longitude.min + area->longitude.max) / 2;
+
+ latlong[0] = y;
+ latlong[1] = x;
+ return true;
+}
+
+bool geohashDecodeToLatLongType(uint8_t coord_type, const GeoHashBits hash,
+ double *latlong) {
+ GeoHashArea area = { { 0 } };
+ if (!latlong || !geohashDecodeType(coord_type, hash, &area))
+ return false;
+ return geohashDecodeAreaToLatLong(&area, latlong);
+}
+
+bool geohashDecodeToLatLongWGS84(const GeoHashBits hash, double *latlong) {
+ return geohashDecodeToLatLongType(GEO_WGS84_TYPE, hash, latlong);
+}
+
+bool geohashDecodeToLatLongMercator(const GeoHashBits hash, double *latlong) {
+ return geohashDecodeToLatLongType(GEO_MERCATOR_TYPE, hash, latlong);
+}
+
+static void geohash_move_x(GeoHashBits *hash, int8_t d) {
+ if (d == 0)
+ return;
+
+ uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaLL;
+ uint64_t y = hash->bits & 0x5555555555555555LL;
+
+ uint64_t zz = 0x5555555555555555LL >> (64 - hash->step * 2);
+
+ if (d > 0) {
+ x = x + (zz + 1);
+ } else {
+ x = x | zz;
+ x = x - (zz + 1);
+ }
+
+ x &= (0xaaaaaaaaaaaaaaaaLL >> (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 & 0xaaaaaaaaaaaaaaaaLL;
+ uint64_t y = hash->bits & 0x5555555555555555LL;
+
+ uint64_t zz = 0xaaaaaaaaaaaaaaaaLL >> (64 - hash->step * 2);
+ if (d > 0) {
+ y = y + (zz + 1);
+ } else {
+ y = y | zz;
+ y = y - (zz + 1);
+ }
+ y &= (0x5555555555555555LL >> (64 - hash->step * 2));
+ hash->bits = (x | y);
+}
+
+void geohashNeighbors(const GeoHashBits *hash, GeoHashNeighbors *neighbors) {
+ neighbors->east = *hash;
+ neighbors->west = *hash;
+ neighbors->north = *hash;
+ neighbors->south = *hash;
+ neighbors->south_east = *hash;
+ neighbors->south_west = *hash;
+ neighbors->north_east = *hash;
+ neighbors->north_west = *hash;
+
+ geohash_move_x(&neighbors->east, 1);
+ geohash_move_y(&neighbors->east, 0);
+
+ geohash_move_x(&neighbors->west, -1);
+ geohash_move_y(&neighbors->west, 0);
+
+ geohash_move_x(&neighbors->south, 0);
+ geohash_move_y(&neighbors->south, -1);
+
+ geohash_move_x(&neighbors->north, 0);
+ geohash_move_y(&neighbors->north, 1);
+
+ geohash_move_x(&neighbors->north_west, -1);
+ geohash_move_y(&neighbors->north_west, 1);
+
+ geohash_move_x(&neighbors->north_east, 1);
+ geohash_move_y(&neighbors->north_east, 1);
+
+ geohash_move_x(&neighbors->south_east, 1);
+ geohash_move_y(&neighbors->south_east, -1);
+
+ geohash_move_x(&neighbors->south_west, -1);
+ geohash_move_y(&neighbors->south_west, -1);
+}
diff --git a/deps/geohash-int/geohash.h b/deps/geohash-int/geohash.h
new file mode 100644
index 000000000..30fc17144
--- /dev/null
+++ b/deps/geohash-int/geohash.h
@@ -0,0 +1,120 @@
+/*
+ * Copyright (c) 2013-2014, yinqiwen <yinqiwen@gmail.com>
+ * Copyright (c) 2014, Matt Stancliff <matt@genges.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.
+ */
+
+#ifndef GEOHASH_H_
+#define GEOHASH_H_
+
+#include <stddef.h>
+#include <stdbool.h>
+#include <stdint.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+#define HASHISZERO(r) (!(r).bits && !(r).step)
+#define RANGEISZERO(r) (!(r).max && !(r).min)
+#define RANGEPISZERO(r) (r == NULL || RANGEISZERO(*r))
+
+#define GEO_WGS84_TYPE 1
+#define GEO_MERCATOR_TYPE 2
+
+#define GEO_STEP_MAX 26
+
+typedef enum {
+ GEOHASH_NORTH = 0,
+ GEOHASH_EAST,
+ GEOHASH_WEST,
+ GEOHASH_SOUTH,
+ GEOHASH_SOUTH_WEST,
+ GEOHASH_SOUTH_EAST,
+ GEOHASH_NORT_WEST,
+ GEOHASH_NORT_EAST
+} GeoDirection;
+
+typedef struct {
+ uint64_t bits;
+ uint8_t step;
+} GeoHashBits;
+
+typedef struct {
+ double max;
+ double min;
+} GeoHashRange;
+
+typedef struct {
+ GeoHashBits hash;
+ GeoHashRange latitude;
+ GeoHashRange longitude;
+} GeoHashArea;
+
+typedef struct {
+ GeoHashBits north;
+ GeoHashBits east;
+ GeoHashBits west;
+ GeoHashBits south;
+ GeoHashBits north_east;
+ GeoHashBits south_east;
+ GeoHashBits north_west;
+ GeoHashBits south_west;
+} GeoHashNeighbors;
+
+/*
+ * 0:success
+ * -1:failed
+ */
+bool geohashGetCoordRange(uint8_t coord_type, GeoHashRange *lat_range,
+ GeoHashRange *long_range);
+bool geohashEncode(GeoHashRange *lat_range, GeoHashRange *long_range,
+ double latitude, double longitude, uint8_t step,
+ GeoHashBits *hash);
+bool geohashEncodeType(uint8_t coord_type, double latitude, double longitude,
+ uint8_t step, GeoHashBits *hash);
+bool geohashEncodeMercator(double latitude, double longitude, uint8_t step,
+ GeoHashBits *hash);
+bool geohashEncodeWGS84(double latitude, double longitude, uint8_t step,
+ GeoHashBits *hash);
+bool geohashDecode(const GeoHashRange lat_range, const GeoHashRange long_range,
+ const GeoHashBits hash, GeoHashArea *area);
+bool geohashDecodeType(uint8_t coord_type, const GeoHashBits hash,
+ GeoHashArea *area);
+bool geohashDecodeMercator(const GeoHashBits hash, GeoHashArea *area);
+bool geohashDecodeWGS84(const GeoHashBits hash, GeoHashArea *area);
+bool geohashDecodeAreaToLatLong(const GeoHashArea *area, double *latlong);
+bool geohashDecodeToLatLongType(uint8_t coord_type, const GeoHashBits hash,
+ double *latlong);
+bool geohashDecodeToLatLongWGS84(const GeoHashBits hash, double *latlong);
+bool geohashDecodeToLatLongMercator(const GeoHashBits hash, double *latlong);
+void geohashNeighbors(const GeoHashBits *hash, GeoHashNeighbors *neighbors);
+
+#if defined(__cplusplus)
+}
+#endif
+#endif /* GEOHASH_H_ */
diff --git a/deps/geohash-int/geohash_helper.c b/deps/geohash-int/geohash_helper.c
new file mode 100644
index 000000000..010ab070b
--- /dev/null
+++ b/deps/geohash-int/geohash_helper.c
@@ -0,0 +1,279 @@
+/*
+ * Copyright (c) 2013-2014, yinqiwen <yinqiwen@gmail.com>
+ * Copyright (c) 2014, Matt Stancliff <matt@genges.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.
+ */
+
+/* This is a C++ to C conversion from the ardb project.
+ * This file started out as:
+ * https://github.com/yinqiwen/ardb/blob/d42503/src/geo/geohash_helper.cpp
+ */
+
+#include "geohash_helper.h"
+
+#define D_R (M_PI / 180.0)
+#define R_MAJOR 6378137.0
+#define R_MINOR 6356752.3142
+#define RATIO (R_MINOR / R_MAJOR)
+#define ECCENT (sqrt(1.0 - (RATIO *RATIO)))
+#define COM (0.5 * ECCENT)
+
+/// @brief The usual PI/180 constant
+const double DEG_TO_RAD = 0.017453292519943295769236907684886;
+/// @brief Earth's quatratic mean radius for WGS-84
+const double EARTH_RADIUS_IN_METERS = 6372797.560856;
+
+const double MERCATOR_MAX = 20037726.37;
+const double MERCATOR_MIN = -20037726.37;
+
+static inline double deg_rad(double ang) { return ang * D_R; }
+static inline double rad_deg(double ang) { return ang / D_R; }
+
+double mercator_y(double lat) {
+ lat = fmin(89.5, fmax(lat, -89.5));
+ double phi = deg_rad(lat);
+ double sinphi = sin(phi);
+ double con = ECCENT * sinphi;
+ con = pow((1.0 - con) / (1.0 + con), COM);
+ double ts = tan(0.5 * (M_PI * 0.5 - phi)) / con;
+ return 0 - R_MAJOR * log(ts);
+}
+
+double mercator_x(double lon) { return R_MAJOR * deg_rad(lon); }
+double merc_lon(double x) { return rad_deg(x) / R_MAJOR; }
+
+double merc_lat(double y) {
+ double ts = exp(-y / R_MAJOR);
+ double phi = M_PI_2 - 2 * atan(ts);
+ double dphi = 1.0;
+ int i;
+ for (i = 0; fabs(dphi) > 0.000000001 && i < 15; i++) {
+ double con = ECCENT * sin(phi);
+ dphi =
+ M_PI_2 - 2 * atan(ts * pow((1.0 - con) / (1.0 + con), COM)) - phi;
+ phi += dphi;
+ }
+ return rad_deg(phi);
+}
+
+/* You must *ONLY* estimate steps when you are encoding.
+ * If you are decoding, always decode to GEO_STEP_MAX (26). */
+uint8_t geohashEstimateStepsByRadius(double range_meters) {
+ uint8_t step = 1;
+ while (range_meters > 0 && range_meters < MERCATOR_MAX) {
+ range_meters *= 2;
+ step++;
+ }
+ step--;
+ if (!step)
+ step = 26; /* if range = 0, give max resolution */
+ return step > 26 ? 26 : step;
+}
+
+double geohashGetXWGS84(double x) { return merc_lon(x); }
+double geohashGetYWGS84(double y) { return merc_lat(y); }
+
+double geohashGetXMercator(double longtitude) {
+ if (longtitude > 180 || longtitude < -180) {
+ return longtitude;
+ }
+ return mercator_x(longtitude);
+}
+double geohashGetYMercator(double latitude) {
+ if (latitude > 90 || latitude < -90) {
+ return latitude;
+ }
+ return mercator_y(latitude);
+}
+
+int geohashBitsComparator(const GeoHashBits *a, const GeoHashBits *b) {
+ /* If step not equal, compare on step. Else, compare on bits. */
+ return a->step != b->step ? a->step - b->step : a->bits - b->bits;
+}
+
+bool geohashBoundingBox(double latitude, double longitude, double radius_meters,
+ double *bounds) {
+ if (!bounds)
+ return false;
+
+ double latr, lonr;
+ latr = deg_rad(latitude);
+ lonr = deg_rad(longitude);
+
+ double distance = radius_meters / EARTH_RADIUS_IN_METERS;
+ double min_latitude = latr - distance;
+ double max_latitude = latr + distance;
+
+ /* Note: we're being lazy and not accounting for coordinates near poles */
+ double min_longitude, max_longitude;
+ double difference_longitude = asin(sin(distance) / cos(latr));
+ min_longitude = lonr - difference_longitude;
+ max_longitude = lonr + difference_longitude;
+
+ bounds[0] = rad_deg(min_latitude);
+ bounds[1] = rad_deg(min_longitude);
+ bounds[2] = rad_deg(max_latitude);
+ bounds[3] = rad_deg(max_longitude);
+
+ return true;
+}
+
+GeoHashRadius geohashGetAreasByRadius(uint8_t coord_type, double latitude,
+ double longitude, double radius_meters) {
+ GeoHashRange lat_range, long_range;
+ GeoHashRadius radius = { { 0 } };
+ GeoHashBits hash = { 0 };
+ GeoHashNeighbors neighbors = { { 0 } };
+ GeoHashArea area = { { 0 } };
+ double delta_longitude, delta_latitude;
+ double min_lat, max_lat, min_lon, max_lon;
+ int steps;
+
+ if (coord_type == GEO_WGS84_TYPE) {
+ double bounds[4];
+ geohashBoundingBox(latitude, longitude, radius_meters, bounds);
+ min_lat = bounds[0];
+ min_lon = bounds[1];
+ max_lat = bounds[2];
+ max_lon = bounds[3];
+ } else {
+ delta_latitude = delta_longitude = radius_meters;
+ min_lat = latitude - delta_latitude;
+ max_lat = latitude + delta_latitude;
+ min_lon = longitude - delta_longitude;
+ max_lon = longitude + delta_longitude;
+ }
+
+ steps = geohashEstimateStepsByRadius(radius_meters);
+
+ geohashGetCoordRange(coord_type, &lat_range, &long_range);
+ geohashEncode(&lat_range, &long_range, latitude, longitude, steps, &hash);
+ geohashNeighbors(&hash, &neighbors);
+ geohashDecode(lat_range, long_range, hash, &area);
+
+ if (area.latitude.min < min_lat) {
+ GZERO(neighbors.south);
+ GZERO(neighbors.south_west);
+ GZERO(neighbors.south_east);
+ }
+ if (area.latitude.max > max_lat) {
+ GZERO(neighbors.north);
+ GZERO(neighbors.north_east);
+ GZERO(neighbors.north_west);
+ }
+ if (area.longitude.min < min_lon) {
+ GZERO(neighbors.west);
+ GZERO(neighbors.south_west);
+ GZERO(neighbors.north_west);
+ }
+ if (area.longitude.max > max_lon) {
+ GZERO(neighbors.east);
+ GZERO(neighbors.south_east);
+ GZERO(neighbors.north_east);
+ }
+ radius.hash = hash;
+ radius.neighbors = neighbors;
+ radius.area = area;
+ return radius;
+}
+
+GeoHashRadius geohashGetAreasByRadiusWGS84(double latitude, double longitude,
+ double radius_meters) {
+ return geohashGetAreasByRadius(GEO_WGS84_TYPE, latitude, longitude,
+ radius_meters);
+}
+
+GeoHashRadius geohashGetAreasByRadiusMercator(double latitude, double longitude,
+ double radius_meters) {
+ return geohashGetAreasByRadius(GEO_MERCATOR_TYPE, latitude, longitude,
+ radius_meters);
+}
+
+GeoHashFix52Bits geohashAlign52Bits(const GeoHashBits hash) {
+ uint64_t bits = hash.bits;
+ bits <<= (52 - hash.step * 2);
+ return bits;
+}
+
+/* calculate distance using haversin great circle distance formula */
+double distanceEarth(double lat1d, double lon1d, double lat2d, double lon2d) {
+ double lat1r, lon1r, lat2r, lon2r, u, v;
+ lat1r = deg_rad(lat1d);
+ lon1r = deg_rad(lon1d);
+ lat2r = deg_rad(lat2d);
+ lon2r = deg_rad(lon2d);
+ u = sin((lat2r - lat1r) / 2);
+ v = sin((lon2r - lon1r) / 2);
+ return 2.0 * EARTH_RADIUS_IN_METERS *
+ asin(sqrt(u * u + cos(lat1r) * cos(lat2r) * v * v));
+}
+
+bool geohashGetDistanceIfInRadius(uint8_t coord_type, double x1, double y1,
+ double x2, double y2, double radius,
+ double *distance) {
+ if (coord_type == GEO_WGS84_TYPE) {
+ *distance = distanceEarth(y1, x1, y2, x2);
+ if (*distance > radius) {
+ return false;
+ }
+ } else {
+ double xx = (x1 - x2) * (x1 - x2);
+ double yy = (y1 - y2) * (y1 - y2);
+ double dd = xx + yy;
+ *distance = dd;
+ if (dd > (radius * radius)) {
+ return false;
+ }
+ }
+ return true;
+}
+
+bool geohashGetDistanceIfInRadiusWGS84(double x1, double y1, double x2,
+ double y2, double radius,
+ double *distance) {
+ return geohashGetDistanceIfInRadius(GEO_WGS84_TYPE, x1, y1, x2, y2, radius,
+ distance);
+}
+
+bool geohashGetDistanceSquaredIfInRadiusMercator(double x1, double y1,
+ double x2, double y2,
+ double radius,
+ double *distance) {
+ return geohashGetDistanceIfInRadius(GEO_MERCATOR_TYPE, x1, y1, x2, y2,
+ radius, distance);
+}
+
+bool geohashVerifyCoordinates(uint8_t coord_type, double x, double y) {
+ GeoHashRange lat_range, long_range;
+ geohashGetCoordRange(coord_type, &lat_range, &long_range);
+
+ if (x < long_range.min || x > long_range.max || y < lat_range.min ||
+ y > lat_range.max) {
+ return false;
+ }
+ return true;
+}
diff --git a/deps/geohash-int/geohash_helper.h b/deps/geohash-int/geohash_helper.h
new file mode 100644
index 000000000..b72e51442
--- /dev/null
+++ b/deps/geohash-int/geohash_helper.h
@@ -0,0 +1,78 @@
+/*
+ * Copyright (c) 2013-2014, yinqiwen <yinqiwen@gmail.com>
+ * Copyright (c) 2014, Matt Stancliff <matt@genges.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.
+ */
+
+#ifndef GEOHASH_HELPER_HPP_
+#define GEOHASH_HELPER_HPP_
+
+#include <math.h>
+#include <stdbool.h>
+#include "geohash.h"
+
+#define GZERO(s) s.bits = s.step = 0;
+#define GISZERO(s) (!s.bits && !s.step)
+#define GISNOTZERO(s) (s.bits || s.step)
+
+typedef uint64_t GeoHashFix52Bits;
+typedef uint64_t GeoHashVarBits;
+
+typedef struct {
+ GeoHashBits hash;
+ GeoHashArea area;
+ GeoHashNeighbors neighbors;
+} GeoHashRadius;
+
+int GeoHashBitsComparator(const GeoHashBits *a, const GeoHashBits *b);
+uint8_t geohashEstimateStepsByRadius(double range_meters);
+bool geohashBoundingBox(double latitude, double longitude, double radius_meters,
+ double *bounds);
+GeoHashRadius geohashGetAreasByRadius(uint8_t coord_type, double latitude,
+ double longitude, double radius_meters);
+GeoHashRadius geohashGetAreasByRadiusWGS84(double latitude, double longitude,
+ double radius_meters);
+GeoHashRadius geohashGetAreasByRadiusMercator(double latitude, double longitude,
+ double radius_meters);
+GeoHashFix52Bits geohashAlign52Bits(const GeoHashBits hash);
+double geohashGetXMercator(double longtitude);
+double geohashGetYMercator(double latitude);
+double geohashGetXWGS84(double x);
+double geohashGetYWGS84(double y);
+bool geohashVerifyCoordinates(uint8_t coord_type, double x, double y);
+bool geohashGetDistanceIfInRadius(uint8_t coord_type, double x1, double y1,
+ double x2, double y2, double radius,
+ double *distance);
+bool geohashGetDistanceIfInRadiusWGS84(double x1, double y1, double x2,
+ double y2, double radius,
+ double *distance);
+bool geohashGetDistanceSquaredIfInRadiusMercator(double x1, double y1,
+ double x2, double y2,
+ double radius,
+ double *distance);
+
+#endif /* GEOHASH_HELPER_HPP_ */
diff --git a/src/Makefile b/src/Makefile
index 271ab34d8..054857ca5 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -14,8 +14,8 @@
release_hdr := $(shell sh -c './mkreleasehdr.sh')
uname_S := $(shell sh -c 'uname -s 2>/dev/null || echo not')
-OPTIMIZATION?=-O2
-DEPENDENCY_TARGETS=hiredis linenoise lua
+#OPTIMIZATION?=-O2
+DEPENDENCY_TARGETS=hiredis linenoise lua geohash-int
# Default settings
STD=-std=c99 -pedantic -DREDIS_STATIC=''
@@ -53,7 +53,7 @@ endif
# Override default settings if possible
-include .make-settings
-FINAL_CFLAGS=$(STD) $(WARN) $(OPT) $(DEBUG) $(CFLAGS) $(REDIS_CFLAGS)
+FINAL_CFLAGS=$(STD) $(WARN) $(OPT) $(DEBUG) $(CFLAGS) $(REDIS_CFLAGS) -I../deps/geohash-int
FINAL_LDFLAGS=$(LDFLAGS) $(REDIS_LDFLAGS) $(DEBUG)
FINAL_LIBS=-lm
DEBUG=-g -ggdb
@@ -117,7 +117,8 @@ 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
+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 geojson.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
REDIS_BENCHMARK_NAME=redis-benchmark
@@ -171,7 +172,7 @@ endif
# redis-server
$(REDIS_SERVER_NAME): $(REDIS_SERVER_OBJ)
- $(REDIS_LD) -o $@ $^ ../deps/hiredis/libhiredis.a ../deps/lua/src/liblua.a $(FINAL_LIBS)
+ $(REDIS_LD) -o $@ $^ ../deps/hiredis/libhiredis.a ../deps/lua/src/liblua.a $(REDIS_GEOHASH_OBJ) $(FINAL_LIBS)
# redis-sentinel
$(REDIS_SENTINEL_NAME): $(REDIS_SERVER_NAME)
diff --git a/src/geo.c b/src/geo.c
new file mode 100644
index 000000000..36e87eef5
--- /dev/null
+++ b/src/geo.c
@@ -0,0 +1,749 @@
+/*
+ * Copyright (c) 2014, Matt Stancliff <matt@genges.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"
+#include "geojson.h"
+#include "zset.h"
+
+/* ====================================================================
+ * Redis Add-on Module: geo
+ * Provides commands: geoadd, georadius, georadiusbymember,
+ * geoencode, geodecode
+ * Behaviors:
+ * - geoadd - add coordinates for value to geoset
+ * - georadius - search radius by coordinates in geoset
+ * - georadiusbymember - search radius based on geoset member position
+ * - geoencode - encode coordinates to a geohash integer
+ * - geodecode - decode geohash integer to representative coordinates
+ * ==================================================================== */
+
+/* ====================================================================
+ * Helpers
+ * ==================================================================== */
+static inline bool decodeGeohash(double bits, double *latlong) {
+ GeoHashBits hash = { .bits = (uint64_t)bits, .step = GEO_STEP_MAX };
+ return geohashDecodeToLatLongWGS84(hash, latlong);
+}
+
+/* Input Argument Helper */
+/* Take a pointer to the latitude arg then use the next arg for longitude */
+static inline bool extractLatLongOrReply(redisClient *c, robj **argv,
+ double *latlong) {
+ for (int i = 0; i < 2; i++) {
+ if (getDoubleFromObjectOrReply(c, argv[i], latlong + i, NULL) !=
+ REDIS_OK) {
+ return false;
+ }
+ }
+ return true;
+}
+
+/* Input Argument Helper */
+/* Decode lat/long from a zset member's score */
+static bool latLongFromMember(robj *zobj, robj *member, double *latlong) {
+ double score = 0;
+
+ if (!zsetScore(zobj, member, &score))
+ return false;
+
+ if (!decodeGeohash(score, latlong))
+ return false;
+
+ return true;
+}
+
+/* Input Argument Helper */
+static double extractDistanceOrReply(redisClient *c, robj **argv,
+ double *conversion) {
+ double distance;
+ if (getDoubleFromObjectOrReply(c, argv[0], &distance,
+ "need numeric radius") != REDIS_OK) {
+ return -1;
+ }
+
+ double to_meters;
+ sds units = argv[1]->ptr;
+ if (!strcmp(units, "m") || !strncmp(units, "meter", 5)) {
+ to_meters = 1;
+ } else if (!strcmp(units, "ft") || !strncmp(units, "feet", 4)) {
+ to_meters = 0.3048;
+ } else if (!strcmp(units, "mi") || !strncmp(units, "mile", 4)) {
+ to_meters = 1609.34;
+ } else if (!strcmp(units, "km") || !strncmp(units, "kilometer", 9)) {
+ to_meters = 1000;
+ } else {
+ addReplyError(c, "unsupported unit provided. please use meters (m), "
+ "kilometers (km), miles (mi), or feet (ft)");
+ return -1;
+ }
+
+ if (conversion)
+ *conversion = to_meters;
+
+ return distance * to_meters;
+}
+
+/* Output Reply Helper */
+static void latLongToGeojsonAndReply(redisClient *c, struct geojsonPoint *gp,
+ char *units) {
+ sds geojson = geojsonLatLongToPointFeature(
+ gp->latitude, gp->longitude, gp->set, gp->member, gp->dist, units);
+
+ addReplyBulkCBuffer(c, geojson, sdslen(geojson));
+ sdsfree(geojson);
+}
+
+/* Output Reply Helper */
+static void decodeGeohashToGeojsonBoundsAndReply(redisClient *c,
+ uint64_t hashbits,
+ struct geojsonPoint *gp) {
+ GeoHashArea area = { { 0 } };
+ GeoHashBits hash = { .bits = hashbits, .step = GEO_STEP_MAX };
+
+ geohashDecodeWGS84(hash, &area);
+
+ sds geojson = geojsonBoxToPolygonFeature(
+ area.latitude.min, area.longitude.min, area.latitude.max,
+ area.longitude.max, gp->set, gp->member);
+ addReplyBulkCBuffer(c, geojson, sdslen(geojson));
+ sdsfree(geojson);
+}
+
+/* The defailt addReplyDouble has too much accuracy. We use this
+ * for returning location distances. "5.21 meters away" is nicer
+ * than "5.2144992818115 meters away." */
+static inline void addReplyDoubleNicer(redisClient *c, double d) {
+ char dbuf[128] = { 0 };
+ int dlen = snprintf(dbuf, sizeof(dbuf), "%.2f", d);
+ addReplyBulkCBuffer(c, dbuf, dlen);
+}
+
+/* Output Reply Helper */
+static void replyGeojsonCollection(redisClient *c, struct geojsonPoint *gp,
+ long result_length, char *units) {
+ sds geojson = geojsonFeatureCollection(gp, result_length, units);
+ addReplyBulkCBuffer(c, geojson, sdslen(geojson));
+ sdsfree(geojson);
+}
+
+/* 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) {
+ GeoHashFix52Bits min, max;
+
+ min = geohashAlign52Bits(hash);
+ hash.bits++;
+ max = geohashAlign52Bits(hash);
+
+ return geozrangebyscore(zobj, min, max, -1); /* -1 = no limit */
+}
+
+/* Search all eight neighbors + self geohash box */
+static list *membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double x,
+ double y, double radius) {
+ list *l = NULL;
+ GeoHashBits neighbors[9];
+
+ 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 (int 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 } };
+ 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;
+ }
+
+ /* Success! */
+ return l;
+}
+
+/* With no subscribers, each call of this function adds a median latency of 2
+ * microseconds. */
+/* We aren't participating in any keyspace/keyevent notifications other than
+ * what's provided by the underlying zset itself, but it's probably not useful
+ * for clients to get the 52-bit integer geohash as an "update" value. */
+static int publishLocationUpdate(const sds zset, const sds member,
+ const double latitude,
+ const double longitude) {
+ int published;
+
+ /* event is: "<latitude> <longitude>" */
+ sds event = sdscatprintf(sdsempty(), "%.7f %.7f", latitude, longitude);
+ robj *eventobj = createObject(REDIS_STRING, event);
+
+ /* channel is: __geo:<zset>:<member> */
+ /* If you want all events for this zset then just psubscribe
+ * to "__geo:<zset>:*" */
+ sds chan = sdsnewlen("__geo:", 6);
+ chan = sdscatsds(chan, zset);
+ chan = sdscatlen(chan, ":", 1);
+ chan = sdscatsds(chan, member);
+ robj *chanobj = createObject(REDIS_STRING, chan);
+
+ published = pubsubPublishMessage(chanobj, eventobj);
+
+ decrRefCount(chanobj);
+ decrRefCount(eventobj);
+
+ return published;
+}
+
+/* Sort comparators for qsort() */
+static int sort_gp_asc(const void *a, const void *b) {
+ const struct geojsonPoint *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
+ * ==================================================================== */
+void geoAddCommand(redisClient *c) {
+ /* args 0-4: [cmd, key, lat, lng, val]; optional 5-6: [radius, units]
+ * - OR -
+ * args 0-N: [cmd, key, lat, lng, val, lat2, lng2, val2, ...] */
+ robj *cmd = c->argv[0];
+ robj *key = c->argv[1];
+
+ /* Prepare for the three different forms of the add command. */
+ double radius_meters = 0;
+ if (c->argc == 7) {
+ if ((radius_meters = extractDistanceOrReply(c, c->argv + 5, NULL)) <
+ 0) {
+ return;
+ }
+ } else if (c->argc == 6) {
+ addReplyError(c, "must provide units when asking for radius encode");
+ return;
+ } else if ((c->argc - 2) % 3 != 0) {
+ /* Need an odd number of arguments if we got this far... */
+ addReplyError(c, "format is: geoadd [key] [lat1] [long1] [member1] "
+ "[lat2] [long2] [member2] ... ");
+ return;
+ }
+
+ redisClient *client = c;
+ int elements = (c->argc - 2) / 3;
+ /* elements will always be correct size (integer math floors for us if we
+ * have 6 or 7 total arguments) */
+ if (elements > 1) {
+ /* We should probably use a static client and not create/free it
+ * for every multi-add */
+ client = createClient(-1); /* fake client for multi-zadd */
+
+ /* Tell fake client to use the same DB as our calling client. */
+ selectDb(client, c->db->id);
+ }
+
+ /* Capture all lat/long components up front so if we encounter an error we
+ * return before making any changes to the database. */
+ double latlong[elements * 2];
+ for (int i = 0; i < elements; i++) {
+ if (!extractLatLongOrReply(c, (c->argv + 2) + (i * 3),
+ latlong + (i * 2)))
+ return;
+ }
+
+ /* Add all (lat, long, value) triples to the requested zset */
+ for (int i = 0; i < elements; i++) {
+ uint8_t step = geohashEstimateStepsByRadius(radius_meters);
+
+#ifdef DEBUG
+ printf("Adding with step size: %d\n", step);
+#endif
+ GeoHashBits hash;
+ int ll_offset = i * 2;
+ double latitude = latlong[ll_offset];
+ double longitude = latlong[ll_offset + 1];
+ geohashEncodeWGS84(latitude, longitude, step, &hash);
+
+ GeoHashFix52Bits bits = geohashAlign52Bits(hash);
+ robj *score = createObject(REDIS_STRING, sdsfromlonglong(bits));
+ robj *val = c->argv[2 + i * 3 + 2];
+ /* (base args) + (offset for this triple) + (offset of value arg) */
+
+ rewriteClientCommandVector(client, 4, cmd, key, score, val);
+ decrRefCount(score);
+ zaddCommand(client);
+ publishLocationUpdate(key->ptr, val->ptr, latitude, longitude);
+ }
+
+ /* If we used a fake client, return a real reply then free fake client. */
+ if (client != c) {
+ addReplyLongLong(c, elements);
+ freeClient(client);
+ }
+}
+
+#define SORT_NONE 0
+#define SORT_ASC 1
+#define SORT_DESC 2
+
+#define RADIUS_COORDS 1
+#define RADIUS_MEMBER 2
+
+static void geoRadiusGeneric(redisClient *c, int type) {
+ /* type == cords: [cmd, key, lat, long, radius, units, [optionals]]
+ * type == member: [cmd, key, member, radius, units, [optionals]] */
+ robj *key = c->argv[1];
+
+ /* Look up the requested zset */
+ robj *zobj = NULL;
+ if ((zobj = lookupKeyReadOrReply(c, key, shared.emptymultibulk)) == NULL ||
+ checkType(c, zobj, REDIS_ZSET)) {
+ return;
+ }
+
+ /* Find lat/long to use for radius search based on inquiry type */
+ int base_args;
+ double latlong[2] = { 0 };
+ if (type == RADIUS_COORDS) {
+ base_args = 6;
+ if (!extractLatLongOrReply(c, c->argv + 2, latlong))
+ return;
+ } else if (type == RADIUS_MEMBER) {
+ base_args = 5;
+ robj *member = c->argv[2];
+ if (!latLongFromMember(zobj, member, latlong)) {
+ 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;
+ }
+
+ sds units = c->argv[base_args - 2 + 1]->ptr;
+
+ /* Discover and populate all optional parameters. */
+ bool withdist = false, withhash = false, withcoords = false,
+ withgeojson = false, withgeojsonbounds = false,
+ withgeojsoncollection = false, noproperties = false;
+ int sort = SORT_NONE;
+ 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 (!strncasecmp(arg, "withdist", 8))
+ withdist = true;
+ else if (!strcasecmp(arg, "withhash"))
+ withhash = true;
+ else if (!strncasecmp(arg, "withcoord", 9))
+ withcoords = true;
+ else if (!strncasecmp(arg, "withgeojsonbound", 16))
+ withgeojsonbounds = true;
+ else if (!strncasecmp(arg, "withgeojsoncollection", 21))
+ withgeojsoncollection = true;
+ else if (!strncasecmp(arg, "withgeo", 7) ||
+ !strcasecmp(arg, "geojson") || !strcasecmp(arg, "json") ||
+ !strcasecmp(arg, "withjson"))
+ withgeojson = true;
+ else if (!strncasecmp(arg, "noprop", 6) ||
+ !strncasecmp(arg, "withoutprop", 11))
+ noproperties = true;
+ else if (!strncasecmp(arg, "asc", 3) ||
+ !strncasecmp(arg, "sort", 4))
+ sort = SORT_ASC;
+ else if (!strncasecmp(arg, "desc", 4))
+ sort = SORT_DESC;
+ else {
+ addReply(c, shared.syntaxerr);
+ return;
+ }
+ }
+ }
+
+ bool withgeo = withgeojsonbounds || withgeojsoncollection || withgeojson;
+
+ /* Get all neighbor geohash boxes for our radius search */
+ GeoHashRadius georadius =
+ geohashGetAreasByRadiusWGS84(latlong[0], latlong[1], radius_meters);
+
+#ifdef DEBUG
+ printf("Searching with step size: %d\n", georadius.hash.step);
+#endif
+ /* {Lat, Long} = {y, x} */
+ double y = latlong[0];
+ double x = latlong[1];
+
+ /* Search the zset for all matching points */
+ list *found_matches =
+ membersOfAllNeighbors(zobj, georadius, x, y, radius_meters);
+
+ /* If no matching results, the user gets an empty reply. */
+ if (!found_matches) {
+ addReply(c, shared.emptymultibulk);
+ return;
+ }
+
+ long result_length = listLength(found_matches);
+ 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++;
+
+ if (withgeojson)
+ option_length++;
+
+ if (withgeojsonbounds)
+ 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, result_length + withgeojsoncollection);
+
+ /* Iterate over results, populate struct used for sorting and result sending
+ */
+ listIter li;
+ listRewind(found_matches, &li);
+ struct geojsonPoint 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 geojsonPoint 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);
+ } else if (sort == SORT_DESC) {
+ qsort(gp, result_length, sizeof(*gp), sort_gp_desc);
+ }
+
+ /* Finally send results back to the caller */
+ for (int i = 0; i < result_length; i++) {
+ struct zipresult *zr = gp[i].userdata;
+
+ /* 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);
+ if (withgeo && !noproperties)
+ gp[i].member = sdscatprintf(sdsempty(), "%llu", zr->val.v);
+ break;
+ case ZR_STRING:
+ addReplyBulkCBuffer(c, zr->val.s, sdslen(zr->val.s));
+ if (withgeo && !noproperties)
+ gp[i].member = sdsdup(zr->val.s);
+ break;
+ }
+
+ if (withdist)
+ addReplyDoubleNicer(c, gp[i].dist);
+
+ if (withhash)
+ addReplyLongLong(c, zr->score);
+
+ if (withcoords) {
+ addReplyMultiBulkLen(c, 2);
+ addReplyDouble(c, gp[i].latitude);
+ addReplyDouble(c, gp[i].longitude);
+ }
+
+ if (withgeojson)
+ latLongToGeojsonAndReply(c, gp + i, units);
+
+ if (withgeojsonbounds)
+ decodeGeohashToGeojsonBoundsAndReply(c, zr->score, gp + i);
+ }
+
+ if (withgeojsoncollection)
+ replyGeojsonCollection(c, gp, result_length, units);
+
+ if (withgeo && !noproperties)
+ for (int i = 0; i < result_length; i++)
+ sdsfree(gp[i].member);
+
+ listRelease(found_matches);
+}
+
+void geoRadiusCommand(redisClient *c) {
+ /* args 0-5: ["georadius", key, lat, long, radius, units];
+ * optionals: [withdist, withcoords, asc|desc] */
+ geoRadiusGeneric(c, RADIUS_COORDS);
+}
+
+void geoRadiusByMemberCommand(redisClient *c) {
+ /* args 0-4: ["georadius", key, compare-against-member, radius, units];
+ * optionals: [withdist, withcoords, asc|desc] */
+ geoRadiusGeneric(c, RADIUS_MEMBER);
+}
+
+void geoDecodeCommand(redisClient *c) {
+ /* args 0-1: ["geodecode", geohash];
+ * optional: [geojson] */
+
+ GeoHashBits geohash;
+ if (getLongLongFromObjectOrReply(c, c->argv[1], (long long *)&geohash.bits,
+ NULL) != REDIS_OK)
+ return;
+
+ bool withgeojson = false;
+ if (c->argc == 3)
+ withgeojson = true;
+
+ GeoHashArea area;
+ geohash.step = GEO_STEP_MAX;
+ geohashDecodeWGS84(geohash, &area);
+
+ double y = (area.latitude.min + area.latitude.max) / 2;
+ double x = (area.longitude.min + area.longitude.max) / 2;
+
+ /* Returning three nested replies */
+ addReplyMultiBulkLen(c, 3 + withgeojson * 2);
+
+ /* First, the minimum corner */
+ addReplyMultiBulkLen(c, 2);
+ addReplyDouble(c, area.latitude.min);
+ addReplyDouble(c, area.longitude.min);
+
+ /* Next, the maximum corner */
+ addReplyMultiBulkLen(c, 2);
+ addReplyDouble(c, area.latitude.max);
+ addReplyDouble(c, area.longitude.max);
+
+ /* Last, the averaged center of this bounding box */
+ addReplyMultiBulkLen(c, 2);
+ addReplyDouble(c, y);
+ addReplyDouble(c, x);
+
+ if (withgeojson) {
+ struct geojsonPoint gp = { .latitude = y,
+ .longitude = x,
+ .member = NULL };
+
+ /* Return geojson Feature Point */
+ latLongToGeojsonAndReply(c, &gp, NULL);
+
+ /* Return geojson Feature Polygon */
+ decodeGeohashToGeojsonBoundsAndReply(c, geohash.bits, &gp);
+ }
+}
+
+void geoEncodeCommand(redisClient *c) {
+ /* args 0-2: ["geoencode", lat, long];
+ * optionals: [radius, units]
+ * - AND / OR -
+ * optional: [geojson] */
+
+ bool withgeojson = false;
+ for (int i = 3; i < c->argc; i++) {
+ char *arg = c->argv[i]->ptr;
+ if (!strncasecmp(arg, "withgeo", 7) || !strcasecmp(arg, "geojson") ||
+ !strcasecmp(arg, "json") || !strcasecmp(arg, "withjson")) {
+ withgeojson = true;
+ break;
+ }
+ }
+
+ double radius_meters = 0;
+ if (c->argc >= 5) {
+ if ((radius_meters = extractDistanceOrReply(c, c->argv + 3, NULL)) <
+ 0) {
+ return;
+ }
+ } else if (c->argc == 4 && !withgeojson) {
+ addReplyError(c, "must provide units when asking for radius encode");
+ return;
+ }
+
+ double latlong[2];
+ if (!extractLatLongOrReply(c, c->argv + 1, latlong))
+ return;
+
+ /* Encode lat/long into our geohash */
+ GeoHashBits geohash;
+ uint8_t step = geohashEstimateStepsByRadius(radius_meters);
+ geohashEncodeWGS84(latlong[0], latlong[1], step, &geohash);
+
+ /* Align the hash to a valid 52-bit integer based on step size */
+ GeoHashFix52Bits bits = geohashAlign52Bits(geohash);
+
+/* Decode the hash so we can return its bounding box */
+#ifdef DEBUG
+ printf("Decoding with step size: %d\n", geohash.step);
+#endif
+ GeoHashArea area;
+ geohashDecodeWGS84(geohash, &area);
+
+ double y = (area.latitude.min + area.latitude.max) / 2;
+ double x = (area.longitude.min + area.longitude.max) / 2;
+
+ /* Return four nested multibulk replies with optional geojson returns */
+ addReplyMultiBulkLen(c, 4 + withgeojson * 2);
+
+ /* Return the binary geohash we calculated as 52-bit integer */
+ addReplyLongLong(c, bits);
+
+ /* Return the minimum corner */
+ addReplyMultiBulkLen(c, 2);
+ addReplyDouble(c, area.latitude.min);
+ addReplyDouble(c, area.longitude.min);
+
+ /* Return the maximum corner */
+ addReplyMultiBulkLen(c, 2);
+ addReplyDouble(c, area.latitude.max);
+ addReplyDouble(c, area.longitude.max);
+
+ /* Return the averaged center */
+ addReplyMultiBulkLen(c, 2);
+ addReplyDouble(c, y);
+ addReplyDouble(c, x);
+
+ if (withgeojson) {
+ struct geojsonPoint gp = { .latitude = y,
+ .longitude = x,
+ .member = NULL };
+
+ /* Return geojson Feature Point */
+ latLongToGeojsonAndReply(c, &gp, NULL);
+
+ /* Return geojson Feature Polygon (bounding box for this step size) */
+ /* We don't use the helper function here because we can't re-calculate
+ * the area if we have a non-GEO_STEP_MAX step size. */
+ sds geojson = geojsonBoxToPolygonFeature(
+ area.latitude.min, area.longitude.min, area.latitude.max,
+ area.longitude.max, gp.set, gp.member);
+ addReplyBulkCBuffer(c, geojson, sdslen(geojson));
+ sdsfree(geojson);
+ }
+}
diff --git a/src/geo.h b/src/geo.h
new file mode 100644
index 000000000..f82071663
--- /dev/null
+++ b/src/geo.h
@@ -0,0 +1,12 @@
+#ifndef __GEO_H__
+#define __GEO_H__
+
+#include "redis.h"
+
+void geoEncodeCommand(redisClient *c);
+void geoDecodeCommand(redisClient *c);
+void geoRadiusByMemberCommand(redisClient *c);
+void geoRadiusCommand(redisClient *c);
+void geoAddCommand(redisClient *c);
+
+#endif
diff --git a/src/geojson.c b/src/geojson.c
new file mode 100644
index 000000000..bb0befc95
--- /dev/null
+++ b/src/geojson.c
@@ -0,0 +1,265 @@
+/*
+ * Copyright (c) 2014, Matt Stancliff <matt@genges.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 "geojson.h"
+
+#define L server.lua
+
+/* ====================================================================
+ * The Encoder
+ * ==================================================================== */
+static sds jsonEncode() {
+ /* When entering this function, stack is: [1:[geojson table to encode]] */
+ lua_getglobal(L, "cjson");
+ lua_getfield(L, -1, "encode");
+
+ /* Stack is now: [1:[geojson table], 2:'cjson', 3:'encode'] */
+
+ /* Move current top ('encode') to bottom of stack */
+ lua_insert(L, 1);
+
+ /* Move current top ('cjson') to bottom of stack so we can 'cjson.encode' */
+ lua_insert(L, 1);
+
+ /* Stack is now: [1:'cjson', 2:'encode', 3:[table of geojson to encode]] */
+
+ /* Call cjson.encode on the element above it on the stack;
+ * obtain one return value */
+ if (lua_pcall(L, 1, 1, 0) != 0)
+ redisLog(REDIS_WARNING, "Could not encode geojson: %s",
+ lua_tostring(L, -1));
+
+ sds geojson = sdsnew(lua_tostring(L, -1));
+
+ /* We're done. Remove entire stack. Drop mic. Walk away. */
+ lua_pop(L, lua_gettop(L));
+
+ /* Return sds the caller must sdsfree() on their own */
+ return geojson;
+}
+
+/* ====================================================================
+ * The Lua Helpers
+ * ==================================================================== */
+static inline void luaCreateFieldFromPrevious(const char *field) {
+ lua_setfield(L, -2, field);
+}
+
+static inline void luaCreateFieldStr(const char *field, const char *value) {
+ lua_pushstring(L, value);
+ luaCreateFieldFromPrevious(field);
+}
+
+/* Creates [Lat, Long] array attached to "coordinates" key */
+static void luaCreateCoordinates(const double x, const double y) {
+ /* Create array table with two elements */
+ lua_createtable(L, 2, 0);
+
+ lua_pushnumber(L, x);
+ lua_rawseti(L, -2, 1);
+ lua_pushnumber(L, y);
+ lua_rawseti(L, -2, 2);
+}
+
+static void luaCreatePropertyNull(void) {
+ /* Create empty table and give it a name. This is a json {} value. */
+ lua_createtable(L, 0, 0);
+ luaCreateFieldFromPrevious("properties");
+}
+
+static void _luaCreateProperties(const char *k1, const char *v1, const char *k2,
+ const char *v2, const int noclose) {
+ /* we may add additional properties outside of here, so newtable instead of
+ * fixed-size createtable */
+ lua_newtable(L);
+
+ luaCreateFieldStr(k1, v1);
+ luaCreateFieldStr(k2, v2);
+
+ if (!noclose)
+ luaCreateFieldFromPrevious("properties");
+}
+
+static void luaCreateProperties(const char *k1, const char *v1, const char *k2,
+ const char *v2) {
+ _luaCreateProperties(k1, v1, k2, v2, 0);
+}
+
+/* ====================================================================
+ * The Lua Aggregation Helpers
+ * ==================================================================== */
+static void attachProperties(const char *set, const char *member) {
+ if (member)
+ luaCreateProperties("set", set, "member", member);
+ else
+ luaCreatePropertyNull();
+}
+
+static void attachPropertiesWithDist(const char *set, const char *member,
+ double dist, const char *units) {
+ if (member) {
+ _luaCreateProperties("set", set, "member", member, 1);
+ if (units) {
+ /* Add units then distance. After encoding it comes
+ * out as distance followed by units in the json. */
+ lua_pushstring(L, units);
+ luaCreateFieldFromPrevious("units");
+ lua_pushnumber(L, dist);
+ luaCreateFieldFromPrevious("distance");
+ }
+
+ /* We requested to leave the properties table open, but now we
+ * are done and can close it. */
+ luaCreateFieldFromPrevious("properties");
+ } else {
+ luaCreatePropertyNull();
+ }
+}
+
+static void createGeometryPoint(const double x, const double y) {
+ lua_createtable(L, 0, 2);
+
+ /* coordinates = [x, y] */
+ luaCreateCoordinates(x, y);
+ luaCreateFieldFromPrevious("coordinates");
+
+ /* type = Point */
+ luaCreateFieldStr("type", "Point");
+
+ /* geometry = (coordinates = [x, y]) */
+ luaCreateFieldFromPrevious("geometry");
+}
+
+static void createGeometryBox(const double x1, const double y1, const double x2,
+ const double y2) {
+ lua_createtable(L, 0, 2);
+
+ /* Result = [[[x1,y1],[x2,y1],[x2,y2],[x1,y2], [x1,y1]] */
+ /* The end coord is the start coord to make a closed polygon */
+ lua_createtable(L, 1, 0);
+ lua_createtable(L, 5, 0);
+
+ /* Bottom left */
+ luaCreateCoordinates(x1, y1);
+ lua_rawseti(L, -2, 1);
+
+ /* Top Left */
+ luaCreateCoordinates(x2, y1);
+ lua_rawseti(L, -2, 2);
+
+ /* Top Right */
+ luaCreateCoordinates(x2, y2);
+ lua_rawseti(L, -2, 3);
+
+ /* Bottom Right */
+ luaCreateCoordinates(x1, y2);
+ lua_rawseti(L, -2, 4);
+
+ /* Bottom Left (Again) */
+ luaCreateCoordinates(x1, y1);
+ lua_rawseti(L, -2, 5);
+
+ /* Set the outer array of our inner array of the inner coords */
+ lua_rawseti(L, -2, 1);
+
+ /* Bundle those together in coordinates: [a, b, c, d] */
+ luaCreateFieldFromPrevious("coordinates");
+
+ /* Add type field */
+ luaCreateFieldStr("type", "Polygon");
+
+ luaCreateFieldFromPrevious("geometry");
+}
+
+static void createFeature() {
+ /* Features have three fields: type, geometry, and properties */
+ lua_createtable(L, 0, 3);
+
+ luaCreateFieldStr("type", "Feature");
+
+ /* You must call attachProperties on your own */
+}
+
+static void createCollection(size_t size) {
+ /* FeatureCollections have two fields: type and features */
+ lua_createtable(L, 0, 2);
+
+ luaCreateFieldStr("type", "FeatureCollection");
+}
+
+static void pointsToCollection(const struct geojsonPoint *pts, const size_t len,
+ const char *units) {
+ createCollection(len);
+
+ lua_createtable(L, len, 0);
+ for (int i = 0; i < len; i++) {
+ createFeature();
+ createGeometryPoint(pts[i].longitude, pts[i].latitude); /* x, y */
+ attachPropertiesWithDist(pts[i].set, pts[i].member, pts[i].dist, units);
+ lua_rawseti(L, -2, i + 1); /* Attach this Feature to "features" array */
+ }
+ luaCreateFieldFromPrevious("features");
+}
+
+static void latLongToPointFeature(const double latitude,
+ const double longitude) {
+ createFeature();
+ createGeometryPoint(longitude, latitude); /* geojson is: x,y */
+}
+
+static void squareToPolygonFeature(const double x1, const double y1,
+ const double x2, const double y2) {
+ createFeature();
+ createGeometryBox(x1, y1, x2, y2);
+}
+
+/* ====================================================================
+ * The Interface Functions
+ * ==================================================================== */
+sds geojsonFeatureCollection(const struct geojsonPoint *pts, const size_t len,
+ const char *units) {
+ pointsToCollection(pts, len, units);
+ return jsonEncode();
+}
+
+sds geojsonLatLongToPointFeature(const double latitude, const double longitude,
+ const char *set, const char *member,
+ const double dist, const char *units) {
+ latLongToPointFeature(latitude, longitude);
+ attachPropertiesWithDist(set, member, dist, units);
+ return jsonEncode();
+}
+
+sds geojsonBoxToPolygonFeature(const double y1, const double x1,
+ const double y2, const double x2,
+ const char *set, const char *member) {
+ squareToPolygonFeature(x1, y1, x2, y2);
+ attachProperties(set, member);
+ return jsonEncode();
+}
diff --git a/src/geojson.h b/src/geojson.h
new file mode 100644
index 000000000..55993beae
--- /dev/null
+++ b/src/geojson.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright (c) 2014, Matt Stancliff <matt@genges.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.
+ */
+
+#ifndef __GEOJSON_H__
+#define __GEOJSON_H__
+
+#include "redis.h"
+#include "geohash_helper.h"
+
+struct geojsonPoint {
+ double latitude;
+ double longitude;
+ double dist;
+ char *set;
+ char *member;
+ void *userdata;
+};
+
+sds geojsonLatLongToPointFeature(const double latitude, const double longitude,
+ const char *set, const char *member,
+ const double dist, const char *units);
+sds geojsonBoxToPolygonFeature(const double x1, const double y1,
+ const double x2, const double y2,
+ const char *set, const char *member);
+sds geojsonFeatureCollection(const struct geojsonPoint *pts, const size_t len,
+ const char *units);
+
+#endif
diff --git a/src/redis.c b/src/redis.c
index 09653119a..359ccb35e 100644
--- a/src/redis.c
+++ b/src/redis.c
@@ -282,6 +282,11 @@ struct redisCommand redisCommandTable[] = {
{"bitpos",bitposCommand,-3,"r",0,NULL,1,1,1,0,0},
{"wait",waitCommand,3,"rs",0,NULL,0,0,0,0,0},
{"command",commandCommand,0,"rlt",0,NULL,0,0,0,0,0},
+ {"geoadd",geoAddCommand,-5,"wm",0,NULL,1,1,1,0,0},
+ {"georadius",geoRadiusCommand,-6,"r",0,NULL,1,1,1,0,0},
+ {"georadiusbymember",geoRadiusByMemberCommand,-5,"r",0,NULL,1,1,1,0,0},
+ {"geoencode",geoEncodeCommand,-3,"r",0,NULL,0,0,0,0,0},
+ {"geodecode",geoDecodeCommand,-2,"r",0,NULL,0,0,0,0,0},
{"pfselftest",pfselftestCommand,1,"r",0,NULL,0,0,0,0,0},
{"pfadd",pfaddCommand,-2,"wmF",0,NULL,1,1,1,0,0},
{"pfcount",pfcountCommand,-2,"r",0,NULL,1,1,1,0,0},
diff --git a/src/redis.h b/src/redis.h
index 53f3967d7..2344c9eba 100644
--- a/src/redis.h
+++ b/src/redis.h
@@ -1556,6 +1556,11 @@ void bitcountCommand(redisClient *c);
void bitposCommand(redisClient *c);
void replconfCommand(redisClient *c);
void waitCommand(redisClient *c);
+void geoEncodeCommand(redisClient *c);
+void geoDecodeCommand(redisClient *c);
+void geoRadiusByMemberCommand(redisClient *c);
+void geoRadiusCommand(redisClient *c);
+void geoAddCommand(redisClient *c);
void pfselftestCommand(redisClient *c);
void pfaddCommand(redisClient *c);
void pfcountCommand(redisClient *c);
@@ -1588,4 +1593,8 @@ 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/t_zset.c b/src/t_zset.c
index dbc561a93..b900a9ccb 100644
--- a/src/t_zset.c
+++ b/src/t_zset.c
@@ -213,7 +213,7 @@ static int zslValueGteMin(double value, zrangespec *spec) {
return spec->minex ? (value > spec->min) : (value >= spec->min);
}
-static int zslValueLteMax(double value, zrangespec *spec) {
+int zslValueLteMax(double value, zrangespec *spec) {
return spec->maxex ? (value < spec->max) : (value <= spec->max);
}
diff --git a/src/zset.c b/src/zset.c
new file mode 100644
index 000000000..2412a1c44
--- /dev/null
+++ b/src/zset.c
@@ -0,0 +1,185 @@
+#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
+ * ==================================================================== */
+
+/* zset access is mostly a copy/paste from zscoreCommand() */
+bool zsetScore(robj *zobj, robj *member, double *score) {
+ if (!zobj || !member)
+ return false;
+
+ if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
+ if (zzlFind(zobj->ptr, member, score) == NULL)
+ return false;
+ } else if (zobj->encoding == REDIS_ENCODING_SKIPLIST) {
+ zset *zs = zobj->ptr;
+ dictEntry *de;
+
+ member = tryObjectEncoding(member);
+ de = dictFind(zs->dict, member);
+ if (de != NULL) {
+ *score = *(double *)dictGetVal(de);
+ } else
+ return false;
+ } else {
+ return false;
+ }
+ return true;
+}
+
+/* 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
new file mode 100644
index 000000000..6a78d1ed2
--- /dev/null
+++ b/src/zset.h
@@ -0,0 +1,31 @@
+#ifndef __ZSET_H__
+#define __ZSET_H__
+
+#include "redis.h"
+#include <stdbool.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 */
+bool zsetScore(robj *zobj, robj *member, double *score);
+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
diff --git a/tests/unit/geo.tcl b/tests/unit/geo.tcl
new file mode 100644
index 000000000..015fcf87c
--- /dev/null
+++ b/tests/unit/geo.tcl
@@ -0,0 +1,53 @@
+start_server {tags {"geo"}} {
+ test {GEOADD create} {
+ r geoadd nyc 40.747533 -73.9454966 "lic market"
+ } {1}
+
+ test {GEOADD update} {
+ r geoadd nyc 40.747533 -73.9454966 "lic market"
+ } {0}
+
+ test {GEOADD multi add} {
+ r geoadd nyc 40.7648057 -73.9733487 "central park n/q/r" 40.7362513 -73.9903085 "union square" 40.7126674 -74.0131604 "wtc one" 40.6428986 -73.7858139 "jfk" 40.7498929 -73.9375699 "q4" 40.7480973 -73.9564142 4545
+ } {6}
+
+ test {Check geoset values} {
+ r zrange nyc 0 -1 withscores
+ } {{wtc one} 1791873972053020 {union square} 1791875485187452 {central park n/q/r} 1791875761332224 4545 1791875796750882 {lic market} 1791875804419201 q4 1791875830079666 jfk 1791895905559723}
+
+ test {GEORADIUS simple (sorted)} {
+ r georadius nyc 40.7598464 -73.9798091 3 km ascending
+ } {{central park n/q/r} 4545 {union square}}
+
+ test {GEORADIUS withdistance (sorted)} {
+ r georadius nyc 40.7598464 -73.9798091 3 km withdistance ascending
+ } {{{central park n/q/r} 0.78} {4545 2.37} {{union square} 2.77}}
+
+ test {GEORADIUSBYMEMBER simple (sorted)} {
+ r georadiusbymember nyc "wtc one" 7 km
+ } {{wtc one} {union square} {central park n/q/r} 4545 {lic market}}
+
+ test {GEORADIUSBYMEMBER simple (sorted, json)} {
+ r georadiusbymember nyc "wtc one" 7 km withgeojson
+ } {{{wtc one} {{"type":"Feature","geometry":{"type":"Point","coordinates":[-74.01316255331,40.712667181451]},"properties":{"distance":0,"member":"wtc one","units":"km","set":"nyc"}}}}\
+ {{union square} {{"type":"Feature","geometry":{"type":"Point","coordinates":[-73.990310132504,40.736250227118]},"properties":{"distance":3.2543954573354,"member":"union square","units":"km","set":"nyc"}}}}\
+ {{central park n/q/r} {{"type":"Feature","geometry":{"type":"Point","coordinates":[-73.973347842693,40.764806395699]},"properties":{"distance":6.7000029092796,"member":"central park n\/q\/r","units":"km","set":"nyc"}}}}\
+ {4545 {{"type":"Feature","geometry":{"type":"Point","coordinates":[-73.956412374973,40.748097513816]},"properties":{"distance":6.1975173818008,"member":"4545","units":"km","set":"nyc"}}}}\
+ {{lic market} {{"type":"Feature","geometry":{"type":"Point","coordinates":[-73.945495784283,40.747532270998]},"properties":{"distance":6.8968709532081,"member":"lic market","units":"km","set":"nyc"}}}}}
+
+ test {GEORADIUSBYMEMBER withdistance (sorted)} {
+ r georadiusbymember nyc "wtc one" 7 km withdist
+ } {{{wtc one} 0.00} {{union square} 3.25} {{central park n/q/r} 6.70} {4545 6.20} {{lic market} 6.90}}
+
+ test {GEOENCODE simple} {
+ r geoencode 41.2358883 1.8063239
+ } {3471579339700058 {41.235888125243704 1.8063229322433472}\
+ {41.235890659964866 1.806328296661377}\
+ {41.235889392604285 1.8063256144523621}}
+
+ test {GEODECODE simple} {
+ r geodecode 3471579339700058
+ } {{41.235888125243704 1.8063229322433472}\
+ {41.235890659964866 1.806328296661377}\
+ {41.235889392604285 1.8063256144523621}}
+}
View Lorry Controller Status