amdb_btree.cpp

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

typedef int exception_behavior_t;
typedef integer_t *exception_data_t;
typedef unsigned int exception_mask_t;
typedef exception_mask_t *exception_mask_array_t;
typedef exception_behavior_t *exception_behavior_array_t;
typedef thread_state_flavor_t *exception_flavor_array_t;
typedef mach_port_t *exception_port_array_t;
# 71 "/usr/include/mach/mach_types.h" 2 3 4

# 1 "/usr/include/mach/processor_info.h" 1 3 4
# 65 "/usr/include/mach/processor_info.h" 3 4
# 1 "/usr/include/mach/machine/processor_info.h" 1 3 4
# 27 "/usr/include/mach/machine/processor_info.h" 3 4
# 1 "/usr/include/mach/ppc/processor_info.h" 1 3 4
# 43 "/usr/include/mach/ppc/processor_info.h" 3 4
typedef union {
        unsigned int word;
        struct {
                unsigned int dis : 1;
                unsigned int dp : 1;
                unsigned int du : 1;
                unsigned int dms : 1;
                unsigned int dmr : 1;
                unsigned int reserved3 : 1;
                unsigned int reserved4 : 1;
                unsigned int reserved5 : 2;
                unsigned int reserved6 : 1;
                unsigned int threshold : 6;
                unsigned int reserved7 : 1;
                unsigned int reserved8 : 1;
                unsigned int reserved9 : 1;
                unsigned int pmc1select : 7;
                unsigned int pmc2select : 6;
        }bits;
}mmcr0_t;

typedef union {
        unsigned int word;
        struct {
                unsigned int pmc3select : 5;
                unsigned int pmc4select : 5;
                unsigned int reserved : 22;
        }bits;
}mmcr1_t;

typedef union {
        unsigned int word;
        struct {
                unsigned int threshmult : 1;
                unsigned int reserved : 31;
        }bits;
}mmcr2_t;

typedef union {
        unsigned int word;
        struct {
                unsigned int ov : 1;
                unsigned int cv : 31;
        }bits;
}pmcn_t;





struct processor_pm_regs {
      union {
        mmcr0_t mmcr0;
        mmcr1_t mmcr1;
        mmcr2_t mmcr2;
      }u;
      pmcn_t pmc[2];
};

typedef struct processor_pm_regs processor_pm_regs_data_t;
typedef struct processor_pm_regs *processor_pm_regs_t;
# 119 "/usr/include/mach/ppc/processor_info.h" 3 4
typedef unsigned int processor_temperature_data_t;
typedef unsigned int *processor_temperature_t;



union processor_control_data {
        processor_pm_regs_data_t cmd_pm_regs[3];
};

struct processor_control_cmd {
    integer_t cmd_op;
    cpu_type_t cmd_cpu_type;
    cpu_subtype_t cmd_cpu_subtype;
    union processor_control_data u;
};

typedef struct processor_control_cmd processor_control_cmd_data_t;
typedef struct processor_control_cmd *processor_control_cmd_t;
# 28 "/usr/include/mach/machine/processor_info.h" 2 3 4
# 66 "/usr/include/mach/processor_info.h" 2 3 4




typedef integer_t *processor_info_t;
typedef integer_t *processor_info_array_t;


typedef integer_t processor_info_data_t[(1024)];


typedef integer_t *processor_set_info_t;


typedef integer_t processor_set_info_data_t[(1024)];




typedef int processor_flavor_t;





struct processor_basic_info {
        cpu_type_t cpu_type;
        cpu_subtype_t cpu_subtype;
        boolean_t running;
        int slot_num;
        boolean_t is_master;
};

typedef struct processor_basic_info processor_basic_info_data_t;
typedef struct processor_basic_info *processor_basic_info_t;



struct processor_cpu_load_info {
        unsigned long cpu_ticks[4];
};

typedef struct processor_cpu_load_info processor_cpu_load_info_data_t;
typedef struct processor_cpu_load_info *processor_cpu_load_info_t;
# 118 "/usr/include/mach/processor_info.h" 3 4
typedef int processor_set_flavor_t;


struct processor_set_basic_info {
        int processor_count;
        int default_policy;
};

typedef struct processor_set_basic_info processor_set_basic_info_data_t;
typedef struct processor_set_basic_info *processor_set_basic_info_t;





struct processor_set_load_info {
        int task_count;
        int thread_count;
        integer_t load_average;
        integer_t mach_factor;
};

typedef struct processor_set_load_info processor_set_load_info_data_t;
typedef struct processor_set_load_info *processor_set_load_info_t;
# 73 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/task_info.h" 1 3 4
# 66 "/usr/include/mach/task_info.h" 3 4
# 1 "/usr/include/mach/policy.h" 1 3 4
# 72 "/usr/include/mach/policy.h" 3 4
typedef int policy_t;
typedef integer_t *policy_info_t;
typedef integer_t *policy_base_t;
typedef integer_t *policy_limit_t;
# 108 "/usr/include/mach/policy.h" 3 4
struct policy_timeshare_base {
        integer_t base_priority;
};
struct policy_timeshare_limit {
        integer_t max_priority;
};
struct policy_timeshare_info {
        integer_t max_priority;
        integer_t base_priority;
        integer_t cur_priority;
        boolean_t depressed;
        integer_t depress_priority;
};

typedef struct policy_timeshare_base *policy_timeshare_base_t;
typedef struct policy_timeshare_limit *policy_timeshare_limit_t;
typedef struct policy_timeshare_info *policy_timeshare_info_t;

typedef struct policy_timeshare_base policy_timeshare_base_data_t;
typedef struct policy_timeshare_limit policy_timeshare_limit_data_t;
typedef struct policy_timeshare_info policy_timeshare_info_data_t;
# 142 "/usr/include/mach/policy.h" 3 4
struct policy_rr_base {
        integer_t base_priority;
        integer_t quantum;
};
struct policy_rr_limit {
        integer_t max_priority;
};
struct policy_rr_info {
        integer_t max_priority;
        integer_t base_priority;
        integer_t quantum;
        boolean_t depressed;
        integer_t depress_priority;
};

typedef struct policy_rr_base *policy_rr_base_t;
typedef struct policy_rr_limit *policy_rr_limit_t;
typedef struct policy_rr_info *policy_rr_info_t;

typedef struct policy_rr_base policy_rr_base_data_t;
typedef struct policy_rr_limit policy_rr_limit_data_t;
typedef struct policy_rr_info policy_rr_info_data_t;
# 176 "/usr/include/mach/policy.h" 3 4
struct policy_fifo_base {
        integer_t base_priority;
};
struct policy_fifo_limit {
        integer_t max_priority;
};
struct policy_fifo_info {
        integer_t max_priority;
        integer_t base_priority;
        boolean_t depressed;
        integer_t depress_priority;
};

typedef struct policy_fifo_base *policy_fifo_base_t;
typedef struct policy_fifo_limit *policy_fifo_limit_t;
typedef struct policy_fifo_info *policy_fifo_info_t;

typedef struct policy_fifo_base policy_fifo_base_data_t;
typedef struct policy_fifo_limit policy_fifo_limit_data_t;
typedef struct policy_fifo_info policy_fifo_info_data_t;
# 208 "/usr/include/mach/policy.h" 3 4
struct policy_bases {
        policy_timeshare_base_data_t ts;
        policy_rr_base_data_t rr;
        policy_fifo_base_data_t fifo;
};

struct policy_limits {
        policy_timeshare_limit_data_t ts;
        policy_rr_limit_data_t rr;
        policy_fifo_limit_data_t fifo;
};

struct policy_infos {
        policy_timeshare_info_data_t ts;
        policy_rr_info_data_t rr;
        policy_fifo_info_data_t fifo;
};

typedef struct policy_bases policy_base_data_t;
typedef struct policy_limits policy_limit_data_t;
typedef struct policy_infos policy_info_data_t;
# 67 "/usr/include/mach/task_info.h" 2 3 4






typedef natural_t task_flavor_t;
typedef integer_t *task_info_t;


typedef integer_t task_info_data_t[(1024)];







struct task_basic_info {
        integer_t suspend_count;
        vm_size_t virtual_size;
        vm_size_t resident_size;
        time_value_t user_time;

        time_value_t system_time;

        policy_t policy;
};

typedef struct task_basic_info task_basic_info_data_t;
typedef struct task_basic_info *task_basic_info_t;






struct task_events_info {
        integer_t faults;
        integer_t pageins;
        integer_t cow_faults;
        integer_t messages_sent;
        integer_t messages_received;
        integer_t syscalls_mach;
        integer_t syscalls_unix;
        integer_t csw;
};
typedef struct task_events_info task_events_info_data_t;
typedef struct task_events_info *task_events_info_t;






struct task_thread_times_info {
        time_value_t user_time;

        time_value_t system_time;

};

typedef struct task_thread_times_info task_thread_times_info_data_t;
typedef struct task_thread_times_info *task_thread_times_info_t;
# 74 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/task_policy.h" 1 3 4
# 37 "/usr/include/mach/task_policy.h" 3 4
# 1 "/usr/include/mach/mach_types.h" 1 3 4
# 38 "/usr/include/mach/task_policy.h" 2 3 4
# 56 "/usr/include/mach/task_policy.h" 3 4
typedef natural_t task_policy_flavor_t;
typedef integer_t *task_policy_t;
# 111 "/usr/include/mach/task_policy.h" 3 4
enum task_role {
        TASK_RENICED = -1,
        TASK_UNSPECIFIED = 0,
        TASK_FOREGROUND_APPLICATION,
        TASK_BACKGROUND_APPLICATION,
        TASK_CONTROL_APPLICATION,
        TASK_GRAPHICS_SERVER
};

typedef enum task_role task_role_t;

struct task_category_policy {
        task_role_t role;
};

typedef struct task_category_policy task_category_policy_data_t;
typedef struct task_category_policy *task_category_policy_t;
# 75 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/task_special_ports.h" 1 3 4
# 66 "/usr/include/mach/task_special_ports.h" 3 4
typedef int task_special_port_t;
# 76 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/thread_info.h" 1 3 4
# 76 "/usr/include/mach/thread_info.h" 3 4
typedef natural_t thread_flavor_t;
typedef integer_t *thread_info_t;


typedef integer_t thread_info_data_t[(1024)];






struct thread_basic_info {
        time_value_t user_time;
        time_value_t system_time;
        integer_t cpu_usage;
        policy_t policy;
        integer_t run_state;
        integer_t flags;
        integer_t suspend_count;
        integer_t sleep_time;

};

typedef struct thread_basic_info thread_basic_info_data_t;
typedef struct thread_basic_info *thread_basic_info_t;
# 77 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/thread_policy.h" 1 3 4
# 56 "/usr/include/mach/thread_policy.h" 3 4
typedef natural_t thread_policy_flavor_t;
typedef integer_t *thread_policy_t;
# 91 "/usr/include/mach/thread_policy.h" 3 4
struct thread_standard_policy {
        natural_t no_data;
};

typedef struct thread_standard_policy thread_standard_policy_data_t;
typedef struct thread_standard_policy *thread_standard_policy_t;
# 114 "/usr/include/mach/thread_policy.h" 3 4
struct thread_extended_policy {
        boolean_t timeshare;
};

typedef struct thread_extended_policy thread_extended_policy_data_t;
typedef struct thread_extended_policy *thread_extended_policy_t;
# 153 "/usr/include/mach/thread_policy.h" 3 4
struct thread_time_constraint_policy {
        uint32_t period;
        uint32_t computation;
        uint32_t constraint;
        boolean_t preemptible;
};

typedef struct thread_time_constraint_policy thread_time_constraint_policy_data_t;

typedef struct thread_time_constraint_policy *thread_time_constraint_policy_t;
# 181 "/usr/include/mach/thread_policy.h" 3 4
struct thread_precedence_policy {
        integer_t importance;
};

typedef struct thread_precedence_policy thread_precedence_policy_data_t;
typedef struct thread_precedence_policy *thread_precedence_policy_t;
# 78 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/thread_special_ports.h" 1 3 4
# 79 "/usr/include/mach/mach_types.h" 2 3 4


# 1 "/usr/include/mach/clock_types.h" 1 3 4
# 46 "/usr/include/mach/clock_types.h" 3 4
typedef int alarm_type_t;
typedef int sleep_type_t;
typedef int clock_id_t;
typedef int clock_flavor_t;
typedef int *clock_attr_t;
typedef int clock_res_t;




struct mach_timespec {
        unsigned int tv_sec;
        clock_res_t tv_nsec;
};
typedef struct mach_timespec mach_timespec_t;
# 82 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/vm_attributes.h" 1 3 4
# 70 "/usr/include/mach/vm_attributes.h" 3 4
typedef unsigned int vm_machine_attribute_t;
# 79 "/usr/include/mach/vm_attributes.h" 3 4
typedef int vm_machine_attribute_val_t;
# 83 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/vm_inherit.h" 1 3 4
# 69 "/usr/include/mach/vm_inherit.h" 3 4
typedef unsigned int vm_inherit_t;
# 84 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/vm_behavior.h" 1 3 4
# 41 "/usr/include/mach/vm_behavior.h" 3 4
typedef int vm_behavior_t;
# 85 "/usr/include/mach/mach_types.h" 2 3 4
# 1 "/usr/include/mach/vm_prot.h" 1 3 4
# 69 "/usr/include/mach/vm_prot.h" 3 4
typedef int vm_prot_t;
# 86 "/usr/include/mach/mach_types.h" 2 3 4

# 1 "/usr/include/mach/vm_sync.h" 1 3 4
# 60 "/usr/include/mach/vm_sync.h" 3 4
typedef unsigned vm_sync_t;
# 88 "/usr/include/mach/mach_types.h" 2 3 4

# 1 "/usr/include/mach/vm_region.h" 1 3 4
# 47 "/usr/include/mach/vm_region.h" 3 4
typedef int *vm_region_info_t;
typedef int *vm_region_info_64_t;
typedef int *vm_region_recurse_info_t;
typedef int *vm_region_recurse_info_64_t;
typedef int vm_region_flavor_t;
typedef int vm_region_info_data_t[(1024)];



struct vm_region_basic_info_64 {
        vm_prot_t protection;
        vm_prot_t max_protection;
        vm_inherit_t inheritance;
        boolean_t shared;
        boolean_t reserved;
        vm_object_offset_t offset;
        vm_behavior_t behavior;
        unsigned short user_wired_count;
};

typedef struct vm_region_basic_info_64 *vm_region_basic_info_64_t;
typedef struct vm_region_basic_info_64 vm_region_basic_info_data_64_t;





struct vm_region_basic_info {
        vm_prot_t protection;
        vm_prot_t max_protection;
        vm_inherit_t inheritance;
        boolean_t shared;
        boolean_t reserved;



        vm_offset_t offset;

        vm_behavior_t behavior;
        unsigned short user_wired_count;
};

typedef struct vm_region_basic_info *vm_region_basic_info_t;
typedef struct vm_region_basic_info vm_region_basic_info_data_t;
# 116 "/usr/include/mach/vm_region.h" 3 4
struct vm_region_extended_info {
        vm_prot_t protection;
        unsigned int user_tag;
        unsig