diff options
Diffstat (limited to 'private/unimodem/new/match/mt.c')
| -rw-r--r-- | private/unimodem/new/match/mt.c | 424 |
1 files changed, 424 insertions, 0 deletions
diff --git a/private/unimodem/new/match/mt.c b/private/unimodem/new/match/mt.c new file mode 100644 index 000000000..c5950272a --- /dev/null +++ b/private/unimodem/new/match/mt.c @@ -0,0 +1,424 @@ +#include "unimdm.h" +#include "mcxp.h" + +#if 0 +#include <windows.h> +#endif + +#include <stdio.h> +#include <string.h> +#include "mt.h" + +// #define SILENT + +#ifdef SILENT +# define PRINTF0(_a) (0) +# define PRINTF1(_a,_b) (0) +# define PRINTF2(_a,_b,_c) (0) +# define PRINTF3(_a,_b,_c,_d) (0) +#else +#ifdef CONSOLE +# define PRINTF0(_a) printf(_a) +# define PRINTF1(_a,_b) printf((_a),(_b)) +# define PRINTF2(_a,_b,_c) printf((_a),(_b),(_c)) +# define PRINTF3(_a,_b,_c,_d) printf((_a),(_b),(_c),(_d)) +#else +# define PRINTF0(_a) DPRINTF(_a) +# define PRINTF1(_a,_b) DPRINTF1((_a),(_b)) +# define PRINTF2(_a,_b,_c) DPRINTF2((_a),(_b),(_c)) +# define PRINTF3(_a,_b,_c,_d) DPRINTF3((_a),(_b),(_c),(_d)) +#endif //!CONSOLE +#endif // !SILENT + +// ======================== PRIVATES =================================== + +#define ASSERT(_c) \ + ((_c) ? 0: printf("Assertion failed in %s:%d\n", __FILE__, __LINE__)) + +typedef struct _MNODE +{ + MATCHREC mr; + struct _MNODE *pmnNext; + struct _MNODE *pmnCh; + +} MNODE, *PMNODE; + +PMNODE mn_create_raw_tree(PMATCHREC pmr, DWORD dwcmr); +BOOL mn_cook_tree (PMNODE pmn, DWORD dwMin); +void mn_free_tree (PMNODE pmn); +PMNODE mn_alloc (PMATCHREC pmr, PMNODE pmnNext); +void mn_free (PMNODE pmn); +void mn_dump_tree (PMNODE pmn, UINT uDepth, UINT uWidth); +DWORD mn_find_smallest(PMNODE pmn); +DWORD mn_find_match(PMNODE pmn, PMATCHREC pmr); +// ======================== PRIVATES (end) =================================== + +HMATCHTREE mtCreateTree(PMATCHREC pmr, DWORD dwcmr) +{ + PMNODE pmn = mn_create_raw_tree(pmr, dwcmr); + + if (!mn_cook_tree(pmn, MAXDWORD)) + { + mn_free_tree(pmn); + pmn=NULL; + } + + return (DWORD) pmn; +} + +void mtFreeTree(HMATCHTREE hmt) +{ + PMNODE pmn = (PMNODE) hmt; + + mn_free_tree(pmn); // NULL is a valid tree +} + + +// Returns one or more fMATCH_ flags. +// Searches through all its siblings as well... +// Recursive function, so keep locals to a minimum. +DWORD mtFindMatch(HMATCHTREE hmt, PMATCHREC pmr) +{ + MATCHREC mr; + DWORD dwRet = 0; + + if (!pmr) goto end; + + mr = *pmr; // Structure copy. + dwRet = mn_find_match((PMNODE)hmt, &mr); + // mn_find_match trashes dwLen and cb fields of pmr, only pv field is valid + pmr->pv = mr.pv; + +end: + return dwRet; +} + + +#ifdef DEBUG +void mtDumpTree(HMATCHTREE hmt) +{ + PMNODE pmn = (PMNODE) hmt; + + mn_dump_tree(pmn, 0, 0); +} +#endif // DEBUG + + +PMNODE mn_create_raw_tree(PMATCHREC pmr, DWORD dwcmr) +{ + PMNODE pmnFirst=NULL; + + for (;dwcmr--;pmr++) + { + PMNODE pmnTmp = mn_alloc(pmr, pmnFirst); + if (!pmnTmp) goto failure; + pmnFirst=pmnTmp; + } + goto end; + +failure: + mn_free_tree(pmnFirst); // NULL is a valid tree to free + pmnFirst=NULL; + // FALL THROUGH + +end: + return pmnFirst; +} + + +PMNODE mn_alloc(PMATCHREC pmr, PMNODE pmnNext) +{ + PMNODE pmn = (pmr && pmr->pb && pmr->dwLen) + ? LocalAlloc(LPTR, sizeof(MNODE)) : NULL; + + if (pmn) + { + pmn->mr = *pmr; // structure copy. + pmn->pmnNext=pmnNext; + pmn->pmnCh=NULL; + } + + return pmn; +} + +void mn_free(PMNODE pmn) +{ + if (pmn) + { + ASSERT(!pmn->pmnCh && !pmn->pmnNext); + LocalFree(pmn); + } +} + + +void mn_free_tree(PMNODE pmn) +{ + if (pmn) + { + mn_free_tree(pmn->pmnCh); // recurse down + mn_free_tree(pmn->pmnNext); // recurse left + pmn->pmnNext=pmn->pmnCh=NULL; + mn_free(pmn); + } +} + +BOOL mn_cook_tree(PMNODE pmn, DWORD dwMin) +{ + // Find smallest string of me and siblings + if (dwMin==MAXDWORD) dwMin = mn_find_smallest(pmn); + + if (!pmn) goto success; + + // These are all serious problems -- so we assert on failure: + if (!dwMin || pmn->pmnCh || !pmn->mr.pb || (pmn->mr.dwLen<dwMin)) + goto failure; + + // Start my children's list by creating one if pmn->pb is longer + // than the minimum, in which case we also NULL pv, because pv should + // be NULL for internal (non-leaf) nodes. + if (pmn->mr.dwLen>dwMin) + { + MATCHREC mr; + mr.pb=pmn->mr.pb+dwMin; + mr.dwLen=pmn->mr.dwLen-dwMin; + mr.pv=pmn->mr.pv; + pmn->pmnCh = mn_alloc(&mr, NULL); + if (!pmn->pmnCh) goto failure; + pmn->mr.pv=NULL; + pmn->mr.dwLen=dwMin; + } + + // Add to my children's list by converting those siblings which + // share my dwMin-sized prefix into my children. (Obviously) remove + // these siblings from the sibling list. + { + PMNODE pmnTmp = pmn; + while(pmnTmp->pmnNext) + { + PMNODE pmnTmp1 = pmnTmp->pmnNext; + + if (pmnTmp1->mr.dwLen<dwMin || !pmnTmp1->mr.pb) goto failure; + + if (!_strnicmp(pmn->mr.pb, pmnTmp1->mr.pb, dwMin)) + { + // Found a prefix match -- remove from sibling list + // and add to child list if non-null + pmnTmp->pmnNext = pmnTmp1->pmnNext; + pmnTmp1->mr.dwLen-=dwMin; + pmnTmp1->mr.pb+=dwMin; + pmnTmp1->pmnNext=NULL; + // If nothing left to add -- we're at the end of pb -- + // (leaf node) so we make pmn->pv non-NULL, and free pmnTmp1 + // Otherwise we add it to pmn's child's list. + if (!pmnTmp1->mr.dwLen) + { + if (pmn->mr.pv) {PRINTF0("Warning: overriding pv!\n");} + pmn->mr.pv = pmnTmp1->mr.pv; + ASSERT(!pmnTmp1->pmnCh && !pmnTmp1->pmnNext); + mn_free(pmnTmp1); + } + else + { + pmnTmp1->pmnNext = pmn->pmnCh; + pmn->pmnCh=pmnTmp1; + } + } + else + { + pmnTmp = pmnTmp->pmnNext; + } + if (!pmnTmp) break; + } + } + + // recurse down + if (!mn_cook_tree(pmn->pmnCh, MAXDWORD)) goto failure; + + // recurse left + if (!mn_cook_tree(pmn->pmnNext, dwMin)) goto failure; + + // FALL THROUGH + +success: + return TRUE; + +failure: + ASSERT(FALSE); + return FALSE; +} + +DWORD mn_find_smallest(PMNODE pmn) +{ + DWORD dw = MAXDWORD; + + if (pmn) + { + dw = mn_find_smallest(pmn->pmnNext); + if (dw>pmn->mr.dwLen) dw=pmn->mr.dwLen; + } + return dw; +} + +void mn_dump_tree(PMNODE pmn, UINT uDepth, UINT uWidth) +{ + static char rgchFill[]="----------------------------------------"; + LONG lOff = sizeof(rgchFill) - (uDepth+1); + if (lOff<0) lOff=0; + // if(!pmn) return; + PRINTF2("%02lu%s", (unsigned long) uDepth, rgchFill+lOff); + if (!pmn) + { + PRINTF1("NULL(w=%lu)\n", (unsigned long) uWidth); + } + else + { + CHAR *pb = (pmn->mr.pb)?pmn->mr.pb:"\"\""; + CHAR c = pb[pmn->mr.dwLen]; + CHAR *pc2 = (CHAR *) pmn->mr.pv; + if (!pc2) pc2=""; + pb[pmn->mr.dwLen]=0; + PRINTF3("[%s]:%02lu %s\n", pc2, + (unsigned long) pmn->mr.dwLen, pb); + pb[pmn->mr.dwLen]=c; + mn_dump_tree(pmn->pmnCh, uDepth+1,0); // recurse down + mn_dump_tree(pmn->pmnNext, uDepth, uWidth+1); // recurse left + } +} + + +// Returns one or more fMATCH_ flags. +// Searches through all its siblings as well... +// Recursive function, so keep locals to a minimum. +// WARNING: Trashes dwLen and cb fields of pmr. +DWORD mn_find_match(PMNODE pmn, PMATCHREC pmr) +{ + DWORD dwRet=0; + DWORD dwcbMin; + CHAR *pc; + +#ifdef DEBUG + DWORD dwcb; + CHAR rgchTmp[256]; + DWORD dwcbTmp; +#endif // DEBUG + + if (!pmn || !pmr) goto end; + +#ifdef DEBUG +# define DWCB dwcb +# define DBGPSZ rgchTmp + DWCB = pmr->dwLen; + dwcbTmp = sizeof(DBGPSZ)-1; + if (dwcbTmp>DWCB) dwcbTmp=DWCB; + // We do this because pb is not null terminated. + CopyMemory(DBGPSZ, pmr->pb, dwcbTmp); + DBGPSZ[dwcbTmp]=0; +#else // !DEBUG +# define DBGPSZ "" +# define DWCB 0 +#endif // !DEBUG + + PRINTF1("Entering mn_find_match(-, [%s], -)\n", DBGPSZ); + + + + // Iterate through siblings, looking for matches and partial matches. + // We stop when we find the first match or partial match, because all + // the substrings at the same level are unique and have the same length: + // so if we found a match we can't find a partial match among the siblings, + // and vice versa. Furthermore, if we find a partial match, we don't really + // care which (could be more than one) sibling it is a partial match for. + // If in the future we we *do* return the node for efficiency purposes + // (so that the next call can start where we left off), + // we would return the node for the *first* partial match we found. + pc = pmr->pb; + dwcbMin = pmn->mr.dwLen; + if (pmr->dwLen<dwcbMin) + { + dwcbMin=pmr->dwLen; + dwRet = fMATCH_PARTIAL; + } + else if (pmr->dwLen==dwcbMin) + { + dwRet = fMATCH_COMPLETE; + } + else + { + // pmr->dwLen>pmn->mr.dwU, dwRet==0, so do nothing + } + + // WARNING: we trash pmr here, except for pmr->pv + pmr->dwLen-=dwcbMin; + pmr->pb+=dwcbMin; + + while(pmn) + { + // Fundamental assumption is that all dwLens of siblings are equal. + ASSERT((pmn->pmnNext)? pmn->mr.dwLen==pmn->pmnNext->mr.dwLen:TRUE); + + if (!_strnicmp(pc, pmn->mr.pb, dwcbMin)) + { + PRINTF3("Match: dwcb=%lu; pmn->mr.dwLen=%lu; pc=[%s]\n", + (unsigned long) DWCB, + (unsigned long) pmn->mr.dwLen, + DBGPSZ); + + // Note: dwRet is computed just once, out of the while loop. + // we were really overloading dwRet then. Now we compute the + // true return value. + switch(dwRet) + { + case 0: // i.e., (DWCB > pmn->mr.dwLen) + ASSERT(DWCB>pmn->mr.dwLen); + // Recurse down. WARNING: pmr is trashed, except for pmr->pv + dwRet = mn_find_match(pmn->pmnCh, pmr); + break; + + case fMATCH_PARTIAL: // i.e., (DWCB < pmn->mr.dwLen) + ASSERT(DWCB<pmn->mr.dwLen); + break; + + case fMATCH_COMPLETE: // i.e., (DWCB == pmn->mr.dwLen) + ASSERT(DWCB==pmn->mr.dwLen); + // Now let's see if we're truly a perfect macth: non-null + // pv indicates an actual response terminates in this node. + dwRet=0; + if (pmn->mr.pv) + { + pmr->pv = pmn->mr.pv; + dwRet = fMATCH_COMPLETE; + } + // Non-null pmnCh implies there are postfixes, i.e., longer + // responses + if (pmn->pmnCh) + { + dwRet |= fMATCH_PARTIAL; + } + break; + + default: + ASSERT(FALSE); + dwRet=0; + goto end; + } + if (dwRet) break; // break out of while loop if we got something + } + pmn=pmn->pmnNext; + + } + + if (!pmn) + { + dwRet=0; + } + else + { + ASSERT(dwRet && !_strnicmp(pc, pmn->mr.pb, dwcbMin)); + } + + PRINTF2("Exiting mn_find_match(-, [%s], -) returing 0x%lx\n", DBGPSZ, + (unsigned long) dwRet); + +end: + return dwRet; +} |