From 439f3a4381416112cab5332b2f4725260e4ef0bb Mon Sep 17 00:00:00 2001 From: Imran Navruzbekov Date: Tue, 4 Dec 2012 12:32:29 +0400 Subject: [PATCH] Deleted files with deprecated code --- dalvik_handlers/Kbuild | 4 - dalvik_handlers/Makefile | 18 --- dalvik_handlers/Makefile.am | 10 -- dalvik_handlers/dalvik_defs.h | 343 ----------------------------------------- dalvik_handlers/handlers.c | 219 -------------------------- dalvik_handlers/index_tree.c | 348 ------------------------------------------ dalvik_handlers/index_tree.h | 60 -------- 7 files changed, 1002 deletions(-) delete mode 100644 dalvik_handlers/Kbuild delete mode 100644 dalvik_handlers/Makefile delete mode 100644 dalvik_handlers/Makefile.am delete mode 100644 dalvik_handlers/dalvik_defs.h delete mode 100644 dalvik_handlers/handlers.c delete mode 100644 dalvik_handlers/index_tree.c delete mode 100644 dalvik_handlers/index_tree.h diff --git a/dalvik_handlers/Kbuild b/dalvik_handlers/Kbuild deleted file mode 100644 index 59ae279..0000000 --- a/dalvik_handlers/Kbuild +++ /dev/null @@ -1,4 +0,0 @@ -EXTRA_CFLAGS := -I$(src)/../../common -I$(src)/../driver -I$(src)/../../dalvik_probes -DEC_ARCH_$(ARCH) $(debug_opt) $(android_opt) - -obj-m := dalvik_handlers.o -dalvik_handlers-y := handlers.o index_tree.o ../../symbol/android/demangle.o diff --git a/dalvik_handlers/Makefile b/dalvik_handlers/Makefile deleted file mode 100644 index 26435e2..0000000 --- a/dalvik_handlers/Makefile +++ /dev/null @@ -1,18 +0,0 @@ -target_kernel_src=@KERNEL@ -target_arch = @ARCH@ -handlers_module_dir = $(realpath $(srcdir)) -module_name=dalvik_handlers -cross_compiler = $(subst gcc,,$(CC)) - -all-local: - cp $(top_srcdir)/src/modules/driver/Module.symvers $(handlers_module_dir) - $(MAKE) CROSS_COMPILE=$(cross_compiler) ARCH=$(target_arch) android_opt=$(android_opt) debug_opt=$(debug_opt) $(AM_MAKEFLAGS) -C $(target_kernel_src) M=$(handlers_module_dir) modules - - echo "generate data for version patching <$(OBJDUMP)><$(READELF)>" - $(top_srcdir)/src/modules/driver/patchko.sh -g $(handlers_module_dir)/$(module_name).ko $(OBJDUMP) $(READELF) - -clean-local: - $(MAKE) CROSS_COMPILE=$(cross_compiler) ARCH=$(target_arch) $(AM_MAKEFLAGS) -C $(target_kernel_src) M=$(handlers_module_dir) clean - -install-exec-local: - install -m 644 $(handlers_module_dir)/$(module_name).ko $(prefix) diff --git a/dalvik_handlers/Makefile.am b/dalvik_handlers/Makefile.am deleted file mode 100644 index 5e4b781..0000000 --- a/dalvik_handlers/Makefile.am +++ /dev/null @@ -1,10 +0,0 @@ -if DEBUG -debug_opt = -D__DEBUG -endif - -if ANDROID -android_opt = -D__ANDROID -android = yes -endif - -include Makefile diff --git a/dalvik_handlers/dalvik_defs.h b/dalvik_handlers/dalvik_defs.h deleted file mode 100644 index ec2f23a..0000000 --- a/dalvik_handlers/dalvik_defs.h +++ /dev/null @@ -1,343 +0,0 @@ -//////////////////////////////////////////////////////////////////////////////////// -// -// FILE: dalvik_defs.h -// -// DESCRIPTION: imported Dalvik VM definitions -// -// SEE ALSO: -// AUTHOR: L.Astakhov -// COMPANY NAME: Samsung Research Center in Moscow -// DEPT NAME: Advanced Software Group -// CREATED: 2011.07.08 -// VERSION: 1.0 -// REVISION DATE: 2011.07.08 -// -//////////////////////////////////////////////////////////////////////////////////// - -#ifndef __DALVIK_DEFS_H -#define __DALVIK_DEFS_H - -typedef unsigned short int __uint16_t; -typedef unsigned int __uint32_t; - -typedef union Lock { - __uint32_t thin; - void* mon; -} Lock; - -struct ClassObject; - -typedef struct Object { - struct ClassObject* clazz; - Lock lock; -} Object; - -typedef enum ClassStatus { - CLASS_ERROR = -1, - - CLASS_NOTREADY = 0, - CLASS_LOADED = 1, - CLASS_PREPARED = 2, /* part of linking */ - CLASS_RESOLVED = 3, /* part of linking */ - CLASS_VERIFYING = 4, /* in the process of being verified */ - CLASS_VERIFIED = 5, /* logically part of linking; done pre-init */ - CLASS_INITIALIZING = 6, /* class init in progress */ - CLASS_INITIALIZED = 7, /* ready to go */ -} ClassStatus; - -typedef enum PrimitiveType { - PRIM_NOT = -1, /* value is not a primitive type */ - PRIM_BOOLEAN = 0, - PRIM_CHAR = 1, - PRIM_FLOAT = 2, - PRIM_DOUBLE = 3, - PRIM_BYTE = 4, - PRIM_SHORT = 5, - PRIM_INT = 6, - PRIM_LONG = 7, - PRIM_VOID = 8, - - PRIM_MAX -} PrimitiveType; -#define PRIM_TYPE_TO_LETTER "ZCFDBSIJV" /* must match order in enum */ - -typedef struct InitiatingLoaderList { - /* a list of initiating loader Objects; grown and initialized on demand */ - Object** initiatingLoaders; - /* count of loaders in the above list */ - int initiatingLoaderCount; -}InitiatingLoaderList; - -typedef struct InterfaceEntry { - /* pointer to interface class */ - struct ClassObject* clazz; - /* - * Index into array of vtable offsets. This points into the ifviPool, - * which holds the vtables for all interfaces declared by this class. - */ - int* methodIndexArray; -} InterfaceEntry; - - -typedef union JValue { - unsigned char z; - signed char b; - unsigned short c; - signed short s; - signed int i; - signed long long j; - float f; - double d; - void* l; -} JValue; - -typedef struct DexProto { - const void* dexFile; /* file the idx refers to */ - __uint32_t protoIdx; /* index into proto_ids table of dexFile */ -} DexProto; - - -typedef struct Method { - /* the class we are a part of */ - struct ClassObject* clazz; - - /* access flags; low 16 bits are defined by spec (could be u2?) */ - __uint32_t accessFlags; - - /* - * For concrete virtual methods, this is the offset of the method - * in "vtable". - * - * For abstract methods in an interface class, this is the offset - * of the method in "iftable[n]->methodIndexArray". - */ - __uint16_t methodIndex; - - /* - * Method bounds; not needed for an abstract method. - * - * For a native method, we compute the size of the argument list, and - * set "insSize" and "registerSize" equal to it. - */ - __uint16_t registersSize; /* ins + locals */ - __uint16_t outsSize; - __uint16_t insSize; - - /* method name, e.g. "" or "eatLunch" */ - const char* name; - - /* - * Method prototype descriptor string (return and argument types). - * - * TODO: This currently must specify the DexFile as well as the proto_ids - * index, because generated Proxy classes don't have a DexFile. We can - * remove the DexFile* and reduce the size of this struct if we generate - * a DEX for proxies. - */ - DexProto prototype; - - /* short-form method descriptor string */ - const char* shorty; - - /* - * The remaining items are not used for abstract or native methods. - * (JNI is currently hijacking "insns" as a function pointer, set - * after the first call. For internal-native this stays null.) - */ - - /* the actual code */ - const __uint16_t* insns; /* instructions, in memory-mapped .dex */ - - /* cached JNI argument and return-type hints */ - int jniArgInfo; - -}Method; - - -typedef struct ClassObject { - Object obj; /* MUST be first item */ - - /* leave space for instance data; we could access fields directly if we - freeze the definition of java/lang/Class */ - __uint32_t instanceData[4]; - - /* UTF-8 descriptor for the class; from constant pool, or on heap - if generated ("[C") */ - const char* descriptor; - char* descriptorAlloc; - - /* access flags; low 16 bits are defined by VM spec */ - __uint32_t accessFlags; - - /* VM-unique class serial number, nonzero, set very early */ - __uint32_t serialNumber; - - /* DexFile from which we came; needed to resolve constant pool entries */ - /* (will be NULL for VM-generated, e.g. arrays and primitive classes) */ - void* pDvmDex; - - /* state of class initialization */ - ClassStatus status; - - /* if class verify fails, we must return same error on subsequent tries */ - struct ClassObject* verifyErrorClass; - - /* threadId, used to check for recursive invocation */ - __uint32_t initThreadId; - - /* - * Total object size; used when allocating storage on gc heap. (For - * interfaces and abstract classes this will be zero.) - */ - size_t objectSize; - - /* arrays only: class object for base element, for instanceof/checkcast - (for String[][][], this will be String) */ - struct ClassObject* elementClass; - - /* class object representing an array of this class; set on first use */ - struct ClassObject* arrayClass; - - /* arrays only: number of dimensions, e.g. int[][] is 2 */ - int arrayDim; - - /* primitive type index, or PRIM_NOT (-1); set for generated prim classes */ - PrimitiveType primitiveType; - - /* superclass, or NULL if this is java.lang.Object */ - struct ClassObject* super; - - /* defining class loader, or NULL for the "bootstrap" system loader */ - Object* classLoader; - - /* initiating class loader list */ - /* NOTE: for classes with low serialNumber, these are unused, and the - values are kept in a table in gDvm. */ - InitiatingLoaderList initiatingLoaderList; - - /* array of interfaces this class implements directly */ - int interfaceCount; - struct ClassObject** interfaces; - - /* static, private, and methods */ - int directMethodCount; - Method* directMethods; - - /* virtual methods defined in this class; invoked through vtable */ - int virtualMethodCount; - Method* virtualMethods; - - /* - * Virtual method table (vtable), for use by "invoke-virtual". The - * vtable from the superclass is copied in, and virtual methods from - * our class either replace those from the super or are appended. - */ - int vtableCount; - Method** vtable; - - /* - * Interface table (iftable), one entry per interface supported by - * this class. That means one entry for each interface we support - * directly, indirectly via superclass, or indirectly via - * superinterface. This will be null if neither we nor our superclass - * implement any interfaces. - * - * Why we need this: given "class Foo implements Face", declare - * "Face faceObj = new Foo()". Invoke faceObj.blah(), where "blah" is - * part of the Face interface. We can't easily use a single vtable. - * - * For every interface a concrete class implements, we create a list of - * virtualMethod indices for the methods in the interface. - */ - int iftableCount; - InterfaceEntry* iftable; - - /* - * The interface vtable indices for iftable get stored here. By placing - * them all in a single pool for each class that implements interfaces, - * we decrease the number of allocations. - */ - int ifviPoolCount; - int* ifviPool; - - /* static fields */ - int sfieldCount; - void* sfields; - - /* instance fields - * - * These describe the layout of the contents of a DataObject-compatible - * Object. Note that only the fields directly defined by this class - * are listed in ifields; fields defined by a superclass are listed - * in the superclass's ClassObject.ifields. - * - * All instance fields that refer to objects are guaranteed to be - * at the beginning of the field list. ifieldRefCount specifies - * the number of reference fields. - */ - int ifieldCount; - int ifieldRefCount; // number of fields that are object refs - void* ifields; - - /* bitmap of offsets of ifields */ - __uint32_t refOffsets; - - /* source file name, if known */ - const char* sourceFile; -}ClassObject; - -typedef struct Thread -{ - -}Thread; - -enum { - ACC_PUBLIC = 0x00000001, // class, field, method, ic - ACC_PRIVATE = 0x00000002, // field, method, ic - ACC_PROTECTED = 0x00000004, // field, method, ic - ACC_STATIC = 0x00000008, // field, method, ic - ACC_FINAL = 0x00000010, // class, field, method, ic - ACC_SYNCHRONIZED = 0x00000020, // method (only allowed on natives) - ACC_SUPER = 0x00000020, // class (not used in Dalvik) - ACC_VOLATILE = 0x00000040, // field - ACC_BRIDGE = 0x00000040, // method (1.5) - ACC_TRANSIENT = 0x00000080, // field - ACC_VARARGS = 0x00000080, // method (1.5) - ACC_NATIVE = 0x00000100, // method - ACC_INTERFACE = 0x00000200, // class, ic - ACC_ABSTRACT = 0x00000400, // class, method, ic - ACC_STRICT = 0x00000800, // method - ACC_SYNTHETIC = 0x00001000, // field, method, ic - ACC_ANNOTATION = 0x00002000, // class, ic (1.5) - ACC_ENUM = 0x00004000, // class, field, ic (1.5) - ACC_CONSTRUCTOR = 0x00010000, // method (Dalvik only) - ACC_DECLARED_SYNCHRONIZED = - 0x00020000, // method (Dalvik only) - ACC_CLASS_MASK = - (ACC_PUBLIC | ACC_FINAL | ACC_INTERFACE | ACC_ABSTRACT - | ACC_SYNTHETIC | ACC_ANNOTATION | ACC_ENUM), - ACC_INNER_CLASS_MASK = - (ACC_CLASS_MASK | ACC_PRIVATE | ACC_PROTECTED | ACC_STATIC), - ACC_FIELD_MASK = - (ACC_PUBLIC | ACC_PRIVATE | ACC_PROTECTED | ACC_STATIC | ACC_FINAL - | ACC_VOLATILE | ACC_TRANSIENT | ACC_SYNTHETIC | ACC_ENUM), - ACC_METHOD_MASK = - (ACC_PUBLIC | ACC_PRIVATE | ACC_PROTECTED | ACC_STATIC | ACC_FINAL - | ACC_SYNCHRONIZED | ACC_BRIDGE | ACC_VARARGS | ACC_NATIVE - | ACC_ABSTRACT | ACC_STRICT | ACC_SYNTHETIC | ACC_CONSTRUCTOR - | ACC_DECLARED_SYNCHRONIZED), -}; - -inline int IsNativeMethod(const Method* method) { - return (method->accessFlags & ACC_NATIVE) != 0; -} - -typedef struct InterpState -{ - -}InterpState; - -typedef InterpState MterpGlue; - - -#endif diff --git a/dalvik_handlers/handlers.c b/dalvik_handlers/handlers.c deleted file mode 100644 index 131bf45..0000000 --- a/dalvik_handlers/handlers.c +++ /dev/null @@ -1,219 +0,0 @@ -#include "module.h" -#include "probes.h" -#include "storage.h" - -#include "../kprobe/dbi_kprobes_deps.h" - - -int fp_kallsyms_lookup_name = 0; -module_param(fp_kallsyms_lookup_name, uint, 0); -MODULE_PARM_DESC(fp_kallsyms_lookup_name, - "address of 'kallsyms_lookup_name' function"); - -#if LINUX_VERSION_CODE >= KERNEL_VERSION(2, 6, 11) -#define tcp_opt tcp_sock -#endif - -#if LINUX_VERSION_CODE >= KERNEL_VERSION(2, 6, 20) -#define kmem_cache_t struct kmem_cache -#endif - -#if LINUX_VERSION_CODE >= KERNEL_VERSION(2, 6, 17) -extern void swap_register_notify (struct notifier_block *nb); -extern void swap_unregister_notify (struct notifier_block *nb); -#endif - - -struct handler_map { - unsigned long func_addr; - unsigned long jp_handler_addr; - unsigned long rp_handler_addr; -}; - -#include "../../symbol/android/demangle.h" -#include "index_tree.h" -#include - -struct rb_root class_tree = RB_ROOT; - -#include "probe_code.inc" - -static int start_stop_notify(struct notifier_block *self, unsigned long action, void *data) -{ - unsigned int i =0; - struct rb_root* pClass = 0; - struct rb_root* pMethod = 0; - struct rb_root* pProto = 0; - - - switch (action) - { - case EC_IOCTL_ATTACH: - { - // fill in search tree - DPRINTF("Registering dex probes"); - - for ( i = 0; i < dex_proc_info.ips_count; i++ ) - { - pClass = dict_insert ( &class_tree, dex_proc_info.p_ips[i].class_name ); - pMethod = dict_insert ( pClass, dex_proc_info.p_ips[i].method_name ); - pProto = dict_insert ( pMethod, dex_proc_info.p_ips[i].prototype ); - - DPRINTF( "Registered probe for %s::%s::%s", dex_proc_info.p_ips[i].class_name, dex_proc_info.p_ips[i].method_name, dex_proc_info.p_ips[i].prototype ); - } - - DPRINTF("DEX probes registered OK"); - - DPRINTF("DEX probes selftest..."); - for ( i = 0; i < dex_proc_info.ips_count; i++ ) - { - pClass = dict_search ( &class_tree, dex_proc_info.p_ips[i].class_name ); - if ( 0 == pClass ) - { - DPRINTF("DEX probes selftest class %s not found", dex_proc_info.p_ips[i].class_name ); - DPRINTF("DEX probes selftest...FAILED"); - continue; - } - - pMethod = dict_search ( pClass, dex_proc_info.p_ips[i].method_name ); - if ( 0 == pMethod ) - { - DPRINTF("DEX probes selftest method %s not found", dex_proc_info.p_ips[i].method_name ); - DPRINTF("DEX probes selftest...FAILED"); - continue; - } - - - pProto = dict_search ( pMethod, dex_proc_info.p_ips[i].prototype ); - if ( 0 == pProto ) - { - DPRINTF("DEX probes selftest proto %s not found", dex_proc_info.p_ips[i].prototype ); - DPRINTF("DEX probes selftest...FAILED"); - continue; - } - - DPRINTF( "Dex probe for %s::%s::%s TEST OK", dex_proc_info.p_ips[i].class_name, dex_proc_info.p_ips[i].method_name, dex_proc_info.p_ips[i].prototype ); - } - - - break; - } - case EC_IOCTL_STOP_AND_DETACH: - { - // reset search tree - dict_empty_tree( &class_tree ); - DPRINTF("DEX probes reset OK"); - break; - } - } - -} - -static struct notifier_block swap_nb = { - .notifier_call = start_stop_notify, -}; - - -unsigned long find_jp_handler(unsigned long addr) -{ - int i; - - /* Possibly we can find less expensive way */ - for (i = 0; i < nr_handlers; i++) { - if (handlers[i].func_addr == addr) - return handlers[i].jp_handler_addr; - } - - return 0; -} - -unsigned long find_rp_handler(unsigned long addr) -{ - int i; - - /* Possibly we can find less expensive way */ - for (i = 0; i < nr_handlers; i++) { - if (handlers[i].func_addr == addr) - return handlers[i].rp_handler_addr; - } - - return 0; -} - -DECLARE_PER_CPU (us_proc_ip_t *, gpCurIp); -DECLARE_PER_CPU (struct pt_regs *, gpUserRegs); - -extern void dbi_uprobe_return(void); - -#include "dalvik_defs.h" - - -static inline int IsAndroidEvent ( Method *arg1 ) -{ - const char* szMethodName = arg1->name; - const char* szPrototype = arg1->shorty; - const char* szClassName = arg1->clazz->descriptor; - const char* szDexFile = arg1->clazz->sourceFile; - struct rb_root* pClass = NULL; - struct rb_root* pMethod = NULL; - struct rb_root* pProto = NULL; - - if ( dict_is_empty ( &class_tree ) ) - return 1; - - pClass = dict_search ( &class_tree, szClassName ); - - if ( 0 == pClass ) - { - return 0; - } - - pMethod = dict_search ( pClass, szMethodName ); - - if ( 0 == pMethod ) - { - return 0; - } - - pProto = dict_search ( pMethod, szPrototype ); - - if ( 0 == pProto ) - { - return 0; - } - - return 1; -} - - -#include "uprobe_code.inc" - - -static int __init handlers_init(void) -{ - dbi_install_user_handlers(); - - -#if LINUX_VERSION_CODE >= KERNEL_VERSION(2, 6, 17) - swap_register_notify(&swap_nb); -#endif - - return 0; -} - -static void __exit handlers_exit(void) -{ - -#if LINUX_VERSION_CODE >= KERNEL_VERSION(2, 6, 17) - swap_unregister_notify(&swap_nb); -#endif - - dbi_uninstall_user_handlers(); -} - -module_init(handlers_init); -module_exit(handlers_exit); - -MODULE_LICENSE("GPL"); -MODULE_DESCRIPTION("SWAP Dalvik VM handlers module"); -MODULE_AUTHOR("Leonid Astakhov "); diff --git a/dalvik_handlers/index_tree.c b/dalvik_handlers/index_tree.c deleted file mode 100644 index 8a31686..0000000 --- a/dalvik_handlers/index_tree.c +++ /dev/null @@ -1,348 +0,0 @@ -//////////////////////////////////////////////////////////////////////////////////// -// -// FILE: index_tree.c -// -// DESCRIPTION: fast search implementation based on linux kernel rb_tree -// -// SEE ALSO: -// AUTHOR: L.Astakhov -// COMPANY NAME: Samsung Research Center in Moscow -// DEPT NAME: Advanced Software Group -// CREATED: 2011.06.07 -// VERSION: 1.0 -// REVISION DATE: 2011.06.07 -// -//////////////////////////////////////////////////////////////////////////////////// - -#define __INDEX_TREE_EXPORT__ - -#include "index_tree.h" -#include - -// =================================================================== -// -// Index tree -// -// =================================================================== - - -struct index_tree_node* index_search(struct rb_root *root, unsigned long long index) -{ - struct rb_node *node = root->rb_node; - - while (node) { - struct index_tree_node *data = container_of(node, struct index_tree_node, node); - - if (index < data->index) - node = node->rb_left; - else if (index > data->index) - node = node->rb_right; - else - return data; - } - return NULL; -} - -int index_insert_node(struct rb_root *root, struct index_tree_node *data) -{ - struct rb_node **new = &(root->rb_node), *parent = NULL; - - /* Figure out where to put new node */ - while (*new) { - struct index_tree_node *this = container_of(*new, struct index_tree_node, node); - - parent = *new; - - if ( data->index < this->index ) - new = &((*new)->rb_left); - else if ( data->index > this->index ) - new = &((*new)->rb_right); - else - return 0; - } - - /* Add new node and rebalance tree. */ - rb_link_node(&data->node, parent, new); - rb_insert_color(&data->node, root); - - return 1; -} - -int index_insert(struct rb_root *root, unsigned long long index) -{ - struct index_tree_node* data = NULL; - unsigned int size = sizeof (struct index_tree_node); - - data = allocate ( size ); - data->index = index; - - return index_insert_node( root, data ); -} - -void index_empty_node ( struct rb_node **victim ) -{ - struct index_tree_node *this = NULL; - - this = container_of(*victim, struct index_tree_node, node); - - if ( NULL == this ) - return; - - if ( NULL != (*victim)->rb_left ) - index_empty_node( &(*victim)->rb_left ); - - if ( NULL != (*victim)->rb_right ) - index_empty_node( &(*victim)->rb_right ); - - deallocate ( this ); - *victim = NULL; -} - -void index_empty_tree ( struct rb_root *root ) -{ - index_empty_node( &root->rb_node ); -} - -void index_erase ( struct rb_root *root, unsigned long long index ) -{ - struct index_tree_node* data = NULL; - - if ( NULL == root ) - return; - - data = index_search ( root, index ); - - if ( NULL == data ) - return; - - rb_erase( &data->node, root ); - deallocate ( data ); -} - -// =================================================================== -// -// Dictionary tree -// -// =================================================================== - - -struct rb_node** letter_search_node(struct rb_node **node, char letter) -{ - while ( *node ) - { - struct dict_tree_node *data = container_of(*node, struct dict_tree_node, node); - - if ( letter < data->letter) - node = &((*node)->rb_left); - else if ( letter > data->letter ) - node = &((*node)->rb_right); - else - return node; - } - - return node; -} - -struct dict_tree_node* letter_subsearch(struct rb_node *node, char letter) -{ - while (node) - { - struct dict_tree_node *data = container_of(node, struct dict_tree_node, node); - - if ( letter < data->letter) - node = node->rb_left; - else if ( letter > data->letter ) - node = node->rb_right; - else - return data; - } - - return NULL; -} - -struct dict_tree_node* letter_search(struct rb_root *root, char letter) -{ - struct rb_node *node = root->rb_node; - - return letter_subsearch ( node, letter ); -} - -int letter_insert(struct rb_root *root, struct dict_tree_node *data) -{ - struct rb_node *parent = NULL; - struct rb_node **new = &(root->rb_node); - struct dict_tree_node *this = NULL; - - /* Figure out where to put new node */ - while (*new) { - - this = container_of(*new, struct dict_tree_node, node); - - parent = *new; - - if ( data->letter < this->letter ) - new = &((*new)->rb_left); - else if ( data->letter > this->letter ) - new = &((*new)->rb_right); - else - return 0; - } - - /* Add new node and rebalance tree. */ - rb_link_node(&data->node, parent, new); - rb_insert_color(&data->node, root); - - return 1; -} - -struct dict_tree_node* dict_search_node (struct rb_root *root, const char* str) -{ - struct rb_root *begin = root; - struct dict_tree_node* data = NULL; - const char* pI = str; - - if ( NULL == pI ) - return NULL; - - do - { - data = letter_search ( begin, *pI ); - - if ( NULL == data ) - break; - - begin = &data->subtree; - - } while ( *++pI ); - - return data; -} - -int dict_contains ( struct rb_root *root, const char* str ) -{ - struct dict_tree_node* data = NULL; - - data = dict_search_node ( root, str ); - - if ( NULL == data ) - return 0; - - return data->leaf; -} - -struct rb_root* dict_search (struct rb_root *root, const char* str) -{ - struct dict_tree_node* data = NULL; - - data = dict_search_node ( root, str ); - - if ( NULL == data ) - return NULL; - - return &data->subtree; -} - -struct rb_root* dict_insert ( struct rb_root* root, const char* str ) -{ - struct rb_root *begin = root; - struct dict_tree_node* data = NULL; - struct dict_tree_node *node = NULL; - - unsigned int size = sizeof ( struct dict_tree_node ); - - const char* pI = str; - - if ( NULL == pI ) - return NULL; - - do - { - data = letter_search ( begin, *pI ); - - if ( NULL == data ) - break; - - begin = &data->subtree; - - } while ( *++pI ); - - if ( 0 == *pI ) // the string is already in - return begin; - - // part of the string (probably whole string) is not in tree - do - { - node = allocate ( size ); - *node = RB_DICT_NODE; - - node->letter = *pI; - node->leaf = 0; - - letter_insert ( begin, node ); - - begin = &node->subtree; - - }while ( *++pI ); - - node->leaf = 1; - - return begin; -} - -void dict_erase ( struct rb_root *root, const char* str ) -{ - struct dict_tree_node* data = NULL; - - const char* pI = str; - - if ( NULL == pI || 0 == *pI || NULL == root ) - return; - - data = letter_search ( root, *pI ); - - if ( NULL == data ) - return; - - dict_erase ( &data->subtree, ++pI ); - - if ( NULL != data->subtree.rb_node ) // if subtree is not empty - return; - - if ( 0 != *pI && data->leaf ) // if not last && it is leaf - return; - - rb_erase( &data->node, root ); - deallocate ( data ); -} - -void dict_empty_node ( struct rb_node **victim ) -{ - struct dict_tree_node *this = NULL; - - this = container_of(*victim, struct dict_tree_node, node); - - if ( NULL == this ) - return; - - dict_empty_tree ( &this->subtree ); - - if ( NULL != (*victim)->rb_left ) - dict_empty_node( &(*victim)->rb_left ); - - if ( NULL != (*victim)->rb_right ) - dict_empty_node( &(*victim)->rb_right ); - - deallocate ( this ); - *victim = NULL; - -} - -void dict_empty_tree ( struct rb_root *root ) -{ - dict_empty_node( &root->rb_node ); -} - -int dict_is_empty ( struct rb_root *root ) -{ - return ( 0 == root->rb_node ); -} diff --git a/dalvik_handlers/index_tree.h b/dalvik_handlers/index_tree.h deleted file mode 100644 index 0006c87..0000000 --- a/dalvik_handlers/index_tree.h +++ /dev/null @@ -1,60 +0,0 @@ -//////////////////////////////////////////////////////////////////////////////////// -// -// FILE: index_tree.h -// -// DESCRIPTION: fast search implementation based on linux kernel rb_tree -// -// SEE ALSO: -// AUTHOR: L.Astakhov -// COMPANY NAME: Samsung Research Center in Moscow -// DEPT NAME: Advanced Software Group -// CREATED: 2011.06.07 -// VERSION: 1.0 -// REVISION DATE: 2011.06.07 -// -//////////////////////////////////////////////////////////////////////////////////// - -#ifndef INDEX_TREE_H_ -#define INDEX_TREE_H_ - -#include -#include - -struct index_tree_node { - struct rb_node node; - unsigned long long index; -}; - -struct dict_tree_node { - struct rb_node node; - char letter; - unsigned int leaf; - struct rb_root subtree; -} __attribute__((aligned(sizeof(long)))); - -#define RB_NODE (struct rb_node) { 0, NULL, NULL, } -#define RB_DICT_NODE (struct dict_tree_node) { RB_NODE, 0, 0, RB_ROOT, } - -#ifdef __INDEX_TREE_IMPORT__ -extern "C" -{ -#endif - - struct index_tree_node* index_search( struct rb_root *root, unsigned long long index ); - int index_insert( struct rb_root *root, unsigned long long index ); - void index_erase ( struct rb_root *root, unsigned long long index ); - void index_empty_tree ( struct rb_root *root ); - struct rb_root* dict_search ( struct rb_root *root, const char* str ); - struct rb_root* dict_insert ( struct rb_root* root, const char* str ); - void dict_erase ( struct rb_root *root, const char* str ); - void dict_empty_tree ( struct rb_root *root ); - int dict_is_empty ( struct rb_root *root ); - -#ifdef __INDEX_TREE_IMPORT__ -} -#endif - - - - -#endif /* INDEX_TREE_H_ */ -- 2.7.4