/***************************************************************************
*
* Copyright (c) 1998-1999 Niels Möller
* Copyright (c) 1999 BalaBit Computing
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
* $Id: queue.c,v 1.3 1999/11/22 18:26:24 bazsi Exp $
*
***************************************************************************/
#include "queue.h"
#include "werror.h"
#include <assert.h>
static void do_queue_mark(struct ol_queue *q,
void (*mark)(struct ol_object *o));
static void do_queue_free(struct ol_queue *q);
#define CLASS_DEFINE
#include "queue.h.x"
#undef CLASS_DEFINE
/* Short cuts */
#define next np_links[LSH_QUEUE_NEXT]
#define prev np_links[LSH_QUEUE_PREV]
#define head ht_links[LSH_QUEUE_HEAD]
#define tail ht_links[LSH_QUEUE_TAIL]
#define tailprev ht_links[LSH_QUEUE_TAILPREV]
#define EMPTYP(q) ((q)->tailprev == (struct ol_queue_node *) (q))
#if 0
static void sanity_check_queue(struct ol_queue *q)
{
struct ol_queue_node *n;
debug("sanity_check_queue: q = %xi\n", (UINT32) q);
if (q->tail)
fatal("sanity_check_queue: q->tail not NULL!\n");
n = q->head;
#if 0
if (EMPTYP(q))
{
debug(" queue is empty\n");
if (n->prev)
fatal("sanity_check_queue: "
"Queue looks empty, but n->prev not NULL!\n");
if (q->tail != (struct ol_queue_node *) q)
fatal("sanity_check_queue: "
"Queue looks empty, but q->tail != q !\n");
return;
}
#endif
if (n->prev != (struct ol_queue_node *) q)
fatal("sanity_check_queue: head->next != &q->head !\n");
while (n->next)
{
debug(" n = %xi\n", (UINT32) n);
if (n->prev->next != n)
fatal("n->prev->next != n !\n");
n = n->next;
}
if (n != (struct ol_queue_node *) &(q->tail))
fatal("n != n &t->tail!\n");
}
#else
#define sanity_check_queue(x)
#endif
void ol_queue_init(struct ol_queue *q)
{
q->head = (struct ol_queue_node *) &(q->tail);
q->tail = NULL;
q->tailprev = (struct ol_queue_node *) &(q->head);
sanity_check_queue(q);
}
int ol_queue_is_empty(struct ol_queue *q)
{
sanity_check_queue(q);
return EMPTYP(q);
}
void ol_queue_add_head(struct ol_queue *q, struct ol_queue_node *n)
{
sanity_check_queue(q);
n->next = q->head;
n->prev = (struct ol_queue_node *) &(q->head);
n->prev->next = n;
n->next->prev = n;
sanity_check_queue(q);
}
void ol_queue_add_tail(struct ol_queue *q, struct ol_queue_node *n)
{
sanity_check_queue(q);
n->next = (struct ol_queue_node *) &(q->tail);
n->prev = q->tailprev;
n->prev->next = n;
n->next->prev = n;
sanity_check_queue(q);
}
void ol_queue_remove(struct ol_queue_node *n)
{
assert(n->next);
assert(n->prev);
n->next->prev = n->prev;
n->prev->next = n->next;
}
struct ol_queue_node *ol_queue_remove_head(struct ol_queue *q)
{
struct ol_queue_node *n = q->head;
sanity_check_queue(q);
assert(!EMPTYP(q));
ol_queue_remove(n);
sanity_check_queue(q);
return n;
}
struct ol_queue_node *ol_queue_remove_tail(struct ol_queue *q)
{
struct ol_queue_node *n = q->tailprev;
sanity_check_queue(q);
assert(!EMPTYP(q));
ol_queue_remove(n);
sanity_check_queue(q);
return n;
}
/* object_queue */
static struct object_queue_node *
make_object_queue_node(struct ol_object *o)
{
struct object_queue_node *n;
NEW_SPACE(n);
n->o = o;
return n;
}
struct object_queue *make_object_queue(void)
{
NEW(object_queue, q);
ol_queue_init(&q->q);
return q;
}
int object_queue_is_empty(struct object_queue *q)
{
return EMPTYP(&q->q);
}
struct object_queue_node *
object_queue_add_head(struct object_queue *q, struct ol_object *o)
{
struct object_queue_node *n = make_object_queue_node(o);
ol_queue_add_head(&q->q, &n->header);
return n;
}
struct object_queue_node *
object_queue_add_tail(struct object_queue *q, struct ol_object *o)
{
struct object_queue_node *n = make_object_queue_node(o);
ol_queue_add_tail(&q->q, &n->header);
return n;
}
static struct ol_object *
object_queue_get_contents(struct ol_queue_node *l)
{
struct object_queue_node *n = (struct object_queue_node *) l;
struct ol_object *res = n->o;
ol_space_free(n);
return res;
}
static struct ol_object *
object_queue_peek(struct ol_queue_node *n)
{
return ( (struct object_queue_node *) n)->o;
}
void object_queue_remove(struct object_queue_node *n)
{
ol_queue_remove(&n->header);
ol_space_free(n);
}
struct ol_object *object_queue_remove_head(struct object_queue *q)
{
return object_queue_get_contents(ol_queue_remove_head(&q->q));
}
struct ol_object *object_queue_remove_tail(struct object_queue *q)
{
return object_queue_get_contents(ol_queue_remove_tail(&q->q));
}
struct ol_object *object_queue_peek_head(struct object_queue *q)
{
return EMPTYP(&q->q) ? NULL : object_queue_peek(q->q.head);
}
struct ol_object *object_queue_peek_tail(struct object_queue *q)
{
return EMPTYP(&q->q) ? NULL : object_queue_peek(q->q.tailprev);
}
/* For gc */
static void do_queue_mark(struct ol_queue *q,
void (*mark)(struct ol_object *o))
{
FOR_QUEUE(q, struct object_queue_node *, n)
mark(n->o);
}
static void do_queue_free(struct ol_queue *q)
{
FOR_QUEUE(q, struct object_queue_node *, n)
ol_space_free(n);
}
void object_queue_kill(struct object_queue *q)
{
do_queue_free(&q->q);
}
syntax highlighted by Code2HTML, v. 0.9.1