/*************************************************************************** * * 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 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); }