kdtree的源码C语言版

/*
This file is part of ‘‘kdtree‘‘ a library for working with kd-trees.
Copyright （C） 2007-2009 John Tsiombikas 

Redistribution and use in source and binary forms with or without
modification are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice this
   list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ‘‘AS IS‘‘ AND ANY EXPRESS OR IMPLIED
WARRANTIES INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT INDIRECT INCIDENTAL SPECIAL
EXEMPLARY OR CONSEQUENTIAL DAMAGES （INCLUDING BUT NOT LIMITED TO PROCUREMENT
OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE DATA OR PROFITS; OR BUSINESS
INTERRUPTION） HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY WHETHER IN
CONTRACT STRICT LIABILITY OR TORT （INCLUDING NEGLIGENCE OR OTHERWISE） ARISING
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE EVEN IF ADVISED OF THE POSSIBILITY
OF SUCH DAMAGE.
*/
/* single nearest neighbor search written by Tamas Nepusz  */
#include 
#include 
#include 
#include 
#include “kdtree.h“

#if defined（WIN32） || defined（__WIN32__）
#include 
#endif

#ifdef USE_LIST_NODE_ALLOCATOR

#ifndef NO_PTHREADS
#include 
#else

#ifndef I_WANT_THREAD_BUGS
#error “You are compiling with the fast list node allocator with pthreads disabled! This WILL break if used from multiple threads.“
#endif	/* I want thread bugs */

#endif	/* pthread support */
#endif	/* use list node allocator */

struct kdhyperrect {
	int dim;
	double *min *max;              /* minimum/maximum coords */
};

struct kdnode {
	double *pos;
	int dir;
	void *data;

	struct kdnode *left *right;	/* negative/positive side */
};

struct res_node {
	struct kdnode *item;
	double dist_sq;
	struct res_node *next;
};

struct kdtree {
	int dim;
	struct kdnode *root;
	struct kdhyperrect *rect;
	void （*destr）（void*）;
};

struct kdres {
	struct kdtree *tree;
	struct res_node *rlist *riter;
	int size;
};

#define SQ（x）			（（x） * （x））


static void clear_rec（struct kdnode *node void （*destr）（void*））;
static int insert_rec（struct kdnode **node const double *pos void *data int dir int dim）;
static int rlist_insert（struct res_node *list struct kdnode *item double dist_sq）;
static void clear_results（struct kdres *set）;

static struct kdhyperrect* hyperrect_create（int dim const double *min const double *max）;
static void hyperrect_free（struc