/*
 * Doubly linked list implementation with sentinel node.
 */

#ifndef _DBLLIST_H
# define _DBLLIST_H

#define _GNU_SOURCE

#include <stdlib.h>
#include <stdbool.h>

/* This is supposed to be defined in stdlib.h (I also see it
 * in search.h) but ifdef __USE_GNU surrounds it and for
 * some reason that I can't determine, defining _GNU_SOURCE
 * isn't enough to pull this in.  I can't figure out why
 * this is; according to my read of features.h this should
 * be defined.  I give up tracking it down for now and just
 * define it here. */
typedef __compar_fn_t comparison_fn_t;

/*
 * Basic storage handle for an item of data in the list.
 */
typedef struct dbll_node {
        struct dbll_node        *next;
        struct dbll_node        *prev;
        void                    *item;
} dbll_node_t;

/*
 * Basic storage handle for the list of items.  The sentinel
 * node will always contain a null item.  Note that the
 * library does not guarantee that any other node doesn't
 * also have a null item, but this should be enforced by the
 * program making use of our facilities.
 */
typedef struct dbll_head {
        dbll_node_t             *sentinel;
        unsigned long int       nr_nodes; /* not including
                                             sentinel */
} dbll_head_t;

typedef bool    (*dbll_iterate_fn_t)    (dbll_node_t *);
typedef void    (*dbll_deletion_fn_t)   (void *);
typedef void    *(*dbll_copy_fn_t)      (void *);

/*
 * Methods implemented so far by the libary.
 */

extern dbll_head_t      *dbll_create            (void);
extern dbll_head_t      *dbll_copy              (dbll_head_t *orig,
                                                 dbll_copy_fn_t copy_fn);

extern void             dbll_destroy            (dbll_head_t *list);
extern void             dbll_sort               (dbll_head_t *list,
                                                 comparison_fn_t comparison_fn);
extern void             dbll_replace            (dbll_head_t *list,
                                                 void *key,
                                                 comparison_fn_t comparison_fn,
                                                 dbll_deletion_fn_t deletion_fn);

extern void             *dbll_search            (dbll_head_t *list,
                                                 void *key,
                                                 comparison_fn_t comparison_fn);
extern void             *dbll_item              (dbll_node_t *node);

extern dbll_node_t      *dbll_insert_before     (dbll_node_t *node, void *item);
extern dbll_node_t      *dbll_insert_after      (dbll_node_t *node, void *item);
extern dbll_node_t      *dbll_add               (dbll_head_t *list, void *item);
extern dbll_node_t      *dbll_delete            (dbll_head_t *list,
                                                 dbll_node_t *node);

extern dbll_node_t      *dbll_first             (dbll_head_t *list);
extern dbll_node_t      *dbll_last              (dbll_head_t *list);
extern dbll_node_t      *dbll_next              (dbll_node_t *node);

extern unsigned int     dbll_iterate            (dbll_head_t *list,
                                                 dbll_node_t *first,
                                                 dbll_node_t *last,
                                                 dbll_iterate_fn_t callback);
extern unsigned int     dbll_iterate_all        (dbll_head_t *list,
                                                 dbll_iterate_fn_t callback);
extern unsigned int     dbll_iterate_all_rev    (dbll_head_t *list,
                                                 dbll_iterate_fn_t callback);

bool                    print_node_as_stringpair        (dbll_node_t *node);

/*
 * Methods the library does not yet provide, but the API is obvious so I
 * document here.
 */
# if 0
dbll_head_t *   dbll_split      (dbll_head_t *list, dbll_node_t *atnode);
dbll_head_t *   dbll_splice     (dbll_head_t *list1, *list2);
# endif

#endif

/* abstract the particulars of the list implementation */
#define list_node_t                             dbll_node_t
#define list_head_t                             dbll_head_t
#define list_create                             dbll_create
#define list_copy                               dbll_copy
#define list_destroy                            dbll_destroy
#define list_sort                               dbll_sort
#define list_replace                            dbll_replace
#define list_search                             dbll_search
#define list_item                               dbll_item
#define list_insert_before                      dbll_insert_before
#define list_insert_after                       dbll_insert_after
#define list_add                                dbll_add
#define list_delete                             dbll_delete
#define list_first                              dbll_first
#define list_last                               dbll_last
#define list_next                               dbll_next
#define list_iterate                            dbll_iterate
#define list_iterate_all                        dbll_iterate_all
#define list_iterate_all_rev                    dbll_iterate_all_rev