ptrlist.h 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293
  1. #ifndef PTR_LIST_H
  2. #define PTR_LIST_H
  3. #include <stdlib.h>
  4. #include <stdbool.h>
  5. /*
  6. * Generic pointer list manipulation code.
  7. *
  8. * (C) Copyright Linus Torvalds 2003-2005
  9. */
  10. /* Silly type-safety check ;) */
  11. #define CHECK_TYPE(head,ptr) (void)(&(ptr) == &(head)->list[0])
  12. #define TYPEOF(head) __typeof__(&(head)->list[0])
  13. #define VRFY_PTR_LIST(head) (void)(sizeof((head)->list[0]))
  14. #define LIST_NODE_NR (13)
  15. #define DECLARE_PTR_LIST(listname, type) \
  16. struct listname { \
  17. int nr:8; \
  18. int rm:8; \
  19. struct listname *prev; \
  20. struct listname *next; \
  21. type *list[LIST_NODE_NR]; \
  22. }
  23. DECLARE_PTR_LIST(ptr_list, void);
  24. void * undo_ptr_list_last(struct ptr_list **head);
  25. void * delete_ptr_list_last(struct ptr_list **head);
  26. int delete_ptr_list_entry(struct ptr_list **, void *, int);
  27. int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
  28. bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry);
  29. extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));
  30. extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
  31. extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t);
  32. extern int ptr_list_size(struct ptr_list *);
  33. extern bool ptr_list_empty(const struct ptr_list *head);
  34. extern bool ptr_list_multiple(const struct ptr_list *head);
  35. extern int linearize_ptr_list(struct ptr_list *, void **, int);
  36. extern void *first_ptr_list(struct ptr_list *);
  37. extern void *last_ptr_list(struct ptr_list *);
  38. extern void *ptr_list_nth_entry(struct ptr_list *, unsigned int idx);
  39. extern void pack_ptr_list(struct ptr_list **);
  40. /*
  41. * Hey, who said that you can't do overloading in C?
  42. *
  43. * You just have to be creative, and use some gcc
  44. * extensions..
  45. */
  46. extern void **__add_ptr_list(struct ptr_list **, void *);
  47. extern void **__add_ptr_list_tag(struct ptr_list **, void *, unsigned long);
  48. #define add_ptr_list(list, ptr) ({ \
  49. struct ptr_list** head = (struct ptr_list**)(list); \
  50. CHECK_TYPE(*(list),ptr); \
  51. (__typeof__(&(ptr))) __add_ptr_list(head, ptr); \
  52. })
  53. #define add_ptr_list_tag(list, ptr, tag) ({ \
  54. struct ptr_list** head = (struct ptr_list**)(list); \
  55. CHECK_TYPE(*(list),ptr); \
  56. (__typeof__(&(ptr))) __add_ptr_list_tag(head, ptr, tag);\
  57. })
  58. extern void __free_ptr_list(struct ptr_list **);
  59. #define free_ptr_list(list) do { \
  60. VRFY_PTR_LIST(*(list)); \
  61. __free_ptr_list((struct ptr_list **)(list)); \
  62. } while (0)
  63. ////////////////////////////////////////////////////////////////////////
  64. // API
  65. #define PREPARE_PTR_LIST(head, ptr) \
  66. DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
  67. #define NEXT_PTR_LIST(ptr) \
  68. DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
  69. #define RESET_PTR_LIST(ptr) \
  70. DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
  71. #define FINISH_PTR_LIST(ptr) \
  72. DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
  73. #define RECURSE_PTR_REVERSE(ptr, new) \
  74. DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, \
  75. new, __head##new, __list##new, __nr##new, PTR_ENTRY_UNTAG)
  76. #define FOR_EACH_PTR(head, ptr) \
  77. DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
  78. #define FOR_EACH_PTR_TAG(head, ptr) \
  79. DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
  80. #define END_FOR_EACH_PTR(ptr) \
  81. DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)
  82. #define FOR_EACH_PTR_REVERSE(head, ptr) \
  83. DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
  84. #define FOR_EACH_PTR_REVERSE_TAG(head, ptr) \
  85. DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
  86. #define END_FOR_EACH_PTR_REVERSE(ptr) \
  87. DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)
  88. #define THIS_ADDRESS(ptr) \
  89. DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
  90. #define INSERT_CURRENT(new, ptr) \
  91. DO_INSERT_CURRENT(new, __head##ptr, __list##ptr, __nr##ptr)
  92. #define DELETE_CURRENT_PTR(ptr) \
  93. DO_DELETE_CURRENT(__head##ptr, __list##ptr, __nr##ptr)
  94. #define REPLACE_CURRENT_PTR(ptr, new_ptr) \
  95. do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
  96. // This replace the current element by a null-pointer.
  97. // It's used when an element of the list must be removed
  98. // but the address of the other elements must not be changed.
  99. #define MARK_CURRENT_DELETED(ptr) \
  100. DO_MARK_CURRENT_DELETED(ptr, __list##ptr)
  101. #define PACK_PTR_LIST(x) \
  102. pack_ptr_list((struct ptr_list **)(x))
  103. #define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))
  104. #define TAG_CURRENT(ptr,val) update_tag(THIS_ADDRESS(ptr),val)
  105. // backward compatibility for smatch
  106. #define FOR_EACH_PTR_NOTAG(list, ptr) FOR_EACH_PTR(list, ptr)
  107. #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
  108. ////////////////////////////////////////////////////////////////////////
  109. // Implementation
  110. #define PTR_UNTAG(p) ((void*)(~3UL & (unsigned long)(p)))
  111. #define PTR_ENTRY_NOTAG(h,i) ((h)->list[i])
  112. #define PTR_ENTRY_UNTAG(h,i) PTR_UNTAG((h)->list[i])
  113. #define PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \
  114. do { \
  115. if (__nr < __list->nr) { \
  116. ptr = PTR_ENTRY(__list,__nr); \
  117. __nr++; \
  118. break; \
  119. } \
  120. ptr = NULL; \
  121. __nr = 0; \
  122. } while ((__list = __list->next) != __head) \
  123. #define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY) \
  124. do { \
  125. __typeof__(head) __head = (head); \
  126. __typeof__(head) __list = __head; \
  127. int __nr = 0; \
  128. ptr = NULL; \
  129. if (__head) { \
  130. PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
  131. } \
  132. #define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \
  133. if (ptr) { \
  134. PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
  135. }
  136. #define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY) \
  137. do { \
  138. __nr = 0; \
  139. __list = __head; \
  140. if (__head) \
  141. PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
  142. } while (0)
  143. #define DO_FINISH(ptr, __head, __list, __nr) \
  144. VRFY_PTR_LIST(__head); /* Sanity-check nesting */ \
  145. } while (0)
  146. #define DO_FOR_EACH(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \
  147. __typeof__(head) __head = (head); \
  148. __typeof__(head) __list = __head; \
  149. int __nr; \
  150. if (!__head) \
  151. break; \
  152. do { \
  153. for (__nr = 0; __nr < __list->nr; __nr++) { \
  154. ptr = PTR_ENTRY(__list,__nr); \
  155. if (__list->rm && !ptr) \
  156. continue; \
  157. #define DO_END_FOR_EACH(ptr, __head, __list, __nr) \
  158. } \
  159. } while ((__list = __list->next) != __head); \
  160. } while (0)
  161. #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \
  162. __typeof__(head) __head = (head); \
  163. __typeof__(head) __list = __head; \
  164. int __nr; \
  165. if (!head) \
  166. break; \
  167. do { \
  168. __list = __list->prev; \
  169. __nr = __list->nr; \
  170. while (--__nr >= 0) { \
  171. ptr = PTR_ENTRY(__list,__nr); \
  172. if (__list->rm && !ptr) \
  173. continue; \
  174. #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \
  175. } \
  176. } while (__list != __head); \
  177. } while (0)
  178. #define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead, \
  179. __newlist, __newnr, PTR_ENTRY) do { \
  180. __typeof__(__head) __newhead = __head; \
  181. __typeof__(__head) __newlist = __list; \
  182. int __newnr = __nr; \
  183. new = ptr; \
  184. goto __inside##new; \
  185. do { \
  186. __newlist = __newlist->prev; \
  187. __newnr = __newlist->nr; \
  188. __inside##new: \
  189. while (--__newnr >= 0) { \
  190. new = PTR_ENTRY(__newlist,__newnr); \
  191. #define DO_THIS_ADDRESS(ptr, __head, __list, __nr) \
  192. (&__list->list[__nr])
  193. extern void split_ptr_list_head(struct ptr_list *);
  194. #define DO_INSERT_CURRENT(new, __head, __list, __nr) do { \
  195. TYPEOF(__head) __this, __last; \
  196. if (__list->nr == LIST_NODE_NR) { \
  197. split_ptr_list_head((struct ptr_list*)__list); \
  198. if (__nr >= __list->nr) { \
  199. __nr -= __list->nr; \
  200. __list = __list->next; \
  201. } \
  202. } \
  203. __this = __list->list + __nr; \
  204. __last = __list->list + __list->nr - 1; \
  205. while (__last >= __this) { \
  206. __last[1] = __last[0]; \
  207. __last--; \
  208. } \
  209. *__this = (new); \
  210. __list->nr++; \
  211. } while (0)
  212. #define DO_DELETE_CURRENT(__head, __list, __nr) do { \
  213. TYPEOF(__head) __this = __list->list + __nr; \
  214. TYPEOF(__head) __last = __list->list + __list->nr - 1; \
  215. while (__this < __last) { \
  216. __this[0] = __this[1]; \
  217. __this++; \
  218. } \
  219. *__this = (void *)0xf0f0f0f0; \
  220. __list->nr--; __nr--; \
  221. } while (0)
  222. #define DO_MARK_CURRENT_DELETED(ptr, __list) do { \
  223. REPLACE_CURRENT_PTR(ptr, NULL); \
  224. __list->rm++; \
  225. } while (0)
  226. static inline void update_tag(void *p, unsigned long tag)
  227. {
  228. unsigned long *ptr = p;
  229. *ptr = tag | (~3UL & *ptr);
  230. }
  231. static inline void *tag_ptr(void *ptr, unsigned long tag)
  232. {
  233. return (void *)(tag | (unsigned long)ptr);
  234. }
  235. #endif /* PTR_LIST_H */