#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <fcntl.h>
#include <unistd.h>
#include "kdt.h"

Include dependency graph for kdt.c:

Data Structures
struct	Buffer

struct	Node

struct	Header

struct	_Kdt

struct	FilePointers

Macros
#define	MIN(a, b) ((a) < (b) ? (a) : (b))

#define	MAX(a, b) ((a) > (b) ? (a) : (b))

#define	VERSION 20120405 /* the file format version */

#define	GAP 0.2

#define	MINLEN 6

Functions
FILE *	kdt_tmpfile (void)

static Buffer *	buffer_new (long len)

static Buffer *	buffer_ref (Buffer *b)

static void	buffer_unref (Buffer *b)

void	kdt_heap_resize (KdtHeap *h, long len)

static long	heap_read (KdtHeap *h, long len)

static void	heap_write (KdtHeap *h, long len)

void	kdt_heap_create (KdtHeap h, FILE fp, long start, long len, long buflen)

void	kdt_heap_rewind (KdtHeap *h)

int	kdt_heap_get (KdtHeap h, KdtPoint p)

void	kdt_heap_split (KdtHeap h1, long len1, KdtHeap h2)

void	kdt_heap_put (KdtHeap h, KdtPoint p)

void	kdt_heap_flush (KdtHeap *h)

void	kdt_heap_free (KdtHeap *h)

static int	put (KdtHeap h, KdtPoint p, KdtHeap *merged)

void	kdt_write (KdtHeap h, FILE fp)

static void	merge (KdtHeap h1, KdtHeap h2, int(compar)(const void , const void *), long buflen)

static void	kdt_heap_sort (KdtHeap h, int(compar)(const void , const void ), void(progress)(void ), void *data)

static int	kdt_heap_sort_cost (long len, long buflen)

static int	check_32_bits (const Kdt *kdt)

static void	sizes (const Node n, long nodes, long sums, long leaves)

static void	relative (const KdtRect rect, double o, double h)

static void	sum_add_point (const KdtRect parent, KdtSumCore sum, const KdtPoint a, double w)

static float	area (const KdtRect rect)

static float	length (const KdtRect rect)

void	kdt_rect_write (const KdtRect rect, FILE *fp)

static int	sort_x (const void p1, const void p2)

static int	sort_y (const void p1, const void p2)

static void	kdt_sum_core_init (KdtSumCore *s)

static int	update_sum (const KdtRect rect, KdtSumCore n, KdtHeap h, int index)

static long	update_bounds (KdtRect rect, KdtHeap *h)

static void	progress (void *data)

static void	fwrite_check (const void ptr, size_t size, size_t nmemb, FILE stream)

static void	union_bound (KdtRect b, const KdtRect b1, const KdtRect b2)

static int	split (KdtHeap h1, KdtRect bound, int index, Kdt kdt, float *coverage)

Kdt *	kdt_new (void)

static FILE *	open_ext (const char name, const char ext, const char *mode)

static int	kdt_init (Kdt kdt, const char name, int npmax, long len)

int	kdt_create (Kdt kdt, const char name, int blksize, KdtHeap h, void(progress)(float complete, void data), void data)

int	kdt_open (Kdt kdt, const char name)

void	kdt_destroy (Kdt *kdt)

int	kdt_intersects (const KdtRect rect, const KdtRect query)

int	kdt_includes (const KdtRect rect, const KdtRect query)

static long	query (const Kdt *kdt, const KdtRect rect, long len)

long	kdt_query (const Kdt *kdt, const KdtRect rect)

static void	intersection (const KdtRect rect1, const KdtRect rect2, KdtRect inter)

static float	intersection_area (const KdtRect rect1, const KdtRect rect2)

static void	sum_add_sum (const KdtRect parent, KdtSum sum, const KdtRect rect, const KdtSumCore a)

static long	query_sum (const Kdt kdt, KdtCheck includes, KdtCheck intersects, void data, KdtRect bound, long len, FilePointers f, const KdtRect query, KdtSum sum)

long	kdt_query_sum (const Kdt kdt, KdtCheck includes, KdtCheck intersects, void data, const KdtRect query, KdtSum *sum)

void	kdt_sum_init (KdtSum *s)

Macro Definition Documentation

◆ GAP

#define GAP 0.2

Definition at line 475 of file kdt.c.

◆ MAX

#define MAX	(	a,
		b
	)	((a) > (b) ? (a) : (b))

Definition at line 36 of file kdt.c.

◆ MIN

#define MIN	(	a,
		b
	)	((a) < (b) ? (a) : (b))

Definition at line 35 of file kdt.c.

◆ MINLEN

#define MINLEN 6

Definition at line 476 of file kdt.c.

◆ VERSION

#define VERSION 20120405 /* the file format version */

Definition at line 38 of file kdt.c.

Function Documentation

◆ area()

static float area ( const KdtRect rect )

static

Definition at line 439 of file kdt.c.

References h, l, and x.

Referenced by centroids_curvature_fit(), embed_area_center(), embed_flux(), embed_force(), embed_geometry(), event_viscous_term(), height_curvature_fit(), interface_area(), intersection_area(), line_area(), query_sum(), split(), sum_add_sum(), and zarea().

Here is the caller graph for this function:

◆ buffer_new()

static Buffer * buffer_new ( long len )

static

Definition at line 66 of file kdt.c.

References b, and x.

Referenced by kdt_heap_create().

Here is the caller graph for this function:

◆ buffer_ref()

static Buffer * buffer_ref ( Buffer * b )

static

Definition at line 74 of file kdt.c.

References b, and Buffer::ref.

Referenced by kdt_heap_split().

Here is the caller graph for this function:

◆ buffer_unref()

static void buffer_unref ( Buffer * b )

static

Definition at line 80 of file kdt.c.

References b, and free().

Referenced by kdt_heap_free().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ check_32_bits()

static int check_32_bits ( const Kdt * kdt )

static

Definition at line 368 of file kdt.c.

References x.

Referenced by kdt_init(), and kdt_open().

Here is the caller graph for this function:

◆ fwrite_check()

static void fwrite_check	(	const void *	ptr,
		size_t	size,
		size_t	nmemb,
		FILE *	stream
	)

static

Definition at line 526 of file kdt.c.

References size, and x.

Referenced by kdt_create(), and split().

Here is the caller graph for this function:

◆ heap_read()

static long heap_read	(	KdtHeap *	h,
		long	len
	)

static

Definition at line 106 of file kdt.c.

References assert, h, n, sizeof(), and x.

Referenced by kdt_heap_create(), kdt_heap_get(), and kdt_heap_rewind().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ heap_write()

static void heap_write	(	KdtHeap *	h,
		long	len
	)

static

Definition at line 123 of file kdt.c.

References assert, h, sizeof(), and x.

Referenced by kdt_heap_flush(), and kdt_heap_put().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ intersection()

static void intersection	(	const KdtRect	rect1,
		const KdtRect	rect2,
		KdtRect	inter
	)

static

Definition at line 846 of file kdt.c.

References assert, h, l, MAX, MIN, and x.

◆ intersection_area()

static float intersection_area	(	const KdtRect	rect1,
		const KdtRect	rect2
	)

static

Definition at line 856 of file kdt.c.

References area(), intersection, and x.

Referenced by query_sum(), and sum_add_sum().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_create()

int kdt_create	(	Kdt *	kdt,
		const char *	name,
		int	blksize,
		KdtHeap *	h,
		void()(float complete, void data)	progress,
		void *	data
	)

Definition at line 686 of file kdt.c.

References data, fwrite_check(), h, kdt_heap_resize(), kdt_heap_sort_cost(), kdt_init(), progress, sizeof(), split(), update_bounds(), and x.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_destroy()

void kdt_destroy ( Kdt * kdt )

Definition at line 757 of file kdt.c.

References free(), and x.

Referenced by delete_terrain(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_create()

void kdt_heap_create	(	KdtHeap *	h,
		FILE *	fp,
		long	start,
		long	len,
		long	buflen
	)

Definition at line 134 of file kdt.c.

References assert, buffer_new(), fp, h, heap_read(), scalar::i, and x.

Referenced by kdt_heap_split(), main(), and merge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_flush()

void kdt_heap_flush ( KdtHeap * h )

Definition at line 233 of file kdt.c.

References h, heap_write(), scalar::i, and x.

Referenced by kdt_heap_split(), main(), and merge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_free()

void kdt_heap_free ( KdtHeap * h )

Definition at line 239 of file kdt.c.

References assert, buffer_unref(), h, and x.

Referenced by kdt_heap_split(), merge(), and split().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_get()

int kdt_heap_get	(	KdtHeap *	h,
		KdtPoint *	p
	)

Definition at line 171 of file kdt.c.

References h, heap_read(), scalar::i, kdt_heap_get(), and p.

Referenced by kdt_heap_get(), kdt_heap_split(), kdt_write(), merge(), put(), update_bounds(), and update_sum().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_put()

void kdt_heap_put	(	KdtHeap *	h,
		KdtPoint *	p
	)

Definition at line 224 of file kdt.c.

References h, heap_write(), scalar::i, and p.

Referenced by kdt_heap_split(), main(), and put().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_resize()

void kdt_heap_resize	(	KdtHeap *	h,
		long	len
	)

Definition at line 91 of file kdt.c.

References assert, h, kdt_heap_rewind(), and x.

Referenced by kdt_create(), and kdt_heap_split().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_rewind()

void kdt_heap_rewind ( KdtHeap * h )

Definition at line 157 of file kdt.c.

References assert, h, heap_read(), scalar::i, sizeof(), and x.

Referenced by kdt_heap_resize(), kdt_heap_split(), kdt_write(), merge(), update_bounds(), and update_sum().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_sort()

static void kdt_heap_sort	(	KdtHeap *	h,
		int()(const void , const void *)	compar,
		void()(void )	progress,
		void *	data
	)

static

Definition at line 303 of file kdt.c.

References data, h, kdt_heap_sort(), kdt_heap_split(), merge(), progress, sizeof(), and x.

Referenced by kdt_heap_sort(), and split().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_sort_cost()

static int kdt_heap_sort_cost	(	long	len,
		long	buflen
	)

static

Definition at line 332 of file kdt.c.

References m().

Referenced by kdt_create(), and split().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_heap_split()

void kdt_heap_split	(	KdtHeap *	h1,
		long	len1,
		KdtHeap *	h2
	)

Definition at line 186 of file kdt.c.

References assert, buffer_ref(), h, i, kdt_heap_create(), kdt_heap_flush(), kdt_heap_free(), kdt_heap_get(), kdt_heap_put(), kdt_heap_resize(), kdt_heap_rewind(), kdt_tmpfile(), p, and x.

Referenced by kdt_heap_sort(), and split().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_includes()

int kdt_includes	(	const KdtRect	rect,
		const KdtRect	query
	)

Definition at line 776 of file kdt.c.

References h, l, query(), and x.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_init()

static int kdt_init	(	Kdt *	kdt,
		const char *	name,
		int	npmax,
		long	len
	)

static

Definition at line 660 of file kdt.c.

References check_32_bits(), open_ext(), VERSION, and x.

Referenced by kdt_create().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_intersects()

int kdt_intersects	(	const KdtRect	rect,
		const KdtRect	query
	)

Definition at line 770 of file kdt.c.

References h, l, query(), and x.

Referenced by kdt_query(), main(), and query().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_new()

Kdt * kdt_new ( void )

Definition at line 632 of file kdt.c.

References calloc(), and x.

Referenced by main(), and terrain().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_open()

int kdt_open	(	Kdt *	kdt,
		const char *	name
	)

Definition at line 723 of file kdt.c.

References check_32_bits(), open_ext(), sizeof(), VERSION, and x.

Referenced by main(), and terrain().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_query()

long kdt_query	(	const Kdt *	kdt,
		const KdtRect	rect
	)

Definition at line 834 of file kdt.c.

References h, kdt_intersects(), query(), and x.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_query_sum()

long kdt_query_sum	(	const Kdt *	kdt,
		KdtCheck	includes,
		KdtCheck	intersects,
		void *	data,
		const KdtRect	query,
		KdtSum *	sum
	)

Definition at line 1025 of file kdt.c.

References data, f, h, includes(), intersects(), query(), query_sum(), sum, and x.

Referenced by main(), and terrain().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_rect_write()

void kdt_rect_write	(	const KdtRect	rect,
		FILE *	fp
	)

Definition at line 450 of file kdt.c.

References fp, h, l, and x.

Referenced by query(), query_sum(), and split().

Here is the caller graph for this function:

◆ kdt_sum_core_init()

static void kdt_sum_core_init ( KdtSumCore * s )

static

Definition at line 468 of file kdt.c.

References s, and x.

Referenced by kdt_sum_init(), and update_sum().

Here is the caller graph for this function:

◆ kdt_sum_init()

void kdt_sum_init ( KdtSum * s )

Definition at line 1043 of file kdt.c.

References kdt_sum_core_init(), and s.

Referenced by main(), and terrain().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ kdt_tmpfile()

FILE * kdt_tmpfile ( void )

Definition at line 42 of file kdt.c.

References assert, fp, and x.

Referenced by kdt_heap_split(), and main().

Here is the caller graph for this function:

◆ kdt_write()

void kdt_write	(	KdtHeap *	h,
		FILE *	fp
	)

Definition at line 254 of file kdt.c.

References fp, h, i, kdt_heap_get(), kdt_heap_rewind(), p, and x.

Here is the call graph for this function:

◆ length()

static float length ( const KdtRect rect )

static

Definition at line 444 of file kdt.c.

References h, w, and x.

Referenced by fault(), find_coreGL(), okada(), query_sum(), and split().

Here is the caller graph for this function:

◆ merge()

static void merge	(	KdtHeap *	h1,
		KdtHeap *	h2,
		int()(const void , const void *)	compar,
		long	buflen
	)

static

Definition at line 265 of file kdt.c.

References assert, kdt_heap_create(), kdt_heap_flush(), kdt_heap_free(), kdt_heap_get(), kdt_heap_rewind(), put(), and x.

Referenced by kdt_heap_sort().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ open_ext()

static FILE * open_ext	(	const char *	name,
		const char *	ext,
		const char *	mode
	)

static

Definition at line 638 of file kdt.c.

References buf, fname, fp, free(), and x.

Referenced by kdt_init(), and kdt_open().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ progress()

static void progress ( void * data )

static

Definition at line 519 of file kdt.c.

References data, and x.

◆ put()

static int put	(	KdtHeap *	h,
		KdtPoint *	p,
		KdtHeap *	merged
	)

static

Definition at line 248 of file kdt.c.

References h, kdt_heap_get(), kdt_heap_put(), p, and x.

Referenced by merge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ query()

static long query	(	const Kdt *	kdt,
		const KdtRect	rect,
		long	len
	)

static

Definition at line 782 of file kdt.c.

References i, kdt_intersects(), kdt_rect_write(), n, pos, query(), sizeof(), sizes(), and x.

Referenced by kdt_includes(), kdt_intersects(), kdt_query(), kdt_query_sum(), main(), query(), and query_sum().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ query_sum()

static long query_sum	(	const Kdt *	kdt,
		KdtCheck	includes,
		KdtCheck	intersects,
		void *	data,
		KdtRect	bound,
		long	len,
		FilePointers *	f,
		const KdtRect	query,
		KdtSum *	sum
	)

static

Definition at line 932 of file kdt.c.

References a, area(), data, f, h, i, includes(), intersection_area(), intersects(), kdt_rect_write(), KdtInterval::l, length(), n, pos, query(), query_sum(), s, sizeof(), sizes(), sum, sum_add_point(), sum_add_sum(), w, vector::x, x, and vector::y.

Referenced by kdt_query_sum(), and query_sum().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ relative()

static void relative	(	const KdtRect	rect,
		double *	o,
		double *	h
	)

static

Definition at line 389 of file kdt.c.

References h, l, o, and x.

Referenced by if(), sum_add_point(), and sum_add_sum().

Here is the caller graph for this function:

◆ sizes()

static void sizes	(	const Node *	n,
		long *	nodes,
		long *	sums,
		long *	leaves
	)

static

Definition at line 382 of file kdt.c.

References leaves, and n.

Referenced by query(), and query_sum().

Here is the caller graph for this function:

◆ sort_x()

static int sort_x	(	const void *	p1,
		const void *	p2
	)

static

Definition at line 458 of file kdt.c.

References x.

Referenced by split().

Here is the caller graph for this function:

◆ sort_y()

static int sort_y	(	const void *	p1,
		const void *	p2
	)

static

Definition at line 463 of file kdt.c.

References x.

Referenced by split().

Here is the caller graph for this function:

◆ split()

static int split	(	KdtHeap *	h1,
		KdtRect	bound,
		int	index,
		Kdt *	kdt,
		float *	coverage
	)

static

Definition at line 543 of file kdt.c.

References a, area(), assert, fwrite_check(), index, kdt_heap_free(), kdt_heap_sort(), kdt_heap_sort_cost(), kdt_heap_split(), kdt_rect_write(), Node::len1, length(), n, pos, progress, s, sizeof(), sort_x(), sort_y(), split(), union_bound(), update_bounds(), update_sum(), and x.

Referenced by kdt_create(), and split().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sum_add_point()

static void sum_add_point	(	const KdtRect	parent,
		KdtSumCore *	sum,
		const KdtPoint *	a,
		double	w
	)

static

Definition at line 398 of file kdt.c.

References a, h, o, p, relative(), sum, w, vector::x, and vector::y.

Referenced by query_sum(), and update_sum().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sum_add_sum()

static void sum_add_sum	(	const KdtRect	parent,
		KdtSum *	sum,
		const KdtRect	rect,
		const KdtSumCore *	a
	)

static

Definition at line 863 of file kdt.c.

References a, area(), ha, intersection_area(), op, relative(), sum, w, and x.

Referenced by query_sum().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ union_bound()

static void union_bound	(	KdtRect	b,
		const KdtRect	b1,
		const KdtRect	b2
	)

static

Definition at line 535 of file kdt.c.

References b, b1, b2, h, l, MAX, and MIN.

Referenced by split().

Here is the caller graph for this function:

◆ update_bounds()

static long update_bounds	(	KdtRect	rect,
		KdtHeap *	h
	)

static

Definition at line 502 of file kdt.c.

References h, kdt_heap_get(), kdt_heap_rewind(), p, x, and KdtPoint::x.

Referenced by kdt_create(), and split().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ update_sum()

static int update_sum	(	const KdtRect	rect,
		KdtSumCore *	n,
		KdtHeap *	h,
		int	index
	)

static

Definition at line 478 of file kdt.c.

References assert, GAP, h, i, index, kdt_heap_get(), kdt_heap_rewind(), kdt_sum_core_init(), min, MINLEN, n, p, s, sum_add_point(), and x.

Referenced by split().

Here is the call graph for this function:

Here is the caller graph for this function:

Data Structures

Macros

Functions

Macro Definition Documentation

◆ GAP

◆ MAX

◆ MIN

◆ MINLEN

◆ VERSION

Function Documentation

◆ area()

◆ buffer_new()

◆ buffer_ref()

◆ buffer_unref()

◆ check_32_bits()

◆ fwrite_check()

◆ heap_read()

◆ heap_write()

◆ intersection()

◆ intersection_area()

◆ kdt_create()

◆ kdt_destroy()

◆ kdt_heap_create()

◆ kdt_heap_flush()

◆ kdt_heap_free()

◆ kdt_heap_get()

◆ kdt_heap_put()

◆ kdt_heap_resize()

◆ kdt_heap_rewind()

◆ kdt_heap_sort()

◆ kdt_heap_sort_cost()

◆ kdt_heap_split()

◆ kdt_includes()

◆ kdt_init()

◆ kdt_intersects()

◆ kdt_new()

◆ kdt_open()

◆ kdt_query()

◆ kdt_query_sum()

◆ kdt_rect_write()

◆ kdt_sum_core_init()

◆ kdt_sum_init()

◆ kdt_tmpfile()

◆ kdt_write()

◆ length()

◆ merge()

◆ open_ext()

◆ progress()

◆ put()

◆ query()

◆ query_sum()

◆ relative()

◆ sizes()

◆ sort_x()

◆ sort_y()

◆ split()

◆ sum_add_point()

◆ sum_add_sum()

◆ union_bound()

◆ update_bounds()

◆ update_sum()