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