home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_02_11 / 2n11018a < prev    next >
Text File  |  1991-09-13  |  8KB  |  294 lines
  1. /* ----------------------------------------------------
  2.  *  LISTING 1
  3.  *
  4.  *  Filename:           bcache.c
  5.  *  Summary:            block cache manager functions
  6.  *  Author:             T.W. Nelson
  7.  *  Compile options:    
  8.  *  Version:            1.00
  9.  *  Date:               04-Sep-1991
  10.  *  Notes:
  11.  *
  12.  *  Source code Copyright (c) 1991 T.W. Nelson. May be
  13.  *  used only for non-commercial purposes with
  14.  *  appropriate acknowledgement of copyright.
  15.  * ------------------------------------------------- */
  16.  
  17. #include <stdio.h>
  18. #include <alloc.h>
  19. #include <dos.h>
  20. #include "bcache.h"
  21. #include <assert.h>
  22.  
  23. //Pointer to default memory allocator function.
  24. //This pointer may be redirected to a customized
  25. //allocator via bc_setalloc() before calling
  26. //bc_open()........
  27. //
  28. static int (*allocp)(BCACHE *cp, int flag) = bc_alloc;
  29.  
  30. int bc_open( BCACHE *cp,    //-> cache descriptor
  31.              int bmax,      //number of blocks
  32.              int bsize,     //size of each block
  33.              void (*proc)(), //processing function
  34.              idnt_t *idnt  )  //cache identifier
  35. {
  36.    /* Open and initialize block cache data
  37.     * structures
  38.     */
  39.  
  40.     int i;
  41.     chdr_t *p;
  42.     chdr_t *q;
  43.  
  44.     if( bmax < 2 )
  45.             return BC_NOBLOCKS;
  46.  
  47.     cp->idnt = idnt;
  48.     cp->bsiz = bsize;
  49.     cp->bmax = bmax;
  50.     cp->proc = proc;
  51.     cp->hits = cp->miss = cp->adds = 0L;
  52.  
  53.     if( (*allocp)( cp, ALLOCATE ) == BC_NOMEMORY )
  54.             return BC_NOMEMORY;
  55.  
  56.     /* setup intial mfru/lfru chain .... */
  57.     cp->mfru = cp->head;
  58.     p = cp->mfru;
  59.     q = GROUND;
  60.  
  61.     for( i = bmax; i ; i-- )    {
  62.             p->stat = RELEASE;
  63.             p->idnt = idnt;
  64.             p->bnum = -1L;
  65.             p->acc  = 0L;
  66.             p->prev = q;
  67.             q = p;
  68.             (size_t) p += BHDR_SIZE + bsize;
  69.             q->next = p;
  70.     }
  71.  
  72.     q->next = GROUND;
  73.     cp->lfru = q;
  74.  
  75.     return BC_NOERROR;          //success
  76. }
  77.  
  78. int bc_setalloc( int (*user_alloc)() )
  79. {
  80.    /* Install a new memory allocator function
  81.     * for bc_open().
  82.     */
  83.  
  84.     allocp = user_alloc;
  85.     return BC_NOERROR;
  86. }
  87.  
  88. int bc_alloc( BCACHE *c,
  89.               int flag )    //alloc/dealloc flag
  90. {
  91.    /* Allocate cache memory on the heap using the
  92.     * given cache parameters. 'c->head' must be
  93.     * initialized to point to the allocated array.
  94.     * This is the default memory allocation method
  95.     * using malloc().
  96.     */
  97.  
  98.     size_t mem;
  99.  
  100.     if( flag == ALLOCATE )  {
  101.         mem = (c->bsiz+BHDR_SIZE) * c->bmax;
  102.  
  103.         if((c->head = (chdr_t *) malloc( mem )) ==
  104.                                        (chdr_t *) 0 )
  105.                 return BC_NOMEMORY;
  106.     }
  107.     else    {       //deallocate memory
  108.         #if defined(__SMALL__) || defined(__MEDIUM__)
  109.             free( (void *) FP_OFF(c->head) );
  110.         #else
  111.             free( (void *) c->head );
  112.         #endif
  113.     }
  114.  
  115.     return BC_NOERROR;
  116. }
  117.  
  118. int bc_free( BCACHE *c )
  119. {
  120.    /* Perform block postprocessing and free all
  121.     * cache memory
  122.     */
  123.  
  124.     bc_flush(c);
  125.     (*allocp)( c, DEALLOCATE );
  126.     c->head = c->mfru = c->lfru = (bufp_t *) 0;
  127.  
  128.     return BC_NOERROR;
  129. }
  130.  
  131. int bc_search( BCACHE *c,       //-> cache descriptor
  132.                ulong bnum,      //block # (0-based)
  133.                bufp_t **bufptr) //-> buffer to assign
  134. {
  135.    /* Search for the given block number in the cache
  136.     * list.  Assign 'bufptr' to point to the found
  137.     * block buffer. Returns NOTFOUND if block number
  138.     * not present.
  139.     */
  140.  
  141.     chdr_t *p = c->mfru;
  142.  
  143.     for( ; p != GROUND; p = p->next ) {
  144.         assert( c->idnt == p->idnt );
  145.  
  146.         if( p->bnum == bnum )   {   //found
  147.             c->hits++;
  148.             p->acc += c->bmax;
  149.             bc_insert( c, p );   //re-insert in chain
  150.             *bufptr = BLOCK_PTR(bufp_t,p);
  151.             return BC_NOERROR;
  152.         }
  153.     }
  154.  
  155.     c->miss++;
  156.     *bufptr = (bufp_t *) 0;
  157.     return BC_NOTFOUND;
  158. }
  159.  
  160. int  bc_insert( BCACHE *c,      //-> cache descriptor
  161.                 chdr_t *p )     //block to re-insert
  162. {
  163.    /* Take the indicated block out of the chain
  164.     * and re-insert it in a new position based on
  165.     * its access count.
  166.     */
  167.  
  168.     chdr_t *q;      //previous block
  169.     chdr_t *r;      //next block
  170.  
  171.     if( p == c->mfru )     //already mfru, return
  172.             return BC_NOERROR;
  173.  
  174.     //disconnect the block from the chain ...
  175.     q = p->prev;
  176.     r = p->next;
  177.     assert( q != GROUND );
  178.     q->next = r;
  179.  
  180.     if( p == c->lfru )      //p is current lfru block
  181.             c->lfru = q;    //prev block is new lfru
  182.     else    {
  183.             assert( r != GROUND );  //not lfru!
  184.             r->prev = q;
  185.     }
  186.  
  187.     //Search thru remaining chain for insertion point,
  188.     //decrementing all access counts by 1 on the way...
  189.     for(r = 0, q = c->mfru; q != GROUND; q = q->next) {
  190.             if( q->acc != 0L )
  191.                     --(q->acc);
  192.  
  193.             if( r == 0 && (p->acc >= q->acc) )
  194.                     r = q;      //r = insertion point
  195.     }
  196.  
  197.     //Insert 'p' between 'q' and 'r'.....
  198.     if( r == 0 )    {
  199.             //Insertion point is beyond current lfru.
  200.             //Re-connect 'p' as the new lfru.....
  201.             q = c->lfru;
  202.             q->next = p;
  203.             p->prev = q;
  204.             p->next = GROUND;
  205.             c->lfru = p;
  206.  
  207.             return BC_NOERROR;
  208.     }
  209.  
  210.     q = r->prev;            //back up one
  211.     p->next = r;
  212.     p->prev = q;
  213.     r->prev = p;
  214.  
  215.     if( q == GROUND )
  216.             c->mfru = p;    //assign new mfru
  217.     else    {
  218.             q->next = p;
  219.     }
  220.  
  221.     return BC_NOERROR;
  222. }
  223.  
  224. int bc_addnew( BCACHE *c, ulong bnum, bufp_t **bufptr)
  225. {
  226.    /* A block was not found in the cache. Re-use the
  227.     * lfru block by re-numbering it and reinserting in
  228.     * the cache list. Assigned access count is bmax/2,
  229.     * which gives it lower priority than a cache hit,
  230.     * since there's no a priori reason to assume it's
  231.     * going to be accessed again.
  232.     */
  233.  
  234.     chdr_t *p = c->lfru;
  235.  
  236.     assert( p->next == GROUND );
  237.  
  238.     // process block if marked ....
  239.     if( p->stat == MARK && c->proc )
  240.             (*(c->proc))( c->idnt, p->bnum,
  241.                             BLOCK_PTR( bufp_t, p ));
  242.     p->stat = RELEASE;  //free block for reuse
  243.     c->adds++;
  244.     p->acc = c->bmax/2; //assign usage cnt
  245.     p->bnum = bnum;     //re-number lfru
  246.     bc_insert( c, p );  //re-insert in chain
  247.     *bufptr = BLOCK_PTR(bufp_t,p);
  248.  
  249.     return BC_NOERROR;
  250. }
  251.  
  252. int bc_mark( BCACHE *c, ulong bnum, size_t flag )
  253. {
  254.    /* Find and mark/unmark a block.
  255.     * Marking a block defers processing (writing)
  256.     * for later.
  257.     */
  258.  
  259.     chdr_t *p = 0;
  260.  
  261.     for( p = c->mfru; p != GROUND; p = p->next ) {
  262.             assert( c->idnt == p->idnt );
  263.  
  264.             if( p->bnum == bnum )   {   //found
  265.                     p->stat = flag;
  266.                     return BC_NOERROR;
  267.             }
  268.     }
  269.  
  270.     return BC_NOTFOUND;
  271. }
  272.  
  273. int bc_flush( BCACHE *c )
  274. {
  275.    /* Process and free all marked records.
  276.     */
  277.  
  278.     chdr_t *p = 0;
  279.  
  280.     if( !(c->proc) )
  281.             return BC_NOERROR;
  282.  
  283.     for( p = c->mfru; p != GROUND; p = p->next ) {
  284.             assert( c->idnt == p->idnt );
  285.             (*(c->proc))( c->idnt, p->bnum,
  286.                             BLOCK_PTR( bufp_t, p ));
  287.             p->stat = RELEASE;
  288.     }
  289.  
  290.     return BC_NOERROR;
  291. }
  292.  
  293. /* ---- End of File -------------------------------- */
  294.