This is Queue.m in view mode; [Download] [Up]
//H+
// Implementation of a LIFO stack or FIFO queue via a
// doubly-linked list.
//
/* $Log: Queue.m,v $
Revision 1.2 94/05/15 18:56:05 ediger
speedup -free method. keep from honking internals up on -pop and -first
methods.
Revision 1.1 94/05/14 17:44:25 ediger
Initial revision
*/
//H-
#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <libc.h>
#include <Queue.h>
#define CHECK_CONTRACT
#ifdef CHECK_CONTRACT
#define REQUIRE(c) if(![self c]) \
[self error:"%s precondition check failed", sel_getName(_cmd)]
#define ENSURE(c) if(![self c]) \
[self error:"%s postcondition check failed", sel_getName(_cmd)]
#else
#define REQUIRE(c)
#define ENSURE(c)
#endif
@implementation Queue: Object
static char RCSQueueIdent[] = "$Id";
#ifdef CHECK_CONTRACT
//M+ -(BOOL)listOK
// PURPOSE:
// Make sure that head and tail dummy nodes are OK.
// Used as pre- and post-condition for most methods when
// CHECK_CONTRACT is #defined
// EDITORIAL:
// Could walk the entire list forward and back to see
// if all the links are correct, but it doesn't.
//M-
-(BOOL)listOK
{
return
(head != NULL) && (tail != NULL)
&& (head->next != NULL)
&& (tail->prev != NULL)
&& (head->next->prev == head)
&& (tail->prev->next == tail)
;
}
#endif
//M+ - init
// PURPOSE:
// initialize internals of an object. In this implementation, that
// means setting up dummy head and tail nodes of doubly-linked list.
//M-
- init
{
head = (struct qs_internal_node *)malloc(sizeof(struct qs_internal_node));
assert(head != NULL);
tail = (struct qs_internal_node *)malloc(sizeof(struct qs_internal_node));
assert(tail != NULL);
head->next = tail;
head->prev = head;
head->ptr = NULL;
tail->next = tail;
tail->prev = head;
tail->ptr = NULL;
ENSURE(listOK);
return self;
}
//M+ -push:(void *)p
// PURPOSE:
// push something onto the stack, or end of queue.
//M-
-push:(void *)p
{
struct qs_internal_node *new;
REQUIRE(listOK);
new = (struct qs_internal_node *)malloc(sizeof *new);
assert(new != NULL);
new->ptr = p;
new->prev = tail->prev;
new->next = tail;
tail->prev = new;
new->prev->next = new;
ENSURE(listOK);
return self;
}
//M+ -(void *)first
// PURPOSE:
// Retrieve the first thing that was pushed onto queue.
// This is the method that makes object a FIFO.
// RETURNS:
// pointer to item stored. If NULL was stored it will return NULL,
// but it will also return NULL if queue is empty.
// NOTE:
// Should deallocate memory used internally by the object.
//M-
-(void *)first
{
void *ret = NULL;
REQUIRE(listOK);
if (head->next != tail)
{ // object has something in it.
struct qs_internal_node *tmp = head->next;
head->next = tmp->next;
head->next->prev = head;
ret = tmp->ptr;
free(tmp);
}
ENSURE(listOK);
return ret;
}
//M+ -(void *)pop
// PURPOSE:
// Retrieve last thing that was pushed onto stack.
// Method used to make object into a LIFO.
// RETURNS:
// pointer to item stored. If NULL was stored it will return NULL,
// but it will also return NULL if stack is empty.
//
// NOTE:
// Should deallocate memory used internally by the object.
//M-
-(void *)pop
{
void *ret = NULL;
REQUIRE(listOK);
if (tail->prev != head)
{ // object has something in it.
struct qs_internal_node *tmp = tail->prev;
tail->prev = tmp->prev;
tail->prev->next = tail;
ret = tmp->ptr;
free(tmp);
}
ENSURE(listOK);
return ret;
}
//M+ -(void *)tail
// PURPOSE:
// Peek at whatever is at tail of stack.
// This is what was just "pushed" on stack.
//M-
-(void *)tail
{
REQUIRE(listOK);
return tail->prev->ptr;
}
//M+ -(void *)head
// PURPOSE:
// Peek at whatever is at head of stack.
// This is what is "first" on queue.
//M-
-(void *)head
{
REQUIRE(listOK);
return head->next->ptr;
}
//M+ -(BOOL)empty
// PURPOSE:
// Determine if stack/queue has anything in it
//M-
-(BOOL)isEmpty
{
REQUIRE(listOK);
return (head->next == tail);
}
//M+ - free
// PURPOSE:
// Deallocate memory used by the object.
// NOTES:
// Doesn't deallocate memory that is contained by the object's
// implementation. Only deallocates memory used by the implementation.
//M-
- free
{
REQUIRE(listOK);
// free the list in implementation independant way
//while(![self empty])
// [self pop];
// free the list in way that depends on doubly-linked lists
// speed up the process, I hope.
while (head->next != tail)
{
struct qs_internal_node *tmp = head->next->next;
free(head->next);
head->next = tmp;
}
free(head);
free(tail);
[super free];
return self;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.