home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / primcuts.zip / priority_queue.c < prev    next >
Text File  |  2000-05-27  |  7KB  |  294 lines
  1. /*
  2.  * This program will create a priority queue implemented as a heap.
  3.  * A heap is a 'balanced tree'
  4.  * A priority queue is a nifty thing. You insert nodes into the queue, each
  5.  * node has a priority. You can then get the first node which always has the
  6.  * top priority.
  7.  *
  8.  * You won't be able to use this source directly in any project. It's not
  9.  * generic enough. ToDo to make it more modular:
  10.  *  - In the PQUEUE structre; add two new entries:
  11.  *      1. A function pointer to a function which will be used to compare
  12.  *         nodes.
  13.  *      2. A node-size variable.
  14.  *  - You need to design a function which will compare two nodes.
  15.  *  - If you're planning on using the queue in multithreaded/shared
  16.  *    application you'll need another variable in the PQUEUE structure:
  17.  *    a mutex sempahore handle. In OS/2, it's common design to make all
  18.  *    libraries multithread safe. Remember to request (and release) the mutex
  19.  *    sempahores in the push and pop functions.
  20.  *
  21.  * References:
  22.  *  http://hissa.ncsl.nist.gov/~black/CRCDict/
  23.  *  http://www.ee.uwa.edu.au/~plsd210/ds/
  24.  */
  25. #pragma strings(readonly)
  26.  
  27. #define INCL_DOSMEMMGR
  28. #define INCL_DOSEXCEPTIONS
  29. #define INCL_DOSERRORS
  30.  
  31. #include <os2.h>
  32.  
  33. #include <memory.h>
  34. #include <stdlib.h>
  35. #include <stdio.h>
  36. #include <time.h>
  37.  
  38.  
  39. /*
  40.  * Each node in the priority queue
  41.  */
  42. typedef struct _NODE
  43. {
  44.    ULONG event;
  45.    ULONG priority;
  46.    PVOID param1;
  47.    PVOID param2;
  48. }NODE, *PNODE;
  49.  
  50. /*
  51.  * Priority queue header
  52.  */
  53. typedef struct _PQUEUE
  54. {
  55.    ULONG cNodes;
  56.    NODE aNodes[1];
  57. }PQUEUE, *PPQUEUE;
  58.  
  59.  
  60. /*
  61.  * Function prototypes
  62.  */
  63. int pqueue_push(PPQUEUE pQueue, PNODE pNew);
  64. PNODE pqueue_pop(PPQUEUE pQueue, PNODE pNode);
  65. PNODE pqueue_pop2(PPQUEUE pQueue);
  66. int pqueue_delete(PPQUEUE pQueue);
  67. int _Inline pqueue_shiftup(PPQUEUE pQueue, ULONG i);
  68.  
  69. static ULONG _System exception_handler(PEXCEPTIONREPORTRECORD pERepRec, PEXCEPTIONREGISTRATIONRECORD pERegRep, PCONTEXTRECORD pCtxRec, PVOID p);
  70.  
  71.  
  72. /*
  73.  * Push a new node onto the heap/priority queue
  74.  */
  75. int pqueue_push(PPQUEUE pQueue, PNODE pNew)
  76. {
  77.    PNODE aNodes = &pQueue->aNodes[0];
  78.    int i = 0, j = 0;
  79.  
  80.    pQueue->cNodes++;
  81.  
  82.    for(j = pQueue->cNodes; j > 1; j = i)
  83.    {
  84.       i = j / 2;
  85.       if(aNodes[i].priority >= pNew->priority)
  86.          break;
  87.       memcpy(&aNodes[j], &aNodes[i], sizeof(NODE));
  88.    }
  89.    memcpy(&aNodes[j], pNew, sizeof(NODE));
  90.  
  91.    return 1;
  92. }
  93.  
  94.  
  95. /*
  96.  * Get the top priority queue
  97.  */
  98. PNODE pqueue_pop(PPQUEUE pQueue, PNODE pNode)
  99. {
  100.    if(pQueue->cNodes < 1)
  101.    {
  102.       return NULL;
  103.    }
  104.    memcpy(pNode, &pQueue->aNodes[1], sizeof(NODE));
  105.  
  106.    pqueue_delete(pQueue);
  107.  
  108.    return pNode;
  109. }
  110.  
  111. /*
  112.  * Since node 0 isn't used, it can be used as a temporary storage
  113.  * for the pop:ed node.
  114.  * Important node: Unless you protect the first node with a sempahore
  115.  * (which isn't good design) this version of getting the top priority node
  116.  * is not thread safe!
  117.  */
  118. PNODE pqueue_pop2(PPQUEUE pQueue)
  119. {
  120.    if(pQueue->cNodes < 1)
  121.    {
  122.       return NULL;
  123.    }
  124.    memcpy(&pQueue->aNodes[0], &pQueue->aNodes[1], sizeof(NODE));
  125.  
  126.    pqueue_delete(pQueue);
  127.  
  128.    return &pQueue->aNodes[0];
  129. }
  130.  
  131. /*
  132.  * Strictly internal function - do not call from application code
  133.  */
  134. int pqueue_delete(PPQUEUE pQueue)
  135. {
  136.    if(pQueue->cNodes < 1)
  137.    {
  138.       return 0;
  139.    }
  140.    else
  141.    {
  142.       memcpy(&pQueue->aNodes[1], &pQueue->aNodes[pQueue->cNodes], sizeof(NODE));
  143.       pQueue->cNodes--;
  144.       pqueue_shiftup(pQueue, 1);
  145.    }
  146.    return 1;
  147. }
  148.  
  149. /*
  150.  * Strictly internal function - do not call from application code
  151.  */
  152. int _Inline pqueue_shiftup(PPQUEUE pQueue, ULONG i)
  153. {
  154.    NODE tmpNode;
  155.    int j = 0;
  156.    int n = pQueue->cNodes;
  157.    PNODE aNodes = &pQueue->aNodes[0];
  158.  
  159.    while((j = 2*i) <= n)
  160.    {
  161.       if((j < n) && aNodes[j].priority < aNodes[j+1].priority)
  162.          j++;
  163.  
  164.       if(aNodes[i].priority < aNodes[j].priority)
  165.       {
  166.          memcpy(&tmpNode, &aNodes[j], sizeof(NODE));
  167.          memcpy(&aNodes[j], &aNodes[i], sizeof(NODE));
  168.          memcpy(&aNodes[i], &tmpNode, sizeof(NODE));
  169.          i = j;
  170.       }
  171.       else
  172.       {
  173.          break;
  174.       }
  175.    }
  176.    return 1;
  177. }
  178.  
  179.  
  180.  
  181. int main(int argc, char *argv)
  182. {
  183.    APIRET rc = NO_ERROR;
  184.    PVOID pAlloc = NULL;
  185.    PPQUEUE heap = NULL;
  186.    int iRet = 0;
  187.    EXCEPTIONREGISTRATIONRECORD xcpthand = { 0, &exception_handler };
  188.    int i = 0;
  189.  
  190.    srand(time(NULL));
  191.  
  192.    /*
  193.     * The whole idea with this sample is to demonstrate how to allocate memory
  194.     * 'as needed'. The best way to do this is to use an exception handler
  195.     */
  196.    rc = DosSetExceptionHandler(&xcpthand);
  197.  
  198.    /*
  199.     * Allocate a very large buffer. This will fit approx 524280 nodes
  200.     * which is way more than you'll need.
  201.     */
  202.    rc = DosAllocMem(&pAlloc, 16*1024*1024, PAG_READ | PAG_WRITE);
  203.    if(rc == NO_ERROR)
  204.    {
  205.       heap = pAlloc;
  206.    }
  207.  
  208.    /*
  209.     * Add some nodes with random priorities
  210.     */
  211.    if(heap)
  212.    {
  213.       NODE tmpNode = { 0 };
  214.       PNODE node = NULL;
  215.  
  216.       puts("Add nodes");
  217.       for(i = 0; i < 100; i++)
  218.       {
  219.          tmpNode.priority = rand();
  220.          printf("Added node with priority: %u\n", tmpNode.priority);
  221.          pqueue_push(heap, &tmpNode);
  222.       }
  223.  
  224.       /*
  225.        * Actually, it's neater to use the nodes-counter..
  226.        */
  227.       puts("\n\nEmpty heap");
  228.       while((node = pqueue_pop2(heap)) != NULL)
  229.       {
  230.          printf("Priority: %u\n", node->priority);
  231.       }
  232.    }
  233.  
  234.  
  235.    /*
  236.     * Free heap buffer
  237.     */
  238.    if(heap)
  239.    {
  240.       DosFreeMem(heap);
  241.    }
  242.  
  243.    /*
  244.     * All registered exception handlers must be deregistered
  245.     */
  246.    DosUnsetExceptionHandler(&xcpthand);
  247.  
  248.    return iRet;
  249. }
  250.  
  251.  
  252.  
  253. /*
  254.  * Exception handler; attempt to commit memory if access violation occures.
  255.  */
  256. static ULONG _System exception_handler(PEXCEPTIONREPORTRECORD pERepRec, PEXCEPTIONREGISTRATIONRECORD pERegRep, PCONTEXTRECORD pCtxRec, PVOID p)
  257. {
  258.    ULONG ulRet = XCPT_CONTINUE_EXECUTION;
  259.  
  260.    switch(pERepRec->ExceptionNum)
  261.    {
  262.       case XCPT_ACCESS_VIOLATION:
  263.          ulRet = XCPT_CONTINUE_SEARCH;
  264.  
  265.          if(pERepRec->ExceptionAddress == (PVOID)XCPT_DATA_UNKNOWN)
  266.          {
  267.          }
  268.          else
  269.          {
  270.             APIRET rc = NO_ERROR;
  271.             ULONG cbMem = 1;
  272.             ULONG flMem = 0;
  273.  
  274.             rc = DosQueryMem((PVOID)pERepRec->ExceptionInfo[1], &cbMem, &flMem);
  275.             if((flMem & PAG_FREE) == 0)
  276.             {
  277.                rc = DosSetMem((PVOID)pERepRec->ExceptionInfo[1], 4096, PAG_DEFAULT | PAG_COMMIT);
  278.                if(rc == NO_ERROR)
  279.                {
  280.                   ulRet = XCPT_CONTINUE_EXECUTION;
  281.                }
  282.             }
  283.          }
  284.          break;
  285.  
  286.       default:
  287.          ulRet = XCPT_CONTINUE_SEARCH;
  288.          break;
  289.    }
  290.  
  291.    return ulRet;
  292. }
  293.  
  294.