From d5672aed4a40af96431ac19e77574813f0a7a2e1 Mon Sep 17 00:00:00 2001 From: Benjamin Reynolds Date: Thu, 14 Jun 2018 18:25:35 +0100 Subject: [PATCH 1/1] Remove quad_tile library and extract to gem Quad tile functions are now installed via a gem with native extension automatically. This improves the run time of the test suite by ~30% for users that didn't bother to build the C version of the functions. Closes #1314 Closes #1899 --- .travis.yml | 2 - Gemfile | 3 + Gemfile.lock | 2 + db/functions/Makefile | 2 +- lib/quad_tile.rb | 81 -------------------- lib/quad_tile/.gitignore | 3 - lib/quad_tile/extconf.rb | 5 -- lib/quad_tile/quad_tile.c | 148 ------------------------------------- lib/quad_tile/quad_tile.h | 25 ------- test/lib/quad_tile_test.rb | 27 ------- 10 files changed, 6 insertions(+), 292 deletions(-) delete mode 100644 lib/quad_tile.rb delete mode 100644 lib/quad_tile/.gitignore delete mode 100644 lib/quad_tile/extconf.rb delete mode 100644 lib/quad_tile/quad_tile.c delete mode 100644 lib/quad_tile/quad_tile.h delete mode 100644 test/lib/quad_tile_test.rb diff --git a/.travis.yml b/.travis.yml index 8ae3d1141..48ddb4a1d 100644 --- a/.travis.yml +++ b/.travis.yml @@ -15,8 +15,6 @@ env: - OSM_MEMCACHE_SERVERS="127.0.0.1" before_script: - cp config/example.application.yml config/application.yml - - ruby -C lib/quad_tile extconf.rb - - make -C lib/quad_tile - psql -U postgres -c "CREATE DATABASE openstreetmap" - psql -U postgres -c "CREATE EXTENSION btree_gist" openstreetmap - make -C db/functions libpgosm.so diff --git a/Gemfile b/Gemfile index 7d59cceb1..addc105d8 100644 --- a/Gemfile +++ b/Gemfile @@ -55,6 +55,9 @@ gem "record_tag_helper" gem "rinku", ">= 1.2.2", :require => "rails_rinku" gem "validates_email_format_of", ">= 1.5.1" +# Native OSM extensions +gem "quad_tile", "~> 1.0.1" + # Sanitise URIs gem "rack-uri_sanitizer" diff --git a/Gemfile.lock b/Gemfile.lock index 8634f8df8..bdf42eeb6 100644 --- a/Gemfile.lock +++ b/Gemfile.lock @@ -235,6 +235,7 @@ GEM psych (3.0.2) public_suffix (3.0.2) puma (3.11.4) + quad_tile (1.0.1) r2 (0.2.7) rack (2.0.5) rack-cors (1.0.2) @@ -403,6 +404,7 @@ DEPENDENCIES poltergeist psych puma (~> 3.7) + quad_tile (~> 1.0.1) r2 (~> 0.2.7) rack-cors rack-uri_sanitizer diff --git a/db/functions/Makefile b/db/functions/Makefile index dac1889dc..6bb966b9a 100644 --- a/db/functions/Makefile +++ b/db/functions/Makefile @@ -1,7 +1,7 @@ PG_CONFIG ?= pg_config DESTDIR ?= . -QTDIR=../../lib/quad_tile +QTDIR=$(shell bundle show quad_tile)/ext/quad_tile OS=$(shell uname -s) ifeq (${OS},Darwin) diff --git a/lib/quad_tile.rb b/lib/quad_tile.rb deleted file mode 100644 index 931ec04a3..000000000 --- a/lib/quad_tile.rb +++ /dev/null @@ -1,81 +0,0 @@ -module QuadTile - begin - require "quad_tile/quad_tile_so" - rescue LoadError - def self.tile_for_point(lat, lon) - x = ((lon.to_f + 180) * 65535 / 360).round - y = ((lat.to_f + 90) * 65535 / 180).round - - tile_for_xy(x, y) - end - - def self.tiles_for_area(bbox) - minx = ((bbox.min_lon + 180) * 65535 / 360).round - maxx = ((bbox.max_lon + 180) * 65535 / 360).round - miny = ((bbox.min_lat + 90) * 65535 / 180).round - maxy = ((bbox.max_lat + 90) * 65535 / 180).round - tiles = [] - - minx.upto(maxx) do |x| - miny.upto(maxy) do |y| - tiles << tile_for_xy(x, y) - end - end - - tiles - end - - def self.tile_for_xy(x, y) - t = 0 - - 16.times do - t = t << 1 - t |= 1 unless (x & 0x8000).zero? - x <<= 1 - t = t << 1 - t |= 1 unless (y & 0x8000).zero? - y <<= 1 - end - - t - end - - def self.iterate_tiles_for_area(bbox) - tiles = tiles_for_area(bbox) - first = last = nil - - tiles.sort.each do |tile| - if last.nil? - first = last = tile - elsif tile == last + 1 - last = tile - else - yield first, last - - first = last = tile - end - end - - yield first, last unless last.nil? - end - end - - def self.sql_for_area(bbox, prefix) - sql = [] - single = [] - - iterate_tiles_for_area(bbox) do |first, last| - if first == last - single.push(first) - else - sql.push("#{prefix}tile BETWEEN #{first} AND #{last}") - end - end - - sql.push("#{prefix}tile IN (#{single.join(',')})") unless single.empty? - - "( " + sql.join(" OR ") + " )" - end - - private_class_method :tile_for_xy, :iterate_tiles_for_area -end diff --git a/lib/quad_tile/.gitignore b/lib/quad_tile/.gitignore deleted file mode 100644 index 978f071e9..000000000 --- a/lib/quad_tile/.gitignore +++ /dev/null @@ -1,3 +0,0 @@ -Makefile -quad_tile.o -quad_tile_so.so diff --git a/lib/quad_tile/extconf.rb b/lib/quad_tile/extconf.rb deleted file mode 100644 index 2264a3e0f..000000000 --- a/lib/quad_tile/extconf.rb +++ /dev/null @@ -1,5 +0,0 @@ -require "mkmf" - -with_cflags("-std=c99 #{$CFLAGS}") do - create_makefile("quad_tile_so") -end diff --git a/lib/quad_tile/quad_tile.c b/lib/quad_tile/quad_tile.c deleted file mode 100644 index 304776982..000000000 --- a/lib/quad_tile/quad_tile.c +++ /dev/null @@ -1,148 +0,0 @@ -#include "ruby.h" -#include "quad_tile.h" - -typedef struct { - unsigned int *tilev; - unsigned int tilec; -} tilelist_t; - -static tilelist_t tilelist_for_area(unsigned int minx, unsigned int miny, unsigned int maxx, unsigned int maxy) -{ - unsigned int x; - unsigned int y; - tilelist_t tl; - unsigned int maxtilec; - - maxtilec = 256; - - tl.tilev = malloc(maxtilec * sizeof(unsigned int)); - tl.tilec = 0; - - for (x = minx; x <= maxx; x++) - { - for (y = miny; y <= maxy; y++) - { - if (tl.tilec == maxtilec) - { - maxtilec = maxtilec * 2; - - tl.tilev = realloc(tl.tilev, maxtilec * sizeof(unsigned int)); - } - - tl.tilev[tl.tilec++] = xy2tile(x, y); - } - } - - return tl; -} - -static int tile_compare(const void *ap, const void *bp) -{ - unsigned int a = *(unsigned int *)ap; - unsigned int b = *(unsigned int *)bp; - - if (a < b) - { - return -1; - } - else if (a > b) - { - return 1; - } - else - { - return 0; - } -} - -static VALUE tile_for_point(VALUE self, VALUE lat, VALUE lon) -{ - unsigned int x = lon2x(NUM2DBL(lon)); - unsigned int y = lat2y(NUM2DBL(lat)); - - return UINT2NUM(xy2tile(x, y)); -} - -static VALUE tiles_for_area(VALUE self, VALUE bbox) -{ - unsigned int minx = lon2x(NUM2DBL(rb_iv_get(bbox, "@min_lon"))); - unsigned int maxx = lon2x(NUM2DBL(rb_iv_get(bbox, "@max_lon"))); - unsigned int miny = lat2y(NUM2DBL(rb_iv_get(bbox, "@min_lat"))); - unsigned int maxy = lat2y(NUM2DBL(rb_iv_get(bbox, "@max_lat"))); - tilelist_t tl = tilelist_for_area(minx, miny, maxx, maxy); - VALUE tiles = rb_ary_new(); - unsigned int t; - - for (t = 0; t < tl.tilec; t++) - { - rb_ary_push(tiles, UINT2NUM(tl.tilev[t])); - } - - free(tl.tilev); - - return tiles; -} - -static VALUE tile_for_xy(VALUE self, VALUE x, VALUE y) -{ - return UINT2NUM(xy2tile(NUM2UINT(x), NUM2UINT(y))); -} - -static VALUE iterate_tiles_for_area(VALUE self, VALUE bbox) -{ - unsigned int minx = lon2x(NUM2DBL(rb_iv_get(bbox, "@min_lon"))); - unsigned int maxx = lon2x(NUM2DBL(rb_iv_get(bbox, "@max_lon"))); - unsigned int miny = lat2y(NUM2DBL(rb_iv_get(bbox, "@min_lat"))); - unsigned int maxy = lat2y(NUM2DBL(rb_iv_get(bbox, "@max_lat"))); - tilelist_t tl = tilelist_for_area(minx, miny, maxx, maxy); - - if (tl.tilec > 0) - { - unsigned int first; - unsigned int last; - unsigned int t; - VALUE a = rb_ary_new(); - - qsort(tl.tilev, tl.tilec, sizeof(unsigned int), tile_compare); - - first = last = tl.tilev[0]; - - for (t = 1; t < tl.tilec; t++) - { - unsigned int tile = tl.tilev[t]; - - if (tile == last + 1) - { - last = tile; - } - else - { - rb_ary_store(a, 0, UINT2NUM(first)); - rb_ary_store(a, 1, UINT2NUM(last)); - rb_yield(a); - - first = last = tile; - } - } - - rb_ary_store(a, 0, UINT2NUM(first)); - rb_ary_store(a, 1, UINT2NUM(last)); - rb_yield(a); - } - - free(tl.tilev); - - return Qnil; -} - -void Init_quad_tile_so(void) -{ - VALUE m = rb_define_module("QuadTile"); - - rb_define_module_function(m, "tile_for_point", tile_for_point, 2); - rb_define_module_function(m, "tiles_for_area", tiles_for_area, 1); - rb_define_module_function(m, "tile_for_xy", tile_for_xy, 2); - rb_define_module_function(m, "iterate_tiles_for_area", iterate_tiles_for_area, 1); - - return; -} diff --git a/lib/quad_tile/quad_tile.h b/lib/quad_tile/quad_tile.h deleted file mode 100644 index 86fa1802d..000000000 --- a/lib/quad_tile/quad_tile.h +++ /dev/null @@ -1,25 +0,0 @@ -#include - -static inline unsigned int xy2tile(unsigned int x, unsigned int y) -{ - unsigned int tile = 0; - int i; - - for (i = 15; i >= 0; i--) - { - tile = (tile << 1) | ((x >> i) & 1); - tile = (tile << 1) | ((y >> i) & 1); - } - - return tile; -} - -static inline unsigned int lon2x(double lon) -{ - return round((lon + 180.0) * 65535.0 / 360.0); -} - -static inline unsigned int lat2y(double lat) -{ - return round((lat + 90.0) * 65535.0 / 180.0); -} diff --git a/test/lib/quad_tile_test.rb b/test/lib/quad_tile_test.rb deleted file mode 100644 index ef03ed4a5..000000000 --- a/test/lib/quad_tile_test.rb +++ /dev/null @@ -1,27 +0,0 @@ -require "test_helper" - -class QuadTileTest < ActiveSupport::TestCase - def test_tile_for_point - assert_equal 3493907048, QuadTile.tile_for_point(51.0, 1.0) - assert_equal 3493908088, QuadTile.tile_for_point(51.1, 1.0) - assert_equal 3493913808, QuadTile.tile_for_point(51.1, 1.1) - assert_equal 1221887424, QuadTile.tile_for_point(10.0, -123.0) - assert_equal 2147483648, QuadTile.tile_for_point(-90.0, 0.0) - end - - def test_tiles_for_area - assert_equal [3493906992, 3493906993, 3493906996, 3493906997, 3493907040, 3493907041, 3493907044, 3493907045, 3493906994, 3493906995, 3493906998, 3493906999, 3493907042, 3493907043, 3493907046, 3493907047, 3493907000, 3493907001, 3493907004, 3493907005, 3493907048, 3493907049, 3493907052, 3493907053, 3493907002, 3493907003, 3493907006, 3493907007, 3493907050, 3493907051, 3493907054, 3493907055], QuadTile.tiles_for_area(BoundingBox.new(0.99, 50.99, 1.01, 51.01)) - assert_equal [3493908065, 3493908068, 3493908069, 3493908080, 3493908081, 3493908084, 3493908085, 3493908256, 3493908067, 3493908070, 3493908071, 3493908082, 3493908083, 3493908086, 3493908087, 3493908258, 3493908073, 3493908076, 3493908077, 3493908088, 3493908089, 3493908092, 3493908093, 3493908264, 3493908075, 3493908078, 3493908079, 3493908090, 3493908091, 3493908094, 3493908095, 3493908266], QuadTile.tiles_for_area(BoundingBox.new(0.99, 51.09, 1.01, 51.11)) - assert_equal [3493913705, 3493913708, 3493913709, 3493913720, 3493913721, 3493913724, 3493913725, 3493913896, 3493913707, 3493913710, 3493913711, 3493913722, 3493913723, 3493913726, 3493913727, 3493913898, 3493913793, 3493913796, 3493913797, 3493913808, 3493913809, 3493913812, 3493913813, 3493913984, 3493913795, 3493913798, 3493913799, 3493913810, 3493913811, 3493913814, 3493913815, 3493913986, 3493913801, 3493913804, 3493913805, 3493913816, 3493913817, 3493913820, 3493913821, 3493913992], QuadTile.tiles_for_area(BoundingBox.new(1.09, 51.09, 1.11, 51.11)) - assert_equal [3509256924, 3509256925, 3509257096, 3509257097, 3509257100, 3509257101, 3509257112, 3509257113, 3509256926, 3509256927, 3509257098, 3509257099, 3509257102, 3509257103, 3509257114, 3509257115, 3509256948, 3509256949, 3509257120, 3509257121, 3509257124, 3509257125, 3509257136, 3509257137, 3509256950, 3509256951, 3509257122, 3509257123, 3509257126, 3509257127, 3509257138, 3509257139, 3509256956, 3509256957, 3509257128, 3509257129, 3509257132, 3509257133, 3509257144, 3509257145], QuadTile.tiles_for_area(BoundingBox.new(9.99, -123.01, 10.01, -122.99)) - assert_equal [1252698792, 1252698793, 1252698796, 1252698797, 1252698794, 1252698795, 1252698798, 1252698799, 1610612736, 1610612737, 1610612740, 1610612741, 1610612738, 1610612739, 1610612742, 1610612743, 1610612744, 1610612745, 1610612748, 1610612749], QuadTile.tiles_for_area(BoundingBox.new(-90.01, 0.0, -89.99, 0.01)) - end - - def test_sql_for_area - assert_equal "( tile BETWEEN 3493906992 AND 3493907007 OR tile BETWEEN 3493907040 AND 3493907055 )", QuadTile.sql_for_area(BoundingBox.new(0.99, 50.99, 1.01, 51.01), "") - assert_equal "( tile BETWEEN 3493908067 AND 3493908071 OR tile BETWEEN 3493908075 AND 3493908095 OR tile IN (3493908065,3493908073,3493908256,3493908258,3493908264,3493908266) )", QuadTile.sql_for_area(BoundingBox.new(0.99, 51.09, 1.01, 51.11), "") - assert_equal "( tile BETWEEN 3493913707 AND 3493913711 OR tile BETWEEN 3493913720 AND 3493913727 OR tile BETWEEN 3493913795 AND 3493913799 OR tile BETWEEN 3493913804 AND 3493913805 OR tile BETWEEN 3493913808 AND 3493913817 OR tile BETWEEN 3493913820 AND 3493913821 OR tile IN (3493913705,3493913793,3493913801,3493913896,3493913898,3493913984,3493913986,3493913992) )", QuadTile.sql_for_area(BoundingBox.new(1.09, 51.09, 1.11, 51.11), "") - assert_equal "( tile BETWEEN 3509256924 AND 3509256927 OR tile BETWEEN 3509256948 AND 3509256951 OR tile BETWEEN 3509256956 AND 3509256957 OR tile BETWEEN 3509257096 AND 3509257103 OR tile BETWEEN 3509257112 AND 3509257115 OR tile BETWEEN 3509257120 AND 3509257129 OR tile BETWEEN 3509257132 AND 3509257133 OR tile BETWEEN 3509257136 AND 3509257139 OR tile BETWEEN 3509257144 AND 3509257145 )", QuadTile.sql_for_area(BoundingBox.new(9.99, -123.01, 10.01, -122.99), "") - assert_equal "( tile BETWEEN 1252698792 AND 1252698799 OR tile BETWEEN 1610612736 AND 1610612745 OR tile BETWEEN 1610612748 AND 1610612749 )", QuadTile.sql_for_area(BoundingBox.new(-90.01, 0.0, -89.99, 0.01), "") - end -end -- 2.43.2