Print this page
new smatch
*** 1,268 ****
#ifndef PTR_LIST_H
#define PTR_LIST_H
#include <stdlib.h>
/*
* Generic pointer list manipulation code.
*
* (C) Copyright Linus Torvalds 2003-2005
*/
/* Silly type-safety check ;) */
- #define DECLARE_PTR_LIST(listname,type) struct listname { type *list[1]; }
#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]))
! /*
! * The "unnecessary" statement expression is there to shut up a totally
! * bogus gcc warning about unused expressions, brought on by the fact
! * that we cast the result to the proper type.
! */
! #define MKTYPE(head,expr) ({ (TYPEOF(head))(expr); })
! #define LIST_NODE_NR (29)
! struct ptr_list {
! int nr:8;
! int rm:8;
! struct ptr_list *prev;
! struct ptr_list *next;
! void *list[LIST_NODE_NR];
! };
- #define ptr_list_empty(x) ((x) == NULL)
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);
extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));
- extern void **__add_ptr_list(struct ptr_list **, void *, unsigned long);
extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
! extern void __free_ptr_list(struct ptr_list **);
extern int ptr_list_size(struct ptr_list *);
extern int linearize_ptr_list(struct ptr_list *, void **, int);
/*
* Hey, who said that you can't do overloading in C?
*
* You just have to be creative, and use some gcc
* extensions..
*/
! #define add_ptr_list_tag(list,entry,tag) \
! MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), (entry), (tag))))
! #define add_ptr_list_notag(list,entry) \
! MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), \
! (void *)((unsigned long)(entry) & ~3UL), \
! (unsigned long)(entry) & 3)))
! #define add_ptr_list(list,entry) \
! add_ptr_list_tag(list,entry,0)
! #define free_ptr_list(list) \
! do { VRFY_PTR_LIST(*(list)); __free_ptr_list((struct ptr_list **)(list)); } while (0)
! #define PTR_ENTRY_NOTAG(h,i) ((h)->list[i])
! #define PTR_ENTRY(h,i) (void *)(~3UL & (unsigned long)PTR_ENTRY_NOTAG(h,i))
! static inline void *first_ptr_list(struct ptr_list *list)
! {
! struct ptr_list *head = list;
- if (!list)
- return NULL;
! while (list->nr == 0) {
! list = list->next;
! if (list == head)
! return NULL;
! }
! return PTR_ENTRY(list, 0);
! }
! static inline void *last_ptr_list(struct ptr_list *list)
! {
! struct ptr_list *head = list;
! if (!list)
! return NULL;
! list = list->prev;
! while (list->nr == 0) {
! if (list == head)
! return NULL;
! list = list->prev;
! }
! return PTR_ENTRY(list, list->nr-1);
! }
! #define PTR_DEREF(__head, idx, PTR_ENTRY) ({ \
! struct ptr_list *__list = __head; \
! while (__list && __list->nr == 0) { \
! __list = __list->next; \
! if (__list == __head) \
! __list = NULL; \
} \
! __list ? PTR_ENTRY(__list, idx) : NULL; \
! })
#define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY) \
do { \
! struct ptr_list *__head = (struct ptr_list *) (head); \
! struct ptr_list *__list = __head; \
int __nr = 0; \
! CHECK_TYPE(head,ptr); \
! ptr = PTR_DEREF(__head, 0, PTR_ENTRY); \
#define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \
if (ptr) { \
! if (++__nr < __list->nr) { \
! ptr = PTR_ENTRY(__list,__nr); \
! } else { \
! __list = __list->next; \
! ptr = NULL; \
! while (__list->nr == 0 && __list != __head) \
! __list = __list->next; \
! if (__list != __head) { \
! __nr = 0; \
! ptr = PTR_ENTRY(__list,0); \
! } \
! } \
}
#define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY) \
do { \
__nr = 0; \
__list = __head; \
! if (__head) ptr = PTR_DEREF(__head, 0, PTR_ENTRY); \
} while (0)
#define DO_FINISH(ptr, __head, __list, __nr) \
! (void)(__nr); /* Sanity-check nesting */ \
} while (0)
- #define PREPARE_PTR_LIST(head, ptr) \
- DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
-
- #define NEXT_PTR_LIST(ptr) \
- DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
-
- #define RESET_PTR_LIST(ptr) \
- DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
-
- #define FINISH_PTR_LIST(ptr) \
- DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
-
#define DO_FOR_EACH(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \
! struct ptr_list *__head = (struct ptr_list *) (head); \
! struct ptr_list *__list = __head; \
! CHECK_TYPE(head,ptr); \
! if (__head) { \
! do { int __nr; \
! for (__nr = 0; __nr < __list->nr; __nr++) { \
do { \
ptr = PTR_ENTRY(__list,__nr); \
if (__list->rm && !ptr) \
continue; \
- do {
#define DO_END_FOR_EACH(ptr, __head, __list, __nr) \
- } while (0); \
- } while (0); \
} \
} while ((__list = __list->next) != __head); \
- } \
} while (0)
#define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \
! struct ptr_list *__head = (struct ptr_list *) (head); \
! struct ptr_list *__list = __head; \
! CHECK_TYPE(head,ptr); \
! if (__head) { \
! do { int __nr; \
__list = __list->prev; \
__nr = __list->nr; \
while (--__nr >= 0) { \
- do { \
ptr = PTR_ENTRY(__list,__nr); \
if (__list->rm && !ptr) \
continue; \
- do {
#define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \
- } while (0); \
- } while (0); \
} \
} while (__list != __head); \
- } \
} while (0)
#define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead, \
__newlist, __newnr, PTR_ENTRY) do { \
! struct ptr_list *__newhead = __head; \
! struct ptr_list *__newlist = __list; \
int __newnr = __nr; \
new = ptr; \
goto __inside##new; \
- if (1) { \
do { \
__newlist = __newlist->prev; \
__newnr = __newlist->nr; \
__inside##new: \
while (--__newnr >= 0) { \
- do { \
new = PTR_ENTRY(__newlist,__newnr); \
- do {
- #define RECURSE_PTR_REVERSE(ptr, new) \
- DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, \
- new, __head##new, __list##new, __nr##new, PTR_ENTRY)
-
#define DO_THIS_ADDRESS(ptr, __head, __list, __nr) \
! ((__typeof__(&(ptr))) (__list->list + __nr))
- #define FOR_EACH_PTR(head, ptr) \
- DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
- #define END_FOR_EACH_PTR(ptr) \
- DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)
-
- #define FOR_EACH_PTR_NOTAG(head, ptr) \
- DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
-
- #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
-
- #define FOR_EACH_PTR_REVERSE(head, ptr) \
- DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
-
- #define END_FOR_EACH_PTR_REVERSE(ptr) \
- DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)
-
- #define FOR_EACH_PTR_REVERSE_NOTAG(head, ptr) \
- DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
-
- #define END_FOR_EACH_PTR_REVERSE_NOTAG(ptr) END_FOR_EACH_PTR_REVERSE(ptr)
-
- #define THIS_ADDRESS(ptr) \
- DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
-
extern void split_ptr_list_head(struct ptr_list *);
! #define DO_SPLIT(ptr, __head, __list, __nr) do { \
! split_ptr_list_head(__list); \
if (__nr >= __list->nr) { \
__nr -= __list->nr; \
__list = __list->next; \
! }; \
! } while (0)
!
! #define DO_INSERT_CURRENT(new, ptr, __head, __list, __nr) do { \
! void **__this, **__last; \
! if (__list->nr == LIST_NODE_NR) \
! DO_SPLIT(ptr, __head, __list, __nr); \
__this = __list->list + __nr; \
__last = __list->list + __list->nr - 1; \
while (__last >= __this) { \
__last[1] = __last[0]; \
__last--; \
--- 1,257 ----
#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--; \
*** 269,310 ****
} \
*__this = (new); \
__list->nr++; \
} while (0)
! #define INSERT_CURRENT(new, ptr) \
! DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)
!
! #define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do { \
! void **__this = __list->list + __nr; \
! void **__last = __list->list + __list->nr - 1; \
while (__this < __last) { \
__this[0] = __this[1]; \
__this++; \
} \
*__this = (void *)0xf0f0f0f0; \
__list->nr--; __nr--; \
} while (0)
- #define DELETE_CURRENT_PTR(ptr) \
- DO_DELETE_CURRENT(ptr, __head##ptr, __list##ptr, __nr##ptr)
- #define REPLACE_CURRENT_PTR(ptr, new_ptr) \
- do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
-
#define DO_MARK_CURRENT_DELETED(ptr, __list) do { \
REPLACE_CURRENT_PTR(ptr, NULL); \
__list->rm++; \
} while (0)
- #define MARK_CURRENT_DELETED(ptr) \
- DO_MARK_CURRENT_DELETED(ptr, __list##ptr)
- extern void pack_ptr_list(struct ptr_list **);
-
- #define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x))
-
static inline void update_tag(void *p, unsigned long tag)
{
unsigned long *ptr = p;
*ptr = tag | (~3UL & *ptr);
}
--- 258,285 ----
} \
*__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);
}
*** 312,320 ****
static inline void *tag_ptr(void *ptr, unsigned long tag)
{
return (void *)(tag | (unsigned long)ptr);
}
- #define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))
- #define TAG_CURRENT(ptr,val) update_tag(THIS_ADDRESS(ptr),val)
-
#endif /* PTR_LIST_H */
--- 287,292 ----