home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / iutil / ndxsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-01-23  |  3.7 KB  |  152 lines
  1. # include    <ingres.h>
  2. # include    <aux.h>
  3. # include    <symbol.h>
  4. # include    <access.h>
  5. # include    <lock.h>
  6. # include    <sccs.h>
  7.  
  8. SCCSID(@(#)ndxsearch.c    8.1    12/31/84)
  9.  
  10.  
  11. /*
  12. **  NDXSEARCH -- search an ISAM directory
  13. **    
  14. **    Looks for an available page, if this would force out a page from
  15. **    the relation it adds its own.  Searches each level of the dirctory
  16. **    for the lowest (highest) page on which the key could occur if mode
  17. **    is < (>) 0.  At each level the number of keys on the page is checked
  18. **    if it is <= SEARCHFUDGE a linear sharch is done, otherwize a binary
  19. **    search is preformed.  If the full key matches exactly the seach
  20. **    can stop.  Note that the keys tell the minimum value on that page.
  21. **
  22. **    Parameters:
  23. **        d    - pointer to descriptor of open relation
  24. **        tid    - returns tid of page to start (end) looking
  25. **        key    - to look for
  26. **        mode    - < 0 lowkey, > 0 hikey
  27. **        keyok    - true if all keys are assumed to be set
  28. **
  29. **    Returns:
  30. **        -2    - pageflush failure
  31. **        -1    - get_page failure
  32. **        0    - success
  33. **
  34. **    Side Effects:
  35. **        causes I/O
  36. */
  37.  
  38. # define    SEARCHFUDGE    6    /* # of linenos to do a binary search */
  39.  
  40. ndxsearch(d, tid, tuple, mode, keyok)
  41. DESC        *d;        
  42. register TID    *tid;        
  43. char        tuple[];    
  44. int        mode;    
  45. int        keyok;
  46. {
  47.     register int        i;
  48.     long            pageid;
  49.     int            j, keylen, dno, partialkey;
  50.     char            *p;
  51.     int            pagerr;
  52.     struct accessparam    relparm;
  53.     int            top;
  54.     register        bottom;
  55.     extern char        *get_addr();
  56.  
  57.     pagerr = 0;
  58.     paramd(d, &relparm);    /* get domains in key order */
  59.  
  60.     /* assume fullkey is given */
  61.     partialkey = FALSE;
  62.  
  63.     /* remove any key domains not given by the user */
  64.     if (!keyok)
  65.     {
  66.         for (i = 0; dno = relparm.keydno[i]; i++)
  67.         {
  68.             if (d->relgiven[dno])
  69.                 continue;
  70.             relparm.keydno[i] = 0;
  71.             partialkey = TRUE;
  72.             break;
  73.         }
  74.     }
  75.  
  76.     /* if the first key isn't given, just return else search directory */
  77.     if (relparm.keydno[0] != 0)
  78.     {
  79.         /* The actual ISAM directory search must be performed */
  80.         pageid = d->reldum.relprim;
  81.         stuff_page(tid, &pageid);
  82.  
  83.         Acclock = FALSE;
  84.  
  85.         do
  86.         {
  87.             if (pagerr = get_page(d, tid))
  88.                 break;    /* fatal error */
  89.             Acc_head->bufstatus |= BUF_DIRECT;  /* don't get confused */
  90.             bottom = 0;
  91.             top = Acc_head->nxtlino - 1;
  92.  
  93.             if (top >= SEARCHFUDGE)  /* we are past breakeven */
  94.             {
  95.                 while (top != bottom)    /* binary search */
  96.                 {
  97.                     tid->line_id = ((1 + top - bottom) >> 1) + bottom;    /* get to half way point */
  98.                     p = get_addr(tid);
  99.                     for (j = 0; dno = relparm.keydno[j]; j++)
  100.                     {
  101.                         keylen = d->relfrml[dno] & I1MASK;
  102.                         if (i = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
  103.                             break;
  104.                         p += keylen;
  105.                     }
  106.                     /* if key is below directory, then we are in the bottom half */
  107.                     if (i < 0 || (i == 0 && partialkey && mode < 0))
  108.                         top = (tid->line_id & I1MASK) - 1;
  109.  
  110.                     else if (i == 0 && !partialkey)
  111.                     {
  112.                         bottom = (tid->line_id & I1MASK);
  113.                         break;
  114.                     }
  115.                     else
  116.                         bottom = (tid->line_id & I1MASK);
  117.                 }
  118.             }
  119.             else    /* do a linar search */
  120.             {
  121.                 for (tid->line_id = 0; (tid->line_id & I1MASK) < Acc_head->nxtlino; tid->line_id++)
  122.                 {
  123.                     p = get_addr(tid);
  124.                     for (i = 0; dno = relparm.keydno[i]; i++)
  125.                     {
  126.                         keylen = d->relfrml[dno] & I1MASK;
  127.                         if (j = icompare(&tuple[d->reloff[dno]], p, d->relfrmt[dno], keylen))
  128.                             break;
  129.                         p += keylen;
  130.                     }
  131.                     /* if key is below directory, then we have passed the position */
  132.                     if (j < 0)
  133.                         break;
  134.  
  135.                     /* if lowkey search on partial key matches, then done */
  136.                     if (j == 0 && partialkey && mode < 0)
  137.                         break;
  138.                     bottom = tid->line_id;
  139.                     if (j == 0 && mode < 0)
  140.                         break;
  141.                 }
  142.             }
  143.             pageid = Acc_head->ovflopg + bottom;
  144.             stuff_page(tid, &pageid);
  145.         } while (Acc_head->mainpg);  /* if at level zero then done */
  146.         Acclock = TRUE;
  147.     
  148.     }
  149.     tid->line_id = -1;
  150.     return (pagerr);
  151. }
  152.