home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_07_04 / v7n4010a.txt < prev    next >
Text File  |  1989-03-07  |  3KB  |  124 lines
  1. Figure 1
  2.  
  3.  
  4.  
  5. freelist
  6.        \
  7. --------\-----+-----+-----+-----+-----+-----+-----+--------
  8.   . . . |\    |     |     |     |     |     |     |. . . . 
  9.   . . . | >  --->  --->  --->  --->  --->  ---> 0 |. . . .
  10.   . . . |     |     |     |     |     |     |     |. . . .
  11. --------+-----+-----+-----+-----+-----+-----+-----+--------
  12.  
  13.  
  14. Figure 2
  15.  
  16.  
  17.  
  18. freelist ---------\          --------------
  19.                    \        /              \
  20. --------+-----+-----\-----+/----+-----+-----\-----+--------
  21.   . . . | in  | in  |\    / in  |     | in  |\    |. . . . 
  22.   . . . | use | use | >  /| use | > 0 | use | > / |. . . .
  23.   . . . |     |     |     |     |  \  |     |  /  |. . . .
  24. --------+-----+-----+-----+-----+---\-+-----+-/---+--------
  25.                                      \       /
  26.                                       -------
  27.  
  28. Listing 1
  29.  
  30. mem.h
  31. -----
  32. /* mem.h - defs for fixed size block memory allocator */
  33.  
  34. typedef int Align;
  35.  
  36. union freelist {
  37.         union freelist *next;   /* next block on free list */
  38.         char memory;            /* user data */
  39.         Align aligner;          /* force alignment of blocks */
  40. };
  41.  
  42. typedef union freelist Freelist;
  43.  
  44. struct freelist_head {
  45.         int size;   /* size of a single elt incl. next ptr */
  46.         int bytes;  /* if we run out, allocate memory by this many bytes */
  47.         Freelist *freelist;
  48. };
  49.  
  50. char *sbrk(), *new();
  51. /* end of mem.h */
  52.  
  53.  
  54. Listing 2
  55.  
  56.  
  57. mem.c
  58. -----
  59. /* mem.c - subroutines to allocate fixed-size blocks */
  60.  
  61. #include <stdio.h>
  62. #include "mem.h"
  63.  
  64. /* chop up big block into linked list of small blocks */
  65. Freelist * /* return 0 for failure */
  66. create_freelist(flh,bytes)
  67. struct freelist_head *flh;      /* freelist head */
  68. int bytes;                      /* new memory size */
  69. {
  70.         Freelist *current = (Freelist *)sbrk(bytes);
  71.         if ((Freelist *)-1 == current) return(0);
  72.         flh->freelist = current;
  73.         while ((char *)current + flh->size <
  74.                         ((char *)flh->freelist + bytes)) {
  75.                 current-next = (Freelist *)(¤t->memory + flh->size);
  76.                 current = current->next;
  77.         }
  78.         current->next = NULL;
  79.         return(current);
  80. }
  81.  
  82. memory_init(flh,size,alloc1,alloc2)
  83. struct freelist_head *flh;      /* freelist head */
  84. int size;                       /* size of a single element */
  85. int alloc1;                     /* number to allocate initially */
  86. int alloc2;                     /* number to allocate if we run out */
  87. {
  88.         /* make block large enough to hold the linked list pointer */
  89.         flh->size = (size>sizeof(Freelist *)?size:sizeof(Freelist *));
  90.         /* set up for future allocations */
  91.         flh->bytes = flh->size * alloc2;
  92.  
  93.         if (0 == create_freelist(flh,flh->size*alloc1)) {
  94.                 fprintf(stderr,"memory_init: out of space");
  95.                 exit(-1);
  96.         }
  97. }
  98.  
  99. char *
  100. new(flh)
  101. struct freelist_head *flh;
  102. {
  103.         char *obj;
  104.  
  105.         if (flh->freelist == NULL && 0 == create_freelist(flh,flh->bytes)) {
  106.                 fprintf(stderr,"new: out of space");
  107.                 return(0);
  108.         }
  109.  
  110.         obj = &flh->freelist->memory;
  111.         flh->freelist = flh->freelist->next;
  112.  
  113.         return(obj);
  114. }
  115.  
  116. delete(flh,link)
  117. struct freelist_head *flh;
  118. Freelist *link;
  119. {
  120.         link->next = flh->freelist;
  121.         flh->freelist = link; 
  122. } 
  123.  
  124.