Changeset: a9977cbf44b8 for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=a9977cbf44b8 Modified Files: sql/backends/monet5/k3m/3dtree.c sql/backends/monet5/k3m/3dtree.h sql/backends/monet5/k3m/Tests/k3m.sql sql/backends/monet5/k3m/k3m.c Branch: k3match Log Message:
K3M: Support insertion into existing tree diffs (truncated from 339 to 300 lines): diff --git a/sql/backends/monet5/k3m/3dtree.c b/sql/backends/monet5/k3m/3dtree.c --- a/sql/backends/monet5/k3m/3dtree.c +++ b/sql/backends/monet5/k3m/3dtree.c @@ -1,25 +1,16 @@ /************************************************************************** - * This file is part of the K3Match library. * - * Copyright (C) 2010 Pim Schellart <[email protected]> * + * This file is part of K3Match. * + * Copyright (C) 2016 Pim Schellart <[email protected]> * * * - * This library is free software: you can redistribute it and/or modify * - * it under the terms of the GNU General Public License as published by * - * the Free Software Foundation, either version 3 of the License, or * - * (at your option) any later version. * - * * - * This library is distributed in the hope that it will be useful, * - * but WITHOUT ANY WARRANTY; without even the implied warranty of * - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * - * GNU General Public License for more details. * - * * - * You should have received a copy of the GNU General Public License * - * along with this library. If not, see <http://www.gnu.org/licenses/>. * + * This Source Code Form is subject to the terms of the Mozilla Public * + * License, v. 2.0. If a copy of the MPL was not distributed with this * + * file, You can obtain one at http://mozilla.org/MPL/2.0/. * **************************************************************************/ #include <stdlib.h> #include <stdio.h> -#include "k3match.h" +#include <k3match.h> #define SQUARE(x) ((x) * (x)) @@ -57,6 +48,40 @@ void k3m_build_balanced_tree(node_t *tre } } +node_t* k3m_insert_node(node_t *tree, node_t *node) +{ + int axis = 0; + node_t *parent = NULL; + node_t *current = tree; + + node->left = NULL; + node->right = NULL; + node->parent = NULL; + + while (current != NULL) { + parent = current; + if (node->point->value[axis] < current->point->value[axis]) { + current = current->left; + } else { + current = current->right; + } + axis = (axis + 1) % 3; + } + + node->parent = parent; + node->axis = axis; + + if (tree == NULL) { + tree = node; + } else if (node->point->value[parent->axis] < parent->point->value[parent->axis]) { + parent->left = node; + } else { + parent->right = node; + } + + return tree; +} + void k3m_print_tree(node_t *tree) { if (!tree) return; diff --git a/sql/backends/monet5/k3m/3dtree.h b/sql/backends/monet5/k3m/3dtree.h --- a/sql/backends/monet5/k3m/3dtree.h +++ b/sql/backends/monet5/k3m/3dtree.h @@ -1,24 +1,17 @@ /************************************************************************** - * This file is part of the K3Match library. * - * Copyright (C) 2010 Pim Schellart <[email protected]> * + * This file is part of K3Match. * + * Copyright (C) 2016 Pim Schellart <[email protected]> * * * - * This library is free software: you can redistribute it and/or modify * - * it under the terms of the GNU General Public License as published by * - * the Free Software Foundation, either version 3 of the License, or * - * (at your option) any later version. * - * * - * This library is distributed in the hope that it will be useful, * - * but WITHOUT ANY WARRANTY; without even the implied warranty of * - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * - * GNU General Public License for more details. * - * * - * You should have received a copy of the GNU General Public License * - * along with this library. If not, see <http://www.gnu.org/licenses/>. * + * This Source Code Form is subject to the terms of the Mozilla Public * + * License, v. 2.0. If a copy of the MPL was not distributed with this * + * file, You can obtain one at http://mozilla.org/MPL/2.0/. * **************************************************************************/ #ifndef __K3MATCH_3DTREE_H__ #define __K3MATCH_3DTREE_H__ +#include <k3match.h> + typedef struct node_t node_t; struct node_t { @@ -35,6 +28,8 @@ void k3m_print_tree(node_t *tree); void k3m_print_dot_tree(node_t *tree); +node_t* k3m_insert_node(node_t *tree, node_t *node); + node_t* k3m_closest_leaf(node_t *tree, point_t *point); node_t* k3m_nearest_neighbour(node_t *tree, point_t *point); diff --git a/sql/backends/monet5/k3m/Tests/k3m.sql b/sql/backends/monet5/k3m/Tests/k3m.sql --- a/sql/backends/monet5/k3m/Tests/k3m.sql +++ b/sql/backends/monet5/k3m/Tests/k3m.sql @@ -4,14 +4,30 @@ start transaction; create table catalog(id int, ra double, decl double); insert into catalog values (1, 222.3, 79.5 ), (2, 122.3, 88.5), (3, 22.3, 79.5 ), (4, 88.0, 38.0); + +create table catalog2(id int, ra double, decl double); +insert into catalog2 values (5, 122.3, 89.5 ), (6, 32.3, 98.5), (7, 32.3, 89.5 ), (8, 98.0, 48.0); + + create table sourcelist(id int, ra double, decl double); insert into sourcelist values (11, 22.305, 79.499 ), (12,122.305, 88.499), (13, 222.305, 79.499 ); select * from k3m_free(); -select * from k3m_build((select id, ra, decl from catalog as s)); -select * from k3m_query((select id, ra, decl, 0.01745329 from sourcelist)); +select * from k3m_build((select id, ra*PI()/180, decl*PI()/180 from catalog as s)); +select * from k3m_query((select id, ra*PI()/180, decl*PI()/180, 0.01745329 from sourcelist)); + + +select * from k3m_build((select id, ra*PI()/180, decl*PI()/180 from catalog2 as s)); +select * from k3m_query((select id, ra*PI()/180, decl*PI()/180, 0.01745329 from sourcelist)) order by idc; select * from k3m_free(); +create table catalog_union as select id, ra*PI()/180, decl*PI()/180 from catalog union all select id, ra*PI()/180, decl*PI()/180 from catalog2 with data; + +select * from k3m_build((select * from catalog_union as s)); +select * from k3m_query((select id, ra*PI()/180, decl*PI()/180, 0.01745329 from sourcelist)) order by idc; +; + + ROLLBACK; diff --git a/sql/backends/monet5/k3m/k3m.c b/sql/backends/monet5/k3m/k3m.c --- a/sql/backends/monet5/k3m/k3m.c +++ b/sql/backends/monet5/k3m/k3m.c @@ -40,6 +40,12 @@ typedef struct { static k3m_tree_tpe *k3m_tree = NULL; static MT_Lock k3m_lock; +#define K3M_ALLOCS_DEFAULT_SIZE 10 + +static size_t k3m_allocs_size = K3M_ALLOCS_DEFAULT_SIZE; +static size_t k3m_allocs_pos = 0; +static k3m_tree_tpe **k3m_allocs = NULL; + k3m_export str K3Mprelude(void *ret) { (void) ret; MT_lock_init(&k3m_lock, "k3m_lock"); @@ -54,11 +60,10 @@ str K3Mbuild(Client cntxt, MalBlkPtr mb, int_t i; int_t npool = 0; bit b = bit_nil; - - K3Mfree(cntxt, mb, stk, pci); + bit newtree = !k3m_tree; + k3m_tree_tpe *k3m_tree_alloc = NULL; + (void) cntxt; MT_lock_set(&k3m_lock); - k3m_tree = GDKmalloc(sizeof(k3m_tree_tpe)); - assert(k3m_tree); if (!isaBatType(getArgType(mb,pci,0)) || !isaBatType(getArgType(mb,pci,1)) || !isaBatType(getArgType(mb,pci,2)) || !isaBatType(getArgType(mb,pci,3))) { @@ -70,51 +75,90 @@ str K3Mbuild(Client cntxt, MalBlkPtr mb, } } ids = BATdescriptor(*getArgReference_bat(stk, pci, 1)); - ra = BATdescriptor(*getArgReference_bat(stk, pci, 2)); + ra = BATdescriptor(*getArgReference_bat(stk, pci, 2)); dec = BATdescriptor(*getArgReference_bat(stk, pci, 3)); N_a = BATcount(ids); assert(ids && ra && dec); // TODO: dynamic checks & errors instead of asserts ids_a = ((int*) Tloc(ids, BUNfirst(ids))); - ra_a = ((dbl*) Tloc(ra, BUNfirst(ra))); + ra_a = ((dbl*) Tloc(ra, BUNfirst(ra))); dec_a = ((dbl*) Tloc(dec, BUNfirst(dec))); assert(ids_a && ra_a && dec_a); // TODO: dynamic checks & errors instead of asserts - k3m_tree->values = GDKmalloc(3 * N_a * sizeof(real_t)); - k3m_tree->catalog = GDKmalloc(N_a * sizeof(point_t*)); - *k3m_tree->catalog = GDKmalloc(N_a * sizeof(point_t)); - k3m_tree->tree = (node_t*) GDKmalloc(N_a * sizeof(node_t)); + if (newtree) { + k3m_tree = GDKmalloc(sizeof(k3m_tree_tpe)); + k3m_allocs = GDKmalloc(k3m_allocs_size); + if (!k3m_allocs) { + // yes I know we should probably free some stuff here but its very unlikely this fails + return createException(MAL, "k3m.build", "Memory allocation failed 1."); + } + k3m_allocs[k3m_allocs_pos++] = k3m_tree; + k3m_tree_alloc = k3m_tree; + } else { + k3m_tree_alloc = GDKmalloc(sizeof(k3m_tree_tpe)); + // enlarge malloc pointer array size if neccessary + if (k3m_allocs_pos >= k3m_allocs_size) { + k3m_allocs_size *= 2; + k3m_allocs = GDKrealloc(k3m_allocs, k3m_allocs_size); + if (!k3m_allocs) { + // see above + return createException(MAL, "k3m.build", "Memory allocation failed 2."); + } + } + k3m_allocs[k3m_allocs_pos++] = k3m_tree_alloc; + } - if (!k3m_tree->values || !k3m_tree->catalog || !*k3m_tree->catalog || !k3m_tree) { - if (k3m_tree->values) { - GDKfree(k3m_tree->values); + if (!k3m_tree || !k3m_tree_alloc) { + if (k3m_tree) { + GDKfree(k3m_tree); } - if (k3m_tree->catalog) { - GDKfree(k3m_tree->catalog); + if (k3m_tree_alloc) { + GDKfree(k3m_tree_alloc); } - if (*k3m_tree->catalog) { - GDKfree(*k3m_tree->catalog); + return createException(MAL, "k3m.build", "Memory allocation failed 3."); + } + + k3m_tree_alloc->values = GDKmalloc(3 * N_a * sizeof(real_t)); + k3m_tree_alloc->catalog = GDKmalloc(N_a * sizeof(point_t*)); + *k3m_tree_alloc->catalog = GDKmalloc(N_a * sizeof(point_t)); + k3m_tree_alloc->tree = (node_t*) GDKmalloc(N_a * sizeof(node_t)); + + if (!k3m_tree_alloc->values || !k3m_tree_alloc->catalog || !*k3m_tree_alloc->catalog) { + if (k3m_tree_alloc->values) { + GDKfree(k3m_tree_alloc->values); } - if (k3m_tree->tree) { - GDKfree(k3m_tree->tree); + if (k3m_tree_alloc->catalog) { + GDKfree(k3m_tree_alloc->catalog); } - return createException(MAL, "k3m.build", "Memory allocation failed."); + if (*k3m_tree_alloc->catalog) { + GDKfree(*k3m_tree_alloc->catalog); + } + if (k3m_tree_alloc->tree) { + GDKfree(k3m_tree_alloc->tree); + } + return createException(MAL, "k3m.build", "Memory allocation failed 4."); } for (i=0; i<N_a; i++) { - k3m_tree->catalog[i] = k3m_tree->catalog[0] + i; - k3m_tree->catalog[i]->id = ids_a[i]; - k3m_tree->catalog[i]->value = k3m_tree->values + 3 * i; - k3m_tree->catalog[i]->value[0] = cos(dec_a[i]) * cos(ra_a[i]); - k3m_tree->catalog[i]->value[1] = cos(dec_a[i]) * sin(ra_a[i]); - k3m_tree->catalog[i]->value[2] = sin(dec_a[i]); + k3m_tree_alloc->catalog[i] = k3m_tree_alloc->catalog[0] + i; + k3m_tree_alloc->catalog[i]->id = ids_a[i]; + k3m_tree_alloc->catalog[i]->value = k3m_tree_alloc->values + 3 * i; + k3m_tree_alloc->catalog[i]->value[0] = cos(dec_a[i]) * cos(ra_a[i]); + k3m_tree_alloc->catalog[i]->value[1] = cos(dec_a[i]) * sin(ra_a[i]); + k3m_tree_alloc->catalog[i]->value[2] = sin(dec_a[i]); } - k3m_tree->tree->parent = NULL; - k3m_build_balanced_tree(k3m_tree->tree, k3m_tree->catalog, N_a, 0, &npool); - + if (newtree) { + k3m_tree->tree->parent = NULL; + k3m_build_balanced_tree(k3m_tree->tree, k3m_tree->catalog, N_a, 0, &npool); + } else { + for (i=0; i<N_a; i++) { + k3m_tree_alloc->tree[i].point = k3m_tree_alloc->catalog[i]; + k3m_tree->tree = k3m_insert_node(k3m_tree->tree, &k3m_tree_alloc->tree[i]); + } + } _______________________________________________ checkin-list mailing list [email protected] https://www.monetdb.org/mailman/listinfo/checkin-list
