Dico

6.2 Strategies

A search strategy is described by the following structure:

struct dico_strategy {
    char *name;          /* Strategy name */
    char *descr;         /* Strategy description */
    dico_select_t sel;   /* Selector function */
    void *closure;       /* Additional data for SEL */ 
    int is_default;      /* True, if this is a default strategy */
    dico_list_t stratcl; /* Strategy access control list */  
};

The first two members are mandatory and must be defined for each strategy:

member of struct dico_strategy: char * name

Short name of the strategy. It is used as second argument to the MATCH command (see MATCH) and is displayed in the first column of output by the SHOW STRAT command (see SHOW STRAT).

member of struct dico_strategy: char * descr

Strategy description. It is the string shown in the second column of SHOW STRAT output (see SHOW STRAT).

member of struct dico_strategy: dico_select_t sel

A selector function, which is used in iterative matches to select matching headwords. The sel function is called for each headword in the database with the headword and search key as its arguments and returns 1 if the headword matches the key and 0 otherwise. The dico_select_t type is defined as:

typedef int (*dico_select_t) (int, dico_key_t,
                              const char *);

See Selector, for a detailed description.

member of struct dico_strategy: void * closure

An opaque data pointer intended for use by the selector function.

member of struct dico_strategy: int is_default

This member is set to 1 by the server if this strategy is selected as the default one (see default strategy).

member of struct dico_strategy: dico_list_t stratcl

A control list associated with this strategy. See Strategies and Default Searches.

6.2.1 Search Key Structure

The dico_key_t is defined as a pointer to the structure dico_key:

struct dico_key {
    char *word;
    void *call_data;
    dico_strategy_t strat;
    int flags;
};

The structure represents a search key for matching algorithms. Its members are:

member of struct dico_key: char * word

The search word or expression.

member of struct dico_key: void * call_data

A pointer to selector-specific data. If necessary, it can be initialized by the selector when called with the ‘DICO_SELECT_BEGIN’ opcode and deallocated when called with the ‘DICO_SELECT_END’ opcode.

member of struct dico_key: dico_strategy_t strat

A pointer to the strategy structure.

member of struct dico_key: int flags

Key-specific flags. These are used by the server.

The following functions are defined to operate on search keys:

function: int dico_key_init (struct dico_key *key, dico_strategy_t strat, const char *word)

Initialize the key structure key with the given strategy strat and search word word. If strat has a selector function, it will be called with the ‘DICO_SELECT_BEGIN’ opcode (see DICO_SELECT_BEGIN) to carry out the necessary initializations.

The key itself may point to any kind of memory storage.

function: void dico_key_deinit (struct dico_key *key)

Deinitialize the dico_key structure initialized by a prior call to dico_key_init. If the key strategy has a selector, it will be called with the ‘DICO_SELECT_END’ opcode.

Note that this function makes no assumptions about the storage type of key. If it points to a dynamically allocated memory, it is the caller responsibility to free it.

function: int dico_key_match (struct dico_key *key, const char *word)

Match headword and key. Return 1 if they match, 0 if they don’t match and -1 in case of error. This function calls the strategy selector with the ‘DICO_SELECT_RUN’ opcode (see DICO_SELECT_RUN). It is an error if the strategy selector is not defined.

6.2.2 Strategy Selectors

Wherever possible, modules should implement strategies using effective look up algorithms. For example, ‘exact’ and ‘prefix’ strategies must normally be implemented using binary search in the database index. The ‘suffix’ strategy can also be implemented using binary search if a special reverse index is built for the database (this is the approach taken by outline and dictorg modules).

However, some strategies can only be implemented using a relatively expensive iteration over all keys in the database index. For example, ‘soundex’ and ‘levenshtein’ strategies cannot be implemented otherwise.

A strategy that can be used in iterative look ups must define a selector. Strategy selector is a function which is called for each database headword to determine whether it matches the search key.

It is defined as follows:

selector: int select (int opcode, dico_key_t key, const char *headword)

A strategy selector. Its arguments are:

opcode

The operation code. Its possible values are ‘DICO_SELECT_BEGIN’, ‘DICO_SELECT_RUN’ and ‘DICO_SELECT_END’, as described below.

key

The search key.

headword

The database headword.

The selector function is called before entering the iteration loop with ‘DICO_SELECT_BEGIN’ as its argument. If necessary, it can perform any additional initialization of the strategy, such as allocation of auxiliary data structures, etc. The call_data member of dico_key_t structure (see call_data) should be used to keep the pointer to the auxiliary data. The function should return 0 if it successfully finished its initialization and non-zero otherwise.

Once the iteration loop is finished, the selector will be called with ‘DICO_SELECT_END’ as its first argument. This invocation is intended to deallocate any auxiliary memory and release any additional resources allocated at the initialization state.

In these two additional invocations, the headword parameter will be ‘NULL’.

Once the iteration loop is entered, the selector function will be called for each headword. Its opcode parameter will be ‘DICO_SELECT_RUN’ and the headword parameter will point to the headword. The function should return 1 if the headword matches the key, 0 if it does not and a negative value in case of failure.

To illustrate the concept of strategy selector, let’s consider the implementation of the ‘soundex’ strategy in dicod. This strategy computes a four-character soundex code for both search key and the headword and returns 1 (match) if both codes coincide. To speed up the process, the code for the search key is computed only once, at the initialization stage, and stored in a temporary memory assigned to the key->call_data. This memory is reclaimed at the terminating call:

int
soundex_sel(int cmd, dico_key_t key, const char *dict_word)
{
    char dcode[DICO_SOUNDEX_SIZE];

    switch (cmd) {
    case DICO_SELECT_BEGIN:
        key->call_data = malloc(DICO_SOUNDEX_SIZE);
        if (!key->call_data)
            return 1;
        dico_soundex(key->word, key->call_data);
        break;

    case DICO_SELECT_RUN:
        dico_soundex(dict_word, dcode);
        return strcmp(dcode, key->call_data) == 0;

    case DICO_SELECT_END:
        free(key->call_data);
        break;
    }
    return 0;
}