xref: /3.0.2-MP2/couchstore/src/views/spatial.c (revision 9a8beb97)
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
27
28#define BYTE_PER_COORD sizeof(uint32_t)
29
30#define IS_BIT_SET(num, bit)        (num & (1 << bit))
31#define CHUNK_BITS                  (sizeof(unsigned char) * CHAR_BIT)
32#define CHUNK_INDEX(map, size, bit) (size - 1 - ((bit) / CHUNK_BITS))
33#define MAP_CHUNK(map, size, bit)   (map)[CHUNK_INDEX(map, size, bit)]
34#define CHUNK_OFFSET(bit)           ((bit) % CHUNK_BITS)
35
36#define MIN(a, b) (a) < (b) ? a : b
37#define MAX(a, b) (a) > (b) ? a : b
38
39
40STATIC couchstore_error_t encode_spatial_key(const sized_mbb_t *mbb,
41                                          char *key,
42                                          size_t nkey);
43STATIC couchstore_error_t decode_spatial_key(const char *key,
44                                             sized_mbb_t *mbb);
45STATIC couchstore_error_t expand_mbb(sized_mbb_t *original,
46                                     sized_mbb_t *expander);
47
48
49int spatial_key_cmp(const sized_buf *key1, const sized_buf *key2,
50                    const void *user_ctx)
51{
52    scale_factor_t *sf =
53            ((view_spatial_builder_ctx_t *) user_ctx)->scale_factor;
54    uint16_t mbb1_num = decode_raw16(*((raw_16 *) key1->buf));
55    uint16_t mbb2_num = decode_raw16(*((raw_16 *) key2->buf));
56    sized_mbb_t mbbs[2];
57    double *mbbs_center[2];
58    uint32_t *mbbs_scaled[2];
59    unsigned char *mbbs_zcode[2];
60    int res;
61
62    mbbs[0].num = mbb1_num;
63    mbbs[0].mbb = (double *)(key1->buf + sizeof(uint16_t));
64    mbbs_center[0] = spatial_center(&mbbs[0]);
65    mbbs_scaled[0] = spatial_scale_point(mbbs_center[0], sf);
66    mbbs_zcode[0] = interleave_uint32s(mbbs_scaled[0], sf->dim);
67
68    mbbs[1].num = mbb2_num;
69    mbbs[1].mbb = (double *)(key2->buf + sizeof(uint16_t));
70    mbbs_center[1] = spatial_center(&mbbs[1]);
71    mbbs_scaled[1] = spatial_scale_point(mbbs_center[1], sf);
72    mbbs_zcode[1] = interleave_uint32s(mbbs_scaled[1], sf->dim);
73
74    res = memcmp(mbbs_zcode[0], mbbs_zcode[1], sf->dim * BYTE_PER_COORD);
75
76    free(mbbs_center[0]);
77    free(mbbs_scaled[0]);
78    free(mbbs_zcode[0]);
79    free(mbbs_center[1]);
80    free(mbbs_scaled[1]);
81    free(mbbs_zcode[1]);
82
83    return res;
84}
85
86
87scale_factor_t *spatial_scale_factor(const double *mbb, uint16_t dim,
88                                     uint32_t max)
89{
90    int i;
91    double range;
92    scale_factor_t *sf = NULL;
93    double *offsets = NULL;
94    double *scales = NULL;
95
96    sf = (scale_factor_t *)malloc(sizeof(scale_factor_t));
97    if (sf == NULL) {
98        return NULL;
99    }
100    offsets = (double *)malloc(sizeof(double) * dim);
101    if (offsets == NULL) {
102        free(sf);
103        return NULL;
104    }
105    scales = (double *)malloc(sizeof(double) * dim);
106    if (scales == NULL) {
107        free(sf);
108        free(offsets);
109        return NULL;
110    }
111
112    for (i = 0; i < dim; ++i) {
113        offsets[i] = mbb[i*2];
114        range = mbb[(i * 2) + 1] - mbb[i * 2];
115        if (range == 0.0) {
116            scales[i] = 0.0;
117        } else {
118            scales[i] = max / range;
119        }
120    }
121
122    sf->offsets = offsets;
123    sf->scales = scales;
124    sf->dim = dim;
125    return sf;
126}
127
128void free_spatial_scale_factor(scale_factor_t *sf)
129{
130    if (sf == NULL) {
131        return;
132    }
133    free(sf->offsets);
134    free(sf->scales);
135    free(sf);
136}
137
138
139double *spatial_center(const sized_mbb_t *mbb)
140{
141    double *center = (double *)malloc(sizeof(double) * (mbb->num/2));
142    uint32_t i;
143    if (center == NULL) {
144        return NULL;
145    }
146
147    for (i = 0; i < mbb->num; i += 2) {
148        center[i/2] = mbb->mbb[i] + ((mbb->mbb[i+1] - mbb->mbb[i])/2);
149    }
150    return center;
151}
152
153
154uint32_t *spatial_scale_point(const double *point, const scale_factor_t *sf)
155{
156    int i;
157    uint32_t *scaled = (uint32_t *)malloc(sizeof(uint32_t) * sf->dim);
158    if (scaled == NULL) {
159        return NULL;
160    }
161
162    for (i = 0; i < sf->dim; ++i) {
163        /* casting to int is OK. No rounding is needed for the
164           space-filling curve */
165        scaled[i] = (uint32_t)((point[i] - sf->offsets[i]) *
166                               sf->scales[i]);
167    }
168    return scaled;
169}
170
171
172void set_bit_sized(unsigned char *bitmap, uint16_t size, uint16_t bit)
173{
174    (MAP_CHUNK(bitmap, size, bit)) |= (1 << CHUNK_OFFSET(bit));
175}
176
177
178unsigned char *interleave_uint32s(uint32_t *numbers, uint16_t num)
179{
180    uint8_t i;
181    uint16_t j, bitmap_size;
182    unsigned char *bitmap = NULL;
183
184    assert(num < 16384);
185
186    /* bitmap_size in bits (hence the `*8`) */
187    bitmap_size = (sizeof(uint32_t) * num * 8);
188    bitmap = (unsigned char *)calloc(bitmap_size / 8, sizeof(unsigned char));
189    if (bitmap == NULL) {
190        return NULL;
191    }
192
193    /* i is the bit offset within a number
194     * j is the current number offset */
195    for (i = 0; i * num < bitmap_size; i++) {
196        for (j = 0; j < num; j++) {
197            /* Start with the last number, as we built up the bitmap
198             * from right to left */
199            if (IS_BIT_SET(numbers[(num - 1) - j], i)) {
200                set_bit_sized(bitmap, bitmap_size/8, (i * num) + j);
201            }
202        }
203    }
204    return bitmap;
205}
206
207
208STATIC couchstore_error_t decode_spatial_key(const char *key, sized_mbb_t *mbb)
209{
210    mbb->num = decode_raw16(*((raw_16 *) key));
211    mbb->mbb = (double *)(key + 2);
212    return COUCHSTORE_SUCCESS;
213}
214
215
216STATIC couchstore_error_t encode_spatial_key(const sized_mbb_t *mbb,
217                                             char *key,
218                                             size_t nkey)
219{
220    raw_16 num = encode_raw16(mbb->num);
221
222    memcpy(key, &num, 2);
223    key += 2;
224
225    assert(mbb->num * sizeof(double) <= nkey);
226    memcpy(key, mbb->mbb, mbb->num * sizeof(double));
227
228    return COUCHSTORE_SUCCESS;
229}
230
231
232/* Expands the `original` MBB with the `expander` */
233STATIC couchstore_error_t expand_mbb(sized_mbb_t *original,
234                                     sized_mbb_t *expander) {
235    int i;
236
237    assert(original->num == expander->num);
238
239    for (i = 0; i < original->num; ++i) {
240        if (i % 2 == 0) {
241            original->mbb[i] = MIN(original->mbb[i], expander->mbb[i]);
242        } else {
243            original->mbb[i] = MAX(original->mbb[i], expander->mbb[i]);
244        }
245    }
246
247    return COUCHSTORE_SUCCESS;
248}
249