#ifndef PTR_LIST_H
#define PTR_LIST_H

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

/*
 * Generic pointer list manipulation code. 
 *
 * (C) Copyright Linus Torvalds 2003-2005
 */

/* Silly type-safety check ;) */
#define CHECK_TYPE(head,ptr)            (void)(&(ptr) == &(head)->list[0])
#define TYPEOF(head)                    __typeof__(&(head)->list[0])
#define VRFY_PTR_LIST(head)             (void)(sizeof((head)->list[0]))

#define LIST_NODE_NR (13)

#define DECLARE_PTR_LIST(listname, type)        \
        struct listname {                       \
                int nr:8;                       \
                int rm:8;                       \
                struct listname *prev;          \
                struct listname *next;          \
                type *list[LIST_NODE_NR];       \
        }

DECLARE_PTR_LIST(ptr_list, void);


void * undo_ptr_list_last(struct ptr_list **head);
void * delete_ptr_list_last(struct ptr_list **head);
int delete_ptr_list_entry(struct ptr_list **, void *, int);
int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry);
extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));

extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t);
extern int ptr_list_size(struct ptr_list *);
extern bool ptr_list_empty(const struct ptr_list *head);
extern bool ptr_list_multiple(const struct ptr_list *head);
extern int linearize_ptr_list(struct ptr_list *, void **, int);
extern void *first_ptr_list(struct ptr_list *);
extern void *last_ptr_list(struct ptr_list *);
extern void *ptr_list_nth_entry(struct ptr_list *, unsigned int idx);
extern void pack_ptr_list(struct ptr_list **);

/*
 * Hey, who said that you can't do overloading in C?
 *
 * You just have to be creative, and use some gcc
 * extensions..
 */
extern void **__add_ptr_list(struct ptr_list **, void *);
extern void **__add_ptr_list_tag(struct ptr_list **, void *, unsigned long);

#define add_ptr_list(list, ptr) ({                                      \
                struct ptr_list** head = (struct ptr_list**)(list);     \
                CHECK_TYPE(*(list),ptr);                                \
                (__typeof__(&(ptr))) __add_ptr_list(head, ptr);         \
        })
#define add_ptr_list_tag(list, ptr, tag) ({                             \
                struct ptr_list** head = (struct ptr_list**)(list);     \
                CHECK_TYPE(*(list),ptr);                                \
                (__typeof__(&(ptr))) __add_ptr_list_tag(head, ptr, tag);\
        })

extern void __free_ptr_list(struct ptr_list **);
#define free_ptr_list(list)     do {                                    \
                VRFY_PTR_LIST(*(list));                                 \
                __free_ptr_list((struct ptr_list **)(list));            \
        } while (0)


////////////////////////////////////////////////////////////////////////
// API
#define PREPARE_PTR_LIST(head, ptr) \
        DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)

#define NEXT_PTR_LIST(ptr) \
        DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)

#define RESET_PTR_LIST(ptr) \
        DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)

#define FINISH_PTR_LIST(ptr) \
        DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)

#define RECURSE_PTR_REVERSE(ptr, new)                                   \
        DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr,            \
                   new, __head##new, __list##new, __nr##new, PTR_ENTRY_UNTAG)


#define FOR_EACH_PTR(head, ptr) \
        DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)

#define FOR_EACH_PTR_TAG(head, ptr) \
        DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)

#define END_FOR_EACH_PTR(ptr) \
        DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)

#define FOR_EACH_PTR_REVERSE(head, ptr) \
        DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)

#define FOR_EACH_PTR_REVERSE_TAG(head, ptr) \
        DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)

#define END_FOR_EACH_PTR_REVERSE(ptr) \
        DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)

#define THIS_ADDRESS(ptr) \
        DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)

#define INSERT_CURRENT(new, ptr) \
        DO_INSERT_CURRENT(new, __head##ptr, __list##ptr, __nr##ptr)

#define DELETE_CURRENT_PTR(ptr) \
        DO_DELETE_CURRENT(__head##ptr, __list##ptr, __nr##ptr)

#define REPLACE_CURRENT_PTR(ptr, new_ptr)                               \
        do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)

// This replace the current element by a null-pointer.
// It's used when an element of the list must be removed
// but the address of the other elements must not be changed.
#define MARK_CURRENT_DELETED(ptr) \
        DO_MARK_CURRENT_DELETED(ptr, __list##ptr)

#define PACK_PTR_LIST(x) \
        pack_ptr_list((struct ptr_list **)(x))

#define CURRENT_TAG(ptr)        (3 & (unsigned long)*THIS_ADDRESS(ptr))
#define TAG_CURRENT(ptr,val)    update_tag(THIS_ADDRESS(ptr),val)

// backward compatibility for smatch
#define FOR_EACH_PTR_NOTAG(list, ptr)   FOR_EACH_PTR(list, ptr)
#define END_FOR_EACH_PTR_NOTAG(ptr)     END_FOR_EACH_PTR(ptr)

////////////////////////////////////////////////////////////////////////
// Implementation
#define PTR_UNTAG(p)            ((void*)(~3UL & (unsigned long)(p)))
#define PTR_ENTRY_NOTAG(h,i)    ((h)->list[i])
#define PTR_ENTRY_UNTAG(h,i)    PTR_UNTAG((h)->list[i])


#define PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY)                  \
        do {                                                            \
                if (__nr < __list->nr) {                                \
                        ptr = PTR_ENTRY(__list,__nr);                   \
                        __nr++;                                         \
                        break;                                          \
                }                                                       \
                ptr = NULL;                                             \
                __nr = 0;                                               \
        } while ((__list = __list->next) != __head)                     \

#define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY)          \
        do {                                                            \
                __typeof__(head) __head = (head);                       \
                __typeof__(head) __list = __head;                       \
                int __nr = 0;                                           \
                ptr = NULL;                                             \
                if (__head) {                                           \
                        PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
                }                                                       \

#define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY)                   \
                if (ptr) {                                              \
                        PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
                }

#define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY)                  \
        do {                                                            \
                __nr = 0;                                               \
                __list = __head;                                        \
                if (__head)                                             \
                        PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
        } while (0)

#define DO_FINISH(ptr, __head, __list, __nr)                            \
                VRFY_PTR_LIST(__head); /* Sanity-check nesting */       \
        } while (0)

#define DO_FOR_EACH(head, ptr, __head, __list, __nr, PTR_ENTRY) do {    \
        __typeof__(head) __head = (head);                               \
        __typeof__(head) __list = __head;                               \
        int __nr;                                                       \
        if (!__head)                                                    \
                break;                                                  \
        do {                                                            \
                for (__nr = 0; __nr < __list->nr; __nr++) {             \
                        ptr = PTR_ENTRY(__list,__nr);                   \
                        if (__list->rm && !ptr)                         \
                                continue;                               \

#define DO_END_FOR_EACH(ptr, __head, __list, __nr)                      \
                }                                                       \
        } while ((__list = __list->next) != __head);                    \
} while (0)

#define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \
        __typeof__(head) __head = (head);                               \
        __typeof__(head) __list = __head;                               \
        int __nr;                                                       \
        if (!head)                                                      \
                break;                                                  \
        do {                                                            \
                __list = __list->prev;                                  \
                __nr = __list->nr;                                      \
                while (--__nr >= 0) {                                   \
                        ptr = PTR_ENTRY(__list,__nr);                   \
                        if (__list->rm && !ptr)                         \
                                continue;                               \


#define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr)              \
                }                                                       \
        } while (__list != __head);                                     \
} while (0)

#define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead,           \
                   __newlist, __newnr, PTR_ENTRY) do {                  \
        __typeof__(__head) __newhead = __head;                          \
        __typeof__(__head) __newlist = __list;                          \
        int __newnr = __nr;                                             \
        new = ptr;                                                      \
        goto __inside##new;                                             \
        do {                                                            \
                __newlist = __newlist->prev;                            \
                __newnr = __newlist->nr;                                \
        __inside##new:                                                  \
                while (--__newnr >= 0) {                                \
                        new = PTR_ENTRY(__newlist,__newnr);             \

#define DO_THIS_ADDRESS(ptr, __head, __list, __nr)                      \
        (&__list->list[__nr])


extern void split_ptr_list_head(struct ptr_list *);

#define DO_INSERT_CURRENT(new, __head, __list, __nr) do {               \
        TYPEOF(__head) __this, __last;                                  \
        if (__list->nr == LIST_NODE_NR) {                               \
                split_ptr_list_head((struct ptr_list*)__list);          \
                if (__nr >= __list->nr) {                               \
                        __nr -= __list->nr;                             \
                        __list = __list->next;                          \
                }                                                       \
        }                                                               \
        __this = __list->list + __nr;                                   \
        __last = __list->list + __list->nr - 1;                         \
        while (__last >= __this) {                                      \
                __last[1] = __last[0];                                  \
                __last--;                                               \
        }                                                               \
        *__this = (new);                                                \
        __list->nr++;                                                   \
} while (0)

#define DO_DELETE_CURRENT(__head, __list, __nr) do {                    \
        TYPEOF(__head) __this = __list->list + __nr;                    \
        TYPEOF(__head) __last = __list->list + __list->nr - 1;          \
        while (__this < __last) {                                       \
                __this[0] = __this[1];                                  \
                __this++;                                               \
        }                                                               \
        *__this = (void *)0xf0f0f0f0;                                   \
        __list->nr--; __nr--;                                           \
} while (0)


#define DO_MARK_CURRENT_DELETED(ptr, __list) do {                       \
                REPLACE_CURRENT_PTR(ptr, NULL);                         \
                __list->rm++;                                           \
        } while (0)


static inline void update_tag(void *p, unsigned long tag)
{
        unsigned long *ptr = p;
        *ptr = tag | (~3UL & *ptr);
}

static inline void *tag_ptr(void *ptr, unsigned long tag)
{
        return (void *)(tag | (unsigned long)ptr);
}

#endif /* PTR_LIST_H */