| /* |
| * List Abstract Data Type |
| * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net> |
| * |
| * Free Software License: |
| * |
| * All rights are reserved by the author, with the following exceptions: |
| * Permission is granted to freely reproduce and distribute this software, |
| * possibly in exchange for a fee, provided that this copyright notice appears |
| * intact. Permission is also granted to adapt this software to produce |
| * derivative works, as long as the modified versions carry this copyright |
| * notice and additional notices stating that the work has been modified. |
| * This source code may be translated into executable form and incorporated |
| * into proprietary software; there is no requirement for such software to |
| * contain a copyright notice related to this source. |
| * |
| * $Id: list.h,v 1.19 1999/11/14 20:46:19 kaz Exp $ |
| * $Name: kazlib_1_20 $ |
| */ |
| |
| #ifndef LIST_H |
| #define LIST_H |
| |
| #include <limits.h> |
| |
| #ifdef KAZLIB_SIDEEFFECT_DEBUG |
| #include "sfx.h" |
| #define LIST_SFX_CHECK(E) SFX_CHECK(E) |
| #else |
| #define LIST_SFX_CHECK(E) (E) |
| #endif |
| |
| /* |
| * Blurb for inclusion into C++ translation units |
| */ |
| |
| #ifdef __cplusplus |
| extern "C" { |
| #endif |
| |
| typedef unsigned long listcount_t; |
| #define LISTCOUNT_T_MAX ULONG_MAX |
| |
| typedef struct lnode_t { |
| #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) |
| struct lnode_t *list_next; |
| struct lnode_t *list_prev; |
| void *list_data; |
| #else |
| int list_dummy; |
| #endif |
| } lnode_t; |
| |
| typedef struct lnodepool_t { |
| #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) |
| struct lnode_t *list_pool; |
| struct lnode_t *list_free; |
| listcount_t list_size; |
| #else |
| int list_dummy; |
| #endif |
| } lnodepool_t; |
| |
| typedef struct list_t { |
| #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) |
| lnode_t list_nilnode; |
| listcount_t list_nodecount; |
| listcount_t list_maxcount; |
| #else |
| int list_dummy; |
| #endif |
| } list_t; |
| |
| lnode_t *ow_lnode_create(void *); |
| lnode_t *ow_lnode_init(lnode_t *, void *); |
| void ow_lnode_destroy(lnode_t *); |
| void ow_lnode_put(lnode_t *, void *); |
| void *ow_lnode_get(lnode_t *); |
| int ow_lnode_is_in_a_list(lnode_t *); |
| |
| #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) |
| #define lnode_put(N, D) ((N)->list_data = (D)) |
| #define lnode_get(N) ((N)->list_data) |
| #else |
| #define lnode_put ow_lnode_put |
| #define lnode_get ow_lnode_get |
| #endif |
| |
| lnodepool_t *ow_lnode_pool_init(lnodepool_t *, lnode_t *, listcount_t); |
| lnodepool_t *ow_lnode_pool_create(listcount_t); |
| void ow_lnode_pool_destroy(lnodepool_t *); |
| lnode_t *ow_lnode_borrow(lnodepool_t *, void *); |
| void ow_lnode_return(lnodepool_t *, lnode_t *); |
| int ow_lnode_pool_isempty(lnodepool_t *); |
| int ow_lnode_pool_isfrom(lnodepool_t *, lnode_t *); |
| |
| |
| list_t *ow_list_create(listcount_t); |
| /* list_t *ow_list_init(list_t *list, listcount_t maxcount); */ |
| void ow_list_destroy(list_t *); |
| void ow_list_destroy_nodes(list_t *); |
| void ow_list_return_nodes(list_t *, lnodepool_t *); |
| |
| listcount_t ow_list_count(list_t *); |
| int ow_list_isempty(list_t *); |
| int ow_list_isfull(list_t *); |
| int ow_list_contains(list_t *, lnode_t *); |
| |
| void ow_list_append(list_t *, lnode_t *); |
| void ow_list_prepend(list_t *, lnode_t *); |
| void ow_list_ins_before(list_t *, lnode_t *, lnode_t *); |
| void ow_list_ins_after(list_t *, lnode_t *, lnode_t *); |
| |
| lnode_t *ow_list_first(list_t *); |
| lnode_t *ow_list_last(list_t *); |
| lnode_t *ow_list_next(list_t *, lnode_t *); |
| lnode_t *ow_list_prev(list_t *, lnode_t *); |
| |
| lnode_t *ow_list_del_first(list_t *); |
| lnode_t *ow_list_del_last(list_t *); |
| lnode_t *ow_list_delete(list_t *, lnode_t *); |
| lnode_t *ow_list_delete2(list_t *, lnode_t *); |
| |
| void ow_list_process(list_t *, void *, void (*)(list_t *, lnode_t *, void *)); |
| |
| int ow_list_verify(list_t *); |
| |
| #define lnode_create ow_lnode_create |
| #define lnode_init ow_lnode_init |
| #define lnode_destroy ow_lnode_destroy |
| |
| #define lnode_is_in_a_list ow_lnode_is_in_a_list |
| #define lnode_pool_init ow_lnode_pool_init |
| #define lnode_pool_create ow_lnode_pool_create |
| #define lnode_pool_destroy ow_lnode_pool_destroy |
| #define lnode_borrow ow_lnode_borrow |
| #define lnode_return ow_lnode_return |
| |
| #define lnode_pool_isfrom ow_lnode_pool_isfrom |
| |
| #define list_create ow_list_create |
| #define list_init ow_list_init |
| #define list_destroy ow_list_destroy |
| #define list_destroy_nodes ow_list_destroy_nodes |
| #define list_return_nodes ow_list_return_nodes |
| |
| |
| #define list_contains ow_list_contains |
| |
| |
| #define list_ins_before ow_list_ins_before |
| #define list_ins_after ow_list_ins_after |
| |
| |
| #define list_delete ow_list_delete |
| #define list_delete2 ow_list_delete2 |
| |
| #define list_process ow_list_process |
| #define list_verify ow_list_verify |
| |
| |
| #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) |
| #define lnode_pool_isempty(P) ((P)->list_free == 0) |
| #define list_count(L) ((L)->list_nodecount) |
| #define list_isempty(L) ((L == NULL) || ((L)->list_nodecount == 0)) |
| #define list_isfull(L) (LIST_SFX_CHECK(L)->list_nodecount == (L)->list_maxcount) |
| #define list_next(L, N) (LIST_SFX_CHECK(N)->list_next == &(L)->list_nilnode ? NULL : (N)->list_next) |
| #define list_prev(L, N) (LIST_SFX_CHECK(N)->list_prev == &(L)->list_nilnode ? NULL : (N)->list_prev) |
| #define list_first(L) list_next(LIST_SFX_CHECK(L), &(L)->list_nilnode) |
| #define list_last(L) list_prev(LIST_SFX_CHECK(L), &(L)->list_nilnode) |
| #else |
| #define lnode_pool_isempty ow_lnode_pool_isempty |
| #define list_count ow_list_count |
| #define list_isempty ow_list_isempty |
| #define list_isfull ow_list_isfull |
| #define list_first ow_list_first |
| #define list_last ow_list_last |
| #define list_next ow_list_next |
| #define list_prev ow_list_prev |
| #endif |
| |
| #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) |
| #define list_append(L, N) list_ins_before(LIST_SFX_CHECK(L), N, &(L)->list_nilnode) |
| #define list_prepend(L, N) list_ins_after(LIST_SFX_CHECK(L), N, &(L)->list_nilnode) |
| #define list_del_first(L) list_delete(LIST_SFX_CHECK(L), list_first(L)) |
| #define list_del_last(L) list_delete(LIST_SFX_CHECK(L), list_last(L)) |
| #else |
| #define list_append ow_list_append |
| #define list_prepend ow_list_prepend |
| #define list_del_first ow_list_del_first |
| #define list_del_last ow_list_del_last |
| #endif |
| |
| /* destination list on the left, source on the right */ |
| |
| void ow_list_extract(list_t *, list_t *, lnode_t *, lnode_t *); |
| void ow_list_transfer(list_t *, list_t *, lnode_t *first); |
| void ow_list_merge(list_t *, list_t *, int (const void *, const void *)); |
| void ow_list_sort(list_t *, int (const void *, const void *)); |
| lnode_t *ow_list_find(list_t *, const void *, int (const void *, const void *)); |
| int ow_list_is_sorted(list_t *, int (const void *, const void *)); |
| |
| #define list_extract ow_list_extract |
| #define list_transfer ow_list_transfer |
| #define list_merge ow_list_merge |
| #define list_sort ow_list_sort |
| #define list_find ow_list_find |
| #define list_is_sorted ow_list_is_sorted |
| |
| #ifdef __cplusplus |
| } |
| #endif |
| |
| #endif |