home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1995 August / NEBULA.mdf / Apps / DevTools / MachOViewer / Source / Queue.m < prev    next >
Encoding:
Text File  |  1994-05-15  |  4.5 KB  |  247 lines
  1. //H+
  2. //    Implementation of a LIFO stack or FIFO queue via a
  3. //    doubly-linked list.
  4. //
  5. /*    $Log:    Queue.m,v $
  6. Revision 1.2  94/05/15  18:56:05  ediger
  7. speedup -free method.  keep from honking internals up on -pop and -first
  8. methods.
  9.  
  10. Revision 1.1  94/05/14  17:44:25  ediger
  11. Initial revision
  12.  
  13. */
  14.  
  15. //H-
  16. #include <stdio.h>
  17. #include <unistd.h>
  18. #include <assert.h>
  19. #include <libc.h>
  20.  
  21. #include <Queue.h>
  22.  
  23. #define CHECK_CONTRACT
  24.  
  25. #ifdef CHECK_CONTRACT
  26.     #define REQUIRE(c) if(![self c]) \
  27.         [self error:"%s precondition check failed", sel_getName(_cmd)]
  28.     #define ENSURE(c) if(![self c]) \
  29.         [self error:"%s postcondition check failed", sel_getName(_cmd)]
  30. #else
  31.     #define REQUIRE(c)
  32.     #define ENSURE(c)
  33. #endif
  34.  
  35.  
  36. @implementation Queue: Object
  37.  
  38. static char RCSQueueIdent[] = "$Id";
  39.  
  40. #ifdef CHECK_CONTRACT
  41. //M+ -(BOOL)listOK
  42. //    PURPOSE:
  43. //        Make sure that head and tail dummy nodes are OK.
  44. //        Used as pre- and post-condition for most methods when
  45. //        CHECK_CONTRACT is #defined
  46. //    EDITORIAL:
  47. //        Could walk the entire list forward and back to see
  48. //        if all the links are correct, but it doesn't.
  49. //M-
  50. -(BOOL)listOK
  51. {
  52.     return
  53.            (head != NULL) && (tail != NULL)
  54.         && (head->next != NULL)
  55.         && (tail->prev != NULL)
  56.         && (head->next->prev == head)
  57.         && (tail->prev->next == tail)
  58.     ;
  59. }
  60. #endif
  61.  
  62. //M+ - init
  63. //    PURPOSE:
  64. //        initialize internals of an object.  In this implementation, that
  65. //        means setting up dummy head and tail nodes of doubly-linked list.
  66. //M-
  67. - init
  68. {
  69.     head = (struct qs_internal_node *)malloc(sizeof(struct qs_internal_node));
  70.     assert(head != NULL);
  71.     tail = (struct qs_internal_node *)malloc(sizeof(struct qs_internal_node));
  72.     assert(tail != NULL);
  73.  
  74.     head->next = tail;
  75.     head->prev = head;
  76.     head->ptr  = NULL;
  77.  
  78.     tail->next = tail;
  79.     tail->prev = head;
  80.     tail->ptr  = NULL;
  81.  
  82.     ENSURE(listOK);
  83.  
  84.     return self;
  85. }
  86.  
  87. //M+ -push:(void *)p
  88. //    PURPOSE:
  89. //        push something onto the stack, or end of queue.
  90. //M-
  91. -push:(void *)p
  92. {
  93.     struct qs_internal_node *new;
  94.  
  95.     REQUIRE(listOK);
  96.  
  97.     new = (struct qs_internal_node *)malloc(sizeof *new);
  98.     assert(new != NULL);
  99.  
  100.     new->ptr = p;
  101.     new->prev = tail->prev;
  102.     new->next = tail;
  103.  
  104.     tail->prev = new;
  105.  
  106.     new->prev->next = new;
  107.  
  108.     ENSURE(listOK);
  109.  
  110.     return self;
  111. }
  112.  
  113. //M+ -(void *)first
  114. //    PURPOSE:
  115. //        Retrieve the first thing that was pushed onto queue.
  116. //        This is the method that makes object a FIFO.
  117. //    RETURNS:
  118. //        pointer to item stored.  If NULL was stored it will return NULL,
  119. //        but it will also return NULL if queue is empty.
  120. //    NOTE:
  121. //        Should deallocate memory used internally by the object.
  122. //M-
  123. -(void *)first
  124. {
  125.     void *ret = NULL;
  126.  
  127.     REQUIRE(listOK);
  128.  
  129.     if (head->next != tail)
  130.     {    // object has something in it.
  131.  
  132.         struct qs_internal_node *tmp = head->next;
  133.  
  134.         head->next = tmp->next;
  135.         head->next->prev = head;
  136.  
  137.         ret = tmp->ptr;
  138.  
  139.         free(tmp);
  140.     }
  141.  
  142.     ENSURE(listOK);
  143.  
  144.     return ret;
  145. }
  146.  
  147. //M+ -(void *)pop
  148. //    PURPOSE:
  149. //        Retrieve last thing that was pushed onto stack.
  150. //        Method used to make object into a LIFO.
  151. //    RETURNS:
  152. //        pointer to item stored.  If NULL was stored it will return NULL,
  153. //        but it will also return NULL if stack is empty.
  154. //
  155. //    NOTE:
  156. //        Should deallocate memory used internally by the object.
  157. //M-
  158. -(void *)pop
  159. {
  160.     void *ret = NULL;
  161.  
  162.     REQUIRE(listOK);
  163.  
  164.     if (tail->prev != head)
  165.     {    // object has something in it.
  166.  
  167.         struct qs_internal_node *tmp = tail->prev;
  168.  
  169.         tail->prev = tmp->prev;
  170.         tail->prev->next = tail;
  171.  
  172.         ret = tmp->ptr;
  173.  
  174.         free(tmp);
  175.     }
  176.  
  177.     ENSURE(listOK);
  178.  
  179.     return ret;
  180. }
  181.  
  182. //M+ -(void *)tail
  183. //    PURPOSE:
  184. //        Peek at whatever is at tail of stack.
  185. //        This is what was just "pushed" on stack.
  186. //M-
  187. -(void *)tail
  188. {
  189.     REQUIRE(listOK);
  190.     return tail->prev->ptr;
  191. }
  192.  
  193. //M+ -(void *)head
  194. //    PURPOSE:
  195. //        Peek at whatever is at head of stack.
  196. //        This is what is "first" on queue.
  197. //M-
  198. -(void *)head
  199. {
  200.     REQUIRE(listOK);
  201.     return head->next->ptr;
  202. }
  203.  
  204. //M+ -(BOOL)empty
  205. //    PURPOSE:
  206. //        Determine if stack/queue has anything in it
  207. //M-
  208. -(BOOL)isEmpty
  209. {
  210.     REQUIRE(listOK);
  211.     return (head->next == tail);
  212. }
  213.  
  214. //M+ - free
  215. //    PURPOSE:
  216. //        Deallocate memory used by the object.
  217. //    NOTES:
  218. //        Doesn't deallocate memory that is contained by the object's
  219. //        implementation.  Only deallocates memory used by the implementation.
  220. //M-
  221. - free
  222. {
  223.     REQUIRE(listOK);
  224.  
  225.     // free the list in implementation independant way
  226.     //while(![self empty])
  227.     //    [self pop];
  228.  
  229.     // free the list in way that depends on doubly-linked lists
  230.     // speed up the process, I hope.
  231.     while (head->next != tail)
  232.     {
  233.         struct qs_internal_node *tmp = head->next->next;
  234.         free(head->next);
  235.         head->next = tmp;
  236.     }
  237.  
  238.     free(head);
  239.     free(tail);
  240.  
  241.     [super free];
  242.  
  243.     return self;
  244. }
  245.  
  246. @end
  247.