home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1987 / 12 / deikman / cache.c next >
Text File  |  1987-12-21  |  6KB  |  254 lines
  1. /* cache.c - memory cache
  2.  
  3.   alan deikman 12/86
  4.  
  5.   These routines handle a memory cache of fixed sized records.
  6.   All memory is allocated through the standard library routine
  7.   malloc().  
  8.  
  9.   Each routine other than cacallo() takes as the first parameter
  10.   a character pointer that is originally returned by the cacallo()
  11.   routine.
  12.  
  13.   cacallo()    Allocate cache
  14.   cacold()    Get oldest record
  15.   cacnum()    Number oldest record and make it the newest
  16.   cacflsh()    Process all marked records
  17.   cacfind()    Find record n and make it newest
  18.   cacproc()    Mark record for processing when freed
  19.   cacunpc()    Unmark record for processing when freed
  20.   cacstat()    Get cache statistics
  21.   cacfree()    Free cache
  22.  
  23.   */
  24.  
  25. #include <stdio.h>
  26. #include <malloc.h>
  27. #include "cache.h"
  28.  
  29. /* cacallo() - Allocate cache */
  30.  
  31. CACDS *cacallo(num, recl, extf, idnt)
  32. int    num;        /* number of records to allocate */
  33. int    recl;        /* length of each record */
  34. int    (*extf)();    /* pointer to external processing function */
  35. long    idnt;        /* parameter passed to external function */
  36. {
  37.   CACDS    *cac;
  38.   char    *cacmem();
  39.   int    i = 0;
  40.  
  41.   /* set up cac structure with initial values */
  42.   
  43.   if (num < 2) num = 2;
  44.   cac = (CACDS *) cacmem(sizeof(CACDS));
  45.   cac->recl = recl;
  46.   cac->maxr = num;
  47.   cac->proc = extf;
  48.   cac->idnt = idnt;
  49.   cac->hits = 
  50.   cac->miss = 
  51.   cac->adds = 0L;
  52.   cac->nums = (long *)  cacmem(num * sizeof(long));
  53.   cac->next = (short *) cacmem(num * sizeof(short));
  54.   cac->prio = (short *) cacmem(num * sizeof(short));
  55.   cac->mark = cacmem(num);
  56.   cac->recs = cacmem(num * recl);
  57.  
  58.   /* initial lru/mru chain */
  59.   
  60.   while (i < num) {
  61.     cac->next[i] = i + 1;
  62.     cac->prio[i] = i - 1;
  63.     cac->nums[i] = -1;
  64.     cac->mark[i] = 0;
  65.     i++; }
  66.  
  67.   cac->next[num - 1] = cac->prio[0] = -1;
  68.   cac->mru = 0;
  69.   cac->lru = num - 1;
  70.  
  71.   /* return cache pointer */
  72.  
  73.   return cac; }
  74.  
  75.  
  76. /* allocate memory with error checking */
  77.  
  78. char *cacmem(siz)
  79. int    siz;
  80. {
  81.   char *c;
  82.   c = malloc(siz);
  83.   if (c == (char *) 0) {
  84.     fprintf(stderr, "cacallo:  Can't allocate memory.\n");
  85.     fprintf(stderr, "Tried to get %d bytes on top of %ld bytes already\n",
  86.             siz, cacamem);
  87.     exit(1); }
  88.   cacamem += siz;
  89.   return c; }
  90.  
  91. /* number oldest record and make it the newest.  if the record was
  92.    marked for exit procesing, call external processing function.
  93.    return pointer to record */
  94.  
  95. char *cacnum(cac, num)
  96. CACDS    *cac;        /* cache header */
  97. long    num;        /* number new MRU record */
  98. {
  99.   char    *rec = cac->recs + (cac->lru * cac->recl);
  100.  
  101.   /* call external function */
  102.  
  103.   if (cac->mark[cac->lru] && cac->proc)
  104.     (*(cac->proc))(cac->idnt, cac->nums[cac->lru], rec);
  105.  
  106.   /* unmark record and make it newest */
  107.  
  108.   cac->mark[cac->lru] = 0;
  109.   cac->adds++;
  110.   cac->nums[cac->lru] = num;
  111.   cacnew(cac, cac->lru);
  112.  
  113.   /* return record; ready for usage */
  114.  
  115.   return rec; }
  116.  
  117.  
  118. /* get pointer to oldest record without altering age */
  119.  
  120. char *cacold(cac)
  121. CACDS    *cac;        /* cache header */
  122. {
  123.   return cac->recs + (cac->lru * cac->recl); }
  124.  
  125.  
  126. /* if an exit processing routine has been defined, process all marked
  127.    records */
  128.  
  129. cacflsh(cac)
  130. CACDS    *cac;        /* cache header */
  131. {
  132.   int    i;
  133.   char    *rec;
  134.  
  135.   if (!(cac->proc)) return;
  136.  
  137.   for (i = 0; i < cac->maxr; i++) if (cac->mark[i]) {
  138.     rec = cac->recs + (i * cac->recl);
  139.     (*(cac->proc))(cac->idnt, cac->nums[i], rec);
  140.     cac->mark[i] = 0; }
  141.  
  142.   return; }
  143.  
  144.  
  145. /* make record newest */
  146.  
  147. cacnew(cac, rec)
  148. CACDS    *cac;        /* cache header */
  149. short    rec;        /* record to make newest */
  150. {
  151.  
  152.   /* if this record is already the newest, just return */
  153.  
  154.   if (rec == cac->mru) return;
  155.  
  156.   /* change prior's next */
  157.  
  158.   cac->next[cac->prio[rec]] = cac->next[rec];
  159.  
  160.   /* change next's prior - if there was no next that means this was the
  161.      lru record.  change lru */
  162.  
  163.   if (cac->next[rec] != -1)
  164.     cac->prio[cac->next[rec]] = cac->prio[rec];
  165.   else {
  166.     if (rec != cac->lru) {
  167.       fprintf(stderr, "cacnew: panic\n");
  168.       exit(1); }
  169.     cac->lru = cac->prio[rec]; }
  170.  
  171.   /* now the record is out of the chain.  stick it back in at the mru end. */
  172.  
  173.   cac->prio[cac->mru] = rec;
  174.   cac->next[rec]      = cac->mru;
  175.   cac->prio[rec]      = -1;
  176.   cac->mru            = rec;
  177.  
  178.   /* done */
  179.  
  180.   return; }
  181.  
  182. /* find record and make it newest */
  183.  
  184. char *cacfind(cac, num)
  185. CACDS    *cac;        /* cache header */
  186. long    num;        /* record number to look for */
  187. {
  188.   int i;
  189.  
  190.   for (i = 0; i < cac->maxr; i++) if (cac->nums[i] == num) {
  191.     cac->hits++;
  192.     cacnew(cac, i);
  193.     return cac->recs + (i * cac->recl); }
  194.  
  195.   cac->miss++;
  196.   return (char *) 0; }
  197.  
  198. /* mark record for external processing */
  199.  
  200. cacproc(cac, num)
  201. CACDS    *cac;        /* cache header */
  202. long    num;        /* record to mark */
  203. {
  204.   int i;
  205.  
  206.   for (i = 0; i < cac->maxr; i++) if (cac->nums[i] == num) {
  207.     cac->mark[i] = 1;
  208.     return; }
  209.  
  210.   return; }
  211.  
  212. /* un-mark record for external processing */
  213.  
  214. cacunpc(cac, num)
  215. CACDS    *cac;        /* cache header */
  216. long    num;        /* record to unmark */
  217. {
  218.   int i;
  219.  
  220.   for (i = 0; i < cac->maxr; i++) if (cac->nums[i] == num) {
  221.     cac->mark[i] = 0;
  222.     return; }
  223.  
  224.   return; }
  225.  
  226. /* get statistics of the cache */
  227.  
  228. cacstat(cac, hit, mis, add)
  229. CACDS    *cac;        /* cache header */
  230. long    *hit, *mis, *add; /* values to return */
  231. {
  232.   *hit = cac->hits;
  233.   *mis = cac->miss;
  234.   *add = cac->adds;
  235.   return; }
  236.  
  237. /* free cache */
  238.  
  239. cacfree(cac)
  240. CACDS    *cac;        /* cache header */
  241. {
  242.   cacflsh(cac);
  243.   cacamem -= sizeof(CACDS) + (cac->maxr * sizeof(long)) +
  244.              (cac->maxr * 2 * sizeof(short)) + (cac->maxr) + 
  245.              (cac->maxr * cac->recl);
  246.   free(cac->recs);
  247.   free(cac->prio);
  248.   free(cac->next);
  249.   free(cac->nums);
  250.   free(cac);
  251.  
  252.   return; }
  253.  
  254.