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;
}