null+****@clear*****
null+****@clear*****
2010年 8月 9日 (月) 14:21:17 JST
Kouhei Sutou 2010-08-09 05:21:17 +0000 (Mon, 09 Aug 2010)
New Revision: be60ac31368122b5a2b91597470c28f8e6e7d237
Log:
move grn_table_sort_geo() to geo.c.
Modified files:
lib/db.c
lib/geo.c
lib/geo.h
Modified: lib/db.c (+1 -452)
===================================================================
--- lib/db.c 2010-08-09 01:43:43 +0000 (bef5a31)
+++ lib/db.c 2010-08-09 05:21:17 +0000 (90d5f09)
@@ -6502,457 +6502,6 @@ range_is_idp(grn_obj *obj)
return 0;
}
-#define GEO_RESOLUTION 3600000
-#define GEO_RADIOUS 6357303
-#define GEO_BES_C1 6334834
-#define GEO_BES_C2 6377397
-#define GEO_BES_C3 0.006674
-#define GEO_GRS_C1 6335439
-#define GEO_GRS_C2 6378137
-#define GEO_GRS_C3 0.006694
-#define GEO_INT2RAD(x) ((M_PI / (GEO_RESOLUTION * 180)) * (x))
-
-typedef struct {
- grn_id id;
- double d;
-} geo_entry;
-
-static int
-compute_diff_bit(uint8_t *geo_key1, uint8_t *geo_key2)
-{
- int i, diff_bit = 0;
-
- for (i = 0; i < sizeof(grn_geo_point); i++) {
- if (geo_key1[i] == geo_key2[i]) {
- continue;
- }
-
- if ((geo_key1[i] & 0xc0) != (geo_key2[i] & 0xc0)) {
- diff_bit = 0;
- break;
- } else if ((geo_key1[i] & 0x30) != (geo_key2[i] & 0x30)) {
- diff_bit = 2;
- break;
- } else if ((geo_key1[i] & 0x0c) != (geo_key2[i] & 0x0c)) {
- diff_bit = 4;
- break;
- } else if ((geo_key1[i] & 0x03) != (geo_key2[i] & 0x03)) {
- diff_bit = 6;
- break;
- }
- }
-
- return i * 8 + diff_bit;
-}
-
-static void
-compute_min_and_max(grn_geo_point *base_point, int diff_bit,
- grn_geo_point *geo_min, grn_geo_point *geo_max)
-{
- int diff_byte, diff_bit_mask;
- uint8_t geo_key_base[sizeof(grn_geo_point)];
- uint8_t geo_key_min[sizeof(grn_geo_point)];
- uint8_t geo_key_max[sizeof(grn_geo_point)];
-
- diff_byte = diff_bit / 8;
- diff_bit_mask = 0xff >> (diff_bit % 8);
- grn_gton(geo_key_base, base_point, sizeof(grn_geo_point));
-
- memcpy(geo_key_min, geo_key_base, diff_byte + 1);
- geo_key_min[diff_byte] &= ~diff_bit_mask;
- memset(geo_key_min + diff_byte + 1, 0,
- sizeof(grn_geo_point) - diff_byte - 1);
-
- memcpy(geo_key_max, geo_key_base, diff_byte + 1);
- geo_key_max[diff_byte] |= diff_bit_mask;
- memset(geo_key_max + diff_byte + 1, 0xff,
- sizeof(grn_geo_point) - diff_byte - 1);
-
- grn_ntog((uint8_t *)geo_min, geo_key_min, sizeof(grn_geo_point));
- grn_ntog((uint8_t *)geo_max, geo_key_max, sizeof(grn_geo_point));
-}
-
-static int
-grn_table_sort_geo_detect_far_point(grn_ctx *ctx, grn_obj *table, grn_obj *index,
- grn_pat *pat, geo_entry *entries,
- grn_pat_cursor *pc, int n, int accessorp,
- grn_geo_point *base_point,
- double *d_far, int *diff_bit)
-{
- int i = 0, diff_bit_prev, diff_bit_current;
- grn_id tid;
- geo_entry *ep, *p;
- double d;
- uint8_t geo_key_prev[sizeof(grn_geo_point)];
- uint8_t geo_key_curr[sizeof(grn_geo_point)];
- grn_geo_point point;
-
- *d_far = 0.0;
- grn_gton(geo_key_curr, base_point, sizeof(grn_geo_point));
- *diff_bit = sizeof(grn_geo_point) * 8;
- diff_bit_current = sizeof(grn_geo_point) * 8;
- memcpy(&point, base_point, sizeof(grn_geo_point));
- ep = entries;
- while ((tid = grn_pat_cursor_next(ctx, pc))) {
- grn_ii_cursor *ic = grn_ii_cursor_open(ctx, (grn_ii *)index, tid, 0, 0, 1, 0);
- if (ic) {
- grn_ii_posting *posting;
- grn_gton(geo_key_prev, &point, sizeof(grn_geo_point));
- grn_pat_get_key(ctx, pat, tid, &point, sizeof(grn_geo_point));
- grn_gton(geo_key_curr, &point, sizeof(grn_geo_point));
- d = grn_geo_distance_raw(ctx, base_point, &point);
-
- diff_bit_prev = diff_bit_current;
- diff_bit_current = compute_diff_bit(geo_key_curr, geo_key_prev);
- if (diff_bit_current < diff_bit_prev && *diff_bit > diff_bit_current) {
- if (i == n) {
- break;
- }
- *diff_bit = diff_bit_current;
- }
-
- if (d > *d_far) {
- *d_far = d;
- }
- while ((posting = grn_ii_cursor_next(ctx, ic))) {
- grn_id rid = accessorp
- ? grn_table_get(ctx, table, &posting->rid, sizeof(grn_id))
- : posting->rid;
- if (rid) {
- for (p = ep; entries < p && p[-1].d > d; p--) {
- p->id = p[-1].id;
- p->d = p[-1].d;
- }
- p->id = rid;
- p->d = d;
- if (i < n) {
- ep++;
- i++;
- }
- }
- }
- grn_ii_cursor_close(ctx, ic);
- }
- }
-
- return i;
-}
-
-typedef struct
-{
- grn_geo_point key;
- int key_size;
-} mesh_entry;
-
-/* #define GEO_SORT_DEBUG */
-
-#ifdef GEO_SORT_DEBUG
-#include <stdio.h>
-
-static void
-inspect_mesh_entry(grn_ctx *ctx, mesh_entry *entries, int n)
-{
- mesh_entry *entry;
- grn_geo_point min, max;
-
- entry = entries + n;
- printf("mesh: %d:%d\n", n, entry->key_size);
-
- printf("key: ");
- grn_p_geo_point(ctx, &(entry->key));
-
- compute_min_and_max(&(entry->key), entry->key_size, &min, &max);
- printf("min: ");
- grn_p_geo_point(ctx, &min);
- printf("max: ");
- grn_p_geo_point(ctx, &max);
-}
-
-static void
-inspect_tid(grn_ctx *ctx, grn_id tid, grn_geo_point *point,
- double x, double y, double d)
-{
- printf("tid: %d:%g (%g,%g)", tid, d, x, y);
- grn_p_geo_point(ctx, point);
-}
-#else
-# define inspect_mesh_entry(...)
-# define inspect_tid(...)
-#endif
-
-typedef enum {
- MESH_LEFT_TOP,
- MESH_RIGHT_TOP,
- MESH_RIGHT_BOTTOM,
- MESH_LEFT_BOTTOM
-} mesh_position;
-
-static int
-grn_table_sort_geo_collect_points(grn_ctx *ctx, grn_obj *table, grn_obj *index,
- grn_pat *pat,
- geo_entry *entries, int n_entries,
- int n, int accessorp,
- grn_geo_point *base_point,
- double d_far, int diff_bit)
-{
- int n_meshes;
- grn_geo_point geo_base, geo_min, geo_max;
- mesh_entry meshes[19];
- int lat_diff, lng_diff;
- double d;
- geo_entry *ep, *p;
- mesh_position position;
-
- compute_min_and_max(base_point, diff_bit, &geo_min, &geo_max);
-
- lat_diff = geo_max.latitude - geo_min.latitude + 1;
- lng_diff = geo_max.longitude - geo_min.longitude + 1;
- if (base_point->latitude >= geo_min.latitude + lat_diff / 2) {
- geo_base.latitude = geo_max.latitude + 1;
- if (base_point->longitude >= geo_min.longitude + lng_diff / 2) {
- geo_base.longitude = geo_max.longitude + 1;
- position = MESH_LEFT_BOTTOM;
- } else {
- geo_base.longitude = geo_min.longitude;
- position = MESH_RIGHT_BOTTOM;
- }
- } else {
- geo_base.latitude = geo_min.latitude;
- if (base_point->longitude >= geo_min.longitude + lng_diff / 2) {
- geo_base.longitude = geo_max.longitude + 1;
- position = MESH_LEFT_TOP;
- } else {
- geo_base.longitude = geo_min.longitude;
- position = MESH_RIGHT_TOP;
- }
- }
- /*
- base_point: b
- geo_min: i
- geo_max: a
- geo_base: x: must be at the left bottom in the top right mesh.
-
- e.g.: base_point is at the left bottom mesh case:
- +------+------+
- | | |
- | |x |
- ^+------+------+
- || a| |
- lng_diff || b | |
- \/i------+------+
- <------>
- lat_diff
-
- grn_min + lat_diff -> the right mesh.
- grn_min + lng_diff -> the top mesh.
- */
-#ifdef GEO_SORT_DEBUG
- grn_p_geo_point(ctx, base_point);
- printf("base: ");
- grn_p_geo_point(ctx, &geo_base);
- printf("min: ");
- grn_p_geo_point(ctx, geo_min);
- printf("max: ");
- grn_p_geo_point(ctx, geo_max);
- printf("diff: %d (%d, %d)\n", diff_bit, lat_diff, lng_diff);
-#endif
-
- n_meshes = 0;
-
-#define add_mesh(lat_diff_,lng_diff_,key_size_)\
- meshes[n_meshes].key.latitude = geo_base.latitude + (lat_diff_);\
- meshes[n_meshes].key.longitude = geo_base.longitude + (lng_diff_);\
- meshes[n_meshes].key_size = key_size_;\
- n_meshes++;
-
- if (position != MESH_LEFT_TOP) {
- add_mesh(0, -lng_diff, diff_bit);
- }
- if (position != MESH_RIGHT_TOP) {
- add_mesh(0, 0, diff_bit);
- }
- if (position != MESH_RIGHT_BOTTOM) {
- add_mesh(-lat_diff, 0, diff_bit);
- }
- if (position != MESH_LEFT_BOTTOM) {
- add_mesh(-lat_diff, -lng_diff, diff_bit);
- }
-
-#define add_sub_mesh(lat_diff_cmp,lng_diff_cmp,lat_diff_base,lng_diff_base)\
- meshes[n_meshes].key.latitude = geo_base.latitude + (lat_diff_cmp);\
- meshes[n_meshes].key.longitude = geo_base.longitude + (lng_diff_cmp);\
- d = grn_geo_distance_raw(ctx, base_point, &(meshes[n_meshes].key));\
- if (d < d_far) {\
- add_mesh(lat_diff_base, lng_diff_base, diff_bit + 2);\
- }
-
- /*
- b: base_point
- 1-16: sub meshes. 1-16 are added order.
-
- +---+---+---+---+
- | 1 | 2 | 3 | 4 |
- +---+---+---+---+---+---+
- |16 | | | 5 |
- +---+ | +---+
- |15 | |b | 6 |
- +---+-------+-------+---+
- |14 | | | 7 |
- +---+ base meshes +---+
- |13 | | | 8 |
- +---+---+---+---+---+---+
- |12 |11 |10 | 9 |
- +---+---+---+---+
- */
- add_sub_mesh(lat_diff, -(lng_diff + 1) / 2 - 1,
- lat_diff, -lng_diff);
- add_sub_mesh(lat_diff, -1,
- lat_diff, -(lng_diff + 1) / 2);
- add_sub_mesh(lat_diff, 0,
- lat_diff, 0);
- add_sub_mesh(lat_diff, (lng_diff + 1) / 2,
- lat_diff, (lng_diff + 1) / 2);
-
- add_sub_mesh((lat_diff + 1) / 2, lng_diff,
- (lat_diff + 1) / 2, lng_diff);
- add_sub_mesh(0, lng_diff,
- 0, lng_diff);
- add_sub_mesh(-1, lng_diff,
- -(lat_diff + 1) / 2, lng_diff);
- add_sub_mesh(-(lat_diff + 1) / 2 - 1, lng_diff,
- -lat_diff, lng_diff);
-
- add_sub_mesh(-lat_diff - 1, (lng_diff + 1) / 2,
- -lat_diff * 2, (lng_diff + 1) / 2);
- add_sub_mesh(-lat_diff - 1, 0,
- -lat_diff * 2, 0);
- add_sub_mesh(-lat_diff - 1, -1,
- -lat_diff * 2, -(lng_diff + 1) / 2);
- add_sub_mesh(-lat_diff - 1, -(lng_diff + 1) / 2 - 1,
- -lat_diff * 2, -lng_diff);
-
- add_sub_mesh(-(lat_diff + 1) / 2 - 1, -lng_diff - 1,
- -lat_diff, -lng_diff * 2);
- add_sub_mesh(-1, -lng_diff - 1,
- -(lat_diff + 1) / 2, -lng_diff * 2);
- add_sub_mesh(0, -lng_diff - 1,
- 0, -lng_diff * 2);
- add_sub_mesh((lat_diff + 1) / 2, -lng_diff - 1,
- (lat_diff + 1) / 2, -lng_diff * 2);
-
-#undef add_sub_mesh
-#undef add_mesh
-
- ep = entries + n_entries;
- while (n_meshes--) {
- grn_id tid;
- grn_pat_cursor *pc = grn_pat_cursor_open(ctx, pat,
- &(meshes[n_meshes].key),
- meshes[n_meshes].key_size,
- NULL, 0,
- 0, -1,
- GRN_CURSOR_PREFIX|GRN_CURSOR_SIZE_BY_BIT);
- inspect_mesh_entry(ctx, meshes, n_meshes);
- if (pc) {
- while ((tid = grn_pat_cursor_next(ctx, pc))) {
- grn_ii_cursor *ic = grn_ii_cursor_open(ctx, (grn_ii *)index, tid, 0, 0, 1, 0);
- if (ic) {
- grn_geo_point pos;
- grn_ii_posting *posting;
- grn_pat_get_key(ctx, pat, tid, &pos, sizeof(grn_geo_point));
- d = grn_geo_distance_raw(ctx, base_point, &pos);
- inspect_tid(ctx, tid, &pos, x, y, d);
- while ((posting = grn_ii_cursor_next(ctx, ic))) {
- grn_id rid = accessorp
- ? grn_table_get(ctx, table, &posting->rid, sizeof(grn_id))
- : posting->rid;
- if (rid) {
- for (p = ep; entries < p && p[-1].d > d; p--) {
- p->id = p[-1].id;
- p->d = p[-1].d;
- }
- p->id = rid;
- p->d = d;
- if (n_entries < n) {
- ep++;
- n_entries++;
- }
- }
- }
- grn_ii_cursor_close(ctx, ic);
- }
- }
- grn_pat_cursor_close(ctx, pc);
- }
- }
- return n_entries;
-}
-
-static int
-grn_table_sort_geo(grn_ctx *ctx, grn_obj *table, int offset, int limit,
- grn_obj *result, grn_table_sort_key *keys, int n_keys)
-{
- grn_obj *index;
- int i = 0, e = offset + limit, sid, accessorp = GRN_ACCESSORP(keys->key);
- if (n_keys == 2 && grn_column_index(ctx, keys->key, GRN_OP_LESS, &index, 1, &sid)) {
- grn_id tid;
- grn_obj *arg = keys[1].key;
- grn_pat *pat = (grn_pat *)grn_ctx_at(ctx, index->header.domain);
- grn_id domain = pat->obj.header.domain;
- grn_pat_cursor *pc = grn_pat_cursor_open(ctx, pat, NULL, 0,
- GRN_BULK_HEAD(arg), GRN_BULK_VSIZE(arg),
- 0, -1, GRN_CURSOR_PREFIX);
- if (pc) {
- if (domain != GRN_DB_TOKYO_GEO_POINT && domain != GRN_DB_WGS84_GEO_POINT) {
- while (i < e && (tid = grn_pat_cursor_next(ctx, pc))) {
- grn_ii_cursor *ic = grn_ii_cursor_open(ctx, (grn_ii *)index, tid, 0, 0, 1, 0);
- if (ic) {
- grn_ii_posting *posting;
- while (i < e && (posting = grn_ii_cursor_next(ctx, ic))) {
- if (offset <= i) {
- grn_id *v;
- if (!grn_array_add(ctx, (grn_array *)result, (void **)&v)) { break; }
- *v = posting->rid;
- }
- i++;
- }
- grn_ii_cursor_close(ctx, ic);
- }
- }
- grn_pat_cursor_close(ctx, pc);
- } else {
- geo_entry *entries;
-
- if ((entries = GRN_MALLOC(sizeof(geo_entry) * (e + 1)))) {
- int n, diff_bit;
- double d_far;
- grn_id *v;
- grn_geo_point *base_point;
- geo_entry *ep;
-
- base_point = (grn_geo_point *)GRN_BULK_HEAD(arg);
- n = grn_table_sort_geo_detect_far_point(ctx, table, index, pat,
- entries, pc, e, accessorp,
- base_point,
- &d_far, &diff_bit);
- grn_pat_cursor_close(ctx, pc);
- if (diff_bit > 0) {
- n += grn_table_sort_geo_collect_points(ctx, table, index, pat,
- entries, n, e, accessorp,
- base_point, d_far, diff_bit);
- }
- for (i = 0, ep = entries + offset; i < limit && ep < entries + n; i++, ep++) {
- if (!grn_array_add(ctx, (grn_array *)result, (void **)&v)) { break; }
- *v = ep->id;
- }
- GRN_FREE(entries);
- }
- }
- }
- }
- return i;
-}
-
int
grn_table_sort(grn_ctx *ctx, grn_obj *table, int offset, int limit,
grn_obj *result, grn_table_sort_key *keys, int n_keys)
@@ -6986,7 +6535,7 @@ grn_table_sort(grn_ctx *ctx, grn_obj *table, int offset, int limit,
e = offset + limit;
}
if (keys->flags & GRN_TABLE_SORT_GEO) {
- i = grn_table_sort_geo(ctx, table, offset, limit, result, keys, n_keys);
+ i = grn_geo_table_sort(ctx, table, offset, limit, result, keys, n_keys);
goto exit;
}
if (n_keys == 1 && grn_column_index(ctx, keys->key, GRN_OP_LESS, &index, 1, NULL)) {
Modified: lib/geo.c (+452 -0)
===================================================================
--- lib/geo.c 2010-08-09 01:43:43 +0000 (f1a0d8b)
+++ lib/geo.c 2010-08-09 05:21:17 +0000 (d93ef20)
@@ -20,6 +20,458 @@
#include "geo.h"
#include "ii.h"
#include "db.h"
+#include "pat.h"
+
+#define GEO_RESOLUTION 3600000
+#define GEO_RADIOUS 6357303
+#define GEO_BES_C1 6334834
+#define GEO_BES_C2 6377397
+#define GEO_BES_C3 0.006674
+#define GEO_GRS_C1 6335439
+#define GEO_GRS_C2 6378137
+#define GEO_GRS_C3 0.006694
+#define GEO_INT2RAD(x) ((M_PI / (GEO_RESOLUTION * 180)) * (x))
+
+typedef struct {
+ grn_id id;
+ double d;
+} geo_entry;
+
+static int
+compute_diff_bit(uint8_t *geo_key1, uint8_t *geo_key2)
+{
+ int i, diff_bit = 0;
+
+ for (i = 0; i < sizeof(grn_geo_point); i++) {
+ if (geo_key1[i] == geo_key2[i]) {
+ continue;
+ }
+
+ if ((geo_key1[i] & 0xc0) != (geo_key2[i] & 0xc0)) {
+ diff_bit = 0;
+ break;
+ } else if ((geo_key1[i] & 0x30) != (geo_key2[i] & 0x30)) {
+ diff_bit = 2;
+ break;
+ } else if ((geo_key1[i] & 0x0c) != (geo_key2[i] & 0x0c)) {
+ diff_bit = 4;
+ break;
+ } else if ((geo_key1[i] & 0x03) != (geo_key2[i] & 0x03)) {
+ diff_bit = 6;
+ break;
+ }
+ }
+
+ return i * 8 + diff_bit;
+}
+
+static void
+compute_min_and_max(grn_geo_point *base_point, int diff_bit,
+ grn_geo_point *geo_min, grn_geo_point *geo_max)
+{
+ int diff_byte, diff_bit_mask;
+ uint8_t geo_key_base[sizeof(grn_geo_point)];
+ uint8_t geo_key_min[sizeof(grn_geo_point)];
+ uint8_t geo_key_max[sizeof(grn_geo_point)];
+
+ diff_byte = diff_bit / 8;
+ diff_bit_mask = 0xff >> (diff_bit % 8);
+ grn_gton(geo_key_base, base_point, sizeof(grn_geo_point));
+
+ memcpy(geo_key_min, geo_key_base, diff_byte + 1);
+ geo_key_min[diff_byte] &= ~diff_bit_mask;
+ memset(geo_key_min + diff_byte + 1, 0,
+ sizeof(grn_geo_point) - diff_byte - 1);
+
+ memcpy(geo_key_max, geo_key_base, diff_byte + 1);
+ geo_key_max[diff_byte] |= diff_bit_mask;
+ memset(geo_key_max + diff_byte + 1, 0xff,
+ sizeof(grn_geo_point) - diff_byte - 1);
+
+ grn_ntog((uint8_t *)geo_min, geo_key_min, sizeof(grn_geo_point));
+ grn_ntog((uint8_t *)geo_max, geo_key_max, sizeof(grn_geo_point));
+}
+
+static int
+grn_table_sort_geo_detect_far_point(grn_ctx *ctx, grn_obj *table, grn_obj *index,
+ grn_pat *pat, geo_entry *entries,
+ grn_pat_cursor *pc, int n, int accessorp,
+ grn_geo_point *base_point,
+ double *d_far, int *diff_bit)
+{
+ int i = 0, diff_bit_prev, diff_bit_current;
+ grn_id tid;
+ geo_entry *ep, *p;
+ double d;
+ uint8_t geo_key_prev[sizeof(grn_geo_point)];
+ uint8_t geo_key_curr[sizeof(grn_geo_point)];
+ grn_geo_point point;
+
+ *d_far = 0.0;
+ grn_gton(geo_key_curr, base_point, sizeof(grn_geo_point));
+ *diff_bit = sizeof(grn_geo_point) * 8;
+ diff_bit_current = sizeof(grn_geo_point) * 8;
+ memcpy(&point, base_point, sizeof(grn_geo_point));
+ ep = entries;
+ while ((tid = grn_pat_cursor_next(ctx, pc))) {
+ grn_ii_cursor *ic = grn_ii_cursor_open(ctx, (grn_ii *)index, tid, 0, 0, 1, 0);
+ if (ic) {
+ grn_ii_posting *posting;
+ grn_gton(geo_key_prev, &point, sizeof(grn_geo_point));
+ grn_pat_get_key(ctx, pat, tid, &point, sizeof(grn_geo_point));
+ grn_gton(geo_key_curr, &point, sizeof(grn_geo_point));
+ d = grn_geo_distance_raw(ctx, base_point, &point);
+
+ diff_bit_prev = diff_bit_current;
+ diff_bit_current = compute_diff_bit(geo_key_curr, geo_key_prev);
+ if (diff_bit_current < diff_bit_prev && *diff_bit > diff_bit_current) {
+ if (i == n) {
+ break;
+ }
+ *diff_bit = diff_bit_current;
+ }
+
+ if (d > *d_far) {
+ *d_far = d;
+ }
+ while ((posting = grn_ii_cursor_next(ctx, ic))) {
+ grn_id rid = accessorp
+ ? grn_table_get(ctx, table, &posting->rid, sizeof(grn_id))
+ : posting->rid;
+ if (rid) {
+ for (p = ep; entries < p && p[-1].d > d; p--) {
+ p->id = p[-1].id;
+ p->d = p[-1].d;
+ }
+ p->id = rid;
+ p->d = d;
+ if (i < n) {
+ ep++;
+ i++;
+ }
+ }
+ }
+ grn_ii_cursor_close(ctx, ic);
+ }
+ }
+
+ return i;
+}
+
+typedef struct
+{
+ grn_geo_point key;
+ int key_size;
+} mesh_entry;
+
+/* #define GEO_SORT_DEBUG */
+
+#ifdef GEO_SORT_DEBUG
+#include <stdio.h>
+
+static void
+inspect_mesh_entry(grn_ctx *ctx, mesh_entry *entries, int n)
+{
+ mesh_entry *entry;
+ grn_geo_point min, max;
+
+ entry = entries + n;
+ printf("mesh: %d:%d\n", n, entry->key_size);
+
+ printf("key: ");
+ grn_p_geo_point(ctx, &(entry->key));
+
+ compute_min_and_max(&(entry->key), entry->key_size, &min, &max);
+ printf("min: ");
+ grn_p_geo_point(ctx, &min);
+ printf("max: ");
+ grn_p_geo_point(ctx, &max);
+}
+
+static void
+inspect_tid(grn_ctx *ctx, grn_id tid, grn_geo_point *point,
+ double x, double y, double d)
+{
+ printf("tid: %d:%g (%g,%g)", tid, d, x, y);
+ grn_p_geo_point(ctx, point);
+}
+#else
+# define inspect_mesh_entry(...)
+# define inspect_tid(...)
+#endif
+
+typedef enum {
+ MESH_LEFT_TOP,
+ MESH_RIGHT_TOP,
+ MESH_RIGHT_BOTTOM,
+ MESH_LEFT_BOTTOM
+} mesh_position;
+
+static int
+grn_table_sort_geo_collect_points(grn_ctx *ctx, grn_obj *table, grn_obj *index,
+ grn_pat *pat,
+ geo_entry *entries, int n_entries,
+ int n, int accessorp,
+ grn_geo_point *base_point,
+ double d_far, int diff_bit)
+{
+ int n_meshes;
+ grn_geo_point geo_base, geo_min, geo_max;
+ mesh_entry meshes[19];
+ int lat_diff, lng_diff;
+ double d;
+ geo_entry *ep, *p;
+ mesh_position position;
+
+ compute_min_and_max(base_point, diff_bit, &geo_min, &geo_max);
+
+ lat_diff = geo_max.latitude - geo_min.latitude + 1;
+ lng_diff = geo_max.longitude - geo_min.longitude + 1;
+ if (base_point->latitude >= geo_min.latitude + lat_diff / 2) {
+ geo_base.latitude = geo_max.latitude + 1;
+ if (base_point->longitude >= geo_min.longitude + lng_diff / 2) {
+ geo_base.longitude = geo_max.longitude + 1;
+ position = MESH_LEFT_BOTTOM;
+ } else {
+ geo_base.longitude = geo_min.longitude;
+ position = MESH_RIGHT_BOTTOM;
+ }
+ } else {
+ geo_base.latitude = geo_min.latitude;
+ if (base_point->longitude >= geo_min.longitude + lng_diff / 2) {
+ geo_base.longitude = geo_max.longitude + 1;
+ position = MESH_LEFT_TOP;
+ } else {
+ geo_base.longitude = geo_min.longitude;
+ position = MESH_RIGHT_TOP;
+ }
+ }
+ /*
+ base_point: b
+ geo_min: i
+ geo_max: a
+ geo_base: x: must be at the left bottom in the top right mesh.
+
+ e.g.: base_point is at the left bottom mesh case:
+ +------+------+
+ | | |
+ | |x |
+ ^+------+------+
+ || a| |
+ lng_diff || b | |
+ \/i------+------+
+ <------>
+ lat_diff
+
+ grn_min + lat_diff -> the right mesh.
+ grn_min + lng_diff -> the top mesh.
+ */
+#ifdef GEO_SORT_DEBUG
+ grn_p_geo_point(ctx, base_point);
+ printf("base: ");
+ grn_p_geo_point(ctx, &geo_base);
+ printf("min: ");
+ grn_p_geo_point(ctx, geo_min);
+ printf("max: ");
+ grn_p_geo_point(ctx, geo_max);
+ printf("diff: %d (%d, %d)\n", diff_bit, lat_diff, lng_diff);
+#endif
+
+ n_meshes = 0;
+
+#define add_mesh(lat_diff_,lng_diff_,key_size_)\
+ meshes[n_meshes].key.latitude = geo_base.latitude + (lat_diff_);\
+ meshes[n_meshes].key.longitude = geo_base.longitude + (lng_diff_);\
+ meshes[n_meshes].key_size = key_size_;\
+ n_meshes++;
+
+ if (position != MESH_LEFT_TOP) {
+ add_mesh(0, -lng_diff, diff_bit);
+ }
+ if (position != MESH_RIGHT_TOP) {
+ add_mesh(0, 0, diff_bit);
+ }
+ if (position != MESH_RIGHT_BOTTOM) {
+ add_mesh(-lat_diff, 0, diff_bit);
+ }
+ if (position != MESH_LEFT_BOTTOM) {
+ add_mesh(-lat_diff, -lng_diff, diff_bit);
+ }
+
+#define add_sub_mesh(lat_diff_cmp,lng_diff_cmp,lat_diff_base,lng_diff_base)\
+ meshes[n_meshes].key.latitude = geo_base.latitude + (lat_diff_cmp);\
+ meshes[n_meshes].key.longitude = geo_base.longitude + (lng_diff_cmp);\
+ d = grn_geo_distance_raw(ctx, base_point, &(meshes[n_meshes].key));\
+ if (d < d_far) {\
+ add_mesh(lat_diff_base, lng_diff_base, diff_bit + 2);\
+ }
+
+ /*
+ b: base_point
+ 1-16: sub meshes. 1-16 are added order.
+
+ +---+---+---+---+
+ | 1 | 2 | 3 | 4 |
+ +---+---+---+---+---+---+
+ |16 | | | 5 |
+ +---+ | +---+
+ |15 | |b | 6 |
+ +---+-------+-------+---+
+ |14 | | | 7 |
+ +---+ base meshes +---+
+ |13 | | | 8 |
+ +---+---+---+---+---+---+
+ |12 |11 |10 | 9 |
+ +---+---+---+---+
+ */
+ add_sub_mesh(lat_diff, -(lng_diff + 1) / 2 - 1,
+ lat_diff, -lng_diff);
+ add_sub_mesh(lat_diff, -1,
+ lat_diff, -(lng_diff + 1) / 2);
+ add_sub_mesh(lat_diff, 0,
+ lat_diff, 0);
+ add_sub_mesh(lat_diff, (lng_diff + 1) / 2,
+ lat_diff, (lng_diff + 1) / 2);
+
+ add_sub_mesh((lat_diff + 1) / 2, lng_diff,
+ (lat_diff + 1) / 2, lng_diff);
+ add_sub_mesh(0, lng_diff,
+ 0, lng_diff);
+ add_sub_mesh(-1, lng_diff,
+ -(lat_diff + 1) / 2, lng_diff);
+ add_sub_mesh(-(lat_diff + 1) / 2 - 1, lng_diff,
+ -lat_diff, lng_diff);
+
+ add_sub_mesh(-lat_diff - 1, (lng_diff + 1) / 2,
+ -lat_diff * 2, (lng_diff + 1) / 2);
+ add_sub_mesh(-lat_diff - 1, 0,
+ -lat_diff * 2, 0);
+ add_sub_mesh(-lat_diff - 1, -1,
+ -lat_diff * 2, -(lng_diff + 1) / 2);
+ add_sub_mesh(-lat_diff - 1, -(lng_diff + 1) / 2 - 1,
+ -lat_diff * 2, -lng_diff);
+
+ add_sub_mesh(-(lat_diff + 1) / 2 - 1, -lng_diff - 1,
+ -lat_diff, -lng_diff * 2);
+ add_sub_mesh(-1, -lng_diff - 1,
+ -(lat_diff + 1) / 2, -lng_diff * 2);
+ add_sub_mesh(0, -lng_diff - 1,
+ 0, -lng_diff * 2);
+ add_sub_mesh((lat_diff + 1) / 2, -lng_diff - 1,
+ (lat_diff + 1) / 2, -lng_diff * 2);
+
+#undef add_sub_mesh
+#undef add_mesh
+
+ ep = entries + n_entries;
+ while (n_meshes--) {
+ grn_id tid;
+ grn_pat_cursor *pc = grn_pat_cursor_open(ctx, pat,
+ &(meshes[n_meshes].key),
+ meshes[n_meshes].key_size,
+ NULL, 0,
+ 0, -1,
+ GRN_CURSOR_PREFIX|GRN_CURSOR_SIZE_BY_BIT);
+ inspect_mesh_entry(ctx, meshes, n_meshes);
+ if (pc) {
+ while ((tid = grn_pat_cursor_next(ctx, pc))) {
+ grn_ii_cursor *ic = grn_ii_cursor_open(ctx, (grn_ii *)index, tid, 0, 0, 1, 0);
+ if (ic) {
+ grn_geo_point pos;
+ grn_ii_posting *posting;
+ grn_pat_get_key(ctx, pat, tid, &pos, sizeof(grn_geo_point));
+ d = grn_geo_distance_raw(ctx, base_point, &pos);
+ inspect_tid(ctx, tid, &pos, x, y, d);
+ while ((posting = grn_ii_cursor_next(ctx, ic))) {
+ grn_id rid = accessorp
+ ? grn_table_get(ctx, table, &posting->rid, sizeof(grn_id))
+ : posting->rid;
+ if (rid) {
+ for (p = ep; entries < p && p[-1].d > d; p--) {
+ p->id = p[-1].id;
+ p->d = p[-1].d;
+ }
+ p->id = rid;
+ p->d = d;
+ if (n_entries < n) {
+ ep++;
+ n_entries++;
+ }
+ }
+ }
+ grn_ii_cursor_close(ctx, ic);
+ }
+ }
+ grn_pat_cursor_close(ctx, pc);
+ }
+ }
+ return n_entries;
+}
+
+int
+grn_geo_table_sort(grn_ctx *ctx, grn_obj *table, int offset, int limit,
+ grn_obj *result, grn_table_sort_key *keys, int n_keys)
+{
+ grn_obj *index;
+ int i = 0, e = offset + limit, sid, accessorp = GRN_ACCESSORP(keys->key);
+ if (n_keys == 2 && grn_column_index(ctx, keys->key, GRN_OP_LESS, &index, 1, &sid)) {
+ grn_id tid;
+ grn_obj *arg = keys[1].key;
+ grn_pat *pat = (grn_pat *)grn_ctx_at(ctx, index->header.domain);
+ grn_id domain = pat->obj.header.domain;
+ grn_pat_cursor *pc = grn_pat_cursor_open(ctx, pat, NULL, 0,
+ GRN_BULK_HEAD(arg), GRN_BULK_VSIZE(arg),
+ 0, -1, GRN_CURSOR_PREFIX);
+ if (pc) {
+ if (domain != GRN_DB_TOKYO_GEO_POINT && domain != GRN_DB_WGS84_GEO_POINT) {
+ while (i < e && (tid = grn_pat_cursor_next(ctx, pc))) {
+ grn_ii_cursor *ic = grn_ii_cursor_open(ctx, (grn_ii *)index, tid, 0, 0, 1, 0);
+ if (ic) {
+ grn_ii_posting *posting;
+ while (i < e && (posting = grn_ii_cursor_next(ctx, ic))) {
+ if (offset <= i) {
+ grn_id *v;
+ if (!grn_array_add(ctx, (grn_array *)result, (void **)&v)) { break; }
+ *v = posting->rid;
+ }
+ i++;
+ }
+ grn_ii_cursor_close(ctx, ic);
+ }
+ }
+ grn_pat_cursor_close(ctx, pc);
+ } else {
+ geo_entry *entries;
+
+ if ((entries = GRN_MALLOC(sizeof(geo_entry) * (e + 1)))) {
+ int n, diff_bit;
+ double d_far;
+ grn_id *v;
+ grn_geo_point *base_point;
+ geo_entry *ep;
+
+ base_point = (grn_geo_point *)GRN_BULK_HEAD(arg);
+ n = grn_table_sort_geo_detect_far_point(ctx, table, index, pat,
+ entries, pc, e, accessorp,
+ base_point,
+ &d_far, &diff_bit);
+ grn_pat_cursor_close(ctx, pc);
+ if (diff_bit > 0) {
+ n += grn_table_sort_geo_collect_points(ctx, table, index, pat,
+ entries, n, e, accessorp,
+ base_point, d_far, diff_bit);
+ }
+ for (i = 0, ep = entries + offset; i < limit && ep < entries + n; i++, ep++) {
+ if (!grn_array_add(ctx, (grn_array *)result, (void **)&v)) { break; }
+ *v = ep->id;
+ }
+ GRN_FREE(entries);
+ }
+ }
+ }
+ }
+ return i;
+}
grn_rc
grn_geo_search(grn_ctx *ctx, grn_obj *obj, grn_obj **args, int nargs,
Modified: lib/geo.h (+2 -0)
===================================================================
--- lib/geo.h 2010-08-09 01:43:43 +0000 (6db6309)
+++ lib/geo.h 2010-08-09 05:21:17 +0000 (d3654dc)
@@ -46,6 +46,8 @@ extern "C" {
grn_rc grn_geo_search(grn_ctx *ctx, grn_obj *obj, grn_obj **args, int nargs,
grn_obj *res, grn_operator op);
+int grn_geo_table_sort(grn_ctx *ctx, grn_obj *table, int offset, int limit,
+ grn_obj *result, grn_table_sort_key *keys, int n_keys);
unsigned grn_geo_in_circle(grn_ctx *ctx, grn_obj *point, grn_obj *center,
grn_obj *radius_or_point);