diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /indexing/glo+idxtex/idxbuild.c |
Initial commit
Diffstat (limited to 'indexing/glo+idxtex/idxbuild.c')
-rw-r--r-- | indexing/glo+idxtex/idxbuild.c | 771 |
1 files changed, 771 insertions, 0 deletions
diff --git a/indexing/glo+idxtex/idxbuild.c b/indexing/glo+idxtex/idxbuild.c new file mode 100644 index 0000000000..c615c159f8 --- /dev/null +++ b/indexing/glo+idxtex/idxbuild.c @@ -0,0 +1,771 @@ +/* #module IdxBuild "3-001" + *********************************************************************** + * * + * The software was developed at the Monsanto Company and is provided * + * "as-is". Monsanto Company and the auther disclaim all warranties * + * on the software, including without limitation, all implied warran- * + * ties of merchantabilitiy and fitness. * + * * + * This software does not contain any technical data or information * + * that is proprietary in nature. It may be copied, modified, and * + * distributed on a non-profit basis and with the inclusion of this * + * notice. * + * * + *********************************************************************** + */ +/* + * Module Name: IdxBuild + * + * Author: R L Aurbach CR&DS MIS Group 27-Apr-1986 + * + * Function: + * Build the Index Tree data structure + * + * Modification History: + * + * Version Initials Date Description + * ------------------------------------------------------------------------ + * 1-001 RLA 27-Apr-1986 Original Code + * 1-002 RLA 03-May-1986 Add support for page-no highlighting + * and move spell-string processing to a + * separate module. + * 2-003 RLA 09-Apr-1987 Add support for volumes (used in master + * index processing). + * 2-004 RLA 14-Apr-1987 Add new page highlight flag + * 2-005 RLA 15-Apr-1987 Add support for cross-referencing + * 3-001 F.H. 17-May-1991 converted to portable C + */ +/* + * Module IdxBuild - Module-Wide Data Description Section + * + * Include Files: + */ +#ifdef MSDOS +#include <stdlib.h> +#include <io.h> +#define F_OK 0 /* access(): File exists */ +#else +# include <sys/file.h> +extern char *sprintf(); +#endif +#include <string.h> +#include <stdio.h> +#include <malloc.h> +#include <ctype.h> +#include "IdxDef.h" +/* + * Module Definitions: + */ +#define TRUE 1 +#define FALSE 0 +#define linebfsize 133 +/* + * Global Declarations: + */ +/* + * Static Declarations: + */ +static char *page_ref; +static char *tok_spell; +static char see_spell[linebfsize]; +#ifdef MSDOS +void idx_build_tree(char *token_1, char *token_2, char *token_3, + char *page_no, char token_ct, char *vol, int flag); +TREE_PTR idx_locate_node(TREE_PTR *head, char *token, char *desc); +void idx_add_page_ref(PGNODE_PTR *pghead, char *token, + char highlight, char *vol); +void idx_add_cross_ref(PGNODE_PTR *seehead, char *token, + char highlight, char *vol); +TREE_PTR idx_allocate_node(char *token, char *desc); +PGNODE_PTR idx_allocate_pgnode(char *vol, char *dsc, char hlite); +#else +void idx_build_tree(); +TREE_PTR idx_locate_node(); +void idx_add_page_ref(); +void idx_add_cross_ref(); +TREE_PTR idx_allocate_node(); +PGNODE_PTR idx_allocate_pgnode(); +#endif +/* + * External References: + */ +extern TREE_PTR root; /* root of the Index Tree */ +#ifdef MSDOS +extern void idx_build_spell_string(char *desc); +extern void idx_parse(char *linebf, char *token_1, char *token_2, + char *token_3, char *page_no, int *token_ct, int *flag); +#else +extern void idx_build_spell_string(); +extern void idx_parse(); +#endif +/* + * Functions Called: + */ +/* + * Function Idx_Build_Tree - Documentation Section + * + * Discussion: + * This routine uses the information parsed by Idx_Parse to build the Index + * Tree. + * + * Calling Synopsis: + * Call Idx_Build_Tree (token_1, token_2, token_3, page_no, token_ct, + * vol, flag) + * + * Inputs: + * token_1 -> is the top level item token. ASCIZ string passed by + * reference. + * + * token_2 -> is the second level item token. ASCIZ string passed by + * reference. + * + * token_3 -> is the third level item token. ASCIZ string passed by + * reference. + * + * page_no -> is the page number token. ASCIZ string passed by + * reference. + * + * token_ct -> is the number of tokens seen for this index entry. + * integer passed by value. + * + * vol -> is a pointer to the string descriptor for a volume + * string. The pointer is passed by value. + * + * flag -> is a boolean flag. If TRUE, the page_no variable is + * really a cross-reference string. + * + * Outputs: + * none + * + * Return Value: + * none + * + * Global Data: + * The Index Tree is updated. + * + * Files Used: + * none + * + * Assumed Entry State: + * none + * + * Normal Exit State: + * Tree is updated. + * + * Error Conditions: + * The only expected error is a memory allocation failure. In this case, + * a message is printed and the entry is ignored. + * + * Algorithm: + * A. Check for a page-no highlighting flag. + * B. Check for a valid set of input data. Ignore if not. + * C. Build a Spell String for the top-level item. + * D. Locate the top-level item in the tree. + * 1. If it does not exist, + * A. Allocate a new node and link it in. + * E. If token_ct == 1, + * 1. Add page number to list. + * F. Else, + * 1. Build a Spell String for the second-level item. + * 2. Locate the second-level item in the tree. + * A. If it does not exist, + * 1. Allocate a new node and link it in. + * 3. If token_ct == 2, + * A. Add page number to list. + * 4. Else, + * A. Build a Spell String for the third-level item. + * B. Locate the third-level item in the tree. + * 1. If it does not exist, + * a. Allocate a new node and link it in. + * C. Add page number to list. + * + * Special Notes: + * The first character of token_1 may be a special character. Special + * characters are used to indicate special highlighting to be performed + * on the page-no for this index entry. The special characters are: + * ^ use boldface + * ~ use italic + * _ use underlining + * Only one type of highlighting is supported for each page entry. + */ +/* + * Function Idx_Build_Tree - Code Section + */ +void idx_build_tree (token_1, token_2, token_3, page_no, token_ct, vol, flag) + char *token_1; + char *token_2; + char *token_3; + char *page_no; + char token_ct; + char *vol; + int flag; +{ +/* + * Local Declarations + */ + char spell_str[linebfsize]; + TREE_PTR node; + int test_char; + char *real_token_1; + char highlight; +/* + * Module Body + */ +/* Check for page-no highlighting flag */ + if (token_ct == 0) return; + if (token_1[0] == '\0') return; + real_token_1 = &token_1[1]; + test_char = token_1[0]; + switch (test_char) { + case '_' : + highlight = IDX_K_UNDERLINE; + break; + case '~' : + highlight = IDX_K_ITALIC; + break; + case '^' : + highlight = IDX_K_BOLD; + break; + case '#' : + highlight = IDX_K_FOLLOW; + break; + default : + highlight = IDX_K_NONE; + real_token_1 = &token_1[0]; + break; + } +/* Check out the item for validity */ + if (real_token_1[0] == '\0') return; + if ((token_ct > 1) && (token_2[0] == '\0')) return; + if ((token_ct > 2) && (token_3[0] == '\0')) return; + if (token_ct > 3) return; + if (page_no[0] == '\0') return; +/* First level token processing */ + (void)strcpy(spell_str, real_token_1); + idx_build_spell_string (spell_str); + node = idx_locate_node (&root, real_token_1, spell_str); + if (node == 0) { + (void)printf("Error processing index item %s\n", real_token_1); + return; + } + if (token_ct == 1) { + if (!flag) + idx_add_page_ref (&node->pghead, page_no, highlight, vol); + else idx_add_cross_ref (&node->seehead, page_no, highlight, vol); + } +/* Second level token processing */ + else { + (void)strcpy(spell_str,token_2); + idx_build_spell_string(spell_str); + node = idx_locate_node (&node->subhead, token_2, spell_str); + if (node == 0) { + (void)printf("Error processing index subitem %s\n", token_2); + return; + } + if (token_ct == 2) { + if (!flag) + idx_add_page_ref (&node->pghead, page_no, highlight, vol); + else + idx_add_cross_ref (&node->seehead, page_no, highlight, vol); + } +/* Third level token processing */ + else { + (void)strcpy(spell_str,token_3); + idx_build_spell_string(spell_str); + node = idx_locate_node (&node->subhead, token_3, spell_str); + if (node == 0) { + (void)printf("Error processing index subsubitem %s\n", token_3); + return; + } + if (!flag) + idx_add_page_ref (&node->pghead, page_no, highlight, vol); + else + idx_add_cross_ref (&node->seehead, page_no, highlight, vol); + } + } +} + +/* + * Function Idx_Locate_Node - Documentation Section + * + * Discussion: + * This routine scans the list of nodes (starting from the listhead), + * looking for one which has a spell-string identical to the given + * spell string. If it doesn't find one, it adds a node in the right place + * in the chain to maintain alphabetical order. + * + * Calling Synopsis: + * node = Idx_Locate_Node (head, token, desc) + * + * Inputs: + * head -> is the address of the listhead of the list to be + * scanned. As such, it is a TREE_PTR, passed by + * reference. + * + * token -> is the token to be located or entered in the list. + * ASCIZ string passed by reference. + * + * desc -> is the spell string, passed by descriptor. + * + * Outputs: + * none + * + * Return Value: + * node -> is the address of the tree leaf for the current token. + * It is a TREE_PTR, passed by value. If the leaf did not + * already exist and if the system was unable to allocate + * one, the node is returned as 0. + * + * Global Data: + * The list specified by the listhead will be modified if it is not + * possible to add a new leaf when necessary. + * + * Files Used: + * none + * + * Assumed Entry State: + * An empty listhead contains 0. + * + * Normal Exit State: + * The node is returned. + * + * Error Conditions: + * Allocation failure -- node = 0. + * + * Algorithm: + * A. If the list is empty, + * 1. Allocate a node and link it in. + * B. Else, + * 1. Beginning with the first node, + * a. If spell-string < node-spell-string, + * 1. Get next node. + * b. If spell-string = node-spell-string, + * 1. Return node pointer. + * c. If spell-string > node-spell-string, + * 1. Allocate a node and link it in. + * + * Special Notes: + * Although this algorithm isn't a very efficient way to alphatize things, + * it has the tremendous virtue of being easy to implement. Since the + * program is not run often (typically a couple of times per document), + * the inefficiency is not important. + */ +/* + * Function Idx_Locate_Node - Code Section + */ +TREE_PTR idx_locate_node (head, token, desc) + TREE_PTR *head; + char *token; + char *desc; +{ +/* + * Local Declarations + */ + TREE_PTR node; + TREE_PTR old_node; + TREE_PTR new_node; + int status; +/* + * Module Body + */ +/* Chain through the list, looking for the right place */ + old_node = 0; + new_node = *head; + while (new_node != 0) { + status = strcmp(new_node->spell, desc); + if (status < 0) { + old_node = new_node; + new_node = new_node->link; + continue; + } + if (status == 0) return (new_node); + if (status > 0) { + node = idx_allocate_node (token, desc); + if (old_node == 0) *head = node; + else old_node->link = node; + node->link = new_node; + return (node); + } + } +/* If the list is exhausted, allocate a node immediately */ + node = idx_allocate_node (token, desc); + if (old_node == 0) *head = node; + else old_node->link = node; + return (node); +} + +/* + * Function Idx_Allocate_Node - Documentation Section + * + * Discussion: + * Allocate and initialize a leaf of the Index Tree. + * + * Calling Synopsis: + * node = Idx_Allocate_Node (token, desc) + * + * Inputs: + * token -> token string. ASCIZ string passed by reference. + * + * desc -> spell string. Character string passed by descriptor. + * + * Outputs: + * none + * + * Return Value: + * node -> Address of the allocated node. TREE_PTR passed by + * value. + * + * Global Data: + * none + * + * Files Used: + * none + * + * Assumed Entry State: + * none + * + * Normal Exit State: + * node is allocated. + * + * Error Conditions: + * allocation failure -- node is returned == 0. + * + * Algorithm: + * A. Allocate virtual memory for the node. + * B. Initialize the node structure. + * + * Special Notes: + * none + */ +/* + * Function Idx_Allocate_Node - Code Section + */ +TREE_PTR idx_allocate_node (token, desc) + char *token; + char *desc; +{ +/* + * Local Declarations + */ + TREE_PTR node; +/* + * Module Body + */ + node = (TREE_PTR) malloc (sizeof(TREE)); + if (node != 0) { + node->link = 0; + node->subhead = 0; + node->pghead = 0; + node->seehead = 0; + node->spell = strdup(desc); + node->item = strdup(token); + } + return (node); +} + +/* + * Function Idx_Add_Page_Ref - Documentation Section + * + * Discussion: + * If the specified page reference is not already in the current list, + * add it to the end of the list. + * + * Calling Synopsis: + * Call Idx_Add_Page_Ref (pghead, token, highlight, vol) + * + * Inputs: + * pghead -> the address of the listhead for the page reference list. + * a PGNODE_PTR, passed by reference. + * + * token -> the page reference. ASCIZ string passed by reference. + * + * highlight -> a flag indicating what sort of highlighting to give + * this particular page reference. char passed by value. + * + * vol -> is a pointer to a character string descriptor which + * describes the volume string. + * + * Outputs: + * none + * + * Return Value: + * none + * + * Global Data: + * If a new page reference needs to be added, the list is updated. + * + * Files Used: + * none + * + * Assumed Entry State: + * none + * + * Normal Exit State: + * If the page reference already exists, nothing happens. If a new + * page reference needs to be added, it is allocated and appended to the + * end of the list. + * + * Error Conditions: + * If there is an allocation failure, the page reference is not added. + * + * Algorithm: + * A. Put the page_no token in a dynamic string. + * B. For all nodes in the list, + * 1. If the page-no in the list does not match the page-no, + * a. Get next node. + * 2. Else, + * a. Return. + * C. If the list is exhausted, + * 1. Allocate a new node. + * 2. Fill it in. + * 3. Chain it to the end of the list. + * + * Special Notes: + * This routine assumes that page-no references are always in numerical + * order. This assumption is necessary, because the variety of page + * numbering (perhaps within the document) makes it impossible to check + * for order. + */ +/* + * Function Idx_Add_Page_Ref - Code Section + */ +void idx_add_page_ref (pghead, token, highlight, vol) + PGNODE_PTR *pghead; + char *token; + char highlight; + char *vol; +{ +/* + * Local Declarations + */ + PGNODE_PTR node; + PGNODE_PTR last_node = *pghead; +/* + * Module Body + */ + page_ref = strdup(token); + while (last_node != 0) { + if ((strcmp(last_node->page_dsc, page_ref) == 0) && + ((strcmp(last_node->vol, vol)) == 0)) { + if (highlight == IDX_K_NONE) return; + last_node->highlight = highlight; + return; + } + if (last_node->link == 0) break; + last_node = last_node->link; + } + node = idx_allocate_pgnode (vol, page_ref, highlight); + if (node != 0) { + if (last_node == 0) *pghead = node; + else last_node->link = node; + } +} + +/* + * Function Idx_Add_Cross_Ref - Documentation Section + * + * Discussion: + * Parse and build a cross reference string. If the string is not already + * on the current list, add it to the list in alphabetical order. + * + * Calling Synopsis: + * Call Idx_Add_Cross_Ref (seehead, token, highlight, vol) + * + * Inputs: + * seehead -> the address of the listhead for the cross-reference + * list. + * + * token -> the cross-reference string. ASCIZ string passed by + * reference. + * + * hightlight -> a flag indicating what sort of highlighting to give" + * this particular cross-reference. char passed by value. + * + * vol -> is a pointer to a character string descriptor which + * describes the volume string.f + * + * Outputs:e + * noneM + * + * Return Value: + * none + * + * Global Data:a + * If a new cross-reference needs to be added, the list is updated.t + * + * Files Used: + * nonea + * + * Assumed Entry State: + * nonef + * + * Normal Exit State:s + * If the cross-reference already exists, nothing happens. If a new + * page reference needs to be added, it is allocated and added to thei + * list. + * + * Error Conditions: + * If there is an allocation failure, the page reference is not added. + * + * Algorithm: + * A. Parse the page reference into tokens. + * B. Build the cross-reference text string and put it in a dynamic string. + * C. Build a spell string for it. + * D. Chain the string into the list. + * + * Special Notes:* + * none* + */ +/* + * Function Idx_Add_Cross_Ref - Code Section + */ +void idx_add_cross_ref (seehead, token, highlight, vol) + PGNODE_PTR *seehead; + char *token; + char highlight; + char *vol; +{ +/* + * Local Declarationsp + */ + int length; + PGNODE_PTR node; + PGNODE_PTR old_node = 0; + PGNODE_PTR new_node = *seehead; + char tok_1[linebfsize]; + char tok_2[linebfsize]; + char tok_3[linebfsize]; + char dummy[linebfsize]; + int tok_ct; + int flag; +/* + * Module Body + */ + +/* + * Parse the cross-reference string into its tokens using Idx_Parse. + * Then combine the results to build a token string and write it to thei + * page_ref dynamic string. Compute its spell string. + */ + idx_parse(token, tok_1, tok_2, tok_3, dummy, &tok_ct, &flag); + if (tok_ct == 0) return; + if (strlen(tok_1) == 0) return; + if (tok_ct > 1 && strlen(tok_2) == 0) return; + if (tok_ct > 2 && strlen(tok_3) == 0) return; + length = strlen(tok_1); + (void)sprintf (dummy, "%s", tok_1); + if (tok_ct > 1) { + (void)sprintf (&dummy[length], ", %s", tok_2); + length += strlen(tok_2); + } + if (tok_ct > 2) { + (void)sprintf(&dummy[length], ", %s", tok_3); + length += strlen(tok_3); + } + page_ref = strdup(dummy); + tok_spell = dummy; + idx_build_spell_string(tok_spell); +/* + * Now scan the list of cross-references to find where to put this one.C + */ + while (new_node != 0) { + (void)strncpy(dummy, new_node->page_dsc, + strlen(new_node->page_dsc)); + dummy[strlen(new_node->page_dsc)] = '\0'; + (void)strcpy(see_spell, dummy); + idx_build_spell_string(see_spell); + flag = strcmp(see_spell, tok_spell); + if (flag < 0) { + old_node = new_node; + new_node = new_node->link; + continue; + } + if (flag == 0) return; + if (flag > 0) { + node = idx_allocate_pgnode(vol, page_ref, highlight); + if (node != 0) { + if (old_node == 0) *seehead = node; + else old_node->link = node; + node->link = new_node; + } + return; + } + } + +/* If the list is exhausted, allocate a node immediately */ + node = idx_allocate_pgnode(vol, page_ref, highlight); + if (node != 0) { + if (old_node == 0) *seehead = node; + else old_node->link = node; + } +} + +/* + * Function Idx_Allocate_PgNode - Documentation Sectioni + * + * Discussion: + * Allocate and initialize a new page node.o + * + * Calling Synopsis: + * node = Idx_Allocate_PgNode (vol, dsc, hlite) + * + * Inputs: + * vol -> is the address of the volume string descriptor. + * + * dsc -> is the address of the page ref string descriptor. + * + * hlite -> is the highlight flag + * + * Outputs: + * nonem + * + * Return Value: + * node -> is the address of the newly allocated node. + * + * Global Data: + * none + * + * Files Used: + * none + * + * Assumed Entry State: + * none + * + * Normal Exit State: + * none + * + * Error Conditions: + * if the allocation failed, node is returned = 0. + * + * Algorithm: + * A. Allocate the node. + * B. If successful, + * 1. Initialize it. + * + * Special Notes: + * none + */ +/* + * Function Idx_Allocate_PgNode - Code Section + */ +PGNODE_PTR idx_allocate_pgnode (vol, dsc, hlite) + char *vol; + char *dsc; + char hlite; +{ +/* + * Local Declarations + */ + PGNODE_PTR node; +/* + * Module Body + */ + node = (PGNODE_PTR) malloc (sizeof(PGNODE)); + if (node != 0) { + node->link = 0; + node->vol = strdup(vol); + node->highlight = hlite; + node->page_dsc = strdup(dsc); + } + return (node); +} |