/* This program is due to R. Strandh, and has been modified by O. Baudon O. Baudon, project GML, February 23, 1994 Copyright (c) 1996 - LaBRI, Universite Bordeaux 1. All rights reserved. See the file "license.terms" for information on usage and redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES. Purpose: Generalized queue (well, list) package. */ #include #ifndef NO_STDLIB_H #include #else #include "compat/stdlib.h" #endif #include #include "gqueue.h" /* data structures */ struct gq_cell_structure { void *element; struct gq_cell_structure *prev; struct gq_cell_structure *next; }; typedef struct gq_cell_structure *gq_cell; struct gqueue_structure { gq_cell head; gq_cell tail; gq_cell cursor; gqueue cursor_save; void (*element_destroy)(); int size; }; void * (* gq_malloc)(size_t size) = (void * (*)(size_t))malloc; void (* gq_free)(void * p) = (void (*)(void *))free; #define ELEMENT void * static gqueue gq_create_aux(void); static void gq_destroy_aux(gqueue q); /* Functions used for debugging. */ static void gq_print(gqueue q); void gq_go_beginning(gqueue q) { q -> cursor = q -> head;} void gq_go_end(gqueue q) { q -> cursor = q -> tail -> prev;} int gq_at_beginning(gqueue q) { return q -> cursor == q -> head;} int gq_at_end(gqueue q) { return q -> cursor == q -> tail -> prev;} int gq_empty(gqueue q) { return q -> head -> next == q -> tail;} void gq_go_forward(gqueue q) { assert(!gq_at_end(q)); q -> cursor = q -> cursor -> next; } void gq_go_backward(gqueue q) { assert(!gq_at_beginning(q)); q -> cursor = q -> cursor -> prev; } void * gq_get(gqueue q) { assert(!gq_at_end(q)); return q -> cursor -> next -> element; } void * gq_get_first(gqueue q) { assert(!gq_empty(q)); return q -> head -> next -> element; } void gq_insert(gqueue q, void *element) { gq_cell temp = (gq_cell) gq_malloc(sizeof(struct gq_cell_structure)); temp -> element = element; temp -> next = q -> cursor -> next; temp -> prev = q -> cursor; q -> cursor -> next -> prev = temp; q -> cursor -> next = temp; q -> cursor = temp; q -> size ++; } void gq_delete(gqueue q) { gq_cell temp; assert(!gq_at_end(q)); temp = q -> cursor -> next; temp -> next -> prev = temp -> prev; temp -> prev -> next = temp -> next; if (q -> element_destroy) (*(q -> element_destroy))(temp -> element); gq_free(temp); q -> size --; } void gq_replace(gqueue q, void *element) { gq_cell temp; assert(!gq_at_end(q)); temp = q -> cursor -> next; if (q -> element_destroy) (*(q -> element_destroy))(temp -> element); temp -> element = element; } static void gq_destroy_aux(q) gqueue q; { gq_go_beginning(q); while(!gq_empty(q)) { gq_delete(q); } gq_free(q->head); gq_free(q->tail); gq_free(q); } void gq_destroy(q) gqueue q; { gq_destroy_aux(q->cursor_save); gq_destroy_aux(q); } void gq_set_destroy(gqueue q,void (*destroy)()) { q -> element_destroy = destroy; } void gq_push_cursor(gqueue q) { gq_insert(q -> cursor_save, q -> cursor); gq_go_beginning(q -> cursor_save); q -> cursor = q -> head; } void gq_pop_cursor(gqueue q) { q -> cursor = gq_get(q -> cursor_save); gq_delete(q -> cursor_save); } static gqueue gq_create_aux() { gqueue temp; temp = (gqueue) gq_malloc(sizeof(struct gqueue_structure)); temp -> element_destroy = NULL; temp -> head = (gq_cell) gq_malloc(sizeof(struct gq_cell_structure)); temp -> tail = (gq_cell) gq_malloc(sizeof(struct gq_cell_structure)); temp->head->element = temp->tail->element = temp->head->prev = temp->tail->next = NULL; temp -> cursor = temp -> head; temp -> head -> next = temp -> tail; temp -> tail -> prev = temp -> head; temp -> size = 0; return(temp); } gqueue gq_copy(gqueue q) { gqueue temp = gq_create(); gq_push_cursor(q); for(gq_go_beginning(q); !gq_at_end(q); gq_go_forward(q)) { gq_insert(temp, gq_get(q)); } gq_pop_cursor(q); return temp; } gqueue gq_create() { gqueue temp = gq_create_aux(); temp -> cursor_save = gq_create_aux(); return temp; } void gq_make_empty(gqueue q) { for(gq_go_beginning(q); !gq_empty(q); ) { gq_delete(q); } assert(q -> size == 0); } int gq_member(gqueue q, void *elem) { gq_push_cursor(q); for(gq_go_beginning(q); !gq_at_end(q); gq_go_forward(q)) { if(gq_get(q) == elem) return 1; } gq_pop_cursor(q); return 0; } void gq_add(gqueue q, void *elem) { gq_push_cursor(q); for(gq_go_beginning(q); !gq_at_end(q); gq_go_forward(q)) { if(gq_get(q) == elem) break; } if(gq_at_end(q)) gq_insert(q, elem); gq_pop_cursor(q); } void gq_subtract(gqueue q, void *elem) { if (q -> cursor -> element == elem) { gq_go_backward(q); gq_delete(q); return; } gq_push_cursor(q); for (gq_go_beginning(q); !gq_at_end(q); gq_go_forward(q)) { if(gq_get(q) == elem) { gq_delete(q); break; } } gq_pop_cursor(q); } void gq_union(gqueue q, gqueue r) { gq_push_cursor(r); for(gq_go_beginning(r); !gq_at_end(r); gq_go_forward(r)) { gq_add(q, gq_get(r)); } gq_pop_cursor(r); } void gq_intersection(gqueue q, gqueue r) { gq_push_cursor(r); for(gq_go_beginning(r); !gq_at_end(r); gq_go_forward(r)) { gq_subtract(q, gq_get(r)); } gq_pop_cursor(r); } void gq_concat(gqueue q, gqueue r) { gq_push_cursor(q); gq_go_end(q); gq_push_cursor(r); for(gq_go_beginning(r); !gq_at_end(r); gq_go_forward(r)) { gq_insert(q, gq_get(r)); } gq_pop_cursor(r); gq_pop_cursor(q); } void gq_map(gqueue q, void (*fun)(void *)) { gq_push_cursor(q); for(gq_go_beginning(q); !gq_at_end(q); gq_go_forward(q)) { fun(gq_get(q)); } gq_pop_cursor(q); } int gq_size(gqueue q) { return q -> size; } /* For debug only. */ static void gq_print(gqueue q) { gq_cell tmp = q->head; printf("queue %0x\n", q); printf("cursor: %0x cursor->elem: %0x\n", q->cursor, q->cursor->element); printf("head: %0x head->next: %0x\n", q->head, q->head->next); for(tmp = q->head; tmp != q->tail; tmp = tmp->next) { printf("cell: %0x elem: %0x prev: %0x next: %0x\n", tmp, tmp->element, tmp->prev, tmp->next); } printf("tail: %0x tail->prev: %0x\n", q->tail, q->tail->prev); }