User Index in BTREE.EXTRACT

BTREE.EXTRACT is a routine that searches a Btree index and returns a list of keys (not to exceed 64K in total length). In addition to the functionality documented in the Developer's Series System Subroutines book, BTREE.EXTRACT supports a developer "hook" or "user index".

The user index allows developers to specify their own algorithm to search indexes without having to deal with the details of the Btree structure. This technical bulletin discusses how to use this feature.

The BTREE.EXTRACT user index is divided into two parts: a parsing module and a compare module. The parsing module is a pre-process to BTREE.EXTRACT that determines if the search value should cause BTREE.EXTRACT to call a custom comparison module. The compare module is a replace-process module that is called as an alternative to the comparison logic normally done by BTREE.EXTRACT.

Figure 1 is a simple illustration of the flow of control for the user index in BTREE.EXTRACT.

BTREE.EXTRACT always looks for a user index by attempting to read a record in the VOC file named %USER.INDEX%. The first field of this record must be the literal text USER.INDEX. The second field is the name of the developer-written parsing module. This may be a cataloged routine or a routine placed into the VERBS file. The third field is optional and is the default compare module (otherwise specified in the parsing module).

For example, the following describes a sample layout for the SYSPTRS record %USER.INDEX%:

The parsing module is called to examine the data entered by a user for an index search. The parsing module has an opportunity to examine the search data before BTREE.EXTRACT uses it to begin a search. As a result, the parsing module can modify the search data, and can, in addition, set a flag to tell BTREE.EXTRACT to call a custom compare module.

The parsing module is called with these parameters:

PARSER( SEARCH_FOR, START_VALUE, USER_INDEX_FLAG, COMPARE_MOD )

The first parameter is the search value as passed to the BTREE.EXTRACT routine. It can contain special characters or patterns to trigger the use of a developer compare module. If a custom compare module is called later in the BTREE.EXTRACT process, the value of this variable as set by the parsing routine will be passed to the compare module to determine an index value hit or miss.

If multiple search criteria are passed to BTREE.EXTRACT, BTREE.EXTRACT will parse and pass each one to the parsing module one at a time. BTREE.EXTRACT will still handle all AND and OR logic for multiple search criteria.

The parsing module can use the START_VALUE parameter to pass a value to BTREE.EXTRACT indicating the point in the index at which to start examining index values. If a null is returned (the default), the search will begin at one end or the other of the Btree index, depending on the direction of the search. If a specific value is passed, BTREE.EXTRACT begins from the point in the index where that value would be found.

The value of the user index flag determines whether the developer compare module will be called to examine the search value. The flag can have these values:

The COMPARE_MOD argument contains the name of the compare module to be called by BTREE.EXTRACT, if any. If a null is returned (the default), the compare module defaults to that specified in field 3 of the %USER.INDEX% record in the VOC file.

If the user index flag is 1 or 2, but no comparison module is specified in either the VOC record or in the COMPARE_MOD parameter, a null load error will occur when BTREE.EXTRACT is called.

The compare module contains custom logic to compare the search data against values in the Btree index. Based on its own comparison logic, the compare module determines whether the search data matches values in the index. BTREE.EXTRACT calls the compare module for each value in the Btree index, starting as designated in START_VALUE.

The compare module is called with these parameters:

COMPARE( CANDIDATE, SEARCH_FOR, FLAG )

This is the value extracted from the Btree index by BTREE.EXTRACT. The candidate value is passed to the compare module and used to compare against the search data. No return value is necessary.

This is the data value that the user has entered to search the index. It is the same data value as that returned by the parsing module. The SEARCH_FOR value is compared against the candidate by the custom compare routine. No return value is necessary.

If this parameter is true (1) upon entry, the candidate is the last value in the current leaf node and no hits have been found in the current leaf node (it is otherwise 0). One of the following return values must be set:

In addition to the arguments, the labeled COMMON area USERIX is available to the parsing and compare routines. There are two labeled common variables to provide additional information about the indexed values. The labeled block is defined as follows:

COMMON /USERIX/ UIX.SM.FLAG, UIX.DCONV

The variable UIX.SM.FLAG is a boolean value, true if the field is left-justified (alpha) sorted and false if the field is right-justified (numeric) sorted. The variable UIX.DCONV contains the output conversion to be applied to the value to change it to its external representation (data is stored in the index in its internal representation).

One potential application for the user index in BTREE.EXTRACT is to allow multiple ways to use the data in a single index. This can save the time and space of creating several slightly different indexes. For example, one can use a developer compare routine as a numeric/alpha test instead of creating a symbolic field, or have a keyword that can be used to search the Btree index for a null value (not supported normally by BTREE.EXTRACT).

Figures 2, 3, and 4 provide an example of using the user index to do a Soundex lookup. Figure 2 is the listing for a parsing routine, Figure 3 the listing for a compare routine, and Figure 4 a listing for a Soundex subroutine.

In the example, a user indicates a Soundex index lookup by prefixing '$' to the search value. The character '$' is the trigger value that tells the parsing routine that a Soundex lookup is desired. For example, if '$AKME' is entered in the Shared Cross Reference window, BTREE.EXTRACT will call the compare module to match the Soundex lookup value with Soundex versions of the data in the index. Keys with index values such as ACME, ACM and AKME would be returned.

                             |---------|
                      ---    |Pre-Parse|
                      |Y|----|Routine? |
                       |     -----+-----
                   |---+--|      -|-
                   |Custom|      |N|
                   |Parser|      ---
                   ----|---       |
                       |---->-----|
                                  |
                            ------+------
                            | Extract   |
               |-------->---|Btree Value|
               |            ------|------
               |              |---|----|
               |         ---  |Replace |  ---
               |      |<-|Y|--|Compare?|--|N|->|
               |      |  ---  ----------  ---  |
               |  ----|----                ----+----
               |  |Custom |                | Btree |
               |  |Compare|                |Compare|
               |  ----|----                ----+----
               |      |                        |
               |      |----->-----|----<-------|
               |                  |
               |          ---  ---+----
               |-------<--|N|--| Done?|
                          ---  ---+----
                                  |
                                 -+-
                                 |Y|
                                 -+-
                                  |
                              ----+----
                              | Return |
                              |Hit List|
                               --------

SUBROUTINE PARSER(SEARCH_FOR, START_VALUE, USER_INDEX_FLAG, COMPARE_MOD)
*
* user index parser routine to intercept Soundex lookups
* (search for value starting with '$')
*
DECLARE SUBROUTINE SOUNDEX ;* a developer routine w/ Soundex algorithm

EQU TRUE$        TO 1
EQU TRIGGER$     TO '$'
EQU COMPARE_MOD$ TO 'COMPARE'

* the following examines the index lookup value and determines whether
* it is a Soundex lookup. If not, the search value is passed through
* to BTREE.EXTRACT as normal.

IF SEARCH_FOR[1,1] = TRIGGER THEN
  SEARCH_FOR[1,1]  = ''               ;* delete the trigger character
  SOUNDEX(SEARCH_FOR)                 ;* convert to Soundex value
  USER_INDEX_FLAG  = TRUE$            ;* use ascending developer compare
  START_VALUE      = SEARCH_FOR[1,1]  ;* start searching at first letter
  COMPARE_MOD      = COMPARE_MOD$     ;* specify compare module
END
RETURN

SUBROUTINE COMPARE(CANDIDATE, SEARCH_FOR, FLAG)

DECLARE SUBROUTINE SOUNDEX

EQU HIT_TRUE$    TO 1
EQU HIT_FALSE$   TO 0
EQU QUIT_SEARCH$ TO 2

IF CANDIDATE[1,1] GT SEARCH_FOR[1,1] THEN
  FLAG = QUIT_SEARCH$ ;* terminate search if first char not same
END ELSE
  SOUNDEX(CANDIDATE)                  ;* convert CANDIDATE to Soundex
  IF SEARCH_FOR EQ CANDIDATE THEN
    FLAG = HIT_TRUE$                  ;* sounds like it is a hit
  END ELSE
    FLAG = HIT_FALSE$                 ;* it does not sound the same
  END
END
RETURN

SUBROUTINE SOUNDEX(SOUNDEX.VALUE)

* process to return the Soundex equivalent of a single word establish the
* numeric code equivalents for all letters of the alphabet -- vowels plus
* 'w', 'y' and 'h' are ignored

EQU ALPHAS$      TO 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
EQU SOUND.CODES$ TO "01230120022455012623010202'
EQU PUNCTUATION$ TO ".,/`';][-=<>?:~}{_)(*^%$#@!\|":CHAR(34)
EQU NUMERALS$    TO "1234567890"
*
* make sure of only one word with no punctuation or lower case

TEXT=TRIM(SOUNDEX.VALUE)
TEXT=FIELD(TEXT,' ',1)

CONVERT PUNCTUATION$ TO '' IN TEXT
CONVERT NUMERALS$    TO '' IN TEXT
CONVERT @LOWER.CASE  TO @UPPER.CASE IN TEXT

* per the standard Soundex algorithm, start w/ second character

FIRST.CHAR    = TEXT[1,1]
TEXT          = TEXT[2,999]
TEXT.LEN      = LEN(TEXT)
SOUNDEX.VALUE = FIRST.CHAR
PREV.CHAR     =  ''
*
FOR LOOP.CNT = 1 TO TEXT.LEN WHILE LEN(SOUNDEX.VALUE) < 4
  * strip off next character
  NEXT.CHAR = TEXT[LOOP.CNT,1]
  IF NEXT.CHAR NE PREV.CHAR THEN
    CONVERT ALPHAS$ TO SOUND.CODES$ IN NEXT.CHAR
    IF NEXT.CHAR NE 0 THEN
       SOUNDEX.VALUE := SOUNDEX.CODE
       PREV.CHAR = NEXT.CHAR
    END
  END
NEXT LOOP.CNT
*
* format to be 4 characters long, zero padded at right if necessary
SOUNDEX.VALUE = FMT(SOUNDEX.VALUE,L(0)#4)
*
RETURN