home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Exec 3 / CD_Magazyn_EXEC_nr_3.iso / Recent / misc / edu / WhirlDisc.lha / WhirlDisc / Source / index.c < prev    next >
C/C++ Source or Header  |  2000-08-13  |  7KB  |  324 lines
  1. /*
  2.  
  3. File: index.c
  4. Author: Neil Cafferkey
  5. Copyright (C) 2000 Neil Cafferkey
  6.  
  7. This program is free software; you can redistribute it and/or
  8. modify it under the terms of the GNU General Public License
  9. as published by the Free Software Foundation; either version 2
  10. of the License, or (at your option) any later version.
  11.  
  12. This program is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program; if not, write to the Free Software
  19. Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  20. MA 02111-1307, USA.
  21.  
  22. */
  23.  
  24. #include "viewer.h"
  25. #include <dos/dos.h>
  26. #include <dos/dostags.h>
  27. #include <exec/memory.h>
  28. #include <string.h>
  29.  
  30. #include "index_protos.h"
  31. #include "index_record_protos.h"
  32. #include "general_protos.h"
  33. #include <proto/exec.h>
  34.  
  35.  
  36. const TEXT FIRST_REC_STRING[]="%FIRST-REC%";
  37. #define FIRST_REC_SIZE 11
  38.  
  39.  
  40. static UBYTE *DataSearch(ULONG length_1,ULONG length_2,UBYTE *buf_1,
  41.    UBYTE *buf_2);
  42. static BOOL DataEqual(ULONG length,UBYTE *buf_1,UBYTE *buf_2);
  43.  
  44.  
  45. /* Function: CreateIndex
  46.  * =====================
  47.  * Creates an Index.
  48.  */
  49.  
  50. Index CreateIndex(TEXT *master_file_name,TEXT *index_file_name)
  51. {
  52.    Index index;
  53.    struct FileInfoBlock *temp_fib;
  54.    BPTR master_file;
  55.  
  56.  
  57.    if((index=(Index)AllocMem(sizeof(Index_imp),MEMF_CLEAR))!=NULL)
  58.    {
  59.  
  60.       /* Open the main index file */
  61.  
  62.       if(!(index->index_file=Open(index_file_name,MODE_OLDFILE)))
  63.          ReportError(NULL,ERROR_REPORT_FILE,index_file_name,0);
  64.  
  65.       /* Open the master index file */
  66.  
  67.       master_file=Open(master_file_name,MODE_OLDFILE);
  68.  
  69.       /* Copy master index file into memory */
  70.  
  71.       if(master_file)
  72.       {
  73.  
  74.          if((temp_fib=(struct FileInfoBlock *)AllocDosObjectTags(
  75.             DOS_FIB,TAG_END))!=NULL)
  76.          {
  77.             /* Get master file size */
  78.  
  79.             ExamineFH(master_file,temp_fib);
  80.             index->block_count=temp_fib->fib_Size/MASTER_REF_SIZE;
  81.             FreeDosObject(DOS_FIB,temp_fib);
  82.  
  83.             /* Allocate memory for master file data */
  84.  
  85.             index->master_index=(UBYTE *)AllocMem(index->block_count
  86.                *MASTER_REF_SIZE,MEMF_ANY);
  87.  
  88.             /* Read link data into memory */
  89.  
  90.             if(index->master_index!=NULL)
  91.                Read(master_file,index->master_index,index->block_count
  92.                   *MASTER_REF_SIZE);
  93.             else
  94.             {
  95.                ReportError(NULL,ERROR_REPORT_MEM,NULL,0);
  96.             }
  97.  
  98.          }
  99.          else
  100.          {
  101.             ReportError(NULL,ERROR_REPORT_MEM,NULL,0);
  102.          }
  103.  
  104.          Close(master_file);
  105.       }
  106.       else
  107.       {
  108.          ReportError(NULL,ERROR_REPORT_FILE,master_file_name,0);
  109.       }
  110.  
  111.       /* Check if there were any errors */
  112.  
  113.       if((index->index_file==NULL)||(index->master_index==NULL))
  114.       {
  115.          KillIndex(index);
  116.          index=NULL;
  117.       }
  118.  
  119.    }
  120.    else
  121.    {
  122.       ReportError(NULL,ERROR_REPORT_MEM,NULL,0);
  123.    }
  124.  
  125.    return index;
  126. }
  127.  
  128.  
  129.  
  130. /* Function: FindIndexRecords
  131.  * ==========================
  132.  * Searches for records within an index.
  133.  */
  134.  
  135. struct List *FindIndexRecords(Index index,TEXT *search_string)
  136. {
  137.    IndexRecord index_rec;
  138.    UWORD first_block,last_block,mid;
  139.    WORD low,high;
  140.    UBYTE *p,*q,*index_buffer;
  141.    struct List *rec_list;
  142.    BOOL success=TRUE;
  143.  
  144.    /* Create a new list to contain the results */
  145.  
  146.    rec_list=AllocMem(sizeof(struct List),MEMF_PUBLIC);
  147.    if(rec_list!=NULL)
  148.    {
  149.       NewList(rec_list);
  150.  
  151.       /* Convert search string to uppercase */
  152.  
  153.       for(p=search_string;*p!='\0';p++)
  154.          *p=toupper(*p);
  155.  
  156.       /* Do a binary search to find the first block needed */
  157.  
  158.       p=index->master_index;
  159.       low=-1;
  160.       high=index->block_count-1;
  161.  
  162.       while(high-low!=1)
  163.       {
  164.          mid=low+(high-low)/2;
  165.          for(q=p+mid*MASTER_REF_SIZE;*q!=0;q-=MASTER_REF_SIZE);
  166.  
  167.          if(strncmp(search_string,q+1,MASTER_REF_SIZE-1)<=0)
  168.             high=mid;
  169.          else
  170.             low=mid;
  171.  
  172.       }
  173.  
  174.       first_block=high;
  175.  
  176.       /* Do a binary search to find the last block needed */
  177.  
  178.       low=-1;
  179.       high=index->block_count-1;
  180.  
  181.       while(high-low!=1)
  182.       {
  183.          mid=low+(high-low)/2;
  184.          for(q=p+mid*MASTER_REF_SIZE;*q!=0;q-=MASTER_REF_SIZE);
  185.  
  186.          if(strncmp(search_string,q+1,MASTER_REF_SIZE-1)<0)
  187.             high=mid;
  188.          else
  189.             low=mid;
  190.  
  191.       }
  192.  
  193.       last_block=high;
  194.  
  195.  
  196.       /* Allocate the index buffer */
  197.  
  198.       index_buffer=AllocMem((last_block-first_block+1)*INDEX_BLOCK_SIZE,
  199.          MEMF_ANY);
  200.  
  201.       if(index_buffer)
  202.       {
  203.  
  204.          /* Read relevant index blocks into memory */
  205.  
  206.          Seek(index->index_file,first_block*INDEX_BLOCK_SIZE,
  207.             OFFSET_BEGINNING);
  208.          Read(index->index_file,index_buffer,(last_block-first_block+1)
  209.             *INDEX_BLOCK_SIZE);
  210.  
  211.          /* Find first-record marker */
  212.  
  213.          p=DataSearch(FIRST_REC_SIZE,2*INDEX_BLOCK_SIZE,
  214.             FIRST_REC_STRING,index_buffer);
  215.  
  216.          /* Find first matching record */
  217.  
  218.          p+=FIRST_REC_SIZE;
  219.          while(strcmp(p+10,search_string)<0)
  220.             p+=GetLittleEndianUWord(p);
  221.  
  222.          /* Put all matching records into the list */
  223.  
  224.          while(strcmp(p+10,search_string)==0)
  225.          {
  226.             index_rec=CreateIndexRecord(p);
  227.             if(index_rec!=NULL)
  228.                AddTail(rec_list,&index_rec->node);
  229.             p+=GetLittleEndianUWord(p);
  230.          }
  231.  
  232.          FreeMem(index_buffer,(last_block-first_block+1)*INDEX_BLOCK_SIZE);
  233.       }
  234.       else
  235.       {
  236.          ReportError(NULL,ERROR_REPORT_MEM,NULL,0);
  237.          success=FALSE;
  238.       }
  239.    }
  240.    else
  241.    {
  242.       ReportError(NULL,ERROR_REPORT_MEM,NULL,0);
  243.       success=FALSE;
  244.    }
  245.  
  246.    return rec_list;
  247. }
  248.  
  249.  
  250.  
  251. /* Function: KillIndexResults
  252.  * ==========================
  253.  */
  254.  
  255. VOID KillIndexResults(struct List *list)
  256. {
  257.    IndexRecord rec;
  258.  
  259.    while(rec=(IndexRecord)RemHead(list))
  260.       KillIndexRecord(rec);
  261.    FreeMem(list,sizeof(struct List));
  262.  
  263.    return;
  264. }
  265.  
  266.  
  267.  
  268. /* Function: DataSearch
  269.  * ====================
  270.  * Searches for one sequence within another sequence.
  271.  */
  272.  
  273. static UBYTE *DataSearch(ULONG length_1,ULONG length_2,UBYTE *buf_1,
  274.    UBYTE *buf_2)
  275. {
  276.    ULONG i,last=length_2-length_1;
  277.    REGISTER UBYTE first=*buf_1;
  278.    BOOL equal=FALSE;
  279.  
  280.    for(i=0;(i<=last)&&!equal;i++)
  281.       {
  282.       if(first==*buf_2) equal=DataEqual(length_1,buf_1,buf_2);
  283.       buf_2++;
  284.       }
  285.  
  286.    if(i<=last) return --buf_2;
  287.    return NULL;
  288. }
  289.  
  290.  
  291.  
  292. /* Function: DataEqual
  293.  * ===================
  294.  * Returns TRUE if two data sequences are equal.
  295.  */
  296.  
  297. static BOOL DataEqual(ULONG length,UBYTE *buf_1,UBYTE *buf_2)
  298. {
  299.    ULONG i;
  300.  
  301.    for(i=0;(i<length)&&(*(buf_1++)==*(buf_2++));i++);
  302.  
  303.    return (i==length);
  304. }
  305.  
  306.  
  307.  
  308. /* Function: KillIndex
  309.  * ===================
  310.  * Destroys an index.
  311.  */
  312.  
  313. VOID KillIndex(Index index)
  314. {
  315.    if(index->index_file!=NULL)
  316.       Close(index->index_file);
  317.    if(index->master_index!=NULL)
  318.       FreeMem(index->master_index,index->block_count*MASTER_REF_SIZE);
  319.    FreeMem(index,sizeof(Index_imp));
  320. }
  321.  
  322.  
  323.  
  324.