xref: /5.5.2/couchstore/src/views/spatial.cc (revision 6ef489f3)
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 <platform/cb_malloc.h>
22#include <stdlib.h>
23#include <limits.h>
24#include "spatial.h"
25#include "../bitfield.h"
26#include "../couch_btree.h"
27#include <platform/cbassert.h>
28#include <vector>
29#include <algorithm>
30
31
32#define BYTE_PER_COORD sizeof(uint32_t)
33
34#define IS_BIT_SET(num, bit)        (num & (1 << bit))
35#define CHUNK_BITS                  (sizeof(unsigned char) * CHAR_BIT)
36#define CHUNK_INDEX(map, size, bit) (size - 1 - ((bit) / CHUNK_BITS))
37#define MAP_CHUNK(map, size, bit)   (map)[CHUNK_INDEX(map, size, bit)]
38#define CHUNK_OFFSET(bit)           ((bit) % CHUNK_BITS)
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    cb_assert(sf->dim > 0);
64
65    mbbs[0].num = mbb1_num;
66    mbbs[0].mbb = (double *)(key1->buf + sizeof(uint16_t));
67    mbbs_center[0] = spatial_center(&mbbs[0]);
68    cb_assert(mbbs_center[0] != NULL);
69    mbbs_scaled[0] = spatial_scale_point(mbbs_center[0], sf);
70    cb_assert(mbbs_scaled[0] != NULL);
71    mbbs_zcode[0] = interleave_uint32s(mbbs_scaled[0], sf->dim);
72    cb_assert(mbbs_zcode[0] != NULL);
73
74    mbbs[1].num = mbb2_num;
75    mbbs[1].mbb = (double *)(key2->buf + sizeof(uint16_t));
76    mbbs_center[1] = spatial_center(&mbbs[1]);
77    cb_assert(mbbs_center[1] != NULL);
78    mbbs_scaled[1] = spatial_scale_point(mbbs_center[1], sf);
79    cb_assert(mbbs_scaled[1] != NULL);
80    mbbs_zcode[1] = interleave_uint32s(mbbs_scaled[1], sf->dim);
81    cb_assert(mbbs_zcode[1] != NULL);
82
83    res = memcmp(mbbs_zcode[0], mbbs_zcode[1], sf->dim * BYTE_PER_COORD);
84
85    cb_free(mbbs_center[0]);
86    cb_free(mbbs_scaled[0]);
87    cb_free(mbbs_zcode[0]);
88    cb_free(mbbs_center[1]);
89    cb_free(mbbs_scaled[1]);
90    cb_free(mbbs_zcode[1]);
91
92    return res;
93}
94
95int spatial_merger_key_cmp(const sized_buf *key1, const sized_buf *key2,
96                           const void *user_ctx)
97{
98    (void)user_ctx;
99
100    /* To be able to remove duplicates, the items in the file needs to have a
101     * a reproducible total order. As it's for de-duplication and not for
102     * some spatial optimizations, the order can be based on the bytes and
103     * doesn't need to put spatially close-by items together. */
104    if (key1->size == key2->size) {
105        return memcmp(key1->buf, key2->buf, key1->size);
106    }
107
108    return key1->size - key2->size;
109}
110
111
112scale_factor_t *spatial_scale_factor(const double *mbb, uint16_t dim,
113                                     uint32_t max)
114{
115    int i;
116    double range;
117    scale_factor_t *sf = NULL;
118    double *offsets = NULL;
119    double *scales = NULL;
120
121    sf = (scale_factor_t *)cb_malloc(sizeof(scale_factor_t));
122    if (sf == NULL) {
123        return NULL;
124    }
125    offsets = (double *)cb_malloc(sizeof(double) * dim);
126    if (offsets == NULL) {
127        cb_free(sf);
128        return NULL;
129    }
130    scales = (double *)cb_malloc(sizeof(double) * dim);
131    if (scales == NULL) {
132        cb_free(sf);
133        cb_free(offsets);
134        return NULL;
135    }
136
137    for (i = 0; i < dim; ++i) {
138        offsets[i] = mbb[i*2];
139        range = mbb[(i * 2) + 1] - mbb[i * 2];
140        if (range == 0.0) {
141            scales[i] = 0.0;
142        } else {
143            scales[i] = max / range;
144        }
145    }
146
147    sf->offsets = offsets;
148    sf->scales = scales;
149    sf->dim = dim;
150    return sf;
151}
152
153void free_spatial_scale_factor(scale_factor_t *sf)
154{
155    if (sf == NULL) {
156        return;
157    }
158    cb_free(sf->offsets);
159    cb_free(sf->scales);
160    cb_free(sf);
161}
162
163
164double *spatial_center(const sized_mbb_t *mbb)
165{
166    double *center = (double *)cb_calloc(mbb->num/2, sizeof(double));
167    uint32_t i;
168    if (center == NULL) {
169        return NULL;
170    }
171
172    for (i = 0; i < mbb->num; i += 2) {
173        center[i/2] = mbb->mbb[i] + ((mbb->mbb[i+1] - mbb->mbb[i])/2);
174    }
175    return center;
176}
177
178
179uint32_t *spatial_scale_point(const double *point, const scale_factor_t *sf)
180{
181    int i;
182    uint32_t *scaled = (uint32_t *)cb_malloc(sizeof(uint32_t) * sf->dim);
183    if (scaled == NULL) {
184        return NULL;
185    }
186
187    for (i = 0; i < sf->dim; ++i) {
188        /* casting to int is OK. No rounding is needed for the
189           space-filling curve */
190        scaled[i] = (uint32_t)((point[i] - sf->offsets[i]) *
191                               sf->scales[i]);
192    }
193    return scaled;
194}
195
196
197void set_bit_sized(unsigned char *bitmap, uint16_t size, uint16_t bit)
198{
199    (MAP_CHUNK(bitmap, size, bit)) |= (1 << CHUNK_OFFSET(bit));
200}
201
202
203unsigned char *interleave_uint32s(uint32_t *numbers, uint16_t num)
204{
205    uint8_t i;
206    uint16_t j, bitmap_size;
207    unsigned char *bitmap = NULL;
208
209    cb_assert(num < 16384);
210
211    /* bitmap_size in bits (hence the `*8`) */
212    bitmap_size = (sizeof(uint32_t) * num * 8);
213    bitmap = (unsigned char *)cb_calloc(bitmap_size / 8, sizeof(unsigned char));
214    if (bitmap == NULL) {
215        return NULL;
216    }
217
218    /* i is the bit offset within a number
219     * j is the current number offset */
220    for (i = 0; i * num < bitmap_size; i++) {
221        for (j = 0; j < num; j++) {
222            /* Start with the last number, as we built up the bitmap
223             * from right to left */
224            if (IS_BIT_SET(numbers[(num - 1) - j], i)) {
225                set_bit_sized(bitmap, bitmap_size/8, (i * num) + j);
226            }
227        }
228    }
229    return bitmap;
230}
231
232
233STATIC couchstore_error_t decode_spatial_key(const char *key, sized_mbb_t *mbb)
234{
235    mbb->num = decode_raw16(*((raw_16 *) key));
236    mbb->mbb = (double *)(key + 2);
237    return COUCHSTORE_SUCCESS;
238}
239
240
241STATIC couchstore_error_t encode_spatial_key(const sized_mbb_t *mbb,
242                                             char *key,
243                                             size_t nkey)
244{
245    raw_16 num = encode_raw16(mbb->num);
246
247    memcpy(key, &num, 2);
248    key += 2;
249
250    cb_assert(mbb->num * sizeof(double) <= nkey);
251    memcpy(key, mbb->mbb, mbb->num * sizeof(double));
252
253    return COUCHSTORE_SUCCESS;
254}
255
256
257/* Expands the `original` MBB with the `expander` */
258STATIC couchstore_error_t expand_mbb(sized_mbb_t *original,
259                                     sized_mbb_t *expander)
260{
261    uint16_t i;
262
263    cb_assert(original->num == expander->num);
264
265    // For aligned access
266    // Copy original->mbb and expander->mbb into their aligned containers
267    std::vector<double> alignedOrig(original->mbb, original->mbb + original->num);
268    std::vector<double> alignedExp(expander->mbb, expander->mbb + expander->num);
269
270    for (i = 0; i < original->num; ++i) {
271        if (i % 2 == 0) {
272            alignedOrig[i] = std::min(alignedOrig[i], alignedExp[i]);
273        } else {
274            alignedOrig[i] = std::max(alignedOrig[i], alignedExp[i]);
275        }
276    }
277
278    // Copy back the calculated bounding box back to original->mbb
279    std::copy(alignedOrig.begin(), alignedOrig.end(), original->mbb);
280
281    return COUCHSTORE_SUCCESS;
282}
283
284
285/* This reduce function is also used for the re-reduce */
286couchstore_error_t view_spatial_reduce(char *dst,
287                                       size_t *size_r,
288                                       const nodelist *leaflist,
289                                       int count,
290                                       void *ctx)
291{
292    sized_mbb_t enclosing;
293    sized_mbb_t tmp_mbb;
294    const nodelist *i;
295    (void) ctx;
296
297    decode_spatial_key(leaflist->key.buf, &enclosing);
298    count--;
299
300    for (i = leaflist->next; i != NULL && count > 0; i = i->next, count--) {
301        decode_spatial_key(i->key.buf, &tmp_mbb);
302        expand_mbb(&enclosing, &tmp_mbb);
303    }
304
305    encode_spatial_key(&enclosing, dst, MAX_REDUCTION_SIZE);
306    /* 2 is the prefix with the number of doubles */
307    *size_r = 2 + (enclosing.num * sizeof(double));
308
309    return COUCHSTORE_SUCCESS;
310}
311
312
313int view_spatial_filter(const sized_buf *k, const sized_buf *v,
314                        const bitmap_t *bm)
315{
316    uint16_t partition = 0;
317    (void) k;
318
319    partition = decode_raw16(*((raw_16 *) v->buf));
320    return is_bit_set(bm, partition);
321}
322