amdb_rtree.cpp

Libgist is an implementation of the Generalized Search Tree, a template index structure that makes i

# 1 "amdb_rtree.cc"
#pragma GCC set_debug_pwd "/Users/jmh/devel/libgist/src/librtree"
# 1 "<built-in>"
# 1 "<command line>"
# 1 "amdb_rtree.cc"




# 1 "/Users/jmh/devel/libgist/include/amdb_ext.h" 1







# 1 "/Users/jmh/devel/libgist/include/gist_defs.h" 1
# 9 "/Users/jmh/devel/libgist/include/gist_defs.h"
# 1 "/usr/include/sys/types.h" 1 3 4
# 66 "/usr/include/sys/types.h" 3 4
# 1 "/usr/include/sys/appleapiopts.h" 1 3 4
# 67 "/usr/include/sys/types.h" 2 3 4


# 1 "/usr/include/sys/cdefs.h" 1 3 4
# 70 "/usr/include/sys/types.h" 2 3 4


# 1 "/usr/include/machine/types.h" 1 3 4
# 30 "/usr/include/machine/types.h" 3 4
# 1 "/usr/include/ppc/types.h" 1 3 4
# 69 "/usr/include/ppc/types.h" 3 4
typedef signed char int8_t;
typedef unsigned char u_int8_t;
typedef short int16_t;
typedef unsigned short u_int16_t;
typedef int int32_t;
typedef unsigned int u_int32_t;
typedef long long int64_t;
typedef unsigned long long u_int64_t;

typedef int32_t register_t;

typedef long int intptr_t;
typedef unsigned long int uintptr_t;
# 31 "/usr/include/machine/types.h" 2 3 4
# 73 "/usr/include/sys/types.h" 2 3 4

# 1 "/usr/include/machine/ansi.h" 1 3 4
# 33 "/usr/include/machine/ansi.h" 3 4
# 1 "/usr/include/ppc/ansi.h" 1 3 4
# 92 "/usr/include/ppc/ansi.h" 3 4
typedef union {
        char __mbstate8[128];
        long long _mbstateL;
} __mbstate_t;
# 34 "/usr/include/machine/ansi.h" 2 3 4
# 75 "/usr/include/sys/types.h" 2 3 4
# 1 "/usr/include/machine/endian.h" 1 3 4
# 30 "/usr/include/machine/endian.h" 3 4
# 1 "/usr/include/ppc/endian.h" 1 3 4
# 81 "/usr/include/ppc/endian.h" 3 4
extern "C" {
unsigned long htonl (unsigned long);
unsigned short htons (unsigned short);
unsigned long ntohl (unsigned long);
unsigned short ntohs (unsigned short);
}
# 31 "/usr/include/machine/endian.h" 2 3 4
# 76 "/usr/include/sys/types.h" 2 3 4


typedef unsigned char u_char;
typedef unsigned short u_short;
typedef unsigned int u_int;
typedef unsigned long u_long;
typedef unsigned short ushort;
typedef unsigned int uint;


typedef u_int64_t u_quad_t;
typedef int64_t quad_t;
typedef quad_t * qaddr_t;

typedef char * caddr_t;
typedef int32_t daddr_t;
typedef int32_t dev_t;
typedef u_int32_t fixpt_t;
typedef u_int32_t gid_t;
typedef u_int32_t in_addr_t;
typedef u_int16_t in_port_t;
typedef u_int32_t ino_t;
typedef long key_t;
typedef u_int16_t mode_t;
typedef u_int16_t nlink_t;
typedef quad_t off_t;
typedef int32_t pid_t;
typedef quad_t rlim_t;
typedef int32_t segsz_t;
typedef int32_t swblk_t;
typedef u_int32_t uid_t;
# 117 "/usr/include/sys/types.h" 3 4
typedef unsigned long clock_t;




typedef long unsigned int size_t;




typedef int ssize_t;




typedef long time_t;
# 146 "/usr/include/sys/types.h" 3 4
typedef int32_t fd_mask;






typedef struct fd_set {
        fd_mask fds_bits[(((1024) + (((sizeof(fd_mask) * 8)) - 1)) / ((sizeof(fd_mask) * 8)))];
} fd_set;
# 182 "/usr/include/sys/types.h" 3 4
struct _pthread_handler_rec
{
        void (*routine)(void *);
        void *arg;
        struct _pthread_handler_rec *next;
};
# 202 "/usr/include/sys/types.h" 3 4
typedef struct _opaque_pthread_t { long sig; struct _pthread_handler_rec *cleanup_stack; char opaque[596];} *pthread_t;

typedef struct _opaque_pthread_attr_t { long sig; char opaque[36]; } pthread_attr_t;

typedef struct _opaque_pthread_mutexattr_t { long sig; char opaque[8]; } pthread_mutexattr_t;

typedef struct _opaque_pthread_mutex_t { long sig; char opaque[40]; } pthread_mutex_t;

typedef struct _opaque_pthread_condattr_t { long sig; char opaque[4]; } pthread_condattr_t;

typedef struct _opaque_pthread_cond_t { long sig; char opaque[24]; } pthread_cond_t;

typedef struct _opaque_pthread_rwlockattr_t { long sig; char opaque[12]; } pthread_rwlockattr_t;

typedef struct _opaque_pthread_rwlock_t { long sig; char opaque[124]; } pthread_rwlock_t;

typedef struct { long sig; char opaque[4]; } pthread_once_t;



typedef unsigned long pthread_key_t;
# 10 "/Users/jmh/devel/libgist/include/gist_defs.h" 2
# 1 "/usr/include/gcc/darwin/3.3/assert.h" 1 3 4
# 14 "/usr/include/gcc/darwin/3.3/assert.h" 3 4
# 1 "/usr/include/stdlib.h" 1 3 4
# 71 "/usr/include/stdlib.h" 3 4
typedef int rune_t;





typedef int wchar_t;


typedef struct {
        int quot;
        int rem;
} div_t;

typedef struct {
        long quot;
        long rem;
} ldiv_t;
# 99 "/usr/include/stdlib.h" 3 4
extern int __mb_cur_max;




extern "C" {
 void
         abort (void);
 int
         abs (int);
int atexit (void (*)(void));
double atof (const char *);
int atoi (const char *);
long atol (const char *);
void *bsearch (const void *, const void *, size_t, size_t, int (*)(const void *, const void *));

void *calloc (size_t, size_t);
 div_t
         div (int, int);
 void
         exit (int);
void free (void *);
char *getenv (const char *);
 long
         labs (long);
 ldiv_t
         ldiv (long, long);
void *malloc (size_t);
void qsort (void *, size_t, size_t, int (*)(const void *, const void *));

int rand (void);
void *realloc (void *, size_t);
void srand (unsigned);
double strtod (const char *, char **);
long strtol (const char *, char **, int);
unsigned long
         strtoul (const char *, char **, int);
int system (const char *);


int mblen (const char *, size_t);
size_t mbstowcs (wchar_t *, const char *, size_t);
int wctomb (char *, wchar_t);
int mbtowc (wchar_t *, const char *, size_t);
size_t wcstombs (char *, const wchar_t *, size_t);


int putenv (const char *);
int setenv (const char *, const char *, int);



double drand48 (void);
double erand48 (unsigned short[3]);
long jrand48 (unsigned short[3]);
void lcong48 (unsigned short[7]);
long lrand48 (void);
long mrand48 (void);
long nrand48 (unsigned short[3]);
unsigned short
        *seed48 (unsigned short[3]);
void srand48 (long);

void *alloca (size_t);

u_int32_t
         arc4random (void);
void arc4random_addrandom (unsigned char *dat, int datlen);
void arc4random_stir (void);
char *getbsize (int *, long *);
char *cgetcap (char *, char *, int);
int cgetclose (void);
int cgetent (char **, char **, char *);
int cgetfirst (char **, char **);
int cgetmatch (char *, char *);
int cgetnext (char **, char **);
int cgetnum (char *, char *, long *);
int cgetset (char *);
int cgetstr (char *, char *, char **);
int cgetustr (char *, char *, char **);

int daemon (int, int);
char *devname (int, int);
int getloadavg (double [], int);

long a64l (const char *);
char *l64a (long);

char *group_from_gid (unsigned long, int);
int heapsort (void *, size_t, size_t, int (*)(const void *, const void *));

char *initstate (unsigned long, char *, long);
int mergesort (void *, size_t, size_t, int (*)(const void *, const void *));

int radixsort (const unsigned char **, int, const unsigned char *, unsigned);

int sradixsort (const unsigned char **, int, const unsigned char *, unsigned);

int rand_r (unsigned *);
long random (void);
void *reallocf (void *, size_t);
char *realpath (const char *, char resolved_path[]);
char *setstate (char *);
void srandom (unsigned long);
char *user_from_uid (unsigned long, int);

long long
         strtoll(const char *, char **, int);
unsigned long long
         strtoull(const char *, char **, int);
long long
         strtoq (const char *, char **, int);
unsigned long long
         strtouq (const char *, char **, int);

void unsetenv (const char *);

}
# 15 "/usr/include/gcc/darwin/3.3/assert.h" 2 3 4
# 40 "/usr/include/gcc/darwin/3.3/assert.h" 3 4
extern "C" {
extern void __eprintf (const char *, const char *, unsigned, const char *)
    __attribute__ ((noreturn));
}
# 11 "/Users/jmh/devel/libgist/include/gist_defs.h" 2
# 1 "/usr/include/gcc/darwin/3.3/c++/vector" 1 3
# 65 "/usr/include/gcc/darwin/3.3/c++/vector" 3

# 1 "/usr/include/gcc/darwin/3.3/c++/bits/functexcept.h" 1 3
# 34 "/usr/include/gcc/darwin/3.3/c++/bits/functexcept.h" 3
# 1 "/usr/include/gcc/darwin/3.3/c++/exception_defines.h" 1 3
# 35 "/usr/include/gcc/darwin/3.3/c++/bits/functexcept.h" 2 3

namespace std
{

  void
  __throw_bad_exception(void);


  void
  __throw_bad_alloc(void);


  void
  __throw_bad_cast(void);

  void
  __throw_bad_typeid(void);


  void
  __throw_logic_error(const char* __s);

  void
  __throw_domain_error(const char* __s);

  void
  __throw_invalid_argument(const char* __s);

  void
  __throw_length_error(const char* __s);

  void
  __throw_out_of_range(const char* __s);

  void
  __throw_runtime_error(const char* __s);

  void
  __throw_range_error(const char* __s);

  void
  __throw_overflow_error(const char* __s);

  void
  __throw_underflow_error(const char* __s);


  void
  __throw_ios_failure(const char* __s);
}
# 67 "/usr/include/gcc/darwin/3.3/c++/vector" 2 3
# 1 "/usr/include/gcc/darwin/3.3/c++/bits/stl_algobase.h" 1 3
# 64 "/usr/include/gcc/darwin/3.3/c++/bits/stl_algobase.h" 3
# 1 "/usr/include/gcc/darwin/3.3/c++/ppc-darwin/bits/c++config.h" 1 3
# 35 "/usr/include/gcc/darwin/3.3/c++/ppc-darwin/bits/c++config.h" 3
# 1 "/usr/include/gcc/darwin/3.3/c++/ppc-darwin/bits/os_defines.h" 1 3
# 72 "/usr/include/gcc/darwin/3.3/c++/ppc-darwin/bits/os_defines.h" 3
extern "C" {
# 83 "/usr/include/gcc/darwin/3.3/c++/ppc-darwin/bits/os_defines.h" 3
typedef enum node_kinds {
        NODE_THREAD_SPECIFIC_DATA=1,
        NODE_PROCESSWIDE_PTR=2,
        NODE_LAST_KIND
        } TnodeKind ;





typedef enum node_mode {
        NM_ALLOW_RECURSION=1,
        NM_RECURSION_ILLEGAL=2,
        NM_ENHANCED_LOCKING=3,
        NM_LOCKED=4
        } TnodeMode ;



extern void * _keymgr_get_per_thread_data(unsigned int key) ;
extern void _keymgr_set_per_thread_data(unsigned int key, void *keydata) ;
extern void *_keymgr_get_and_lock_processwide_ptr(unsigned int key) ;
extern void _keymgr_set_and_unlock_processwide_ptr(unsigned int key, void *ptr) ;
extern void _keymgr_unlock_processwide_ptr(unsigned int key) ;
extern void _keymgr_set_lockmode_processwide_ptr(unsigned int key, unsigned int mode) ;
extern unsigned int _keymgr_get_lockmode_processwide_ptr(unsigned int key) ;
extern int _keymgr_get_lock_count_processwide_ptr(unsigned int key) ;
# 155 "/usr/include/gcc/darwin/3.3/c++/ppc-darwin/bits/os_defines.h" 3
}
# 36 "/usr/include/gcc/darwin/3.3/c++/ppc-darwin/bits/c++config.h" 2 3
# 65 "/usr/include/gcc/darwin/3.3/c++/bits/stl_algobase.h" 2 3
# 1 "/usr/include/gcc/darwin/3.3/c++/cstring" 1 3
# 48 "/usr/include/gcc/darwin/3.3/c++/cstring" 3

# 1 "/usr/include/gcc/darwin/3.3/c++/cstddef" 1 3
# 47 "/usr/include/gcc/darwin/3.3/c++/cstddef" 3

# 1 "/usr/include/stddef.h" 1 3 4
# 66 "/usr/include/stddef.h" 3 4
typedef int ptrdiff_t;
# 49 "/usr/include/gcc/darwin/3.3/c++/cstddef" 2 3

namespace std
{
  using ::ptrdiff_t;
  using ::size_t;
}
# 50 "/usr/include/gcc/darwin/3.3/c++/cstring" 2 3

# 1 "/usr/include/string.h" 1 3 4
# 72 "/usr/include/string.h" 3 4
extern "C" {
void *memchr (const void *, int, size_t);
int memcmp (const void *, const void *, size_t);
void *memcpy (void *, const void *, size_t);
void *memmove (void *, const void *, size_t);
void *memset (void *, int, size_t);
char *strcat (char *, const char *);
char *strchr (const char *, int);
int strcmp (const char *, const char *);
int strcoll (const char *, const char *);
char *strcpy (char *, const char *);
size_t strcspn (const char *, const char *);
char *strerror (int);
size_t strlen (const char *);
char *strncat (char *, const char *, size_t);
int strncmp (const char *, const char *, size_t);
char *strncpy (char *, const char *, size_t);
char *strpbrk (const char *, const char *);
char *strrchr (const char *, int);
size_t strspn (const char *, const char *);
char *strstr (const char *, const char *);
char *strtok (char *, const char *);
size_t strxfrm (char *, const char *, size_t);



int bcmp (const void *, const void *, size_t);
void bcopy (const void *, void *, size_t);
void bzero (void *, size_t);
int ffs (int);
char *index (const char *, int);
void *memccpy (void *, const void *, int, size_t);
char *rindex (const char *, int);
int strcasecmp (const char *, const char *);
char *strdup (const char *);
size_t strlcat (char *, const char *, size_t);
size_t strlcpy (char *, const char *, size_t);
void strmode (int, char *);
int strncasecmp (const char *, const char *, size_t);
char *strsep (char **, const char *);
char *strtok_r (char *, const char *, char **);
void swab (const void *, void *, size_t);

}
# 52 "/usr/include/gcc/darwin/3.3/c++/cstring" 2 3
# 77 "/usr/include/gcc/darwin/3.3/c++/cstring" 3
namespace std
{
  using ::memcpy;
  using ::memmove;
  using ::strcpy;
  using ::strncpy;
  using ::strcat;
  using ::strncat;
  using ::memcmp;
  using ::strcmp;
  using ::strcoll;
  using ::strncmp;
  using ::strxfrm;
  using ::strcspn;
  using ::strspn;
  using ::strtok;
  using ::memset;
  using ::strerror;
  using ::strlen;

  using ::memchr;

  inline void*
  memchr(void* __p, int __c, size_t __n)
  { return memchr(const_cast<const void*>(__p), __c, __n); }

  using ::strchr;

  inline char*
  strchr(char* __s1, int __n)
  { return __builtin_strchr(const_cast<const char*>(__s1), __n); }

  using ::strpbrk;

  inline char*
  strpbrk(char* __s1, const char* __s2)
  { return __builtin_strpbrk(const_cast<const char*>(__s1), __s2); }

  using ::strrchr;

  inline char*
  strrchr(char* __s1, int __n)
  { return __builtin_strrchr(const_cast<const char*>(__s1), __n); }

  using ::strstr;

  inline char*
  strstr(char* __s1, const char* __s2)
  { return __builtin_strstr(const_cast<const char*>(__s1), __s2); }
}
# 66 "/usr/include/gcc/darwin/3.3/c++/bits/stl_algobase.h" 2 3
# 1 "/usr/include/gcc/darwin/3.3/c++/climits" 1 3
# 48 "/usr/include/gcc/darwin/3.3/c++/climits" 3