Nebula 1995 August/NEBULA.mdf/Apps/DevTools/MachOViewer/Source/RCS/Queue.m,v

Text File | 1994-05-15 | 5.6 KB | 350 lines

head     1.2;
branch   ;
access   ;
symbols  ;
locks    ediger:1.2;
comment  @@;


1.2
date     94.05.15.18.56.05;  author ediger;  state Exp;
branches ;
next     1.1;

1.1
date     94.05.14.17.44.25;  author ediger;  state Exp;
branches ;
next     ;


desc
@simple stack and/or queue object implemented via doubly linked lists
@


1.2
log
@speedup -free method.  keep from honking internals up on -pop and -first
methods.
@
text
@//H+
//    Implementation of a LIFO stack or FIFO queue via a
//    doubly-linked list.
//
/*    $Log:    Queue.m,v $
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
@


1.1
log
@Initial revision
@
text
@d5 4
a8 1
/*    $Log$
d14 2
a17 1
#include <libc.h>
d40 5
a44 1
//        Used as pre- and post-condition for most methods.
d66 1
d68 1
d94 1
d112 4
a115 1
//
d121 1
a121 2
    void *ret;
    struct qs_internal_node *tmp;
d125 2
a126 1
    tmp = head->next;
d128 1
a128 2
    head->next = tmp->next;
    head->next->prev = head;
d130 2
a131 1
    ret = tmp->ptr;
d133 1
a133 1
    free(tmp);
d135 3
d146 4
d156 1
a156 2
    void *ret;
    struct qs_internal_node *tmp;
d160 2
a161 1
    tmp = tail->prev;
d163 1
a163 2
    tail->prev = tmp->prev;
    tail->prev->next = tail;
d165 2
a166 1
    ret = tmp->ptr;
d168 1
a168 1
    free(tmp);
d170 3
d181 1
a181 1
//        This is what is "pushed" on stack.
d204 1
a204 1
-(BOOL)empty
d210 1
a210 1
//M+ -(BOOL)empty
d214 1
a214 1
//        Doesn't deallocate memory that is referenced by the object's
d221 12
a232 2
    while(![self empty])
        [self pop];
@