move whether atomic byte/short exists to uatomic_arch_*.h
[urcu.git] / tests / api_gcc.h
CommitLineData
1a43bbd8
MD
1
2#ifndef _INCLUDE_API_H
0578089f
PM
3#define _INCLUDE_API_H
4
d8540fc5
PA
5#include "../config.h"
6
0578089f
PM
7/*
8 * common.h: Common Linux kernel-isms.
9 *
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; but version 2 of the License only due
13 * to code included from the Linux kernel.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23 *
24 * Copyright (c) 2006 Paul E. McKenney, IBM.
25 *
26 * Much code taken from the Linux kernel. For such code, the option
27 * to redistribute under later versions of GPL might not be available.
28 */
29
30#ifndef __always_inline
31#define __always_inline inline
32#endif
33
34#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
35#define BUILD_BUG_ON_ZERO(e) (sizeof(char[1 - 2 * !!(e)]) - 1)
36
37#ifdef __ASSEMBLY__
38# define stringify_in_c(...) __VA_ARGS__
39# define ASM_CONST(x) x
40#else
41/* This version of stringify will deal with commas... */
42# define __stringify_in_c(...) #__VA_ARGS__
43# define stringify_in_c(...) __stringify_in_c(__VA_ARGS__) " "
44# define __ASM_CONST(x) x##UL
45# define ASM_CONST(x) __ASM_CONST(x)
46#endif
47
48
49/*
50 * arch-i386.h: Expose x86 atomic instructions. 80486 and better only.
51 *
52 * This program is free software; you can redistribute it and/or modify
53 * it under the terms of the GNU General Public License as published by
54 * the Free Software Foundation, but version 2 only due to inclusion
55 * of Linux-kernel code.
56 *
57 * This program is distributed in the hope that it will be useful,
58 * but WITHOUT ANY WARRANTY; without even the implied warranty of
59 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
60 * GNU General Public License for more details.
61 *
62 * You should have received a copy of the GNU General Public License
63 * along with this program; if not, write to the Free Software
64 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
65 *
66 * Copyright (c) 2006 Paul E. McKenney, IBM.
67 *
68 * Much code taken from the Linux kernel. For such code, the option
69 * to redistribute under later versions of GPL might not be available.
70 */
71
72/*
73 * Machine parameters.
74 */
75
8adc73ec 76/* #define CACHE_LINE_SIZE 64 */
0578089f
PM
77#define ____cacheline_internodealigned_in_smp \
78 __attribute__((__aligned__(1 << 6)))
79
80#define LOCK_PREFIX "lock ; "
81
6ee91d83 82#if 0 /* duplicate with arch_atomic.h */
0578089f
PM
83/*
84 * Atomic data structure, initialization, and access.
85 */
86
87typedef struct { volatile int counter; } atomic_t;
88
89#define ATOMIC_INIT(i) { (i) }
90
91#define atomic_read(v) ((v)->counter)
92#define atomic_set(v, i) (((v)->counter) = (i))
93
94/*
95 * Atomic operations.
96 */
97
98/**
99 * atomic_add - add integer to atomic variable
100 * @i: integer value to add
101 * @v: pointer of type atomic_t
102 *
103 * Atomically adds @i to @v.
104 */
105
106static __inline__ void atomic_add(int i, atomic_t *v)
107{
108 (void)__sync_fetch_and_add(&v->counter, i);
109}
110
111/**
112 * atomic_sub - subtract the atomic variable
113 * @i: integer value to subtract
114 * @v: pointer of type atomic_t
115 *
116 * Atomically subtracts @i from @v.
117 */
118static __inline__ void atomic_sub(int i, atomic_t *v)
119{
120 (void)__sync_fetch_and_add(&v->counter, -i);
121}
122
123/**
124 * atomic_sub_and_test - subtract value from variable and test result
125 * @i: integer value to subtract
126 * @v: pointer of type atomic_t
127 *
128 * Atomically subtracts @i from @v and returns
129 * true if the result is zero, or false for all
130 * other cases.
131 */
132static __inline__ int atomic_sub_and_test(int i, atomic_t *v)
133{
134 return __sync_add_and_fetch(&v->counter, -i) == 0;
135}
136
137/**
138 * atomic_inc - increment atomic variable
139 * @v: pointer of type atomic_t
140 *
141 * Atomically increments @v by 1.
142 */
143static __inline__ void atomic_inc(atomic_t *v)
144{
145 (void)__sync_fetch_and_add(&v->counter, 1);
146}
147
148/**
149 * atomic_dec - decrement atomic variable
150 * @v: pointer of type atomic_t
151 *
152 * Atomically decrements @v by 1.
153 */
154static __inline__ void atomic_dec(atomic_t *v)
155{
156 (void)__sync_fetch_and_add(&v->counter, -1);
157}
158
159/**
160 * atomic_dec_and_test - decrement and test
161 * @v: pointer of type atomic_t
162 *
163 * Atomically decrements @v by 1 and
164 * returns true if the result is 0, or false for all other
165 * cases.
166 */
167static __inline__ int atomic_dec_and_test(atomic_t *v)
168{
169 return __sync_add_and_fetch(&v->counter, -1) == 0;
170}
171
172/**
173 * atomic_inc_and_test - increment and test
174 * @v: pointer of type atomic_t
175 *
176 * Atomically increments @v by 1
177 * and returns true if the result is zero, or false for all
178 * other cases.
179 */
180static __inline__ int atomic_inc_and_test(atomic_t *v)
181{
182 return __sync_add_and_fetch(&v->counter, 1) == 0;
183}
184
185/**
186 * atomic_add_negative - add and test if negative
187 * @v: pointer of type atomic_t
188 * @i: integer value to add
189 *
190 * Atomically adds @i to @v and returns true
191 * if the result is negative, or false when
192 * result is greater than or equal to zero.
193 */
194static __inline__ int atomic_add_negative(int i, atomic_t *v)
195{
196 return __sync_add_and_fetch(&v->counter, i) < 0;
197}
198
199/**
200 * atomic_add_return - add and return
201 * @v: pointer of type atomic_t
202 * @i: integer value to add
203 *
204 * Atomically adds @i to @v and returns @i + @v
205 */
206static __inline__ int atomic_add_return(int i, atomic_t *v)
207{
208 return __sync_add_and_fetch(&v->counter, i);
209}
210
211static __inline__ int atomic_sub_return(int i, atomic_t *v)
212{
213 return atomic_add_return(-i,v);
214}
215
216static inline unsigned int
217cmpxchg(volatile long *ptr, long oldval, long newval)
218{
219 return __sync_val_compare_and_swap(ptr, oldval, newval);
220}
221
222#define atomic_cmpxchg(v, old, new) ((int)cmpxchg(&((v)->counter), old, new))
223#define atomic_xchg(v, new) (xchg(&((v)->counter), new))
224
225/**
226 * atomic_add_unless - add unless the number is a given value
227 * @v: pointer of type atomic_t
228 * @a: the amount to add to v...
229 * @u: ...unless v is equal to u.
230 *
231 * Atomically adds @a to @v, so long as it was not @u.
232 * Returns non-zero if @v was not @u, and zero otherwise.
233 */
234#define atomic_add_unless(v, a, u) \
235({ \
236 int c, old; \
237 c = atomic_read(v); \
238 for (;;) { \
239 if (unlikely(c == (u))) \
240 break; \
241 old = atomic_cmpxchg((v), c, c + (a)); \
242 if (likely(old == c)) \
243 break; \
244 c = old; \
245 } \
246 c != (u); \
247})
248#define atomic_inc_not_zero(v) atomic_add_unless((v), 1, 0)
249
250#define atomic_inc_return(v) (atomic_add_return(1,v))
251#define atomic_dec_return(v) (atomic_sub_return(1,v))
252
253/* Atomic operations are already serializing on x86 */
254#define smp_mb__before_atomic_dec() barrier()
255#define smp_mb__after_atomic_dec() barrier()
256#define smp_mb__before_atomic_inc() barrier()
257#define smp_mb__after_atomic_inc() barrier()
258
6ee91d83
MD
259#endif //0 /* duplicate with arch_atomic.h */
260
0578089f
PM
261/*
262 * api_pthreads.h: API mapping to pthreads environment.
263 *
264 * This program is free software; you can redistribute it and/or modify
265 * it under the terms of the GNU General Public License as published by
266 * the Free Software Foundation; either version 2 of the License, or
267 * (at your option) any later version. However, please note that much
268 * of the code in this file derives from the Linux kernel, and that such
269 * code may not be available except under GPLv2.
270 *
271 * This program is distributed in the hope that it will be useful,
272 * but WITHOUT ANY WARRANTY; without even the implied warranty of
273 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
274 * GNU General Public License for more details.
275 *
276 * You should have received a copy of the GNU General Public License
277 * along with this program; if not, write to the Free Software
278 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
279 *
280 * Copyright (c) 2006 Paul E. McKenney, IBM.
281 */
282
283#include <stdio.h>
284#include <stdlib.h>
285#include <errno.h>
286#include <limits.h>
287#include <sys/types.h>
288#define __USE_GNU
289#include <pthread.h>
290#include <sched.h>
291#include <sys/param.h>
292/* #include "atomic.h" */
293
294/*
295 * Compiler magic.
296 */
0578089f
PM
297#define container_of(ptr, type, member) ({ \
298 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
299 (type *)( (char *)__mptr - offsetof(type,member) );})
300
301/*
302 * Default machine parameters.
303 */
304
305#ifndef CACHE_LINE_SIZE
8adc73ec 306/* #define CACHE_LINE_SIZE 128 */
0578089f
PM
307#endif /* #ifndef CACHE_LINE_SIZE */
308
309/*
310 * Exclusive locking primitives.
311 */
312
313typedef pthread_mutex_t spinlock_t;
314
315#define DEFINE_SPINLOCK(lock) spinlock_t lock = PTHREAD_MUTEX_INITIALIZER;
316#define __SPIN_LOCK_UNLOCKED(lockp) PTHREAD_MUTEX_INITIALIZER
317
318static void spin_lock_init(spinlock_t *sp)
319{
320 if (pthread_mutex_init(sp, NULL) != 0) {
321 perror("spin_lock_init:pthread_mutex_init");
322 exit(-1);
323 }
324}
325
326static void spin_lock(spinlock_t *sp)
327{
328 if (pthread_mutex_lock(sp) != 0) {
329 perror("spin_lock:pthread_mutex_lock");
330 exit(-1);
331 }
332}
333
334static void spin_unlock(spinlock_t *sp)
335{
336 if (pthread_mutex_unlock(sp) != 0) {
337 perror("spin_unlock:pthread_mutex_unlock");
338 exit(-1);
339 }
340}
341
342#define spin_lock_irqsave(l, f) do { f = 1; spin_lock(l); } while (0)
343#define spin_unlock_irqrestore(l, f) do { f = 0; spin_unlock(l); } while (0)
344
345/*
346 * Thread creation/destruction primitives.
347 */
348
349typedef pthread_t thread_id_t;
350
351#define NR_THREADS 128
352
353#define __THREAD_ID_MAP_EMPTY 0
354#define __THREAD_ID_MAP_WAITING 1
355thread_id_t __thread_id_map[NR_THREADS];
356spinlock_t __thread_id_map_mutex;
357
358#define for_each_thread(t) \
359 for (t = 0; t < NR_THREADS; t++)
360
361#define for_each_running_thread(t) \
362 for (t = 0; t < NR_THREADS; t++) \
363 if ((__thread_id_map[t] != __THREAD_ID_MAP_EMPTY) && \
364 (__thread_id_map[t] != __THREAD_ID_MAP_WAITING))
365
366pthread_key_t thread_id_key;
367
368static int __smp_thread_id(void)
369{
370 int i;
371 thread_id_t tid = pthread_self();
372
373 for (i = 0; i < NR_THREADS; i++) {
374 if (__thread_id_map[i] == tid) {
375 long v = i + 1; /* must be non-NULL. */
376
377 if (pthread_setspecific(thread_id_key, (void *)v) != 0) {
378 perror("pthread_setspecific");
379 exit(-1);
380 }
381 return i;
382 }
383 }
384 spin_lock(&__thread_id_map_mutex);
385 for (i = 0; i < NR_THREADS; i++) {
386 if (__thread_id_map[i] == tid)
387 spin_unlock(&__thread_id_map_mutex);
388 return i;
389 }
390 spin_unlock(&__thread_id_map_mutex);
391 fprintf(stderr, "smp_thread_id: Rogue thread, id: %d(%#x)\n",
392 (int)tid, (int)tid);
393 exit(-1);
394}
395
396static int smp_thread_id(void)
397{
398 void *id;
399
400 id = pthread_getspecific(thread_id_key);
401 if (id == NULL)
402 return __smp_thread_id();
403 return (long)(id - 1);
404}
405
406static thread_id_t create_thread(void *(*func)(void *), void *arg)
407{
408 thread_id_t tid;
409 int i;
410
411 spin_lock(&__thread_id_map_mutex);
412 for (i = 0; i < NR_THREADS; i++) {
413 if (__thread_id_map[i] == __THREAD_ID_MAP_EMPTY)
414 break;
415 }
416 if (i >= NR_THREADS) {
417 spin_unlock(&__thread_id_map_mutex);
418 fprintf(stderr, "Thread limit of %d exceeded!\n", NR_THREADS);
419 exit(-1);
420 }
421 __thread_id_map[i] = __THREAD_ID_MAP_WAITING;
422 spin_unlock(&__thread_id_map_mutex);
423 if (pthread_create(&tid, NULL, func, arg) != 0) {
424 perror("create_thread:pthread_create");
425 exit(-1);
426 }
427 __thread_id_map[i] = tid;
428 return tid;
429}
430
431static void *wait_thread(thread_id_t tid)
432{
433 int i;
434 void *vp;
435
436 for (i = 0; i < NR_THREADS; i++) {
437 if (__thread_id_map[i] == tid)
438 break;
439 }
440 if (i >= NR_THREADS){
441 fprintf(stderr, "wait_thread: bad tid = %d(%#x)\n",
442 (int)tid, (int)tid);
443 exit(-1);
444 }
445 if (pthread_join(tid, &vp) != 0) {
446 perror("wait_thread:pthread_join");
447 exit(-1);
448 }
449 __thread_id_map[i] = __THREAD_ID_MAP_EMPTY;
450 return vp;
451}
452
453static void wait_all_threads(void)
454{
455 int i;
456 thread_id_t tid;
457
458 for (i = 1; i < NR_THREADS; i++) {
459 tid = __thread_id_map[i];
460 if (tid != __THREAD_ID_MAP_EMPTY &&
461 tid != __THREAD_ID_MAP_WAITING)
462 (void)wait_thread(tid);
463 }
464}
465
d8540fc5
PA
466#ifndef HAVE_CPU_SET_T
467typedef unsigned long cpu_set_t;
468# define CPU_ZERO(cpuset) do { *(cpuset) = 0; } while(0)
469# define CPU_SET(cpu, cpuset) do { *(cpuset) |= (1UL << (cpu)); } while(0)
470#endif
471
0578089f
PM
472static void run_on(int cpu)
473{
d8540fc5 474#if HAVE_SCHED_SETAFFINITY
0578089f
PM
475 cpu_set_t mask;
476
477 CPU_ZERO(&mask);
478 CPU_SET(cpu, &mask);
d8540fc5
PA
479#if SCHED_SETAFFINITY_ARGS == 2
480 sched_setaffinity(0, &mask);
481#else
0578089f 482 sched_setaffinity(0, sizeof(mask), &mask);
d8540fc5
PA
483#endif
484#endif /* HAVE_SCHED_SETAFFINITY */
0578089f
PM
485}
486
487/*
488 * timekeeping -- very crude -- should use MONOTONIC...
489 */
490
491long long get_microseconds(void)
492{
493 struct timeval tv;
494
495 if (gettimeofday(&tv, NULL) != 0)
496 abort();
497 return ((long long)tv.tv_sec) * 1000000LL + (long long)tv.tv_usec;
498}
499
500/*
501 * Per-thread variables.
502 */
503
504#define DEFINE_PER_THREAD(type, name) \
505 struct { \
506 __typeof__(type) v \
507 __attribute__((__aligned__(CACHE_LINE_SIZE))); \
508 } __per_thread_##name[NR_THREADS];
509#define DECLARE_PER_THREAD(type, name) extern DEFINE_PER_THREAD(type, name)
510
511#define per_thread(name, thread) __per_thread_##name[thread].v
512#define __get_thread_var(name) per_thread(name, smp_thread_id())
513
514#define init_per_thread(name, v) \
515 do { \
516 int __i_p_t_i; \
517 for (__i_p_t_i = 0; __i_p_t_i < NR_THREADS; __i_p_t_i++) \
518 per_thread(name, __i_p_t_i) = v; \
519 } while (0)
520
521/*
522 * CPU traversal primitives.
523 */
524
525#ifndef NR_CPUS
526#define NR_CPUS 16
527#endif /* #ifndef NR_CPUS */
528
529#define for_each_possible_cpu(cpu) \
530 for (cpu = 0; cpu < NR_CPUS; cpu++)
531#define for_each_online_cpu(cpu) \
532 for (cpu = 0; cpu < NR_CPUS; cpu++)
533
534/*
535 * Per-CPU variables.
536 */
537
538#define DEFINE_PER_CPU(type, name) \
539 struct { \
540 __typeof__(type) v \
541 __attribute__((__aligned__(CACHE_LINE_SIZE))); \
542 } __per_cpu_##name[NR_CPUS]
543#define DECLARE_PER_CPU(type, name) extern DEFINE_PER_CPU(type, name)
544
545DEFINE_PER_THREAD(int, smp_processor_id);
546
547#define per_cpu(name, thread) __per_cpu_##name[thread].v
548#define __get_cpu_var(name) per_cpu(name, smp_processor_id())
549
550#define init_per_cpu(name, v) \
551 do { \
552 int __i_p_c_i; \
553 for (__i_p_c_i = 0; __i_p_c_i < NR_CPUS; __i_p_c_i++) \
554 per_cpu(name, __i_p_c_i) = v; \
555 } while (0)
556
557/*
558 * CPU state checking (crowbarred).
559 */
560
561#define idle_cpu(cpu) 0
562#define in_softirq() 1
563#define hardirq_count() 0
564#define PREEMPT_SHIFT 0
565#define SOFTIRQ_SHIFT (PREEMPT_SHIFT + PREEMPT_BITS)
566#define HARDIRQ_SHIFT (SOFTIRQ_SHIFT + SOFTIRQ_BITS)
567#define PREEMPT_BITS 8
568#define SOFTIRQ_BITS 8
569
570/*
571 * CPU hotplug.
572 */
573
574struct notifier_block {
575 int (*notifier_call)(struct notifier_block *, unsigned long, void *);
576 struct notifier_block *next;
577 int priority;
578};
579
580#define CPU_ONLINE 0x0002 /* CPU (unsigned)v is up */
581#define CPU_UP_PREPARE 0x0003 /* CPU (unsigned)v coming up */
582#define CPU_UP_CANCELED 0x0004 /* CPU (unsigned)v NOT coming up */
583#define CPU_DOWN_PREPARE 0x0005 /* CPU (unsigned)v going down */
584#define CPU_DOWN_FAILED 0x0006 /* CPU (unsigned)v NOT going down */
585#define CPU_DEAD 0x0007 /* CPU (unsigned)v dead */
586#define CPU_DYING 0x0008 /* CPU (unsigned)v not running any task,
587 * not handling interrupts, soon dead */
588#define CPU_POST_DEAD 0x0009 /* CPU (unsigned)v dead, cpu_hotplug
589 * lock is dropped */
590
591/* Used for CPU hotplug events occuring while tasks are frozen due to a suspend
592 * operation in progress
593 */
594#define CPU_TASKS_FROZEN 0x0010
595
596#define CPU_ONLINE_FROZEN (CPU_ONLINE | CPU_TASKS_FROZEN)
597#define CPU_UP_PREPARE_FROZEN (CPU_UP_PREPARE | CPU_TASKS_FROZEN)
598#define CPU_UP_CANCELED_FROZEN (CPU_UP_CANCELED | CPU_TASKS_FROZEN)
599#define CPU_DOWN_PREPARE_FROZEN (CPU_DOWN_PREPARE | CPU_TASKS_FROZEN)
600#define CPU_DOWN_FAILED_FROZEN (CPU_DOWN_FAILED | CPU_TASKS_FROZEN)
601#define CPU_DEAD_FROZEN (CPU_DEAD | CPU_TASKS_FROZEN)
602#define CPU_DYING_FROZEN (CPU_DYING | CPU_TASKS_FROZEN)
603
604/* Hibernation and suspend events */
605#define PM_HIBERNATION_PREPARE 0x0001 /* Going to hibernate */
606#define PM_POST_HIBERNATION 0x0002 /* Hibernation finished */
607#define PM_SUSPEND_PREPARE 0x0003 /* Going to suspend the system */
608#define PM_POST_SUSPEND 0x0004 /* Suspend finished */
609#define PM_RESTORE_PREPARE 0x0005 /* Going to restore a saved image */
610#define PM_POST_RESTORE 0x0006 /* Restore failed */
611
612#define NOTIFY_DONE 0x0000 /* Don't care */
613#define NOTIFY_OK 0x0001 /* Suits me */
614#define NOTIFY_STOP_MASK 0x8000 /* Don't call further */
615#define NOTIFY_BAD (NOTIFY_STOP_MASK|0x0002)
616 /* Bad/Veto action */
617/*
618 * Clean way to return from the notifier and stop further calls.
619 */
620#define NOTIFY_STOP (NOTIFY_OK|NOTIFY_STOP_MASK)
621
622/*
623 * Bug checks.
624 */
625
626#define BUG_ON(c) do { if (!(c)) abort(); } while (0)
627
628/*
629 * Initialization -- Must be called before calling any primitives.
630 */
631
632static void smp_init(void)
633{
634 int i;
635
636 spin_lock_init(&__thread_id_map_mutex);
637 __thread_id_map[0] = pthread_self();
638 for (i = 1; i < NR_THREADS; i++)
639 __thread_id_map[i] = __THREAD_ID_MAP_EMPTY;
640 init_per_thread(smp_processor_id, 0);
641 if (pthread_key_create(&thread_id_key, NULL) != 0) {
642 perror("pthread_key_create");
643 exit(-1);
644 }
645}
646
647/* Taken from the Linux kernel source tree, so GPLv2-only!!! */
648
649#ifndef _LINUX_LIST_H
650#define _LINUX_LIST_H
651
652#define LIST_POISON1 ((void *) 0x00100100)
653#define LIST_POISON2 ((void *) 0x00200200)
654
0578089f
PM
655#define container_of(ptr, type, member) ({ \
656 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
657 (type *)( (char *)__mptr - offsetof(type,member) );})
658
63ff4873 659#if 0
0578089f
PM
660/*
661 * Simple doubly linked list implementation.
662 *
663 * Some of the internal functions ("__xxx") are useful when
664 * manipulating whole lists rather than single entries, as
665 * sometimes we already know the next/prev entries and we can
666 * generate better code by using them directly rather than
667 * using the generic single-entry routines.
668 */
669
670struct list_head {
671 struct list_head *next, *prev;
672};
673
674#define LIST_HEAD_INIT(name) { &(name), &(name) }
675
676#define LIST_HEAD(name) \
677 struct list_head name = LIST_HEAD_INIT(name)
678
679static inline void INIT_LIST_HEAD(struct list_head *list)
680{
681 list->next = list;
682 list->prev = list;
683}
684
685/*
686 * Insert a new entry between two known consecutive entries.
687 *
688 * This is only for internal list manipulation where we know
689 * the prev/next entries already!
690 */
691#ifndef CONFIG_DEBUG_LIST
692static inline void __list_add(struct list_head *new,
693 struct list_head *prev,
694 struct list_head *next)
695{
696 next->prev = new;
697 new->next = next;
698 new->prev = prev;
699 prev->next = new;
700}
701#else
702extern void __list_add(struct list_head *new,
703 struct list_head *prev,
704 struct list_head *next);
705#endif
706
707/**
708 * list_add - add a new entry
709 * @new: new entry to be added
710 * @head: list head to add it after
711 *
712 * Insert a new entry after the specified head.
713 * This is good for implementing stacks.
714 */
715static inline void list_add(struct list_head *new, struct list_head *head)
716{
717 __list_add(new, head, head->next);
718}
719
720
721/**
722 * list_add_tail - add a new entry
723 * @new: new entry to be added
724 * @head: list head to add it before
725 *
726 * Insert a new entry before the specified head.
727 * This is useful for implementing queues.
728 */
729static inline void list_add_tail(struct list_head *new, struct list_head *head)
730{
731 __list_add(new, head->prev, head);
732}
733
734/*
735 * Delete a list entry by making the prev/next entries
736 * point to each other.
737 *
738 * This is only for internal list manipulation where we know
739 * the prev/next entries already!
740 */
741static inline void __list_del(struct list_head * prev, struct list_head * next)
742{
743 next->prev = prev;
744 prev->next = next;
745}
746
747/**
748 * list_del - deletes entry from list.
749 * @entry: the element to delete from the list.
750 * Note: list_empty() on entry does not return true after this, the entry is
751 * in an undefined state.
752 */
753#ifndef CONFIG_DEBUG_LIST
754static inline void list_del(struct list_head *entry)
755{
756 __list_del(entry->prev, entry->next);
757 entry->next = LIST_POISON1;
758 entry->prev = LIST_POISON2;
759}
760#else
761extern void list_del(struct list_head *entry);
762#endif
763
764/**
765 * list_replace - replace old entry by new one
766 * @old : the element to be replaced
767 * @new : the new element to insert
768 *
769 * If @old was empty, it will be overwritten.
770 */
771static inline void list_replace(struct list_head *old,
772 struct list_head *new)
773{
774 new->next = old->next;
775 new->next->prev = new;
776 new->prev = old->prev;
777 new->prev->next = new;
778}
779
780static inline void list_replace_init(struct list_head *old,
781 struct list_head *new)
782{
783 list_replace(old, new);
784 INIT_LIST_HEAD(old);
785}
786
787/**
788 * list_del_init - deletes entry from list and reinitialize it.
789 * @entry: the element to delete from the list.
790 */
791static inline void list_del_init(struct list_head *entry)
792{
793 __list_del(entry->prev, entry->next);
794 INIT_LIST_HEAD(entry);
795}
796
797/**
798 * list_move - delete from one list and add as another's head
799 * @list: the entry to move
800 * @head: the head that will precede our entry
801 */
802static inline void list_move(struct list_head *list, struct list_head *head)
803{
804 __list_del(list->prev, list->next);
805 list_add(list, head);
806}
807
808/**
809 * list_move_tail - delete from one list and add as another's tail
810 * @list: the entry to move
811 * @head: the head that will follow our entry
812 */
813static inline void list_move_tail(struct list_head *list,
814 struct list_head *head)
815{
816 __list_del(list->prev, list->next);
817 list_add_tail(list, head);
818}
819
820/**
821 * list_is_last - tests whether @list is the last entry in list @head
822 * @list: the entry to test
823 * @head: the head of the list
824 */
825static inline int list_is_last(const struct list_head *list,
826 const struct list_head *head)
827{
828 return list->next == head;
829}
830
831/**
832 * list_empty - tests whether a list is empty
833 * @head: the list to test.
834 */
835static inline int list_empty(const struct list_head *head)
836{
837 return head->next == head;
838}
839
840/**
841 * list_empty_careful - tests whether a list is empty and not being modified
842 * @head: the list to test
843 *
844 * Description:
845 * tests whether a list is empty _and_ checks that no other CPU might be
846 * in the process of modifying either member (next or prev)
847 *
848 * NOTE: using list_empty_careful() without synchronization
849 * can only be safe if the only activity that can happen
850 * to the list entry is list_del_init(). Eg. it cannot be used
851 * if another CPU could re-list_add() it.
852 */
853static inline int list_empty_careful(const struct list_head *head)
854{
855 struct list_head *next = head->next;
856 return (next == head) && (next == head->prev);
857}
858
859/**
860 * list_is_singular - tests whether a list has just one entry.
861 * @head: the list to test.
862 */
863static inline int list_is_singular(const struct list_head *head)
864{
865 return !list_empty(head) && (head->next == head->prev);
866}
867
868static inline void __list_cut_position(struct list_head *list,
869 struct list_head *head, struct list_head *entry)
870{
871 struct list_head *new_first = entry->next;
872 list->next = head->next;
873 list->next->prev = list;
874 list->prev = entry;
875 entry->next = list;
876 head->next = new_first;
877 new_first->prev = head;
878}
879
880/**
881 * list_cut_position - cut a list into two
882 * @list: a new list to add all removed entries
883 * @head: a list with entries
884 * @entry: an entry within head, could be the head itself
885 * and if so we won't cut the list
886 *
887 * This helper moves the initial part of @head, up to and
888 * including @entry, from @head to @list. You should
889 * pass on @entry an element you know is on @head. @list
890 * should be an empty list or a list you do not care about
891 * losing its data.
892 *
893 */
894static inline void list_cut_position(struct list_head *list,
895 struct list_head *head, struct list_head *entry)
896{
897 if (list_empty(head))
898 return;
899 if (list_is_singular(head) &&
900 (head->next != entry && head != entry))
901 return;
902 if (entry == head)
903 INIT_LIST_HEAD(list);
904 else
905 __list_cut_position(list, head, entry);
906}
907
908static inline void __list_splice(const struct list_head *list,
909 struct list_head *prev,
910 struct list_head *next)
911{
912 struct list_head *first = list->next;
913 struct list_head *last = list->prev;
914
915 first->prev = prev;
916 prev->next = first;
917
918 last->next = next;
919 next->prev = last;
920}
921
922/**
923 * list_splice - join two lists, this is designed for stacks
924 * @list: the new list to add.
925 * @head: the place to add it in the first list.
926 */
927static inline void list_splice(const struct list_head *list,
928 struct list_head *head)
929{
930 if (!list_empty(list))
931 __list_splice(list, head, head->next);
932}
933
934/**
935 * list_splice_tail - join two lists, each list being a queue
936 * @list: the new list to add.
937 * @head: the place to add it in the first list.
938 */
939static inline void list_splice_tail(struct list_head *list,
940 struct list_head *head)
941{
942 if (!list_empty(list))
943 __list_splice(list, head->prev, head);
944}
945
946/**
947 * list_splice_init - join two lists and reinitialise the emptied list.
948 * @list: the new list to add.
949 * @head: the place to add it in the first list.
950 *
951 * The list at @list is reinitialised
952 */
953static inline void list_splice_init(struct list_head *list,
954 struct list_head *head)
955{
956 if (!list_empty(list)) {
957 __list_splice(list, head, head->next);
958 INIT_LIST_HEAD(list);
959 }
960}
961
962/**
963 * list_splice_tail_init - join two lists and reinitialise the emptied list
964 * @list: the new list to add.
965 * @head: the place to add it in the first list.
966 *
967 * Each of the lists is a queue.
968 * The list at @list is reinitialised
969 */
970static inline void list_splice_tail_init(struct list_head *list,
971 struct list_head *head)
972{
973 if (!list_empty(list)) {
974 __list_splice(list, head->prev, head);
975 INIT_LIST_HEAD(list);
976 }
977}
978
979/**
980 * list_entry - get the struct for this entry
981 * @ptr: the &struct list_head pointer.
982 * @type: the type of the struct this is embedded in.
983 * @member: the name of the list_struct within the struct.
984 */
985#define list_entry(ptr, type, member) \
986 container_of(ptr, type, member)
987
988/**
989 * list_first_entry - get the first element from a list
990 * @ptr: the list head to take the element from.
991 * @type: the type of the struct this is embedded in.
992 * @member: the name of the list_struct within the struct.
993 *
994 * Note, that list is expected to be not empty.
995 */
996#define list_first_entry(ptr, type, member) \
997 list_entry((ptr)->next, type, member)
998
999/**
1000 * list_for_each - iterate over a list
1001 * @pos: the &struct list_head to use as a loop cursor.
1002 * @head: the head for your list.
1003 */
1004#define list_for_each(pos, head) \
1005 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
1006 pos = pos->next)
1007
1008/**
1009 * __list_for_each - iterate over a list
1010 * @pos: the &struct list_head to use as a loop cursor.
1011 * @head: the head for your list.
1012 *
1013 * This variant differs from list_for_each() in that it's the
1014 * simplest possible list iteration code, no prefetching is done.
1015 * Use this for code that knows the list to be very short (empty
1016 * or 1 entry) most of the time.
1017 */
1018#define __list_for_each(pos, head) \
1019 for (pos = (head)->next; pos != (head); pos = pos->next)
1020
1021/**
1022 * list_for_each_prev - iterate over a list backwards
1023 * @pos: the &struct list_head to use as a loop cursor.
1024 * @head: the head for your list.
1025 */
1026#define list_for_each_prev(pos, head) \
1027 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
1028 pos = pos->prev)
1029
1030/**
1031 * list_for_each_safe - iterate over a list safe against removal of list entry
1032 * @pos: the &struct list_head to use as a loop cursor.
1033 * @n: another &struct list_head to use as temporary storage
1034 * @head: the head for your list.
1035 */
1036#define list_for_each_safe(pos, n, head) \
1037 for (pos = (head)->next, n = pos->next; pos != (head); \
1038 pos = n, n = pos->next)
1039
1040/**
1041 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
1042 * @pos: the &struct list_head to use as a loop cursor.
1043 * @n: another &struct list_head to use as temporary storage
1044 * @head: the head for your list.
1045 */
1046#define list_for_each_prev_safe(pos, n, head) \
1047 for (pos = (head)->prev, n = pos->prev; \
1048 prefetch(pos->prev), pos != (head); \
1049 pos = n, n = pos->prev)
1050
1051/**
1052 * list_for_each_entry - iterate over list of given type
1053 * @pos: the type * to use as a loop cursor.
1054 * @head: the head for your list.
1055 * @member: the name of the list_struct within the struct.
1056 */
1057#define list_for_each_entry(pos, head, member) \
1058 for (pos = list_entry((head)->next, typeof(*pos), member); \
1059 prefetch(pos->member.next), &pos->member != (head); \
1060 pos = list_entry(pos->member.next, typeof(*pos), member))
1061
1062/**
1063 * list_for_each_entry_reverse - iterate backwards over list of given type.
1064 * @pos: the type * to use as a loop cursor.
1065 * @head: the head for your list.
1066 * @member: the name of the list_struct within the struct.
1067 */
1068#define list_for_each_entry_reverse(pos, head, member) \
1069 for (pos = list_entry((head)->prev, typeof(*pos), member); \
1070 prefetch(pos->member.prev), &pos->member != (head); \
1071 pos = list_entry(pos->member.prev, typeof(*pos), member))
1072
1073/**
1074 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
1075 * @pos: the type * to use as a start point
1076 * @head: the head of the list
1077 * @member: the name of the list_struct within the struct.
1078 *
1079 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
1080 */
1081#define list_prepare_entry(pos, head, member) \
1082 ((pos) ? : list_entry(head, typeof(*pos), member))
1083
1084/**
1085 * list_for_each_entry_continue - continue iteration over list of given type
1086 * @pos: the type * to use as a loop cursor.
1087 * @head: the head for your list.
1088 * @member: the name of the list_struct within the struct.
1089 *
1090 * Continue to iterate over list of given type, continuing after
1091 * the current position.
1092 */
1093#define list_for_each_entry_continue(pos, head, member) \
1094 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
1095 prefetch(pos->member.next), &pos->member != (head); \
1096 pos = list_entry(pos->member.next, typeof(*pos), member))
1097
1098/**
1099 * list_for_each_entry_continue_reverse - iterate backwards from the given point
1100 * @pos: the type * to use as a loop cursor.
1101 * @head: the head for your list.
1102 * @member: the name of the list_struct within the struct.
1103 *
1104 * Start to iterate over list of given type backwards, continuing after
1105 * the current position.
1106 */
1107#define list_for_each_entry_continue_reverse(pos, head, member) \
1108 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
1109 prefetch(pos->member.prev), &pos->member != (head); \
1110 pos = list_entry(pos->member.prev, typeof(*pos), member))
1111
1112/**
1113 * list_for_each_entry_from - iterate over list of given type from the current point
1114 * @pos: the type * to use as a loop cursor.
1115 * @head: the head for your list.
1116 * @member: the name of the list_struct within the struct.
1117 *
1118 * Iterate over list of given type, continuing from current position.
1119 */
1120#define list_for_each_entry_from(pos, head, member) \
1121 for (; prefetch(pos->member.next), &pos->member != (head); \
1122 pos = list_entry(pos->member.next, typeof(*pos), member))
1123
1124/**
1125 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1126 * @pos: the type * to use as a loop cursor.
1127 * @n: another type * to use as temporary storage
1128 * @head: the head for your list.
1129 * @member: the name of the list_struct within the struct.
1130 */
1131#define list_for_each_entry_safe(pos, n, head, member) \
1132 for (pos = list_entry((head)->next, typeof(*pos), member), \
1133 n = list_entry(pos->member.next, typeof(*pos), member); \
1134 &pos->member != (head); \
1135 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1136
1137/**
1138 * list_for_each_entry_safe_continue
1139 * @pos: the type * to use as a loop cursor.
1140 * @n: another type * to use as temporary storage
1141 * @head: the head for your list.
1142 * @member: the name of the list_struct within the struct.
1143 *
1144 * Iterate over list of given type, continuing after current point,
1145 * safe against removal of list entry.
1146 */
1147#define list_for_each_entry_safe_continue(pos, n, head, member) \
1148 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
1149 n = list_entry(pos->member.next, typeof(*pos), member); \
1150 &pos->member != (head); \
1151 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1152
1153/**
1154 * list_for_each_entry_safe_from
1155 * @pos: the type * to use as a loop cursor.
1156 * @n: another type * to use as temporary storage
1157 * @head: the head for your list.
1158 * @member: the name of the list_struct within the struct.
1159 *
1160 * Iterate over list of given type from current point, safe against
1161 * removal of list entry.
1162 */
1163#define list_for_each_entry_safe_from(pos, n, head, member) \
1164 for (n = list_entry(pos->member.next, typeof(*pos), member); \
1165 &pos->member != (head); \
1166 pos = n, n = list_entry(n->member.next, typeof(*n), member))
1167
1168/**
1169 * list_for_each_entry_safe_reverse
1170 * @pos: the type * to use as a loop cursor.
1171 * @n: another type * to use as temporary storage
1172 * @head: the head for your list.
1173 * @member: the name of the list_struct within the struct.
1174 *
1175 * Iterate backwards over list of given type, safe against removal
1176 * of list entry.
1177 */
1178#define list_for_each_entry_safe_reverse(pos, n, head, member) \
1179 for (pos = list_entry((head)->prev, typeof(*pos), member), \
1180 n = list_entry(pos->member.prev, typeof(*pos), member); \
1181 &pos->member != (head); \
1182 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
1183
63ff4873
MD
1184#endif //0
1185
0578089f
PM
1186/*
1187 * Double linked lists with a single pointer list head.
1188 * Mostly useful for hash tables where the two pointer list head is
1189 * too wasteful.
1190 * You lose the ability to access the tail in O(1).
1191 */
1192
1193struct hlist_head {
1194 struct hlist_node *first;
1195};
1196
1197struct hlist_node {
1198 struct hlist_node *next, **pprev;
1199};
1200
1201#define HLIST_HEAD_INIT { .first = NULL }
1202#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
1203#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
1204static inline void INIT_HLIST_NODE(struct hlist_node *h)
1205{
1206 h->next = NULL;
1207 h->pprev = NULL;
1208}
1209
1210static inline int hlist_unhashed(const struct hlist_node *h)
1211{
1212 return !h->pprev;
1213}
1214
1215static inline int hlist_empty(const struct hlist_head *h)
1216{
1217 return !h->first;
1218}
1219
1220static inline void __hlist_del(struct hlist_node *n)
1221{
1222 struct hlist_node *next = n->next;
1223 struct hlist_node **pprev = n->pprev;
1224 *pprev = next;
1225 if (next)
1226 next->pprev = pprev;
1227}
1228
1229static inline void hlist_del(struct hlist_node *n)
1230{
1231 __hlist_del(n);
1232 n->next = LIST_POISON1;
1233 n->pprev = LIST_POISON2;
1234}
1235
1236static inline void hlist_del_init(struct hlist_node *n)
1237{
1238 if (!hlist_unhashed(n)) {
1239 __hlist_del(n);
1240 INIT_HLIST_NODE(n);
1241 }
1242}
1243
1244static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
1245{
1246 struct hlist_node *first = h->first;
1247 n->next = first;
1248 if (first)
1249 first->pprev = &n->next;
1250 h->first = n;
1251 n->pprev = &h->first;
1252}
1253
1254/* next must be != NULL */
1255static inline void hlist_add_before(struct hlist_node *n,
1256 struct hlist_node *next)
1257{
1258 n->pprev = next->pprev;
1259 n->next = next;
1260 next->pprev = &n->next;
1261 *(n->pprev) = n;
1262}
1263
1264static inline void hlist_add_after(struct hlist_node *n,
1265 struct hlist_node *next)
1266{
1267 next->next = n->next;
1268 n->next = next;
1269 next->pprev = &n->next;
1270
1271 if(next->next)
1272 next->next->pprev = &next->next;
1273}
1274
1275/*
1276 * Move a list from one list head to another. Fixup the pprev
1277 * reference of the first entry if it exists.
1278 */
1279static inline void hlist_move_list(struct hlist_head *old,
1280 struct hlist_head *new)
1281{
1282 new->first = old->first;
1283 if (new->first)
1284 new->first->pprev = &new->first;
1285 old->first = NULL;
1286}
1287
1288#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
1289
1290#define hlist_for_each(pos, head) \
1291 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
1292 pos = pos->next)
1293
1294#define hlist_for_each_safe(pos, n, head) \
1295 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
1296 pos = n)
1297
1298/**
1299 * hlist_for_each_entry - iterate over list of given type
1300 * @tpos: the type * to use as a loop cursor.
1301 * @pos: the &struct hlist_node to use as a loop cursor.
1302 * @head: the head for your list.
1303 * @member: the name of the hlist_node within the struct.
1304 */
1305#define hlist_for_each_entry(tpos, pos, head, member) \
1306 for (pos = (head)->first; \
1307 pos && ({ prefetch(pos->next); 1;}) && \
1308 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1309 pos = pos->next)
1310
1311/**
1312 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1313 * @tpos: the type * to use as a loop cursor.
1314 * @pos: the &struct hlist_node to use as a loop cursor.
1315 * @member: the name of the hlist_node within the struct.
1316 */
1317#define hlist_for_each_entry_continue(tpos, pos, member) \
1318 for (pos = (pos)->next; \
1319 pos && ({ prefetch(pos->next); 1;}) && \
1320 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1321 pos = pos->next)
1322
1323/**
1324 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1325 * @tpos: the type * to use as a loop cursor.
1326 * @pos: the &struct hlist_node to use as a loop cursor.
1327 * @member: the name of the hlist_node within the struct.
1328 */
1329#define hlist_for_each_entry_from(tpos, pos, member) \
1330 for (; pos && ({ prefetch(pos->next); 1;}) && \
1331 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1332 pos = pos->next)
1333
1334/**
1335 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1336 * @tpos: the type * to use as a loop cursor.
1337 * @pos: the &struct hlist_node to use as a loop cursor.
1338 * @n: another &struct hlist_node to use as temporary storage
1339 * @head: the head for your list.
1340 * @member: the name of the hlist_node within the struct.
1341 */
1342#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
1343 for (pos = (head)->first; \
1344 pos && ({ n = pos->next; 1; }) && \
1345 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
1346 pos = n)
1347
1348#endif
1a43bbd8
MD
1349
1350#endif
This page took 0.07327 seconds and 4 git commands to generate.