# Index Searches in C

> Search interfaces locate desired objects or groups of objects by unique identifier or by index. Exact match lookups by `unique` identifier (including `unique hash`, `oid` and `autoid` ) using the `_find()` functions are extremely efficient for locating individual objects. eXtremeDB also offers a rich set of specialized indexes that employ `cursors` to navigate a group of objects as an ordered result set with `tree`-based (including `patricia`, `rtree`, `kdtree` and trigram ), or an unordered sequence of objects with `nonunique hash` or `list` indexes.

> The C API also allows custom user-defined indexes.

> # Find

> Generated `_find()` functions search an index for an exact match. By definition, an exact match lookup on a unique index returns exactly one result or zero if no match is found. So for C applications, the `_find()` functions do not require a cursor; the function returns an object handle through the output parameter. These `_find()` functions are generated for classes that have one or more `unique hash` indexes or one or more `unique tree` indexes declared.

> Note that `oid` and `autoid` are by definition unique. So an internally managed unique `hash` index is implemented for them and only exact match `_find()` functions are appropriate for `oid` and `autoid` object lookups.

> For each unique index, an interface like the following is generated:

>         MCO_RET classname_index_name_find( /*IN*/ mco_trans_h trans,

>                                                                 /*IN*/ <type> [*]param1,

>                                                                 [/*IN*/ uint2 len1,]

>                                                                 [/*IN*/ <type> [*]param2,

>                                         [/*IN*/ uint2 len2,] …]

>                                                                 /*OUT*/ classname *handle);

> ### Exact Match Lookup Example

> To demonstrate an exact match lookup, consider the following database schema:

>         class Employee
>         {
>             string name;
>             uint2  dept_no;

>             unique tree<name> Iname;
>         };

> To lookup an Employee object by the `unique tree` index `Iname`, we could use code like the following:

>         Employee emp;

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if (MCO_S_OK == rc)
>         {
>             rc = Employee_Iname_find(t, search_name, (uint2)strlen(search_name), &emp);
>             if ( MCO_S_OK == rc)
>             {
>                 // Process Employee object
>             }
>             rc = mco_trans_commit(t);
>         }

> ## OID Index Lookups

> As explained in the Indexes and Cursors page, only "exact match" searches are possible for `oid` which are performed using the generated `_oid_find()` function. To demonstrate, consider the following schema:

>         declare database mydb;

>         // Define the OID struct
>         struct oid_struct
>         {
>             uint4 a;
>             int1  b;
>         };

>         declare oid oid_struct[OID_SIZE];

>         class anObject
>         {
>             uint4 value;

>             // Declare the OID index
>             oid;
>         };

> The following `_oid_find()` function would be generated:

>         MCO_RET      anObject_oid_find( mco_trans_h t, const mydb_oid *id, /*OUT*/ A *handle );

> The following code snippet demonstrates how the `_oid_find()` function could be used to perform an "exact match" search:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             anObject rec;
>             oid_struct findObj;
>             findObj.a = 1;
>             findObj.b = 99;

>             rc = anObject_oid_find(t, &findObj, &rec);
>             if ( MCO_S_OK == rc )
>             {
>                 // Process the found object
>             }
>             mco_trans_rollback(t);
>         }

> ## Autoid Index Lookups

> As explained in the Indexes and Cursors page, only "exact match" searches are possible for `autoid` indexes which are performed using the generated `_autoid_find()` function. To demonstrate, consider the following schema:

>         class Department
>         {
>             autoid[1000];
>             string name;

>             unique tree<name> Iname;
>         };

>         class Employee
>         {
>             string name;
>             autoid_t dept;

>             unique tree<name> Iname;
>         };

> Note that a one-to-many relationship between Department and Employee objects can be implemented through the reference field `dept` of type `autoid_t` in class Employee. The following `autoid_find()` function is generated for class Department:

>         MCO_RET      Department_autoid_find( mco_trans_h t, autoid_t autoid_key_,
>                                 /*OUT*/ Department *handle_);

> If each Employee object stores the `autoid` value of the Department object to which it belongs, the owner Department object could be quickly found with code like the following:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             rc = Employee_Iname_find(t, search_name, (uint2)strlen(search_name), &emp);
>             if (MCO_S_OK == rc)
>             {
>                 Employee_dept_get(&emp, &dept_id1);
>                 // Find the Department object by its autoid
>                 rc = Department_autoid_find(t, dept_id1, &dept1);

>                 if (MCO_S_OK == rc)
>                 {
>                     // Process Department object
>                 }
>             }
>             mco_trans_rollback(t);
>         }

> # Search

> A `cursor` is essentially an iterator over the collection of objects in a result set. For each index declared for a class in the schema definition, the DDL compiler generates functions to instantiate a cursor, position it based on some value(s), and obtain a handle to the database object from the cursor. `List`-based and non-unique `hash`-based cursors allow navigation in sequential order (first to last, or last to first), though the order of the sequence is not defined; it is simply a mechanism to iterate over the unordered list of objects of a class. A `list` or `nonunique hash` declaration in the schema file will cause the DDL compiler to generate a cursor `_search()` function.

> The `_search()` functions for `tree` indexes, are used whenever it is necessary to:

> - Establish a starting position in a sorted list with a known starting value and optionally retrieve subsequent results in ascending or descending sorted order.
> - Establish a starting position in a sorted list when only part of the starting value is known, find the closest match, and optionally retrieve subsequent results in ascending or descending sorted order.
> - Establish a starting position as above, iterate over the sorted list in ascending or descending sorted order until a lower or upper bound is reached, using the `_compare()` function to determine when the range limit is reached.

> The `_search()` functions for `nonunique hash` indexes (that allow duplicates) are used whenever it is necessary to:

> - Establish a starting position with a known starting value and iterate over the list to retrieve each duplicate, using the `_compare()` function to determine when the last duplicate was retrieved.

> The following two functions are generated to obtain a cursor for a `list` or a field with a declared index:

>         MCO_RET classname_list_cursor( /*IN*/  mco_trans_h t, /*OUT*/ mco_cursor_h c );

>         MCO_RET classname_indexname_index_cursor( /*IN*/  mco_trans_h t, /*OUT*/ mco_cursor_h c );

> Note that after calling one of the above functions the cursor must be properly positioned with a cursor search or positioning function (see the following section) to retrieve a valid database object handle.

> The `_search()` functions generated for all `tree` indexes are of the following form:

>         MCO_RET classname_indexname_search( /*IN*/ mco_trans_h trans,
>                             /*INOUT*/ mco_cursor_h cursor,
>                             /*IN*/ MCO_OPCODE op,
>                             /*IN*/ [const] <type> [*]param1,
>                             [[/*IN*/ uint2 len1,]
>                             [/*IN*/ [const] <type> [*]param2,
>                             [/*IN*/ uint2 len2,] …]);

> Here `MCO_OPCODE` represents a compare operation as defined in cursor operator codes.

> The `_search()` functions generated for all `nonunique hash` indexes are of the following form:

>         MCO_RET classname_indexname_search( /*IN*/ mco_trans_h trans,
>                             /*INOUT*/ mco_cursor_h cursor,
>                             /*IN*/ [const] <type> key);

> No `MCO_OPCODE` is required in this case because `hash` index searches are always for an exact match.

> ## Cursor Navigation

> After positioning a cursor with a `_search()` function or one of the cursor positioning functions (`mco_cursor_first()`, `mco_cursor_last()`, `mco_cursor_next()`, `mco_cursor_prev()`), the generated `_from_cursor()` function is used to obtain a handle to the object in order to then use object interface functions such as `_get()` or `_put()`:

>         MCO_RET classname_from_cursor( /*IN*/  mco_trans_h t,
>                             /*IN*/  mco_cursor_h c,
>                             /*OUT*/ classname *object);

> The `_locate()` function is used to position a `tree` index cursor based on an object reference. The cursor must have been previously instantiated using the `_index_cursor()` function. The `_locate()` function applies only to `tree`-based cursors (i.e. not to `list` or `hash` cursors):

>         MCO_RET classname_indexname_locate( /*IN*/    mco_trans_h t,
>                             /*INOUT*/ mco_cursor_h c,
>                             /*IN*/    classname * handle);

> An eXtremeDB `tree` index is a tree-like structure in the application’s memory that contains a collection of keys. A key can be simple (based on a single field) or compound (containing more than one field). The `tree` index stores the keys in sorted order. In order to support sorting, the `tree` index must have a compare function. Regardless of the key type (simple or compound), the compare function must be able to compare two keys and determine whether the first key is less than (compare returns -1), equal to (0) or greater than (1) the second key. The `tree` index algorithm sorts the keys based on this comparison.

> > Note: that the `tree` index algorithm sorts the keys based on their relative weight, determined from the compare function results, rather than on the key’s value.

> The `_compare()` function generated for each `tree` index has the following form:

>         MCO_RET	classname_indexname_compare( /*IN*/ mco_trans_h trans,
>                             /*IN*/ mco_cursor_h cursor,
>                             /*IN*/ [const] <type> [*]param1,
>                             [[/*IN*/ uint2 len1,]
>                             [/*IN*/ [const] <type> [*]param2,
>                             [/*IN*/ uint2 len2,] …],
>                             /*OUT*/ int *result);

> ## B-Tree Index Search

> The search algorithm page demonstrates how key weights determine the results of `tree` index searches and cursor navigation operations with two examples. To implement the first example in C, the `tree` index would be defined as a single `uint4` field, and the following compare function would be defined:

>         int compare_uint4( uint4 a, uint4 b)
>         {
>             if ( a == b ) return 0;
>             if ( a > b ) return 1;
>             return -1;
>         };

> For the second example, the key is represented as a structure containing two fields, `uint4` and `char[16]`:

>         typedef struct
>         {
>             uint4 f1;
>             char  f2[16];
>         } the_key;

> The compare function compares integers as in the above sample and the char buffers as ASCII characters:

>         int compare_compound_key ( the_key a, the_key b )
>         {
>             int i;

>             if ( a.f1 < b.f1 ) return -1;
>             if ( a.f2 > b.f2 ) return 1;

>             for ( i=0; i<sizeof(the_key.f2); i++ )
>             {
>                 if ( a.f2[i] < b.f[2] ) return -1;
>                 if ( a.f2[i] > b.f[2] ) return 1;
>             }

>             return 0;
>         };

> Please refer to the search algorithm page to see how the cursor position is determined after calling a `_search()` function, and what would be the results of calling `mco_cursor_prev()` and `mco_cursor_next()` with each of the possible cursor operation codes.

> ### B-Tree search example.

> To demonstrate a common `tree` index search scenario, consider the following database schema:

>         class anObject
>         {
>             uint4 value;

>             tree <value> Idx; // Equivalent to "nonunique tree<value> Idx;"
>         };

> Note that the `tree` declaration without the explicit `unique` qualifier defaults to `nonunique`; i.e. allow duplicates. To perform a search on index `Idx`, we could use code like the following:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             rc = anObject_Idx_index_cursor(t, &csr);
>             if ( MCO_S_OK == rc )
>             {
>                 printf("\nObjects with value == %d : ", search_value);
>                 for (rc = anObject_Idx_search(t, &csr, MCO_EQ, search_value);
>                         MCO_S_OK == rc; rc = mco_cursor_next(t, &csr))
>                 {
>                     int result = 0;
>                     /* Use _compare() to stop before the object with non-equal value */
>                     anObject_Idx_compare(t, &csr, search_value, &result);
>                     if (result) break;

>                     anObject_from_cursor(t, &csr, &obj);
>                     anObject_value_get(&obj, &value);
>                     printf("(%d) ", value);
>                 }
>             }
>             mco_trans_rollback(t);
>         }

> Note that when it returns `MCO_S_OK` the generated `_search()` function positions the `cursor` at the first index value matching the specified key (`search_value`). After processing the first found object, `mco_cursor_next()` is called to advance the cursor. Within the processing loop, the generated `_compare()` function is called to assure that the index value of the current object is still equal to the specified key (`search_value`). When the compare function returns a non-zero value we exit the processing loop.

> ### A common search and delete mistake

> Sometimes, C applications need to obtain a `cursor` to traverse through a class and delete some of the objects in the process. The `cursor` contains a reference to the current object. Therefore, if the current object is deleted, the `cursor` is unable to move and the database runtime returns a `MCO_E_CURSOR_INVALID` error code. To remove an object within a `cursor`, the application needs to first move the `cursor` and, after the `cursor` no longer points to the target object, delete the object. Note that this is true regardless of the type of index to which this `cursor` corresponds. The following pseudo-code illustrates this technique:

>         rc = open_cursor(cursor);
>         while (rc == MCO_S_OK && (rc = from_cursor(cursor,obj)) == MCO_S_OK)
>         {
>             rc = move_cursor(cursor);
>             delete_obj(obj);
>         }

> ## Pattern Search

> As described in the Searches page, eXtremeDB supports wildcard pattern matching. To illustrate the use of the generated pattern search functions, consider the following class definition:

>         class PatternTest
>         {
>             string      key1;
>             char<20>    key2;
>             int4        key3;

>             tree <key1,key2,key3> i1;
>             tree <key2,key3> i2;
>         };

> The schema compiler will generate the following functions for index `i1`:

>         MCO_RET  PatternTest_i1_pattern_size( const    char *key1, uint2 sizeof_key1, const    char *key2,
>                                 uint2 sizeof_key2, int4  key3 /*OUT*/ uint4 *pattern_size);

>         MCO_RET  PatternTest_i1_pattern_search( mco_trans_h t, void        *allocated_pattern, uint4        memsize,
>                                 PatternTest *obj, const char  *key1, uint2        sizeof_key1,
>                                 const char  *key2, uint2        sizeof_key2, int4         key3 );

>         MCO_RET  PatternTest_i1_pattern_next( mco_trans_h  t, void        *allocated_pattern, PatternTest *obj);

> To use `i1` to perform a pattern search, requires the following steps:

> First, allocate a buffer that the eXtremeDB run-time uses as a state machine during the pattern search. The size of the buffer required is determined by `<classname>_pattern_size()`, for example:

>         char *key1 = "Gr?ve*";
>         char *key2 = S"*";
>         uint4 key3 = 46;
>         void *buf;
>         uint4 bsize;
>         PatternTest pat;

>         PatternTest_i1_pattern_size(key1, strlen(key1), key2, strlen(key2), key3, &bsize);
>         buf = malloc(bsize);

> Now a loop to retrieve the index entries that match the specified pattern could be coded as follows:

>         for( rc = PatternTest_i1_pattern_search( transaction, buf, bsize, &pat, key1,
>                                 strlen(key1), key2, strlen(key2), key3 );

>             rc == MCO_S_OK ;
>             rc = PatternTest_i1_pattern_next(transaction, buf, &pat)
>         {
>             ...
>         }
>         free(buf);

> ### Pattern Search Policy

> Pattern search is controlled by information the runtime obtains from a `mco_pattern_policy_t` structure that can be customized by the application. The following functions use the pattern policy structure to get and set the pattern matching policy:

>         typedef struct mco_pattern_policy_t_
>         {
>             char ignore_other_fields; // default = MCO_NO
>             char any_char;            // default = ‘*’
>             char one_char;            // default = ‘?’
>             nchar_t any_nchar;        // default = 0x002a
>             nchar_t one_nchar;        // default = 0x003f
>             #ifdef MCO_CFG_WCHAR_SUPPORT
>                 wchar_t any_wchar;        // default = (wchar_t)0x002a
>                 wchar_t one_wchar;        // default = (wchar_t)0x003f
>             #endif
>         };

>         void mco_get_default_pattern_policy(mco_pattern_policy_t * p);
>         MCO_RET mco_get_pattern_policy(mco_trans_h t, mco_pattern_policy_t *p);
>         MCO_RET mco_set_pattern_policy(mco_trans_h t, const mco_pattern_policy_t *p);

> The `ignore_other_fields` element controls whether non-character fields that participate in an index are considered during the pattern matching or not. In the example at the beginning of this section, an index consisting of two character fields and a 4-byte integer field was defined. By setting `ignore_other_fields = MCO_YES` this index can be used to match patterns on the two character fields without regard to the value of the integer field.

> The following code snippet demonstrates how the pattern matching policy might be changed:

>         mco_pattern_policy_t p;
>         /*
>         * NOTE: The change policy operation must be executed within a Read_Write
>         * transaction.
>         */
>         mco_get_pattern_policy(trn, &p);
>         p.ignore_other_fields = MCO_YES;
>         mco_set_pattern_policy(trn, &p);

> ## Patricia Index Search

> As explained in the Indexes and Cursors page, the `patricia` index can be declared only on single fields (not multiple fields) and can be `unique`; in the absence of the `unique` keyword it defaults to allowing duplicates.

> Searches on `patricia` indexes are performed using the generated functions `_longest_match(), _exact_match(), _prefix_match()` and `_next_match()`.

> Please refer to the Patricia Index page for explanations and examples of how these `patricia`-specific search operations work. To demonstrate use of the `patricia` C APIs, two SDK samples are provided: 05-Indexes_Patricia_Character and 05-Indexes_Patricia_Binary. Code snippets from the second sample are used below to illustrate the different types of `patricia` index searches.

> Consider the class AreaCode with a bit array and string fields like the following:

>         class AreaCode
>         {
>             vector<boolean> areaCode;
>             char<4> strAreaCode

>             patricia<areaCode> IareaCode;
>         };

> ### Sequential search

> To sequentially list the contents of the database using the `patricia` index `IareaCode`, we could use code like the following:

>         rc = mco_trans_start(db, MCO_READ_WRITE, MCO_TRANS_FOREGROUND, &trn);
>         if ( MCO_S_OK == rc )
>         {
>             /* initialize cursor */
>             rc = AreaCodeBool_IareaCode_index_cursor(trn, &csr);
>             if ( MCO_S_OK == rc )
>             {
>                 for (rc = mco_cursor_first(trn, &csr); MCO_S_OK == rc;
>                     rc = mco_cursor_next(trn, &csr))
>                 {
>                     rc = AreaCodeBool_from_cursor(trn, &csr, &areaCode);
>                     prnObject(&areaCode);
>                 }
>             }
>             rc = mco_trans_commit(trn);
>         }

> Note that here the `_search()` function is not needed as the cursor is simply positioned using `mco_cursor_first()` and the sequential navigation of database objects is performed by calling function `mco_cursor_next()`.

> In the search examples that follow, the generated `_next_match()` function will be used to advance the `cursor` position which assures that the next object in the result set still matches the given key value (`AreaCode`).

> Note that the cursor functions `mco_cursor_next()` or `mco_cursor_prev()`could be used, instead of the `patricia`-specific function `_next_match()`, to traverse result sets. But this would require calling the `cursor` compare function to determine if the index still matches the key.

> In the following code snippets, the functions `calcBitLen()`and `make_mask()` work in combination to calculate the size of the bit array and the hex value for a given `AreaCode`; and `prnObject()` simply displays the `AreaCode` and `strAreaCode` values for the current object. (Please see SDK sample 05-Indexes_Patricia_Binary for implementation details.)

> ### Exact Match search

> To perform an "exact match" search, we could use code like the following:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &trn);
>         if ( MCO_S_OK == rc )
>         {
>             rc = AreaCodeBool_IareaCode_index_cursor(trn, &csr);
>             sz = calcBitLen(AreaCode);
>             rc = AreaCodeBool_IareaCode_exact_match(trn, &csr, (char*)make_mask(AreaCode, sz), sz);
>             if ( MCO_S_OK == rc )
>             {
>                 printf("\tFound ExactMatch for key %x:\n", AreaCode);
>                 while ( MCO_S_OK == rc )
>                 {
>                     rc = AreaCodeBool_from_cursor(trn, &csr, &areaCode);
>                     prnObject(&areaCode);
>                     rc = AreaCodeBool_IareaCode_next_match(trn, &csr, (char*)make_mask(AreaCode, sz), sz);
>                 }
>             }
>             else
>             {
>                 printf("\tExactMatch not found for key %x:\n", AreaCode);
>             }
>             rc = mco_trans_commit(trn);
>         }

> ### Prefix Match Search

> To perform a "prefix match" search, we could use code like the following:

>         mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &trn);
>         if ( MCO_S_OK == rc )
>         {
>             rc = AreaCodeBool_IareaCode_index_cursor(trn, &csr);
>             sz = calcBitLen(AreaCodePref);
>             rc = AreaCodeBool_IareaCode_prefix_match(trn, &csr, (char*)make_mask(key, sz), sz);
>             if ( MCO_S_OK == rc )
>             {
>                 int found = 0;
>                 while ( MCO_S_OK == rc )
>                 {
>                     if (!found)
>                     {
>                         printf("\tFound PrefixMatch for key %x:\n", AreaCodePref);
>                     }
>                     found = 1;
>                     rc = AreaCodeBool_from_cursor(trn, &csr, &areaCode);
>                     prnObject(&areaCode);
>                     rc = AreaCodeBool_IareaCode_next_match(trn, &csr, (char*)make_mask(key, sz), sz);
>                 }
>                 if (!found)
>                 {
>                     printf("\tPrefixMatch not found for key %x:\n", AreaCodePref);
>                 }
>             }
>             else
>             {
>                 printf("\tPrefixMatch not found for key %x:\n", AreaCodePref);
>             }
>             rc = mco_trans_commit(trn);
>         }

> ### Longest Match Search

> To perform a "longest match" search, we could use code like the following:

>         mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &trn);
>         if ( MCO_S_OK == rc )
>         {
>             rc = AreaCodeBool_IareaCode_index_cursor(trn, &csr);
>             sz = calcBitLen(AreaCodePref);
>             rc = AreaCodeBool_IareaCode_longest_match(trn, &csr, (char*)make_mask(key, sz), sz);
>             if ( MCO_S_OK == rc )
>             {
>                 int found = 0;
>                 while ( MCO_S_OK == rc )
>                 {
>                     if (!found)
>                     {
>                         printf("\tFound LongestMatch for key %x:\n", AreaCodePref);
>                     }
>                     found = 1;

>                     rc = AreaCodeBool_from_cursor(trn, &csr, &areaCode);
>                     prnObject(&areaCode);
>                     rc = AreaCodeBool_IareaCode_next_match(trn, &csr, (char*)make_mask(key, sz), sz);
>                 }
>                 if (!found)
>                 {
>                     printf("\tLongestMatch not found for key %x:\n", AreaCodePref);
>                 }
>             }
>             else
>             {
>                 printf("\tLongestMatch not found for key %x:\n", AreaCodePref);
>             }
>             rc = mco_trans_commit(trn);
>         }

> ## R-Tree Index Search

> As explained in the Indexes and Cursors page, the `rtree` is commonly used to speed spatial searches. Searches on `rtree` indexes are performed using the generated `_search()` function with one of the four `MCO_OPCODES`: `MCO_EQUAL, MCO_OVERLAP, MCO_CONTAIN` or `MCO_NEIGHBORHOOD`.

> Please refer to the RTree Index page for explanations and examples of how these `rtree`-specific search operations work. To demonstrate use of the `rtree` C APIs, the SDK sample 05-Indexes_rtree is provided. Code snippets from this sample are used below to illustrate the different types of `rtree` index searches.

> Consider the class rtrree_class with a definition like the following:

>         class rtree_class
>         {
>             int2 	square[4];

>             rtree <square>  ridx;
>         };

> ### Sequential search

> To sequentially list the contents of the `cursor` using the `rtree` index `ridx`, we could use code like the following:

>         int iterate_rects(mco_trans_h t, mco_cursor_t *c, mco_bool reverse_order)
>         {
>             MCO_RET rc;
>             int i;
>             rtree_class obj;
>             int2 square[4];

>             rc = (reverse_order == MCO_NO) ? mco_cursor_first(t, c) : mco_cursor_last(t, c);
>             for (i = 0; MCO_S_OK == rc; i++)
>             {
>                 rc = rtree_class_from_cursor(t, c, &obj);
>                 rc = rtree_class_square_get_range(&obj, 0, 4, (int2*)square);
>                 printf("\t%d. (%d,%d) - (%d,%d)\n", i + 1, square[0], square[1], square[2], square[3]);
>                 rc = (reverse_order == MCO_NO) ? mco_cursor_next(t, c) : mco_cursor_prev(t, c);
>             }
>             return i;
>         }

> Note that here the `_search()` function is not needed as the cursor is simply positioned using `mco_cursor_first()` or `mco_cursor_last()` depending on the value of flag `reverse_order` and the sequential navigation of database objects is performed by calling function `mco_cursor_next()` or `mco_cursor_prev()`.

> ### Exact Match search

> To perform an "exact match" search, we use opcode `MCO_EQ` with code like the following:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             mco_cursor_t c;
>             int2 rect[4] = { 25, 25, 50, 35 };

>             rc = rtree_class_ridx_index_cursor(t, &c);
>             rc = rtree_class_ridx_search(t, MCO_EQ, &c, (int2*)rect);
>             if ( MCO_S_OK == rc )
>             {
>                 // Process the found rect
>             }
>             rc = mco_trans_commit(t);
>         }

> ### Overlaps Search

> To find rectangles that overlap the specified `rect` and iterate them, we use opcode `MCO_OVERLAP` with code like the following:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             mco_cursor_t c;
>             int2 rect[4] = { 25, 25, 50, 35 };

>             rc = rtree_class_ridx_index_cursor(t, &c);
>             rc = rtree_class_ridx_search(t, MCO_OVERLAP, &c, (int2*)rect);
>             if ( MCO_S_OK == rc )
>             {
>                 iterate_rects(t, &c, MCO_NO);
>             }
>             rc = mco_trans_commit(t);
>         }

> (Note that the function `iterate_rects()` which sequentially lists the contents of the `cursor` is shown above.)

> ### Contains Search

> To find rectangles that contain the specified `rect` and iterate them, we use opcode `MCO_CONTAIN` with code like the following:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             mco_cursor_t c;
>             int2 rect[4] = { 25, 25, 50, 35 };

>             rc = rtree_class_ridx_index_cursor(t, &c);
>             rc = rtree_class_ridx_search(t, MCO_CONTAIN, &c, (int2*)rect);
>             if ( MCO_S_OK == rc )
>             {
>                 iterate_rects(t, &c, MCO_NO);
>             }
>             rc = mco_trans_commit(t);
>         }

> (Note that the function `iterate_rects()` which sequentially lists the contents of the `cursor` is shown above.)

> ### Neighborhood Search

> To list all rectangles in order of their distance from a specified point (a rectangle with 0 height and width), we use opcode `MCO_NEIGHBOURHOOD` with code like the following:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             mco_cursor_t c;
>             int2 point[4] = { 10, 10, 10, 10 };

>             rc = rtree_class_ridx_index_cursor(t, &c);
>             rc = rtree_class_ridx_search(t, MCO_NEIGHBOURHOOD, &c, (int2*)point);
>             if ( MCO_S_OK == rc )
>             {
>                 iterate_rects(t, &c, MCO_NO);
>             }
>             rc = mco_trans_commit(t);
>         }

> (Note that the function `iterate_rects()`, which sequentially lists the contents of the `cursor`, is shown above. )

> ## KD-Tree Index Search

> As explained in the Indexes and Cursors page, `kdtree` indexes are ideal for multi-dimensional key value searches. Searches on `kdtree` indexes are performed using the generated `_search()` function using a Query-By-Example approach to locate objects that match a given search condition.

> Please refer to the KDTree Index page for explanations and examples of how this `kdtree`-specific search works. To demonstrate use of the `kdtree` C APIs, the SDK sample 05-Indexes_kdtree is provided. Code snippets from this sample are used below to illustrate Query-By-Example searches.

> Consider the database schema presented in the KDTree Index page:

>         class Car
>         {
>             string vendor;
>             string model;
>             string color;
>             uint4 year;
>             uint4 mileage;
>             boolean automatic;
>             boolean ac;
>             uint4 price;
>             char<3> state;
>             string description;

>             kdtree <year, mileage, color, model, vendor, automatic, ac, price> index;
>         };

> To perform a Query-By-Example search, we temporarily insert a single "pattern object" if an exact match search, or two boundary "pattern objects" `from` and `till` to specify a range. Then we call the generated `_search()` function and use the cursor functions `mco_cursor_next()` or `mco_cursor_prev()` to advance through the result set. For example:

>         /* Use read-write transaction to store boundary patterns in the database */
>         rc = mco_trans_start(db, MCO_READ_WRITE, MCO_TRANS_FOREGROUND, &t);
>         if (rc == MCO_S_OK)
>         {
>             Car_new(t, &from); /* Create low boundary pattern object */
>             Car_new(t, &to);   /* Create high boundary pattern object */
>             Car_vendor_put(&from, "Ford", 4); Car_vendor_put(&to, "Ford", 4);
>             Car_price_put(&to, 30000);
>             Car_year_put(&from, 2000); Car_year_put(&to, 2006);
>             Car_mileage_put(&to, 100000);
>             printf("\n\n\tRange results for:");
>             print_car("\t(from", &from );
>             print_car("\t(to", &to );
>             printf("\n");

>             Car_index_index_cursor(t, &cursor);
>             rc = Car_index_search(t, &cursor, &from, &to);
>             for ( i=1; MCO_S_OK == rc; i++ )
>             {
>                 Car choice;
>                 Car_from_cursor(t, &cursor, &choice);
>                 sprintf( str, "%d", i );
>                 print_car( str, &choice);
>                 rc = mco_cursor_next(t, &cursor);
>             }
>             Car_delete(&from); /* Delete pattern */
>             Car_delete(&to); /* Delete pattern */
>             mco_trans_commit(t);
>         }

> ## Trigram Index Search

> As explained in the Indexes and Cursors page, `trigram` indexes are ideal for text searches when the exact spelling of the target object is not precisely known.

> ## Hash Index Searches

> As explained in the Indexes and Cursors page, `hash` indexes are generally used for efficient object lookups. Also, as explained in the Find section above, a `nonunique hash` declaration in the schema file will cause the DDL compiler to generate a cursor `_search()` function which allows navigation in sequential order (first to last, or last to first) over the unordered list of objects of a class. To demonstrate use of the `hash` C APIs, the SDK sample 05-Indexes_hash is provided. Code snippets from this sample are used below to illustrate a `nonunique hash` search.

> Consider the database schema presented in the Indexes and Cursors page:

>         class Record
>         {
>             uint4  iIdx;                  /* Index      */
>             uint4  iSeries;							  /* Series of measurement */

>             hash <iIdx>  I_Index[10000];
>             nonunique hash <iSeries> I_Series[10000];
>         };

> The following code snippet demonstrates how to use a non-unique `hash` index to search for all objects having a specified `hash` table value:

>         /* Show all records with specified value in non-unique index */
>         printf("\n\n\tSearch for records with iSeries == %d :", findValue);

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             /* Open the cursor */
>             rc = Record_I_Series_index_cursor(t, &csr);
>             if ( MCO_S_OK ==  rc )
>             {
>                 /* Search for records with specified value for iSeries */
>                 rc = Record_I_Series_search(t, &csr, findValue);
>                 if ( MCO_S_OK ==  rc )
>                 {
>                     Record rec;
>                     /* Move to first item */
>                     rc = mco_cursor_first(t, &csr);
>                     /* Show all records in cursor */
>                     for (i = 0; i < nRecs && MCO_S_OK == rc; i++)  {
>                     /* Get Record from cursor */
>                     Record_from_cursor(t, &csr, &rec);
>                     Record_iIdx_get(&rec, &idx);
>                     Record_iSeries_get(&rec, &series);
>                     printf("\n\tIndex %d Series %d", idx, series);
>                     /* Move to next item */
>                     rc = mco_cursor_next(t, &csr);
>                 }
>             }
>             /*  Close the transaction */
>             mco_trans_rollback(t);
>         }

> ## List Index Searches

> As explained in the Find section above, a `list` declaration in the schema file will cause the creation of an internal `hash` index which allows navigation in sequential order (first to last, or last to first) over the unordered list of objects of a class.

> To demonstrate, consider the following schema:

>         class anObject
>         {
>             uint4 value;

>             list;
>         };

> For this class a `_cursor()` function is generated like the following:

>         MCO_RET anObject_list_cursor( mco_trans_h t, /*OUT*/ mco_cursor_h c );

> The following code snippet could be used to scroll through the objects of this class:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if ( MCO_S_OK == rc )
>         {
>             rc = anObject_list_cursor(t, &csr);
>             if ( MCO_S_OK == rc )
>             {
>                 printf("All objects             : ");
>                 for (rc = mco_cursor_first(t, &csr);
>                     rc == MCO_S_OK;
>                     rc = mco_cursor_next(t, &csr))
>                 {
>                     anObject_from_cursor(t, &csr, &obj);
>                     anObject_value_get(&obj, &value);
>                     printf("(%d) ", value);
>                 }
>             }
>             mco_trans_rollback(t);
>         }

> ## User Defined Index Searches

> As explained in the Indexes and Cursors page, C applications can declare a `hash` or `tree` index `userdef` and define custom compare functions for them. For `userdef hash` indexes, only a `_find()` function is generated. So only exact match searches are appropriate. But for `userdef tree` indexes, both exact match and index searches can be implemented which will use the custom compare functions defined by the developer.

> Before the user-defined index functions can be used, the application must register the custom compare and hash functions with the database runtime. This is done via the `mco_db_register_udf()` API:

>         MCO_RET mco_db_register_udf( const char * db_name, mco_userdef_funcs_h udfs );

> The second argument `udfs` is a pointer to the custom functions table obtained via the generated `dbname_get_udfs()` function. The `mco_db_register_udf()` must be called after `mco_runtime_start()` and before the call to `mco_db_connect()` that creates a connection to the database. For example:

>         mco_runtime_start();

>         mco_db_open("MyDB", mydb_get_dictionary(), start_mem, DBSIZE, PAGESIZE);

>         mco_db_register_udf("MyDB", mydb_get_udfs());

>         mco_db_connect("MyDB", &db);
>         ...<continue processing>...

> If user-defined indexes are declared for the database, but custom functions are not registered via the `mco_db_register_udf()`, the call to `mco_db_connect()` will return the `MCO_E_NOUSERDEF_FUNCS` return code.

> Now search operations can be performed using the user-defined index in the same manner as a normal `tree` index. For example:

>         rc = mco_trans_start(db, MCO_READ_ONLY, MCO_TRANS_FOREGROUND, &t);
>         if (rc == MCO_S_OK)
>         {
>             /* Using userdef tree index */
>             rc = Record_tudf_index_cursor(t, &c);
>             if (rc == MCO_S_OK) {
>             for (rc = mco_cursor_first(t, &c);
>                 rc == MCO_S_OK;
>                 rc = mco_cursor_next(t, &c))
>             {
>                 Record_from_cursor(t, &c, &rec);
>                 Record_name_get(&rec, buf, 11, &len);
>                 Record_value_get(&rec, &value);
>                 printf("\n\t%-15s, value = %d", buf, value);
>             }
>             rc = mco_trans_commit(t);
>         }