ptrlist.h - pub/scm/devel/sparse/sparse - Git at Google

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