xref: /4.0.0/couchstore/src/views/spatial.c (revision d80f7621)
1/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2
3/**
4 * @copyright 2013 Couchbase, Inc.
5 *
6 * @author Volker Mische  <volker@couchbase.com>
7 *
8 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
9 * use this file except in compliance with the License. You may obtain a copy of
10 * the License at
11 *
12 *  http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing, software
15 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
16 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
17 * License for the specific language governing permissions and limitations under
18 * the License.
19 **/
20
21#include <stdlib.h>
22#include <limits.h>
23#include <assert.h>
24#include "spatial.h"
25#include "../bitfield.h"
26#include "../couch_btree.h"
27
28
29#define BYTE_PER_COORD sizeof(uint32_t)
30
31#define IS_BIT_SET(num, bit)        (num & (1 << bit))
32#define CHUNK_BITS                  (sizeof(unsigned char) * CHAR_BIT)
33#define CHUNK_INDEX(map, size, bit) (size - 1 - ((bit) / CHUNK_BITS))
34#define MAP_CHUNK(map, size, bit)   (map)[CHUNK_INDEX(map, size, bit)]
35#define CHUNK_OFFSET(bit)           ((bit) % CHUNK_BITS)
36
37#define MIN(a, b) (a) < (b) ? a : b
38#define MAX(a, b) (a) > (b) ? a : b
39
40
41STATIC couchstore_error_t encode_spatial_key(const sized_mbb_t *mbb,
42                                          char *key,
43                                          size_t nkey);
44STATIC couchstore_error_t decode_spatial_key(const char *key,
45                                             sized_mbb_t *mbb);
46STATIC couchstore_error_t expand_mbb(sized_mbb_t *original,
47                                     sized_mbb_t *expander);
48
49
50int spatial_key_cmp(const sized_buf *key1, const sized_buf *key2,
51                    const void *user_ctx)
52{
53    scale_factor_t *sf =
54            ((view_spatial_builder_ctx_t *) user_ctx)->scale_factor;
55    uint16_t mbb1_num = decode_raw16(*((raw_16 *) key1->buf));
56    uint16_t mbb2_num = decode_raw16(*((raw_16 *) key2->buf));
57    sized_mbb_t mbbs[2];
58    double *mbbs_center[2];
59    uint32_t *mbbs_scaled[2];
60    unsigned char *mbbs_zcode[2];
61    int res;
62
63    mbbs[0].num = mbb1_num;
64    mbbs[0].mbb = (double *)(key1->buf + sizeof(uint16_t));
65    mbbs_center[0] = spatial_center(&mbbs[0]);
66    mbbs_scaled[0] = spatial_scale_point(mbbs_center[0], sf);
67    mbbs_zcode[0] = interleave_uint32s(mbbs_scaled[0], sf->dim);
68
69    mbbs[1].num = mbb2_num;
70    mbbs[1].mbb = (double *)(key2->buf + sizeof(uint16_t));
71    mbbs_center[1] = spatial_center(&mbbs[1]);
72    mbbs_scaled[1] = spatial_scale_point(mbbs_center[1], sf);
73    mbbs_zcode[1] = interleave_uint32s(mbbs_scaled[1], sf->dim);
74
75    res = memcmp(mbbs_zcode[0], mbbs_zcode[1], sf->dim * BYTE_PER_COORD);
76
77    free(mbbs_center[0]);
78    free(mbbs_scaled[0]);
79    free(mbbs_zcode[0]);
80    free(mbbs_center[1]);
81    free(mbbs_scaled[1]);
82    free(mbbs_zcode[1]);
83
84    return res;
85}
86
87int spatial_merger_key_cmp(const sized_buf *key1, const sized_buf *key2,
88                           const void *user_ctx)
89{
90    (void)user_ctx;
91
92    /* To be able to remove duplicates, the items in the file needs to have a
93     * a reproducible total order. As it's for de-duplication and not for
94     * some spatial optimizations, the order can be based on the bytes and
95     * doesn't need to put spatially close-by items together. */
96    if (key1->size == key2->size) {
97        return memcmp(key1->buf, key2->buf, key1->size);
98    }
99
100    return key1->size - key2->size;
101}
102
103
104scale_factor_t *spatial_scale_factor(const double *mbb, uint16_t dim,
105                                     uint32_t max)
106{
107    int i;
108    double range;
109    scale_factor_t *sf = NULL;
110    double *offsets = NULL;
111    double *scales = NULL;
112
113    sf = (scale_factor_t *)malloc(sizeof(scale_factor_t));
114    if (sf == NULL) {
115        return NULL;
116    }
117    offsets = (double *)malloc(sizeof(double) * dim);
118    if (offsets == NULL) {
119        free(sf);
120        return NULL;
121    }
122    scales = (double *)malloc(sizeof(double) * dim);
123    if (scales == NULL) {
124        free(sf);
125        free(offsets);
126        return NULL;
127    }
128
129    for (i = 0; i < dim; ++i) {
130        offsets[i] = mbb[i*2];
131        range = mbb[(i * 2) + 1] - mbb[i * 2];
132        if (range == 0.0) {
133            scales[i] = 0.0;
134        } else {
135            scales[i] = max / range;
136        }
137    }
138
139    sf->offsets = offsets;
140    sf->scales = scales;
141    sf->dim = dim;
142    return sf;
143}
144
145void free_spatial_scale_factor(scale_factor_t *sf)
146{
147    if (sf == NULL) {
148        return;
149    }
150    free(sf->offsets);
151    free(sf->scales);
152    free(sf);
153}
154
155
156double *spatial_center(const sized_mbb_t *mbb)
157{
158    double *center = (double *)malloc(sizeof(double) * (mbb->num/2));
159    uint32_t i;
160    if (center == NULL) {
161        return NULL;
162    }
163
164    for (i = 0; i < mbb->num; i += 2) {
165        center[i/2] = mbb->mbb[i] + ((mbb->mbb[i+1] - mbb->mbb[i])/2);
166    }
167    return center;
168}
169
170
171uint32_t *spatial_scale_point(const double *point, const scale_factor_t *sf)
172{
173    int i;
174    uint32_t *scaled = (uint32_t *)malloc(sizeof(uint32_t) * sf->dim);
175    if (scaled == NULL) {
176        return NULL;
177    }
178
179    for (i = 0; i < sf->dim; ++i) {
180        /* casting to int is OK. No rounding is needed for the
181           space-filling curve */
182        scaled[i] = (uint32_t)((point[i] - sf->offsets[i]) *
183                               sf->scales[i]);
184    }
185    return scaled;
186}
187
188
189void set_bit_sized(unsigned char *bitmap, uint16_t size, uint16_t bit)
190{
191    (MAP_CHUNK(bitmap, size, bit)) |= (1 << CHUNK_OFFSET(bit));
192}
193
194
195unsigned char *interleave_uint32s(uint32_t *numbers, uint16_t num)
196{
197    uint8_t i;
198    uint16_t j, bitmap_size;
199    unsigned char *bitmap = NULL;
200
201    assert(num < 16384);
202
203    /* bitmap_size in bits (hence the `*8`) */
204    bitmap_size = (sizeof(uint32_t) * num * 8);
205    bitmap = (unsigned char *)calloc(bitmap_size / 8, sizeof(unsigned char));
206    if (bitmap == NULL) {
207        return NULL;
208    }
209
210    /* i is the bit offset within a number
211     * j is the current number offset */
212    for (i = 0; i * num < bitmap_size; i++) {
213        for (j = 0; j < num; j++) {
214            /* Start with the last number, as we built up the bitmap
215             * from right to left */
216            if (IS_BIT_SET(numbers[(num - 1) - j], i)) {
217                set_bit_sized(bitmap, bitmap_size/8, (i * num) + j);
218            }
219        }
220    }
221    return bitmap;
222}
223
224
225STATIC couchstore_error_t decode_spatial_key(const char *key, sized_mbb_t *mbb)
226{
227    mbb->num = decode_raw16(*((raw_16 *) key));
228    mbb->mbb = (double *)(key + 2);
229    return COUCHSTORE_SUCCESS;
230}
231
232
233STATIC couchstore_error_t encode_spatial_key(const sized_mbb_t *mbb,
234                                             char *key,
235                                             size_t nkey)
236{
237    raw_16 num = encode_raw16(mbb->num);
238
239    memcpy(key, &num, 2);
240    key += 2;
241
242    assert(mbb->num * sizeof(double) <= nkey);
243    memcpy(key, mbb->mbb, mbb->num * sizeof(double));
244
245    return COUCHSTORE_SUCCESS;
246}
247
248
249/* Expands the `original` MBB with the `expander` */
250STATIC couchstore_error_t expand_mbb(sized_mbb_t *original,
251                                     sized_mbb_t *expander) {
252    int i;
253
254    assert(original->num == expander->num);
255
256    for (i = 0; i < original->num; ++i) {
257        if (i % 2 == 0) {
258            original->mbb[i] = MIN(original->mbb[i], expander->mbb[i]);
259        } else {
260            original->mbb[i] = MAX(original->mbb[i], expander->mbb[i]);
261        }
262    }
263
264    return COUCHSTORE_SUCCESS;
265}
266
267
268/* This reduce function is also used for the re-reduce */
269couchstore_error_t view_spatial_reduce(char *dst,
270                                       size_t *size_r,
271                                       const nodelist *leaflist,
272                                       int count,
273                                       void *ctx)
274{
275    sized_mbb_t enclosing;
276    sized_mbb_t tmp_mbb;
277    const nodelist *i;
278    (void) ctx;
279
280    decode_spatial_key(leaflist->key.buf, &enclosing);
281    count--;
282
283    for (i = leaflist->next; i != NULL && count > 0; i = i->next, count--) {
284        decode_spatial_key(i->key.buf, &tmp_mbb);
285        expand_mbb(&enclosing, &tmp_mbb);
286    }
287
288    encode_spatial_key(&enclosing, dst, MAX_REDUCTION_SIZE);
289    /* 2 is the prefix with the number of doubles */
290    *size_r = 2 + (enclosing.num * sizeof(double));
291
292    return COUCHSTORE_SUCCESS;
293}
294