The Ego Reference Manual

Table of Contents


Node:Introduction

Introduction

Ego is a free program introspection library released under the terms of the GNU General Public Licence. C does not provide any introspection (reflective) facilities, ie. facilities that allow to get information about the program at run-time and to answer questions such as: What symbols are defined and what are their types? What is the type of the data available at this address? What is the function which called me? Ego aims at providing some of these facilities to the application programmer, by using the debugging information added to binary object files by the compiler. In other words, Ego is pretty much like an embedded debugger, with limited functionalities (eg. no breakpoints), but with maximum information made available to the user1.

The main purpose of Ego is to permit the implementation of Pego (Portable & Persistent Ego), a free program serialization library that can create portable checkpoints of the application data. Note that this could also be used, for instance, to write an automatic serialization library that could be used within a "software bus" la CORBA, or just a debugger (well, we already have GDB so that would not be so useful ;))...


Node:Stabs, Next:, Up:Introduction

Stabs

Ego gets the necessary information about variables (symbol_t), types (ctype_t), line numbers, and so on from the compiled-in debbugging information. Ego works pretty much like a debugger: When it's initialized (by calling ego_init ()), it parses the exectutable file stabs (aka. debugging information) and builds a representation (meta-model) of all symbols and types used by the application. This means that the application has to be compiled with debugging symbols, which results in larger executables (drawback). GCC's option for producing stabs is "-g" or better "-gstabs+" (for GNU stabs). Currently, only the stabs debugging format (with GNU extensions) is recognized by Ego. It has been successfully tested with GCC 2.95.4 and GCC 3.2.3 which uses some IBM and Sun extensions. For further details, you might want to look at The "Stabs" Debug Format.


Node:C++ Support, Previous:Stabs, Up:Introduction

C++ Support

Ego should be able to read and "understand" GNU C++ debugging information (stabs). However, it provides little support for it. For instance, there exist type objects describing C++ methods (see Type Information) but it does not give any clue on the number of arguments, on the argument types, on whether the method is virtual or not, and so on. Also, inheritance is not reflected by Ego's type objects, nor is name "demangling". There was actually no need for it as Pego does not need this type of information.


Node:Basics

Basics

This chapter describes the basic structure of objects representing a given C/C++ program, how they are organized, and what functions can be used to handle them. The way programs are represented by Ego can be seen as a program meta-model.

A C (or C++, etc.) program is made of a main binary file which is the executable file, and of several other binary files including shared dynamically linked libraries that get linked to the program at runtime. The program as a whole (that is, all these elements) is represented by ego_t objects. An ego_t object may contain at least one ego_binary_t object representing the executable file itself, at probably other ego_binary_t objects representing shared libraries2. The user may choose to just use the static analysis of binary files represented by ego_binary_t objects (i.e. mostly getting information about variables, symbols, code structure, etc. ; see Symbols), or he may choose to use ego_t objects that provide more dynamic analysis features (see Memory Objects). The ego_t and ego_binary_t type definitions are available in <ego/ego_types.h>.

Each binary file composing a program (each ego_binary_t) is composed of several source files represented by source_file_t objects. Each of these source files may in turn include several header files which are represented by include_file_t objects. This type of information may sometimes be useful: For example, to accurately represent a type (see Type Information) you need to know not only its name but also the file (either the header or source file) where it is defined (this is because, for instance, foo_t could be defined differently in file a.c and in file b.c). Finally, each source file or include file may define a number of types (see Type Information) and a number of symbols (see Symbols).

The following is the basic API to initialize ego_t and/or ego_binary_t objects. It is defined in <ego/ego.h>.

ego_error_t ego_init (ego_t *ego, const char *program); Function

Initialize ego. program is the executable file name. Fill in ego with the corresponding information. Returns zero if successful.

ego_error_t ego_init_with_hooks (ego_t *ego, const char *program, memory_object_hook_t new_hook, memory_object_hook_t delete_hook, memory_object_hook_t resize_hook, void *data); Function

Same as ego_init () except that new_hook, delete_hook, and resize_hook will be called (if non-null) each time a memory object is created, deleted or resized. data will be assigned to the 'data' field of ego.

const char *ego_error_message (ego_error_t err); Function

Get the error message that corresponds to err. The returned string is static and should not be freed.

ego_error_t ego_binary_init (ego_binary_t * bin, const char *file, ego_error_t (*symhook) (ego_binary_t *, symbol_t *, void *), void *value); Function

Fill in bin with information for the binary file file. Returns zero if successful. If not null, symhook gets called each time a symbol is registered with value as its third parameter. Note that this function is automatically called by ego_init (). However, one can use it without using an ego_t.

ego_error_t ego_data_is_readonly (ego_binary_t *bin, void *address, int *readonly); Function

On success, return zero and set *readonly to zero iff address points to data in bin which is not read-only. If address does not point to static data in bin, then return non-zero.

void ego_debug_set_file (const char *file); Function

Print debugging output to file. This function is only available if Ego was compiled with the debug flag set.


Node:Type Information

Type Information

Types defined in C programs are represented by ctype_t objects created at runtime when ego_init () is called.


Node:Overview, Next:, Up:Type Information

Overview

There are several kinds of C types, defined by the kind field (which is an enumerate of type ctype_kind_t) of ctype_t objects. Basically, regular types are CTYPE_NORMAL, structures and unions are respectively CTYPE_STRUCT and CTYPE_UNION (see Structures and Unions), enumerates are CTYPE_ENUM3, functions are CTYPE_FUNCTION, and C++ methods are either CTYPE_METHOD or CTYPE_STATIC_METHOD.

Each C type has an identifier (field id). If the type was defined in an include file the pair (include-file, type-id) is sufficient to identify a type definition (see Types Origin). ctype_t objects may optionnally have a name, available in the name field. The size of a type is defined by its size field.

The ego_get_ctype () macro defined in <ego/ctypes.h> makes it easy to get the ctype_t object associated to a given type:

     {
       ctype_t *my_type_t_ctype;
     
       my_type_t_ctype = ego_get_ctype (&bin, my_type_t);
     }
     
where my_type_t is a type and bin is a variable that contains a pointers to the relevant ego_binary_t object (see Basics). However, symbols representing variables and functions (see Symbols) also contain a pointer to the ctype_t object representing their type.


Node:Constructed Types, Next:, Previous:Overview, Up:Type Information

Constructed Types

Most of the time, C types are defined using other types as a basis. The idea of cross-references to C types is used to represent such situations. There are several kinds of reference links that can exist between ctype_t objects, depending on how types are defined:

Note that, even if your code, for instance, doesn't typedef int *, a ctype_t object representing the type pointer-to-int will anyway get created.


Node:Structures and Unions, Next:, Previous:Constructed Types, Up:Type Information

Structures and Unions

For ctype_t objects representing structures, unions or C++ class, the fields field is a list containing ctype_struct_field_t objects, each of which represent a given field of this type. Each ctype_struct_field_t object contains the name of the field (the name field which is always non-null), the offset in bits of the field within the structure, union or class (the offset field), the size in bits of the field (size), and a pointer to the ctype_t object representing the type of this field (ctype).

Structure (or union or class) fields may be looked up by name using ego_ctype_struct_field_lookup (), or they may be looked up by offset using ego_ctype_struct_field_find (), or they may be traversed using ego_ctype_struct_traverse_fields () (see C Types API).


Node:Types Origin, Next:, Previous:Structures and Unions, Up:Type Information

Types Origin

As for symbols (see Symbols Origin), it may sometimes be useful to know where (i.e. in which source/include file) a type was defined. For instance, consider two file-scope types having the same name: In order to differentiate between them, it's important to know in which source or include file each of them was defined.

ctype_t objects have a source field (resp. an include field) which points to the source_file_t (resp. include_file_t) object that represents the source file (resp. include file) in which it was defined. One and exactly one of these two fields should always be non-null.


Node:C Types API, Previous:Types Origin, Up:Type Information

C Types API

The functions described below (available in <ego/ctypes.h>) allow to query information about those types.

ego_error_t ego_ctype_find (source_file_t *source, const ctype_id_t *ctypeid, ctype_t **ctype); Function

Look for C type identified by ctypeid in source. On success, return zero and set ctype accordingly.

ego_error_t ego_ctype_lookup (source_file_t *source, const ctype_t *start, const char *name, ctype_t **ctype); Function

Lookup C type with name name in source's C types table and fill in ctype with the corresponding C type information. If start is non-null then the type lookup procedure will start after start; otherwise, name is searched for in the whole C types table. This is very useful since several C types can have the same name.

const ctype_t *ego_ctype_equivalent (const ctype_t *ctype); Function

Browse ctype's references while the reference type is ctype_xref_equals and return the canonical equivalent C type.

int ego_ctype_is_kind (const ctype_t *ctype, ctype_kind_t kind, const ctype_t **equivalent); Function

Returns non-zero if ctype's kind is equivalent to kind (ie. if ctype is kind or if ctype is equal to another C type of kind kind). On success, equivalent points to the type of kind kind equivalent to ctype.

int ego_ctype_is_xref (const ctype_t *ctype, ctype_xref_type_t type, const ctype_t **equivalent); Function

Returns non-zero if ctype's xref is equivalent to type (ie. if ctype is a type xref or if ctype is equal to another C type of xref type). On success, equivalent points to the type of xref type type equivalent to ctype.

ego_error_t ego_ctype_struct_field_lookup (ctype_t *structure, const char *name, ctype_struct_field_t **field); Function

Look for a field named name in structure. On success, zero is returned and *field points to the field found.

ctype_struct_field_t *ego_ctype_struct_field_find (ctype_t *structure, size_t offset, size_t *rem); Function

Return the field of structure (which is assumed to be a ctype_struct) at offset offset (in bytes) and set *rem to the remaining offset within this field.

ego_error_t ego_ctype_struct_traverse_fields (ctype_t *structure, const ctype_struct_field_t *start, int (*func) (ctype_struct_field_t *, void *value), void *value, ctype_struct_field_t **found); Function

Traverse structure's field list starting after start or at the beginning if start is zero. func gets called on each field with argument value. Stops whenever func returns zero and sets found to the field on which func returned zero. structure can be either a struct or a union.

ego_error_t ego_ctype_print (char **string, const ctype_t *ctype, void *value); Function

Print value which is of type ctype in *string. *string may be free ()d by the caller afterwards.

ego_error_t ego_ctype_scan (const char *string, const ctype_t *ctype, void *value); Function

Convert string to a value of type ctype and store it into value. ctype has to be a C built-in type (eg. "int", "char", etc.).

void ego_ctypes_init (source_file_t *source); Function

Initializes source's ctypes list and hash tables.

void ego_ctypes_include_init (include_file_t *include); Function

Initializes include's ctypes list and hash tables.

ego_error_t __parse_typedef (source_file_t *source, include_file_t *include, const char *name, const char *typeinfo); Function

Parses a typedef for type name with type information stored in typeinfo. Register new type(s) for source. If non-null, include represents the current include file.

ego_error_t __parse_type_info (source_file_t *source, include_file_t *include, const char *string, ctype_t ** rettype, char **after); Function

Parse type information available in string (which should start with a type number and may be followed by one or several '=' signs) and set ctype to the type described by string. after is updated to point past the end of the type info in string. New ctypes may be registered while parsing string.


Node:Symbols

Symbols

Symbols (or symbol_t objects) are the basic object type to represent the structure of a program, such as its variables, functions and code blocks.


Node:Symbols Kinds, Next:, Up:Symbols

Symbols Kinds

Symbols (that is, symbol_t objects) may represent any of the following kind of data, depending on the value of its kind field (which is an enumerate of type ctype_kind_t):

Except for SYM_BLOCK symbols, the name field should be non-null and should give the name of the symbol it represents.

The address field is a pointer to the actual symbol when this is relevant. This is not relevant for local variables and parameters, for instance, since they may be allocated either on the stack or in registers at run-time, but it is relevant for non-local functions and variables (see Symbols Scope). For code blocks and functions, the endaddress field also gives the adress where the code ends.


Node:Symbols Scope, Next:, Previous:Symbols Kinds, Up:Symbols

Symbols Scope

The scope field of symbol_t objects represent their scope (type symbol_scope_t which may be any of the following values (defined in <ego/bits/symbols.h>):


Node:Symbols Origin, Next:, Previous:Symbols Scope, Up:Symbols

Symbols Origin

As for C types (see Types Origin), it may sometimes be useful to know where (i.e. in which source/include file, at what line) a symbol was defined. For instance, consider two file-scope variables having the same name: In order to differentiate between them, it's important to be able to know in which source file each of them was defined. The same goes for block-scope variables, except that you also need to know at what line of the source file each of them was defined.

symbol_t objects have a source field which points to the source_file_t object that represents the source file in which it was defined. It should always be non-null. The line field gives the line number at which the symbol was defined in the given source file.

In some cases, header files may declare (file-scope) variables. In such cases, the include field is non-null and points to the include_file_t object that represents the include file in which the variable was defined and the line field is the line number of the variable definition within this include file.


Node:Symbols Tree, Next:, Previous:Symbols Origin, Up:Symbols

Symbols Tree

Ego's symbol_t objects are recorded, for each ego_binary_t, in an hierarchical way that reflects the actual code and scope of each definition. In other words, symbol_t inherits from tree_t (see Trees). For example, the following code:

     int
     foo (int param1, char param2)
     {
       int local1, local2;
       static int static1;
     
       {
         char local3;
       }
     
       return param1;
     }
     

leads to the following symbol_t tree:

     
     [root] (SYM_ROOT)
        +
        |
        +-- foo (SYM_FUNCTION)
             |
             +-- param1  (SYM_PARAMETER)
             +-- param2  (SYM_PARAMETER)
             +-- local1  (SYM_VARIABLE)
             +-- local2  (SYM_VARIABLE)
             +-- static1 (SYM_VARIABLE)
             |
             +-- [block] (SYM_BLOCK)
                    |
                    +-- local3 (SYM_VARIABLE)
     
     


Node:Symbols API, Previous:Symbols Tree, Up:Symbols

Symbols API

The following is the symbol-related API defined in <ego/symbols.h>. Note that it also deals with source files and include files:

ego_error_t ego_source_file_lookup (ego_binary_t *bin, const source_file_t *start, const char *path, source_file_t **file); Function

Look for source file with basename name in bin starting after start (which is useful since several files could have the same basename) if start is non-zero. On success *file points to the source file requested and zero is returned.

ego_error_t ego_source_line_lookup (source_file_t *source, unsigned int line, address_info_t **info); Function

Look for information about line number line in source file source. On success, return zero and set *info to a structure describing the code available at line line.

ego_error_t ego_include_file_lookup (ego_binary_t *bin, const include_file_t *start, const char *path, include_file_t **file); Function

Look for include file with path path in bin starting after start if start is non-zero. On success *file points to the include file requested and zero is returned.

source_file_t *ego_include_file_first_includer (include_file_t *include); Function

Return the first source file that includes include.

ego_error_tego_include_file_traverse_includers (include_file_t *include, int (*func) (source_file_t *, void *value), void *value, source_file_t **source); Function

Traverse include's list of includers (ie. source files that include it). func gets called on each includer with argument value. Stops whenever func returns zero and sets *source to the file on which func returned zero.

ego_error_t ego_symbol_lookup (ego_binary_t * bin, const symbol_t * start, const char *name, symbol_t ** sym); Function

Lookup symbol with name name in bin's symbol table and fill in sym with the corresponding symbol information. If start is non-null then the symbol lookup procedure will start after start; otherwise, name is searched for in the whole symbol table. This is very useful since several (local) symbols can have the same name.

ego_error_t ego_symbol_lookup_specific (ego_binary_t *bin, const symbol_t *start, const char *name, symbol_type_t type, symbol_scope_t scope, const source_file_t *source, const include_file_t *include, unsigned int line, const ctype_t *ctype, symbol_t **sym); Function

Same as ego_symbol_lookup () except that it only looks for symbols of type type, with scope scope (if scope differs from sym_scope_unknown) defined in source file file (if file is non-null) in function function (if non-null) and of type ctype (if ctype is non-null). If either source or include is non-null and line is non-zero, the return the symbol defined in the corresponding file at line line.

ego_error_t ego_symbol_find (ego_binary_t *bin, const void *addr, symbol_t ** sym); Function

Find symbol at address addr in bin's symbol table and fill in sym with the corresponding symbol information.

ego_error_t ego_symbol_traverse (ego_binary_t *bin, symbol_t *start, int (*func) (symbol_t *, void *value), void *value, symbol_t **found); Function

Traverse bin's symbol list starting after start or at the beginning if start is zero. func gets called on each symbol with argument value. Stops whenever func returns zero and sets found to the symbol on which func returned zero.

ego_error_t ego_address_find (ego_binary_t *bin, const void *addr, address_info_t **info); Function

Find address address, an address in bin's code (ie. the 'text' segment) and update *info with the relevant corresponding information. Return zero on success.

void *ego_symbol_address (const symbol_t *sym); Function

Returns the address of sym except if sym is a sym_parameter or a local variable.

const ctype_t *ego_symbol_ctype (const symbol_t *sym); Function

Returns the type of sym except if sym is a sym_block.

symbol_t *ego_symbol_parent_function (symbol_t *variable); Function

If variable has a function-local scope (either static or not), return the symbol of its parent function, NULL otherwise.

ego_error_t ego_symtab_init (ego_binary_t *bin); Function

Initialize bin's symbol table (internal use).

ego_error_t ego_symbol_load_table (ego_binary_t *ego, ego_error_t (*symhook) (ego_binary_t *, symbol_t *, void *value), void *value); Function

Load the symbol table of ego. Return non-zero on error. If not null, symhook is called each time a new symbol is registered with value as its third parameter. (for internal use only: This is automatically called by ego_binary_init ()).


Node:Memory Objects

Memory Objects

The C language allows to dynamically allocate data using malloc () and friends. However, such data is untyped, i.e. the application has no way of knowing the type of the data pointed to by a pointer (and a pointer-to-char does not necessarily point to chars, just like a pointer-to-void does not point to void). C++ partially fills this gap with run-time type idenfication (RTTI) of instances of classes that contain virtual methods, but this technique doesn't give the user much information (the only thing you can do, almost, is compare whether to objects are of the same type).

In C, there is no such thing, so for dynamically allocated memory to be types, you need the application programmer to explicitly write this information (i.e. "such address points to data items of such type"). Moreover, it can be handy to have a universal way of getting information about data stored at a given address, whether it was dynamically allocated or not. This is what Ego's memory objects are about: a memory object (memory_object_t) is basically the meta-object representing a piece of data in memory and it contains information such as its type (see Type Information). In case a memory_object_t object represents a piece of static data, it is also possible to know which symbol (i.e. symbol_t object) contains this piece of data by looking at its symbol field.

Memory objects are created for each non-nested function and non-local variable when the ego_t object was initialized with ego_init () (see Basics). Note that data on the stack doesn't have memory objects associated to it. Each memory object has a unique object ID (type oid_t), so that any address can be converted to an simple ID plus an offset within the object represented by this ID. It is possible, using ego_memobj_find (), to get the memory object associated to a given pointer, and the offset within the object it represents. This feature uses a binary search tree (see Binary Search Trees).


Node:Memory Objects API, Next:, Up:Memory Objects

Memory Objects API

Here is the memory object API as defined in <ego/memobj.h>:

ego_error_t ego_memobj_lookup (ego_t *ego, oid_t id, memory_object_t **obj); Function

Lookup object with id id (a globally unique non-zero identifier) in ego. On success, zero is returned and *obj points to the requested object.

ego_error_t ego_memobj_find (ego_t *ego, const void *addr, memory_object_t **obj, size_t *offset); Function

Find memory object at address addr for ego. If addr points to a (dynamic) array or a structure, then *obj refers to the base of this array and *offset is set to the offset (in bytes) of the object pointed to by addr in this object. Zero is returned on success.

ego_error_t ego_memobj_new (ego_t *ego, ctype_t *ctype, void *addr, size_t size); Function

Register a new (dynamically allocated) array of size objects of type ctype starting at address addr in ego.

ego_error_t ego_memobj_delete (ego_t *ego, void *addr); Function

Delete the dynamic memory object associated to addr. Sub-memory objects (eg. struct fields, array elements) may not be individually deleted; however, if their parent (array or struct) is deleted, they will also get deleted.

ego_error_t ego_memobj_resize (ego_t *ego, void *addr, size_t size); Function

Resize the memory object associated to addr. size represents the number of contiguous elements of the same type pointed to by addr.

ego_error_t ego_memobj_move (ego_t *ego, void *addr, void *newaddr); Function

Notify ego that object previously located at addr has moved to newaddr (probably because of a realloc () or so). This updates the memory object for the dynamic object which was located at addr.

ego_error_t ego_memobj_register (ego_t *ego, ctype_t *ctype, void *addr, symbol_t *symbol, memory_object_t *obj); Function

Register memory object at address addr, of type ctype, related to symbol On success, obj is updated and added to the relevant hash tables and binary search trees for ego.

ego_error_t ego_memobj_unregister (ego_t *ego, memory_object_t *obj); Function

Unregister obj (which may be a child object) without actually freeing it. This is mostly used internally.

hash_key_t ego_hash_oid (const hash_table_t *table, const void *oid); Function

Hash functions for object ids (oid_t).

int ego_compare_oid (const void *oid1, const void *oid2); Function

Hash functions for object ids (oid_t).


Node:Convenience Macros, Previous:Memory Objects API, Up:Memory Objects

Convenience Macros

As explained before, dynamically allocated data is not typed. Therefore, for Ego to know what data has been allocated, what its address is, what its size is, and what its type is, the application has to tell Ego what it is doing. In terms of reflection, this is called reification: the base-level (the application) provides information about its activity to the meta-level (Ego).

The following table shows what standard C programs do when they want to allocate memory and how this should be done when using Pego/Ego:

Standard way The Ego way
     int *p;
     p = malloc (2 * sizeof (int));
     
     int *p;
     p = ego_memobj_alloc (&self, int, 2);
     

     char *p;
     p = calloc (3, sizeof (int));
     
     char *p;
     p = ego_memobj_alloc (&self, int, 3);
     

     char *p;
     p = strdup ("Hello");
     
     char *p;
     p = ego_memobj_strdup (&self, "Hello");
     

     struct stuff *p;
     p = realloc (p, 7 * sizeof (struct stuff));
     
     struct stuff *p;
     p = ego_memobj_realloc (&self, p, struct stuff, 7);
     

     free (p);
     
     ego_memobj_free (&self, p);
     

Note that the self parameter here is the ego_t object for the application (main meta-object). Therefore, it needs to be a global variable so that the above macros can be used in all the source files of the application.


Node:Stack Introspection

Stack Introspection

Ego offers several basic stack introspection facilities as well as facilities to associate a line number to a given address in the code (see ego_address_find () and ego_source_line_lookup () in <ego/symbols.h>, see Symbols). Keep in mind that getting the line number associated to a given address does not work all the time as GCC does not output information about line numbers for every single address. As a consequence, the stack-trace test (in the testsuite directory) may work on some systems and fail on others4.

Here is the (tiny) stack introspection API defined in <ego/stack.h>:

const stack_frame_t *ego_stack_get_current_frame (); Function

The frame layout on x86 and Powerpc

ego_error_t ego_stack_get_frame (const symbol_t * function, stack_frame_t ** frame); Function

Get the stack frame corresponding to the call of function and update *frame to point to it.

ego_error_tego_stack_get_variable (const stack_frame_t *frame, const symbol_t *variable, void **addr); Function

Tries to get local variable (or parameter) variable address and store it in *addr. If variable is not available in the current context (ie. the function that defines it is not in the stack trace), return ego_err_notavail. If variable is a register variable, return ego_err_register.


Node:Miscellaneous

Miscellaneous

This section contains information about the API of various utilities used within Ego, namely lists, hash tables and trees.


Node:Lists, Next:, Up:Miscellaneous

Lists

Thread-safe linked lists. File <ego/list.h> defines the list_t type which represents lists and list_item_t type which represents data item that may be inserted into a list_t. Data types that may need to be inserted into a list_t linked list must inherit from list_item_t as follows:

     
     typedef struct
     {
       /* Inherit from list_item_t */
       list_item_t listitem;
     
       /* Real and imaginary part of a complex number */
       float real;
       float imag;
     } listable_complex_t;
     
     

In this example, objects of type listable_complex_t may be inserted into lists just by casting them to list_item_t:

     
     list_t mylist;
     listable_complex_t foo;
     
     ego_list_init (&mylist);
     ego_list_add (&mylist, (list_item_t *)&foo);
     
     

Here is the complete API for linked lists:

void ego_list_init (list_t *list); Function

Initialize list.

void ego_list_add_head (list_t *list, list_item_t *item); Function

Add item to list's head.

void ego_list_add_tail (list_t *list, list_item_t *item); Function

Add item to list's tail.

int ego_list_remove (list_t *list, list_item_t *item); Function

Remove item from list. Returns non-zero if item is not part of list.

int ego_list_is_empty (const list_t *list); Function

Returns non-zero if list is empty.

list_item_t *ego_list_head (list_t *list); Function

Returns list's head or NULL if list is empty.

list_item_t *ego_list_tail (list_t *list); Function

Returns list's tail or NULL if list is empty.

size_t ego_list_item_number (const list_t *list); Function

Returns the number of items in list.

list_item_t *ego_list_traverse (list_t *list, list_item_t *start, int (*func) (list_item_t *, void *value), void *value); Function

Traverses list starting after start or at the beginning if start is zero. Stops whenever func returns zero. func is called on each list item with value as a second parameter. Returns the item on which func returned zero. This function is deletion-safe, ie. the item passed to func can safely be removed.


Node:Hash Tables, Next:, Previous:Lists, Up:Miscellaneous

Hash Tables

Hash tables in Ego use the list interface presented before. Hash tables are used in a number of key places in Ego: they are used for looking up symbols by names (e.g. ego_symbol_lookup ()), for looking up files (e.g. ego_include_file_lookup () and ego_source_file_lookup ()), or for looking up memory objects (e.g. ego_memobj_find ()).

The hash table API works using the same concept of inheritance as lists (see Lists): Data items that need to be inserted into a hash table should inherit from hash_item_t.

void ego_hash_init (hash_table_t *table, hash_bucket_t *buckets, size_t size, hash_key_t (* make_key) (const hash_table_t *, const void *), int (* compare) (const void *, const void *)); Function

Initialize hash table table using buckets which is size long as its bucket vector. make_key is the function that will be used to compute keys for this table. compare is a function that will be used to compare values and should return zero when the two given values are identical.

void ego_hash_add (hash_table_t *table, hash_item_t *item, const void *value); Function

Add item with value value into table.

int ego_hash_remove (hash_table_t *table, hash_item_t *item); Function

Remove item (previouly returned by hash_lookup ()) from table. Return non-zero if item isn't part of table.

hash_item_t *ego_hash_lookup (hash_table_t *table, const hash_item_t *start, const void *value); Function

Lookup object with value value in table. Returns the object found or NULL. If start is non-null, the lookup procedure will start after start; otherwise, value is searched for in the whole table.

hash_item_t *ego_hash_traverse (hash_table_t *table, hash_item_t *start, int (*func) (hash_item_t *, void *value), void *value); Function

Traverses table starting after start or at the beginning if start is zero. Stops whenever func returns zero. func is called on each list item with value as a second parameter. Returns the item on which func returned zero.

hash_key_t ego_hash_address (const hash_table_t *table, const void *address); Function

Simple hash function for addresses (pointers)

hash_key_t ego_hash_string (const hash_table_t *table, const void *string); Function

Hash function for strings

hash_key_t ego_hash_integer (const hash_table_t *table, const void *i); Function

Hash function for integers (int).

int ego_compare_integer (const void *i1, const void *i2); Function

Integer (int) comparison function.


Node:Trees, Next:, Previous:Hash Tables, Up:Miscellaneous

Trees

Symbols in Ego (i.e. symbol_t objects) are store in an hierarchical way using trees.

void ego_tree_init (tree_t *tree); Function

Initialize tree.

void ego_tree_add_child (tree_t *tree, tree_item_t *item); Function

Add item as a child of tree.

void ego_tree_add_child_tail (tree_t *tree, tree_item_t *item); Function

Add item to the tail of tree's list of children.

void ego_tree_add_child_tree (tree_t *tree, tree_t *item); Function

Add child, a previouly initialized tree, as a child of tree.

void ego_tree_add_child_tree_tail (tree_t *tree, tree_t *item); Function

Add child, a previouly initialized tree, to the tail of tree's list of children.

void ego_tree_remove (tree_t *tree, tree_item_t *item); Function

Remove item from tree.

int ego_tree_is_leaf (const tree_t *tree); Function

Returns non-zero if tree is a leaf.

tree_item_t *ego_tree_parent (const tree_item_t *item); Function

Returns the parent of item.

size_t ego_tree_children_number (const tree_t *tree); Function

Returns the number of children of tree.

tree_item_t *ego_tree_traverse (tree_t *tree, tree_item_t *start, int (*func) (tree_item_t *, void *value), void *value); Function

Traverses tree starting after start (a child of tree) or at the root of tree if start is zero. Stop whenever func returns zero. func is called on each tree item with value as a second parameter. Returns the item on which func returned zero. This function is deletion-safe, ie. the item passed to func can safely be removed (but not its children).

tree_item_t *ego_tree_traverse_children (tree_t * tree, tree_item_t * start, int (*func) (tree_item_t *, void *value), void *value); Function

Traverse the list of tree's children without going in depth. This function is deletion-safe, ie. the item passed to func can safely be removed.


Node:Binary Search Trees, Previous:Trees, Up:Miscellaneous

Binary Search Trees

Binary search trees (or "BSTs") are useful when there is a need for searching for something which may not match the exact given search key but may be the closest before of after the search key (in cases where there exist an "order relation" between keys, e.g. one can say whether a key is greater than another key).

These BST are used to associate data to addresses (i.e. pointers serve as search keys in the BST). Therefore it is possible, for instance, to search for the data associated to the closest pointer lower than or equal to the given pointer. This is what is used for searching for memory objects pointed to by a given pointer in ego_memobj_find () (see Memory Objects).

The API for BSTs is defined in <ego/bst.h>:

void ego_bst_init (bst_t *bst); Function

Initializes bst. bits is the size of the keys.

int ego_bst_add (bst_t *bst, const void *address, void *value); Function

Add value, whose key is address, to bst. On error, return enomem if memory could not be allocated, or eagain if there was already a value associated to address.

void *ego_bst_find (bst_t *bst, void *address); Function

Return the data associated to address in bst.

void *ego_bst_find_closest_before (bst_t *bst, const void *address); Function

Return the data associated to address in bst, or the closest item whose key is lower that address.

void ego_bst_remove (bst_t *bst, void *address); Function

Remove the data associated to address from bst.


Node:Index

Index


Footnotes

  1. Well, actually, it does nothing more than "objdump -g" *note (binutils)::*, or maybe even less, except that it makes this information available to the application programmer. However, the stabs parser that is used in Ego was written from scratch in order to fit its needs, but maybe this could have been avoided since GNU binutils have a clean interface for this (in binutils/debug.h)...

  2. However, as of the current release of Ego, loading of shared libraries has not been implemented yet.

  3. This release actually doesn't have much support for enumerates. For instance, it is not possible to know what value an enum defines.

  4. For this reason, the stack-related tests of the testsuite are not compiled and run by default.