|
Packit |
a38265 |
/*
|
|
Packit |
a38265 |
Copyright (C) 2003 Commonwealth Scientific and Industrial Research
|
|
Packit |
a38265 |
Organisation (CSIRO) Australia
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
Redistribution and use in source and binary forms, with or without
|
|
Packit |
a38265 |
modification, are permitted provided that the following conditions
|
|
Packit |
a38265 |
are met:
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
- Redistributions of source code must retain the above copyright
|
|
Packit |
a38265 |
notice, this list of conditions and the following disclaimer.
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
- Redistributions in binary form must reproduce the above copyright
|
|
Packit |
a38265 |
notice, this list of conditions and the following disclaimer in the
|
|
Packit |
a38265 |
documentation and/or other materials provided with the distribution.
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
- Neither the name of CSIRO Australia nor the names of its
|
|
Packit |
a38265 |
contributors may be used to endorse or promote products derived from
|
|
Packit |
a38265 |
this software without specific prior written permission.
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
|
Packit |
a38265 |
``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
|
Packit |
a38265 |
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
|
|
Packit |
a38265 |
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ORGANISATION OR
|
|
Packit |
a38265 |
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
Packit |
a38265 |
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
Packit |
a38265 |
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
Packit |
a38265 |
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
|
|
Packit |
a38265 |
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
|
Packit |
a38265 |
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
|
Packit |
a38265 |
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
Packit |
a38265 |
*/
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
#include "config.h"
|
|
Packit |
a38265 |
#include <stdlib.h>
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
#include "oggz_dlist.h"
|
|
Packit |
a38265 |
#include "oggz_macros.h"
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
typedef struct OggzDListElem {
|
|
Packit |
a38265 |
struct OggzDListElem * next;
|
|
Packit |
a38265 |
struct OggzDListElem * prev;
|
|
Packit |
a38265 |
void * data;
|
|
Packit |
a38265 |
} OggzDListElem;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
struct _OggzDList {
|
|
Packit |
a38265 |
OggzDListElem * head;
|
|
Packit |
a38265 |
OggzDListElem * tail;
|
|
Packit |
a38265 |
};
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDList *
|
|
Packit |
a38265 |
oggz_dlist_new (void) {
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDList *dlist;
|
|
Packit |
a38265 |
OggzDListElem *dummy_front, *dummy_back;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
dlist = oggz_malloc(sizeof(OggzDList));
|
|
Packit |
a38265 |
if (dlist == NULL) return NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
dummy_front = oggz_malloc(sizeof(OggzDListElem));
|
|
Packit |
a38265 |
if (dummy_front == NULL) {
|
|
Packit |
a38265 |
oggz_free (dlist);
|
|
Packit |
a38265 |
return NULL;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
dummy_back = oggz_malloc(sizeof(OggzDListElem));
|
|
Packit |
a38265 |
if (dummy_back == NULL) {
|
|
Packit |
a38265 |
oggz_free (dummy_front);
|
|
Packit |
a38265 |
oggz_free (dlist);
|
|
Packit |
a38265 |
return NULL;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
dummy_front->next = dummy_back;
|
|
Packit |
a38265 |
dummy_front->prev = NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
dummy_back->prev = dummy_front;
|
|
Packit |
a38265 |
dummy_back->next = NULL;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
dlist->head = dummy_front;
|
|
Packit |
a38265 |
dlist->tail = dummy_back;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return dlist;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void
|
|
Packit |
a38265 |
oggz_dlist_delete(OggzDList *dlist) {
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDListElem *p;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (p = dlist->head->next; p != NULL; p = p->next) {
|
|
Packit |
a38265 |
oggz_free(p->prev);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
oggz_free(dlist->tail);
|
|
Packit |
a38265 |
oggz_free(dlist);
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_dlist_is_empty(OggzDList *dlist) {
|
|
Packit |
a38265 |
return (dlist->head->next == dlist->tail);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_dlist_append(OggzDList *dlist, void *elem) {
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDListElem *new_elem;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (dlist == NULL) return -1;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
new_elem = oggz_malloc(sizeof(OggzDListElem));
|
|
Packit |
a38265 |
if (new_elem == NULL) return -1;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
new_elem->data = elem;
|
|
Packit |
a38265 |
new_elem->next = dlist->tail;
|
|
Packit |
a38265 |
new_elem->prev = dlist->tail->prev;
|
|
Packit |
a38265 |
new_elem->prev->next = new_elem;
|
|
Packit |
a38265 |
new_elem->next->prev = new_elem;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return 0;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_dlist_prepend(OggzDList *dlist, void *elem) {
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDListElem *new_elem;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (dlist == NULL) return -1;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
new_elem = oggz_malloc(sizeof(OggzDListElem));
|
|
Packit |
a38265 |
if (new_elem == NULL) return -1;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
new_elem->data = elem;
|
|
Packit |
a38265 |
new_elem->prev = dlist->head;
|
|
Packit |
a38265 |
new_elem->next = dlist->head->next;
|
|
Packit |
a38265 |
new_elem->prev->next = new_elem;
|
|
Packit |
a38265 |
new_elem->next->prev = new_elem;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return 0;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_dlist_iter(OggzDList *dlist, OggzDListIterFunc func) {
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDListElem *p;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (p = dlist->head->next; p != dlist->tail; p = p->next) {
|
|
Packit |
a38265 |
int r = func(p->data);
|
|
Packit |
a38265 |
if (r == DLIST_ITER_ERROR) {
|
|
Packit |
a38265 |
return -1;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (r == DLIST_ITER_CANCEL) {
|
|
Packit |
a38265 |
break;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
return 0;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void
|
|
Packit |
a38265 |
oggz_dlist_reverse_iter(OggzDList *dlist, OggzDListIterFunc func) {
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDListElem *p;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (p = dlist->tail->prev; p != dlist->head; p = p->prev) {
|
|
Packit |
a38265 |
if (func(p->data) == DLIST_ITER_CANCEL) {
|
|
Packit |
a38265 |
break;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
int
|
|
Packit |
a38265 |
oggz_dlist_deliter(OggzDList *dlist, OggzDListIterFunc func) {
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDListElem *p, *q;
|
|
Packit |
a38265 |
int result = 0;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (p = dlist->head->next; p != dlist->tail; p = q) {
|
|
Packit |
a38265 |
int r = func(p->data);
|
|
Packit |
a38265 |
if (r == DLIST_ITER_ERROR) {
|
|
Packit |
a38265 |
result = -1;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
if (r == DLIST_ITER_CANCEL) {
|
|
Packit |
a38265 |
break;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
q = p->next;
|
|
Packit |
a38265 |
p->prev->next = p->next;
|
|
Packit |
a38265 |
p->next->prev = p->prev;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
oggz_free(p);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
return result;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
void
|
|
Packit |
a38265 |
oggz_dlist_reverse_deliter(OggzDList *dlist, OggzDListIterFunc func) {
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
OggzDListElem *p, *q;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
for (p = dlist->tail->prev; p != dlist->head; p = q) {
|
|
Packit |
a38265 |
if (func(p->data) == DLIST_ITER_CANCEL) {
|
|
Packit |
a38265 |
break;
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
q = p->prev;
|
|
Packit |
a38265 |
p->prev->next = p->next;
|
|
Packit |
a38265 |
p->next->prev = p->prev;
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
oggz_free(p);
|
|
Packit |
a38265 |
}
|
|
Packit |
a38265 |
|
|
Packit |
a38265 |
}
|