xref: /4.0.0/couchstore/src/views/spatial.h (revision 537148b0)
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#ifndef _VIEW_SPATIAL_UTILS_H
22#define _VIEW_SPATIAL_UTILS_H
23
24#include "config.h"
25#include <libcouchstore/couch_db.h>
26#include "../file_merger.h"
27#include "../couch_btree.h"
28#include "bitmap.h"
29
30#ifdef __cplusplus
31extern "C" {
32#endif
33    #define ZCODE_PRECISION 32
34    #define ZCODE_MAX_VALUE UINT32_MAX
35
36    typedef struct {
37        double *mbb;
38        /* the total number of values (two times the dimension) */
39        uint16_t num;
40    } sized_mbb_t;
41
42    /* It is used to scale up MBBs to the relative size of an enclosing one */
43    typedef struct {
44        /* The offset the value needs to be shifted in order to be in the
45         * origin of the enclosing MBB */
46        double *offsets;
47        /* The scale factors for every dimension */
48        double *scales;
49        /* the total number of values, one per dimension */
50        uint8_t dim;
51    } scale_factor_t;
52
53    /* The context to build the initial index */
54    typedef struct {
55        arena                   *transient_arena;
56        couchfile_modify_result *modify_result;
57        /* Scale MBBs up for a better results when using the space filling
58         * curve */
59        scale_factor_t          *scale_factor;
60    } view_spatial_builder_ctx_t;
61
62    /* compare keys of a spatial index */
63    int spatial_key_cmp(const sized_buf *key1, const sized_buf *key2,
64                        const void *user_ctx);
65
66    /* Compare keys of a spatial index for the file merger */
67    int spatial_merger_key_cmp(const sized_buf *key1, const sized_buf *key2,
68                               const void *user_ctx);
69
70    /* Return the scale factor for every dimension that would be needed to
71     * scale this MBB to the maximum value `max` (when shifted to the
72     * origin)
73     * Memory is dynamically allocted within the function, make sure to call
74     * free_spatial_scale_factor() afterwards */
75    scale_factor_t *spatial_scale_factor(const double *mbb, uint16_t dim,
76                                         uint32_t max);
77
78    /* Free the memory that spatial_scale_factor() allocated */
79    void free_spatial_scale_factor(scale_factor_t *sf);
80
81    /* Calculate the center of an multi-dimensional bounding box (MBB) */
82    double *spatial_center(const sized_mbb_t *mbb);
83
84    /* Scales all dimensions of a (multi-dimensional) point
85     * with the given factor and offset */
86    uint32_t *spatial_scale_point(const double *point,
87                                  const scale_factor_t *sf);
88
89    /* Set a bit on a buffer with a certain size */
90    void set_bit_sized(unsigned char *bitmap, uint16_t size, uint16_t bit);
91
92    /* Interleave numbers bitwise. The return value is a unsigned char array
93     * with length 4 bytes * number of numbers.
94     * The maximum number of numbers is (2^14)-1 (16383). */
95    unsigned char *interleave_uint32s(uint32_t *numbers, uint16_t num);
96
97    /* A reduce is used to calculate the enclosing MBB of a parent node (it's
98     * its key) */
99    couchstore_error_t view_spatial_reduce(char *dst,
100                                           size_t *size_r,
101                                           const nodelist *leaflist,
102                                           int count,
103                                           void *ctx);
104
105    /* Puts an item into the results set. If there are enough items they are
106     * are flused to disk */
107    couchstore_error_t spatial_push_item(sized_buf *k, sized_buf *v,
108                                         couchfile_modify_result *dst);
109
110    /* Build an r-tree bottom-up from the already stored leaf nodes */
111    node_pointer* complete_new_spatial(couchfile_modify_result* mr,
112                                       couchstore_error_t *errcode);
113
114    /* Filter function for the compactor */
115    int view_spatial_filter(const sized_buf *k, const sized_buf *v,
116                            const bitmap_t *bm);
117#ifdef __cplusplus
118}
119#endif
120
121#endif
122