home *** CD-ROM | disk | FTP | other *** search
/ CICA 1993 August / CICA.cdr / unzipped / programr / segheap / segheap.c next >
Encoding:
C/C++ Source or Header  |  1992-07-26  |  8.1 KB  |  374 lines
  1. /* Copyright (C) Stephen Chung, 1991-1992.  All rights reserved. */
  2.  
  3. #include <windows.h>
  4.  
  5. #define MAGIC           0x42022667
  6.  
  7. typedef struct MemoryStruct {
  8.     long int magic;
  9.     void far *page;
  10.     unsigned int size;
  11.     BOOL allocated;
  12.     struct MemoryStruct far *next, far *prev;
  13. } MEMHEADER;
  14.  
  15. typedef struct PageHeaderStruct {
  16.     long int magic;
  17.     HANDLE handle;
  18.     unsigned int size;
  19.     unsigned int used;
  20.     unsigned int overhead;
  21.     MEMHEADER far *data, far *empty;
  22.     struct PageHeaderStruct far *next, far *prev;
  23. } MEMPAGEHEADER;
  24.  
  25. typedef struct {
  26.     MEMPAGEHEADER far *pages;
  27.     int nr_pages;
  28. } MAINMEMHEADER;
  29.  
  30. #define PAGESIZE        (4 * 1024)
  31. #define USEABLESIZE     (PAGESIZE - sizeof(MEMPAGEHEADER) - sizeof(MEMHEADER))
  32.  
  33.  
  34. static MAINMEMHEADER header = { NULL, 0 };
  35.  
  36.  
  37.  
  38. static MEMPAGEHEADER far *AddPage(unsigned int n)
  39. {
  40.     void far *cp;
  41.     MEMHEADER far *mp;
  42.     MEMPAGEHEADER far *p;
  43.     HANDLE handle = NULL;
  44.  
  45.     handle = GlobalAlloc(GHND, n);
  46.     if (handle == NULL) {
  47.         ErrorMessage("Out of memory: allocating %d bytes", n);
  48.         return (NULL);
  49.     }
  50.  
  51.     if (header.pages == NULL || header.nr_pages <= 0) {
  52.         p = header.pages = (MEMPAGEHEADER far *) GlobalLock(handle);
  53.         p->prev = NULL;
  54.     } else {
  55.         for (p = header.pages; p->next != NULL; p = p->next);
  56.         p->next = (MEMPAGEHEADER far *) GlobalLock(handle);
  57.         p->next->prev = p;
  58.         p = p->next;
  59.     }
  60.  
  61.     p->magic = MAGIC;
  62.     p->handle = handle;
  63.     p->next = NULL;
  64.     p->size = n;
  65.     p->used = 0;
  66.     p->overhead = sizeof(MEMPAGEHEADER) + sizeof(MEMHEADER);
  67.  
  68.     cp = ((char far *) p) + sizeof(MEMPAGEHEADER);
  69.     mp = (MEMHEADER far *) cp;
  70.  
  71.     p->data = p->empty = mp;
  72.  
  73.     mp->magic = 0L;
  74.     mp->allocated = FALSE;
  75.     mp->page = p;
  76.     mp->size = p->size - p->overhead;
  77.     mp->next = mp->prev = NULL;
  78.  
  79.     header.nr_pages++;
  80.  
  81.     return (p);
  82. }
  83.  
  84.  
  85.  
  86. static void DeletePage (MEMPAGEHEADER far *p)
  87. {
  88.     if (p->next == NULL && p->prev == NULL) {
  89.         header.pages = NULL;
  90.         header.nr_pages = 0;
  91.         GlobalFree(GlobalUnlock(p->handle));
  92.     } else {
  93.         if (p == header.pages) header.pages = p->next;
  94.         header.nr_pages--;
  95.  
  96.         if (p->prev != NULL) p->prev->next = p->next;
  97.         if (p->next != NULL) p->next->prev = p->prev;
  98.  
  99.         GlobalFree(GlobalUnlock(p->handle));
  100.     }
  101. }
  102.  
  103.  
  104.  
  105. void far *SegHeapAlloc (unsigned int n)
  106. {
  107.     MEMPAGEHEADER far *p;
  108.     MEMHEADER far *mp;
  109.     char far *cp;
  110.  
  111.     if (n >= 65535) {
  112.         ErrorMessage("MyGlobalAlloc: size (%u) > 64K!", n);
  113.         return (NULL);
  114.     }
  115.  
  116.     /* Larger than page size? */
  117.  
  118.     if (n > USEABLESIZE) {
  119.         p = AddPage(n + sizeof(MEMPAGEHEADER) + sizeof(MEMHEADER));
  120.  
  121.         mp = p->data;
  122.         mp->magic = MAGIC;
  123.         mp->allocated = TRUE;
  124.  
  125.         p->used = n;
  126.         p->empty = NULL;
  127.  
  128.         cp = ((char far *) mp) + sizeof(MEMHEADER);
  129.         return ((void far *) cp);
  130.     }
  131.  
  132.  
  133.     /* Search for the hole */
  134.  
  135.     for (p = header.pages; p != NULL; p = p->next) {
  136.         /* Scan the chains */
  137.         if (p->size - p->used - p->overhead <= 0) continue;
  138.         if (p->empty == NULL) continue;
  139.  
  140.         for (mp = p->empty; mp != NULL; mp = mp->next) {
  141.             if (!mp->allocated && mp->size >= n) break;
  142.         }
  143.  
  144.         if (mp != NULL) break;
  145.     }
  146.  
  147.     /* New page needed? */
  148.  
  149.     if (p == NULL) {
  150.         p = AddPage(PAGESIZE);
  151.         mp = p->data;
  152.     }
  153.  
  154.     /* Do we need to break it up? */
  155.  
  156.     if (mp->size - n > sizeof(MEMHEADER)) {
  157.         MEMHEADER far *mp2;
  158.  
  159.         cp = ((char far *) mp) + n + sizeof(MEMHEADER);
  160.         mp2 = (MEMHEADER far *) cp;
  161.  
  162.         mp2->magic = 0L;
  163.         mp2->allocated = FALSE;
  164.         mp2->page = p;
  165.         mp2->size = mp->size - n - sizeof(MEMHEADER);
  166.  
  167.         mp2->next = mp->next;
  168.         mp2->prev = mp;
  169.         if (mp->next != NULL) mp->next->prev = mp2;
  170.         mp->next = mp2;
  171.  
  172.  
  173.         p->overhead += sizeof(MEMHEADER);
  174.  
  175.         mp->size = n;
  176.     }
  177.  
  178.     mp->magic = MAGIC;
  179.     mp->allocated = TRUE;
  180.  
  181.     p->used += n;
  182.     cp = ((char far *) mp) + sizeof(MEMHEADER);
  183.  
  184.     /* Search for the next empty hole */
  185.  
  186.     for (; mp != NULL; mp = mp->next) {
  187.         if (!mp->allocated && mp->size > 0) break;
  188.     }
  189.  
  190.     p->empty = mp;
  191.  
  192.     return ((void far *) cp);
  193. }
  194.  
  195.  
  196. void SegHeapFree (void far *vp)
  197. {
  198.     MEMPAGEHEADER far *p;
  199.     MEMHEADER far *mp, far *mp2;
  200.     char far *cp;
  201.  
  202.     cp = ((char far *) vp) - sizeof(MEMHEADER);
  203.     mp = (MEMHEADER far *) cp;
  204.  
  205.     if (mp->magic != MAGIC || !mp->allocated) {
  206.         ErrorMessage("Trying to deallocate invalid memory block [%Fp, %u byte%s]!\n",
  207.                         vp, mp->size, (mp->size > 1) ? "s" : "");
  208.         return;
  209.     }
  210.  
  211.     p = (MEMPAGEHEADER far *) mp->page;
  212.     p->used -= mp->size;
  213.  
  214.     mp->magic = 0L;
  215.     mp->allocated = FALSE;
  216.  
  217.     /* Merge? */
  218.  
  219.     mp2 = mp->prev;
  220.  
  221.     if (mp2 != NULL && !mp2->allocated) {
  222.         mp2->next = mp->next;
  223.         if (mp->next != NULL) mp->next->prev = mp2;
  224.         mp2->size += mp->size + sizeof(MEMHEADER);
  225.  
  226.         p->overhead -= sizeof(MEMHEADER);
  227.  
  228.         mp = mp2;
  229.     }
  230.  
  231.     mp2 = mp->next;
  232.  
  233.     if (mp2 != NULL && !mp2->allocated) {
  234.         mp->next = mp2->next;
  235.         if (mp2->next != NULL) mp2->next->prev = mp;
  236.  
  237.         mp->size += mp2->size + sizeof(MEMHEADER);
  238.  
  239.         p->overhead -= sizeof(MEMHEADER);
  240.     }
  241.  
  242.     if (mp->prev == NULL && mp->next == NULL) {
  243.         DeletePage(p);
  244.     } else {
  245.         if (p->empty == NULL || mp < p->empty) p->empty = mp;
  246.     }
  247. }
  248.  
  249.  
  250.  
  251. void far *SegHeapRealloc (void far *p, unsigned int n)
  252. {
  253.     MEMHEADER far *mp;
  254.     char far *cp;
  255.  
  256.     /* Block already large enough? */
  257.  
  258.     cp = ((char far *) p) - sizeof(MEMHEADER);
  259.     mp = (MEMHEADER far *) cp;
  260.  
  261.     if (mp->magic != MAGIC) {
  262.         ErrorMessage("Trying to reallocate invalid memory block [%Fp, %u byte%s]!\n",
  263.                         p, mp->size, (mp->size > 1) ? "s" : "");
  264.         return (p);
  265.     }
  266.  
  267.     if (mp->size >= n) return (p);      /* No need to do anything */
  268.  
  269.     /* Else swap to another block */
  270.  
  271.     cp = SegHeapAlloc(n);
  272.     _fmemcpy(cp, p, (mp->size >= n) ? n : mp->size);
  273.     SegHeapFree(p);
  274.  
  275.     /* This is not really safe
  276.     SegHeapFree(p);
  277.     cp = SegHeapAlloc(n);
  278.     if ((void far *) cp != p) {
  279.         _fmemcpy(cp, p, (mp->size >= n) ? n : mp->size);
  280.     }
  281.     */
  282.  
  283.     return ((void far *) cp);
  284. }
  285.  
  286.  
  287.  
  288. unsigned int SegHeapGetSize (void far *p)
  289. {
  290.     MEMHEADER far *mp;
  291.     char far *cp;
  292.  
  293.     cp = ((char far *) p) - sizeof(MEMHEADER);
  294.  
  295.     mp = (MEMHEADER far *) cp;
  296.  
  297.     if (mp->magic != MAGIC) {
  298.         ErrorMessage("Trying to get size of invalid memory block [%Fp, %u byte%s]!\n",
  299.                         p, mp->size, (mp->size > 1) ? "s" : "");
  300.         return (0);
  301.     }
  302.  
  303.     return (mp->size);
  304. }
  305.  
  306.  
  307.  
  308. void far *SegHeapDuplicate (void far *p)
  309. {
  310.     unsigned int len;
  311.     void far *p1;
  312.  
  313.     len = SegHeapGetSize(p);
  314.     p1 = SegHeapAlloc(len);
  315.     _fmemcpy(p1, p, len);
  316.  
  317.     return (p1);
  318. }
  319.  
  320.  
  321.  
  322. void MemoryStatistics (long int *allocated, long int *used, long int *overhead)
  323. {
  324.     MEMPAGEHEADER far *p;
  325.  
  326.     *allocated = *used = *overhead = 0L;
  327.  
  328.     for (p = header.pages; p != NULL; p = p->next) {
  329.         *allocated += p->size;
  330.         *used += p->used;
  331.         *overhead += p->overhead;
  332.     }
  333. }
  334.  
  335.  
  336. void FreeAllMemory (void)
  337. {
  338.     MEMPAGEHEADER far *p, far *p1;
  339.  
  340.     for (p = header.pages; p != NULL; ) {
  341.         p1 = p->next;
  342.         GlobalFree(GlobalUnlock(p->handle));
  343.         p = p1;
  344.     }
  345.  
  346.     header.pages = NULL;
  347.     header.nr_pages = 0;
  348. }
  349.  
  350.  
  351. #ifdef DEBUG
  352.  
  353. /* For debugging purposes...  not very pretty */
  354.  
  355. void PrintMemoryChains(void)
  356. {
  357.     MEMPAGEHEADER far *p;
  358.     MEMHEADER far *mp;
  359.     char far *cp;
  360.     char buffer[100];
  361.  
  362.     /* Block already large enough? */
  363.  
  364.  
  365.     for (p = header.pages; p != NULL; p = p->next) {
  366.         for (mp = p->data; mp != NULL; mp = mp->next) {
  367.             sprintf(buffer, "%Fp | %u | %s", mp, mp->size, mp->allocated ? "Alloc" : "Free");
  368.             MessageBox (NULL, buffer, "Memory Chain", MB_ICONEXCLAMATION | MB_OK);
  369.         }
  370.     }
  371. }
  372.  
  373. #endif DEBUG
  374.