Move the ptrlist macros out of the sparse "lib.[ch]" files.

They rate their own "ptrlist" library status, since they are definitely potentially useful outside of sparse.
author: Linus Torvalds <torvalds@ppc970.osdl.org> 2005-03-12 17:53:41 -0700
committer: Linus Torvalds <torvalds@ppc970.osdl.org> 2005-04-07 21:06:29 -0700
commit: 77ac63127dc8981264b31bcfaac825c62971bca2 (patch)
tree: 27cd8abb6be43358f0e45201687103dc242e6746
parent: 67cb76f7d0c76d52588ba6cd24f70ae4e141406c (diff)
download: sparse-dev-77ac63127dc8981264b31bcfaac825c62971bca2.tar.gz
5 files changed, 487 insertions, 462 deletions
diff --git a/Makefile b/Makefile
index 3aea7032..ed6fdb37 100644
--- a/Makefile
+++ b/Makefile
@@ -20,11 +20,11 @@ PROGRAMS=test-lexing test-parsing obfuscate check compile test-linearize example
 
 LIB_H=    token.h parse.h lib.h symbol.h scope.h expression.h target.h \
 	  linearize.h bitmap.h ident-list.h compat.h flow.h allocate.h \
-	  storage.h
+	  storage.h ptrlist.h
 
 LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
 	  expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \
-	  sort.o allocate.o compat-$(OS).o \
+	  sort.o allocate.o compat-$(OS).o ptrlist.o \
 	  flow.o cse.o simplify.o memops.o liveness.o storage.o
 
 LIB_FILE= libsparse.a
@@ -122,3 +122,5 @@ pre-process.h:
 
 clean:
 	rm -f *.[oasi] core core.[0-9]* $(PROGRAMS) $(SLIB_FILE) pre-process.h
+
+% : SCCS/s.%s
diff --git a/lib.c b/lib.c
index ff3880b2..87617799 100644
--- a/lib.c
+++ b/lib.c
@@ -70,218 +70,6 @@ unsigned int hexval(unsigned int c)
 	return retval;
 }
 
-int ptr_list_size(struct ptr_list *head)
-{
-	int nr = 0;
-
-	if (head) {
-		struct ptr_list *list = head;
-		do {
-			nr += list->nr;
-		} while ((list = list->next) != head);
-	}
-	return nr;
-}
-
-/*
- * Linearize the entries of a list up to a total of 'max',
- * and return the nr of entries linearized.
- *
- * The array to linearize into (second argument) should really
- * be "void *x[]", but we want to let people fill in any kind
- * of pointer array, so let's just call it "void *".
- */
-int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
-{
-	int nr = 0;
-	if (head && max > 0) {
-		struct ptr_list *list = head;
-
-		do {
-			int i = list->nr;
-			if (i > max) 
-				i = max;
-			memcpy(arr, list->list, i*sizeof(void *));
-			arr += i;
-			nr += i;
-			max -= i;
-			if (!max)
-				break;
-		} while ((list = list->next) != head);
-	}
-	return nr;
-}
-
-/*
- * When we've walked the list and deleted entries,
- * we may need to re-pack it so that we don't have
- * any empty blocks left (empty blocks upset the
- * walking code
- */
-void pack_ptr_list(struct ptr_list **listp)
-{
-	struct ptr_list *head = *listp;
-
-	if (head) {
-		struct ptr_list *entry = head;
-		do {
-			struct ptr_list *next;
-restart:
-			next = entry->next;
-			if (!entry->nr) {
-				struct ptr_list *prev;
-				if (next == entry) {
-					*listp = NULL;
-					return;
-				}
-				prev = entry->prev;
-				prev->next = next;
-				next->prev = prev;
-				free(entry);
-				if (entry == head) {
-					*listp = next;
-					head = next;
-					entry = next;
-					goto restart;
-				}
-			}
-			entry = next;
-		} while (entry != head);
-	}
-}		
-
-void split_ptr_list_head(struct ptr_list *head)
-{
-	int old = head->nr, nr = old / 2;
-	struct ptr_list *newlist = malloc(sizeof(*newlist));
-	struct ptr_list *next = head->next;
-
-	old -= nr;
-	head->nr = old;
-	newlist->next = next;
-	next->prev = newlist;
-	newlist->prev = head;
-	head->next = newlist;
-	newlist->nr = nr;
-	memcpy(newlist->list, head->list + old, nr * sizeof(void *));
-	memset(head->list + old, 0xf0, nr * sizeof(void *));
-}
-
-void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
-{
-	struct ptr_list *list = *listp;
-	struct ptr_list *last = NULL; /* gcc complains needlessly */
-	void **ret;
-	int nr;
-
-	/* The low two bits are reserved for tags */
-	assert((3 & (unsigned long)ptr) == 0);
-	assert((~3 & tag) == 0);
-	ptr = (void *)(tag | (unsigned long)ptr);
-
-	if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
-		struct ptr_list *newlist = malloc(sizeof(*newlist));
-		if (!newlist)
-			die("out of memory for symbol/statement lists");
-		memset(newlist, 0, sizeof(*newlist));
-		if (!list) {
-			newlist->next = newlist;
-			newlist->prev = newlist;
-			*listp = newlist;
-		} else {
-			newlist->prev = last;
-			newlist->next = list;
-			list->prev = newlist;
-			last->next = newlist;
-		}
-		last = newlist;
-		nr = 0;
-	}
-	ret = last->list + nr;
-	*ret = ptr;
-	nr++;
-	last->nr = nr;
-	return ret;
-}
-
-int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
-{
-	void *ptr;
-
-	FOR_EACH_PTR(*list, ptr) {
-		if (ptr == entry) {
-			DELETE_CURRENT_PTR(ptr);
-			if (!--count)
-				goto out;
-		}
-	} END_FOR_EACH_PTR(ptr);
-	assert(count <= 0);
-out:
-	pack_ptr_list(list);
-	return count;
-}
-
-int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
-{
-	void *ptr;
-
-	FOR_EACH_PTR(*list, ptr) {
-		if (ptr==old_ptr) {
-			REPLACE_CURRENT_PTR(ptr, new_ptr);
-			if (!--count)
-				goto out;
-		}
-	}END_FOR_EACH_PTR(ptr);
-	assert(count <= 0);
-out:
-	return count;
-}
-
-void * delete_ptr_list_last(struct ptr_list **head)
-{
-	void *ptr = NULL;
-	struct ptr_list *last, *first = *head;
-
-	if (!first)
-		return NULL;
-	last = first->prev;
-	if (last->nr)
-		ptr = last->list[--last->nr];
-	if (last->nr <=0) {
-		first->prev = last->prev;
-		last->prev->next = first;
-		if (last == first)
-			*head = NULL;
-		free(last);
-	}
-	return ptr;
-}
-
-void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
-{
-	void *entry;
-	FOR_EACH_PTR(a, entry) {
-		add_ptr_list(b, entry);
-	} END_FOR_EACH_PTR(entry);
-}
-
-void __free_ptr_list(struct ptr_list **listp)
-{
-	struct ptr_list *tmp, *list = *listp;
-
-	if (!list)
-		return;
-
-	list->prev->next = NULL;
-	while (list) {
-		tmp = list;
-		list = list->next;
-		free(tmp);
-	}
-
-	*listp = NULL;
-}
-
 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 {
 	static char buffer[512];
diff --git a/lib.h b/lib.h
index e768963b..cf672e64 100644
--- a/lib.h
+++ b/lib.h
@@ -15,13 +15,11 @@
  */
 
 #include "compat.h"
+#include "ptrlist.h"
 
 extern int verbose, optimize, preprocessing;
 extern int repeat_phase, merge_phi_sources;
 
-#define container(ptr, type, member) \
-	(type *)((void *)(ptr) - offsetof(type, member))
-
 extern unsigned int hexval(unsigned int c);
 
 struct position {
@@ -45,12 +43,6 @@ struct instruction;
 struct multijmp;
 struct pseudo;
 
-/* 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]))
-
 DECLARE_PTR_LIST(symbol_list, struct symbol);
 DECLARE_PTR_LIST(statement_list, struct statement);
 DECLARE_PTR_LIST(expression_list, struct expression);
@@ -75,42 +67,8 @@ extern void error(struct position, const char *, ...) FORMAT_ATTR(2);
 extern void error_die(struct position, const char *, ...) FORMAT_ATTR(2);
 #undef FORMAT_ATTR
 
-#define LIST_NODE_NR (29)
-
-struct ptr_list {
-	int nr;
-	struct ptr_list *prev;
-	struct ptr_list *next;
-	void *list[LIST_NODE_NR];
-};
-
-#define ptr_list_empty(x) ((x) == NULL)
-
-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 tag);
-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 char **handle_switch(char *arg, char **next);
 extern void add_pre_buffer(const char *fmt, ...);
-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) \
-	(TYPEOF(*(list))) (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), (entry), (tag)))
-#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)
 
 extern unsigned int pre_buffer_size;
 extern unsigned char pre_buffer[8192];
@@ -171,24 +129,6 @@ static inline struct basic_block * delete_last_basic_block(struct basic_block_li
 	return delete_ptr_list_last((struct ptr_list **)head);
 }
 
-#define PTR_ENTRY(h,i)	(void *)(~3UL & (unsigned long)(h)->list[i])
-
-static inline void *first_ptr_list(struct ptr_list *list)
-{
-	if (!list)
-		return NULL;
-	return PTR_ENTRY(list, 0);
-}
-
-static inline void *last_ptr_list(struct ptr_list *list)
-{
-
-	if (!list)
-		return NULL;
-	list = list->prev;
-	return PTR_ENTRY(list, list->nr-1);
-}
-
 static inline struct basic_block *first_basic_block(struct basic_block_list *head)
 {
 	return first_ptr_list((struct ptr_list *)head);
@@ -238,193 +178,6 @@ static inline void add_expression(struct expression_list **list, struct expressi
 	add_ptr_list(list, expr);
 }
 
-#define DO_PREPARE(head, ptr, __head, __list, __nr)					\
-	do {										\
-		struct ptr_list *__head = (struct ptr_list *) (head);			\
-		struct ptr_list *__list = __head;					\
-		int __nr = 0;								\
-		CHECK_TYPE(head,ptr);							\
-		if (__head) ptr = PTR_ENTRY(__head, 0);					\
-		else ptr = NULL
-
-#define DO_NEXT(ptr, __head, __list, __nr)						\
-		if (ptr) {								\
-			if (++__nr < __list->nr) {					\
-				ptr = PTR_ENTRY(__list,__nr);				\
-			} else {							\
-				__list = __list->next;					\
-				ptr = NULL;						\
-				if (__list != __head) {					\
-					__nr = 0;					\
-					ptr = PTR_ENTRY(__list,0);			\
-				}							\
-			}								\
-		}
-
-#define DO_RESET(ptr, __head, __list, __nr)						\
-	do {										\
-		__nr = 0;								\
-		__list = __head;							\
-		if (__head) ptr = PTR_ENTRY(__head, 0);					\
-	} 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)
-
-#define NEXT_PTR_LIST(ptr) \
-	DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr)
-
-#define RESET_PTR_LIST(ptr) \
-	DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr)
-
-#define FINISH_PTR_LIST(ptr) \
-	DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
-
-#define DO_FOR_EACH(head, ptr, __head, __list, __nr) 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);			\
-					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) 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);			\
-					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) 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)
-
-#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)
-
-#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)
-
-#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)
-
-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--;								\
-	}										\
-	*__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)
-
-extern void pack_ptr_list(struct ptr_list **);
-
-#define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x))
-
 #define hashval(x) ((unsigned long)(x))
 
-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);
-}
-
-#define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))
-#define TAG_CURRENT(ptr,val)	update_tag(THIS_ADDRESS(ptr),val)
-
 #endif
diff --git a/ptrlist.c b/ptrlist.c
new file mode 100644
index 00000000..065891c3
--- /dev/null
+++ b/ptrlist.c
@@ -0,0 +1,223 @@
+/*
+ * ptrlist.c
+ *
+ * Pointer list manipulation
+ *
+ * (C) Copyright Linus Torvalds 2003-2005
+ */
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include "ptrlist.h"
+
+int ptr_list_size(struct ptr_list *head)
+{
+	int nr = 0;
+
+	if (head) {
+		struct ptr_list *list = head;
+		do {
+			nr += list->nr;
+		} while ((list = list->next) != head);
+	}
+	return nr;
+}
+
+/*
+ * Linearize the entries of a list up to a total of 'max',
+ * and return the nr of entries linearized.
+ *
+ * The array to linearize into (second argument) should really
+ * be "void *x[]", but we want to let people fill in any kind
+ * of pointer array, so let's just call it "void *".
+ */
+int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
+{
+	int nr = 0;
+	if (head && max > 0) {
+		struct ptr_list *list = head;
+
+		do {
+			int i = list->nr;
+			if (i > max) 
+				i = max;
+			memcpy(arr, list->list, i*sizeof(void *));
+			arr += i;
+			nr += i;
+			max -= i;
+			if (!max)
+				break;
+		} while ((list = list->next) != head);
+	}
+	return nr;
+}
+
+/*
+ * When we've walked the list and deleted entries,
+ * we may need to re-pack it so that we don't have
+ * any empty blocks left (empty blocks upset the
+ * walking code
+ */
+void pack_ptr_list(struct ptr_list **listp)
+{
+	struct ptr_list *head = *listp;
+
+	if (head) {
+		struct ptr_list *entry = head;
+		do {
+			struct ptr_list *next;
+restart:
+			next = entry->next;
+			if (!entry->nr) {
+				struct ptr_list *prev;
+				if (next == entry) {
+					*listp = NULL;
+					return;
+				}
+				prev = entry->prev;
+				prev->next = next;
+				next->prev = prev;
+				free(entry);
+				if (entry == head) {
+					*listp = next;
+					head = next;
+					entry = next;
+					goto restart;
+				}
+			}
+			entry = next;
+		} while (entry != head);
+	}
+}		
+
+void split_ptr_list_head(struct ptr_list *head)
+{
+	int old = head->nr, nr = old / 2;
+	struct ptr_list *newlist = malloc(sizeof(*newlist));
+	struct ptr_list *next = head->next;
+
+	old -= nr;
+	head->nr = old;
+	newlist->next = next;
+	next->prev = newlist;
+	newlist->prev = head;
+	head->next = newlist;
+	newlist->nr = nr;
+	memcpy(newlist->list, head->list + old, nr * sizeof(void *));
+	memset(head->list + old, 0xf0, nr * sizeof(void *));
+}
+
+void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag)
+{
+	struct ptr_list *list = *listp;
+	struct ptr_list *last = NULL; /* gcc complains needlessly */
+	void **ret;
+	int nr;
+
+	/* The low two bits are reserved for tags */
+	assert((3 & (unsigned long)ptr) == 0);
+	assert((~3 & tag) == 0);
+	ptr = (void *)(tag | (unsigned long)ptr);
+
+	if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
+		struct ptr_list *newlist = malloc(sizeof(*newlist));
+		assert(newlist);
+		memset(newlist, 0, sizeof(*newlist));
+		if (!list) {
+			newlist->next = newlist;
+			newlist->prev = newlist;
+			*listp = newlist;
+		} else {
+			newlist->prev = last;
+			newlist->next = list;
+			list->prev = newlist;
+			last->next = newlist;
+		}
+		last = newlist;
+		nr = 0;
+	}
+	ret = last->list + nr;
+	*ret = ptr;
+	nr++;
+	last->nr = nr;
+	return ret;
+}
+
+int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
+{
+	void *ptr;
+
+	FOR_EACH_PTR(*list, ptr) {
+		if (ptr == entry) {
+			DELETE_CURRENT_PTR(ptr);
+			if (!--count)
+				goto out;
+		}
+	} END_FOR_EACH_PTR(ptr);
+	assert(count <= 0);
+out:
+	pack_ptr_list(list);
+	return count;
+}
+
+int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr, void *new_ptr, int count)
+{
+	void *ptr;
+
+	FOR_EACH_PTR(*list, ptr) {
+		if (ptr==old_ptr) {
+			REPLACE_CURRENT_PTR(ptr, new_ptr);
+			if (!--count)
+				goto out;
+		}
+	}END_FOR_EACH_PTR(ptr);
+	assert(count <= 0);
+out:
+	return count;
+}
+
+void * delete_ptr_list_last(struct ptr_list **head)
+{
+	void *ptr = NULL;
+	struct ptr_list *last, *first = *head;
+
+	if (!first)
+		return NULL;
+	last = first->prev;
+	if (last->nr)
+		ptr = last->list[--last->nr];
+	if (last->nr <=0) {
+		first->prev = last->prev;
+		last->prev->next = first;
+		if (last == first)
+			*head = NULL;
+		free(last);
+	}
+	return ptr;
+}
+
+void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
+{
+	void *entry;
+	FOR_EACH_PTR(a, entry) {
+		add_ptr_list(b, entry);
+	} END_FOR_EACH_PTR(entry);
+}
+
+void __free_ptr_list(struct ptr_list **listp)
+{
+	struct ptr_list *tmp, *list = *listp;
+
+	if (!list)
+		return;
+
+	list->prev->next = NULL;
+	while (list) {
+		tmp = list;
+		list = list->next;
+		free(tmp);
+	}
+
+	*listp = NULL;
+}
diff --git a/ptrlist.h b/ptrlist.h
new file mode 100644
index 00000000..42e69e00
--- /dev/null
+++ b/ptrlist.h
@@ -0,0 +1,259 @@
+#ifndef PTR_LIST_H
+#define PTR_LIST_H
+
+/*
+ * Generic pointer list manipulation code. 
+ *
+ * (C) Copyright Linus Torvalds 2003-2005
+ */
+
+#define container(ptr, type, member) \
+	(type *)((void *)(ptr) - offsetof(type, member))
+
+/* 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]))
+
+#define LIST_NODE_NR (29)
+
+struct ptr_list {
+	int nr;
+	struct ptr_list *prev;
+	struct ptr_list *next;
+	void *list[LIST_NODE_NR];
+};
+
+#define ptr_list_empty(x) ((x) == NULL)
+
+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 tag);
+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) \
+	(TYPEOF(*(list))) (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), (entry), (tag)))
+#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(h,i)	(void *)(~3UL & (unsigned long)(h)->list[i])
+
+static inline void *first_ptr_list(struct ptr_list *list)
+{
+	if (!list)
+		return NULL;
+	return PTR_ENTRY(list, 0);
+}
+
+static inline void *last_ptr_list(struct ptr_list *list)
+{
+
+	if (!list)
+		return NULL;
+	list = list->prev;
+	return PTR_ENTRY(list, list->nr-1);
+}
+
+#define DO_PREPARE(head, ptr, __head, __list, __nr)					\
+	do {										\
+		struct ptr_list *__head = (struct ptr_list *) (head);			\
+		struct ptr_list *__list = __head;					\
+		int __nr = 0;								\
+		CHECK_TYPE(head,ptr);							\
+		if (__head) ptr = PTR_ENTRY(__head, 0);					\
+		else ptr = NULL
+
+#define DO_NEXT(ptr, __head, __list, __nr)						\
+		if (ptr) {								\
+			if (++__nr < __list->nr) {					\
+				ptr = PTR_ENTRY(__list,__nr);				\
+			} else {							\
+				__list = __list->next;					\
+				ptr = NULL;						\
+				if (__list != __head) {					\
+					__nr = 0;					\
+					ptr = PTR_ENTRY(__list,0);			\
+				}							\
+			}								\
+		}
+
+#define DO_RESET(ptr, __head, __list, __nr)						\
+	do {										\
+		__nr = 0;								\
+		__list = __head;							\
+		if (__head) ptr = PTR_ENTRY(__head, 0);					\
+	} 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)
+
+#define NEXT_PTR_LIST(ptr) \
+	DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr)
+
+#define RESET_PTR_LIST(ptr) \
+	DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr)
+
+#define FINISH_PTR_LIST(ptr) \
+	DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
+
+#define DO_FOR_EACH(head, ptr, __head, __list, __nr) 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);			\
+					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) 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);			\
+					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) 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)
+
+#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)
+
+#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)
+
+#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)
+
+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--;								\
+	}										\
+	*__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)
+
+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);
+}
+
+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 */
author	Linus Torvalds <torvalds@ppc970.osdl.org>	2005-03-12 17:53:41 -0700
committer	Linus Torvalds <torvalds@ppc970.osdl.org>	2005-04-07 21:06:29 -0700
commit	77ac63127dc8981264b31bcfaac825c62971bca2 (patch)
tree	27cd8abb6be43358f0e45201687103dc242e6746
parent	67cb76f7d0c76d52588ba6cd24f70ae4e141406c (diff)
download	sparse-dev-77ac63127dc8981264b31bcfaac825c62971bca2.tar.gz