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