123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293 |
- #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 */
|