home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1994 June / NEBULA_SE.ISO / SourceCode / Crossword / Source / FunctionCache.m < prev    next >
Encoding:
Text File  |  1992-10-11  |  3.6 KB  |  185 lines
  1. /*
  2.  
  3. File FunctionCache.m
  4.  
  5. A cache remembers function values, f(x) = y, so that function evaluations can avoid lengthy recomputations.  Each cache has a finite capacity.  When a new value is added to the cache, the cache discards the value that has gone unused for the longest period of time.  It uses a callback function to alert the application that a value is being discarded.  In this way memory can be freed and reclaimed for other uses.
  6.  
  7. */
  8.  
  9. #import <appkit/appkit.h>
  10. #import <stdlib.h>
  11.  
  12. #import "FunctionCache.h"
  13.  
  14.  
  15. /* ————————————————————————————————————————————————————————————————————————————  */
  16.  
  17.  
  18. static void        freeObject    (void *);
  19.  
  20.  
  21. /* ————————————————————————————————————————————————————————————————————————————  */
  22.  
  23.  
  24. @implementation FunctionCache
  25.  
  26.  
  27. - initKey: (const char *) key
  28.         value: (const char *) value
  29.         capacity: (unsigned) theCapacity
  30.         freeKey: (freeFunction) theFreeKey
  31.         freeValue: (freeFunction) theFreeValue;
  32. {
  33.     [super  init];
  34.     
  35.     cache = [[HashTable  alloc]
  36.     
  37.                     initKeyDesc: key
  38.                     valueDesc: "!"
  39.                     capacity: theCapacity ];
  40.     
  41.     capacity = theCapacity;
  42.     freeKey = theFreeKey;
  43.     freeValue = theFreeValue;
  44.     worst = best = NULL;
  45.     
  46.     return self;
  47. }
  48.  
  49.  
  50. - initKeyType: (int) key  valueType: (int) value  capacity: (unsigned) theCapacity;
  51. {
  52.     freeFunction    theFreeKey, theFreeValue;
  53.     char            * type;
  54.     
  55.     switch (key)
  56.     {
  57.         case ISASTRING:        type = "*";        theFreeKey = free;            break;
  58.         case ISAOBJECT:        type = "@";        theFreeKey = freeObject;    break;
  59.         default:            type = NULL;    theFreeKey = NULL;            break;
  60.     }
  61.     
  62.     switch (value)
  63.     {
  64.         case ISASTRING:        theFreeValue = free;        break;
  65.         case ISAOBJECT:        theFreeValue = freeObject;    break;
  66.         default:            theFreeValue = NULL;        break;
  67.     }
  68.     
  69.     [self    initKey: type
  70.             value: NULL
  71.             capacity: theCapacity
  72.             freeKey: theFreeKey
  73.             freeValue: theFreeValue ];
  74.             
  75.     return self;
  76. }
  77.  
  78.  
  79. - free
  80. {
  81.     [self  setCapacity: 0];
  82.     [cache  free];
  83.     
  84.     return [super  free];
  85. }
  86.  
  87.  
  88. - setCapacity: (unsigned) theCapacity
  89. {
  90.     while ([cache  count] > theCapacity) [self  remove: worst->key];
  91.     capacity = theCapacity;
  92.     
  93.     return self;
  94. }
  95.  
  96.  
  97. /* ————————————————————————————————————————————————————————————————————————————  */
  98.  
  99.  
  100. - add: (void *) key  value: (void *) value;
  101. {
  102.     cacheElement    * new;
  103.     
  104.     new = (cacheElement *) malloc(sizeof(cacheElement));
  105.     new->key = key;
  106.     new->value = value;
  107.     new->previous = NULL;
  108.     new->next = best;
  109.     if (best != NULL) best->previous = new;
  110.     
  111.     [self  release: [self  detach: [cache  insertKey: key  value: new]]];
  112.     
  113.     best = new;
  114.     if (worst == NULL) worst = new;
  115.     if ([cache  count] > capacity) [self  remove: worst->key];
  116.     
  117.     return self;
  118. }
  119.  
  120.  
  121. - remove: (void *) key;
  122. {
  123.     [self  release: [self  detach: [cache  removeKey: key]]];
  124.     return self;
  125. }
  126.  
  127.  
  128. - (void *) find: (void *) key;
  129. {
  130.     cacheElement    * cell;
  131.     
  132.     if ((cell = (cacheElement *) [cache  valueForKey: key]) != NULL)
  133.     {
  134.         [self  detach: cell];
  135.         cell->next = best;
  136.         if (best != NULL) best->previous = cell;
  137.         best = cell;
  138.         if (worst == NULL) worst = cell;
  139.     }
  140.     
  141.     return (cell == NULL) ? NULL:cell->value;
  142. }
  143.  
  144.  
  145. - (cacheElement *) detach: (cacheElement *) cell
  146. {
  147.     if (cell != NULL)
  148.     {
  149.         if (cell->previous) cell->previous->next = cell->next;
  150.         if (cell->next) cell->next->previous = cell->previous;
  151.         if (best == cell) best = cell->next;
  152.         if (worst == cell) worst = cell->previous;
  153.         cell->previous = cell->next = NULL;
  154.     }
  155.     
  156.     return cell;
  157. }
  158.  
  159.  
  160. - release: (cacheElement *) cell
  161. {
  162.     if (cell != NULL)
  163.     {
  164.         if (freeKey != NULL) (* freeKey)(cell->key);
  165.         if (freeValue != NULL) (* freeValue)(cell->value);
  166.         free(cell);
  167.     }
  168.     
  169.     return self;
  170. }
  171.  
  172.  
  173. @end
  174.  
  175.  
  176. /* ————————————————————————————————————————————————————————————————————————————  */
  177.  
  178.  
  179. static void    freeObject    (object)
  180.  
  181. void        * object;
  182.  
  183. {
  184.     [(id) object  free];
  185. }