Project

General

Profile

Feature #9632 ยป 0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch

normalperson (Eric Wong), 03/13/2014 03:25 AM

View differences:

benchmark/bm_vm_thread_close.rb
1
1000.times { Thread.new { sleep } }
2
i = 0
3
while i<100_000 # benchmark loop 3
4
  i += 1
5
  IO.pipe.each(&:close)
6
end
ccan/build_assert/LICENSE
1
Statement of Purpose
2

  
3
The laws of most jurisdictions throughout the world automatically confer exclusive Copyright and Related Rights (defined below) upon the creator and subsequent owner(s) (each and all, an "owner") of an original work of authorship and/or a database (each, a "Work").
4

  
5
Certain owners wish to permanently relinquish those rights to a Work for the purpose of contributing to a commons of creative, cultural and scientific works ("Commons") that the public can reliably and without fear of later claims of infringement build upon, modify, incorporate in other works, reuse and redistribute as freely as possible in any form whatsoever and for any purposes, including without limitation commercial purposes. These owners may contribute to the Commons to promote the ideal of a free culture and the further production of creative, cultural and scientific works, or to gain reputation or greater distribution for their Work in part through the use and efforts of others.
6

  
7
For these and/or other purposes and motivations, and without any expectation of additional consideration or compensation, the person associating CC0 with a Work (the "Affirmer"), to the extent that he or she is an owner of Copyright and Related Rights in the Work, voluntarily elects to apply CC0 to the Work and publicly distribute the Work under its terms, with knowledge of his or her Copyright and Related Rights in the Work and the meaning and intended legal effect of CC0 on those rights.
8

  
9
1. Copyright and Related Rights. A Work made available under CC0 may be protected by copyright and related or neighboring rights ("Copyright and Related Rights"). Copyright and Related Rights include, but are not limited to, the following:
10

  
11
    the right to reproduce, adapt, distribute, perform, display, communicate, and translate a Work;
12
    moral rights retained by the original author(s) and/or performer(s);
13
    publicity and privacy rights pertaining to a person's image or likeness depicted in a Work;
14
    rights protecting against unfair competition in regards to a Work, subject to the limitations in paragraph 4(a), below;
15
    rights protecting the extraction, dissemination, use and reuse of data in a Work;
16
    database rights (such as those arising under Directive 96/9/EC of the European Parliament and of the Council of 11 March 1996 on the legal protection of databases, and under any national implementation thereof, including any amended or successor version of such directive); and
17
    other similar, equivalent or corresponding rights throughout the world based on applicable law or treaty, and any national implementations thereof.
18

  
19
2. Waiver. To the greatest extent permitted by, but not in contravention of, applicable law, Affirmer hereby overtly, fully, permanently, irrevocably and unconditionally waives, abandons, and surrenders all of Affirmer's Copyright and Related Rights and associated claims and causes of action, whether now known or unknown (including existing as well as future claims and causes of action), in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each member of the public at large and to the detriment of Affirmer's heirs and successors, fully intending that such Waiver shall not be subject to revocation, rescission, cancellation, termination, or any other legal or equitable action to disrupt the quiet enjoyment of the Work by the public as contemplated by Affirmer's express Statement of Purpose.
20

  
21
3. Public License Fallback. Should any part of the Waiver for any reason be judged legally invalid or ineffective under applicable law, then the Waiver shall be preserved to the maximum extent permitted taking into account Affirmer's express Statement of Purpose. In addition, to the extent the Waiver is so judged Affirmer hereby grants to each affected person a royalty-free, non transferable, non sublicensable, non exclusive, irrevocable and unconditional license to exercise Affirmer's Copyright and Related Rights in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "License"). The License shall be deemed effective as of the date CC0 was applied by Affirmer to the Work. Should any part of the License for any reason be judged legally invalid or ineffective under applicable law, such partial invalidity or ineffectiveness shall not invalidate the remainder of the License, and in such case Affirmer hereby affirms that he or she will not (i) exercise any of his or her remaining Copyright and Related Rights in the Work or (ii) assert any associated claims and causes of action with respect to the Work, in either case contrary to Affirmer's express Statement of Purpose.
22

  
23
4. Limitations and Disclaimers.
24

  
25
    No trademark or patent rights held by Affirmer are waived, abandoned, surrendered, licensed or otherwise affected by this document.
26
    Affirmer offers the Work as-is and makes no representations or warranties of any kind concerning the Work, express, implied, statutory or otherwise, including without limitation warranties of title, merchantability, fitness for a particular purpose, non infringement, or the absence of latent or other defects, accuracy, or the present or absence of errors, whether or not discoverable, all to the greatest extent permissible under applicable law.
27
    Affirmer disclaims responsibility for clearing rights of other persons that may apply to the Work or any use thereof, including without limitation any person's Copyright and Related Rights in the Work. Further, Affirmer disclaims responsibility for obtaining any necessary consents, permissions or other rights required for any use of the Work.
28
    Affirmer understands and acknowledges that Creative Commons is not a party to this document and has no duty or obligation with respect to this CC0 or use of the Work.
ccan/build_assert/build_assert.h
1
/* CC0 (Public domain) - see LICENSE file for details */
2
#ifndef CCAN_BUILD_ASSERT_H
3
#define CCAN_BUILD_ASSERT_H
4

  
5
/**
6
 * BUILD_ASSERT - assert a build-time dependency.
7
 * @cond: the compile-time condition which must be true.
8
 *
9
 * Your compile will fail if the condition isn't true, or can't be evaluated
10
 * by the compiler.  This can only be used within a function.
11
 *
12
 * Example:
13
 *	#include <stddef.h>
14
 *	...
15
 *	static char *foo_to_char(struct foo *foo)
16
 *	{
17
 *		// This code needs string to be at start of foo.
18
 *		BUILD_ASSERT(offsetof(struct foo, string) == 0);
19
 *		return (char *)foo;
20
 *	}
21
 */
22
#define BUILD_ASSERT(cond) \
23
	do { (void) sizeof(char [1 - 2*!(cond)]); } while(0)
24

  
25
/**
26
 * BUILD_ASSERT_OR_ZERO - assert a build-time dependency, as an expression.
27
 * @cond: the compile-time condition which must be true.
28
 *
29
 * Your compile will fail if the condition isn't true, or can't be evaluated
30
 * by the compiler.  This can be used in an expression: its value is "0".
31
 *
32
 * Example:
33
 *	#define foo_to_char(foo)					\
34
 *		 ((char *)(foo)						\
35
 *		  + BUILD_ASSERT_OR_ZERO(offsetof(struct foo, string) == 0))
36
 */
37
#define BUILD_ASSERT_OR_ZERO(cond) \
38
	(sizeof(char [1 - 2*!(cond)]) - 1)
39

  
40
#endif /* CCAN_BUILD_ASSERT_H */
ccan/check_type/LICENSE
1
Statement of Purpose
2

  
3
The laws of most jurisdictions throughout the world automatically confer exclusive Copyright and Related Rights (defined below) upon the creator and subsequent owner(s) (each and all, an "owner") of an original work of authorship and/or a database (each, a "Work").
4

  
5
Certain owners wish to permanently relinquish those rights to a Work for the purpose of contributing to a commons of creative, cultural and scientific works ("Commons") that the public can reliably and without fear of later claims of infringement build upon, modify, incorporate in other works, reuse and redistribute as freely as possible in any form whatsoever and for any purposes, including without limitation commercial purposes. These owners may contribute to the Commons to promote the ideal of a free culture and the further production of creative, cultural and scientific works, or to gain reputation or greater distribution for their Work in part through the use and efforts of others.
6

  
7
For these and/or other purposes and motivations, and without any expectation of additional consideration or compensation, the person associating CC0 with a Work (the "Affirmer"), to the extent that he or she is an owner of Copyright and Related Rights in the Work, voluntarily elects to apply CC0 to the Work and publicly distribute the Work under its terms, with knowledge of his or her Copyright and Related Rights in the Work and the meaning and intended legal effect of CC0 on those rights.
8

  
9
1. Copyright and Related Rights. A Work made available under CC0 may be protected by copyright and related or neighboring rights ("Copyright and Related Rights"). Copyright and Related Rights include, but are not limited to, the following:
10

  
11
    the right to reproduce, adapt, distribute, perform, display, communicate, and translate a Work;
12
    moral rights retained by the original author(s) and/or performer(s);
13
    publicity and privacy rights pertaining to a person's image or likeness depicted in a Work;
14
    rights protecting against unfair competition in regards to a Work, subject to the limitations in paragraph 4(a), below;
15
    rights protecting the extraction, dissemination, use and reuse of data in a Work;
16
    database rights (such as those arising under Directive 96/9/EC of the European Parliament and of the Council of 11 March 1996 on the legal protection of databases, and under any national implementation thereof, including any amended or successor version of such directive); and
17
    other similar, equivalent or corresponding rights throughout the world based on applicable law or treaty, and any national implementations thereof.
18

  
19
2. Waiver. To the greatest extent permitted by, but not in contravention of, applicable law, Affirmer hereby overtly, fully, permanently, irrevocably and unconditionally waives, abandons, and surrenders all of Affirmer's Copyright and Related Rights and associated claims and causes of action, whether now known or unknown (including existing as well as future claims and causes of action), in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each member of the public at large and to the detriment of Affirmer's heirs and successors, fully intending that such Waiver shall not be subject to revocation, rescission, cancellation, termination, or any other legal or equitable action to disrupt the quiet enjoyment of the Work by the public as contemplated by Affirmer's express Statement of Purpose.
20

  
21
3. Public License Fallback. Should any part of the Waiver for any reason be judged legally invalid or ineffective under applicable law, then the Waiver shall be preserved to the maximum extent permitted taking into account Affirmer's express Statement of Purpose. In addition, to the extent the Waiver is so judged Affirmer hereby grants to each affected person a royalty-free, non transferable, non sublicensable, non exclusive, irrevocable and unconditional license to exercise Affirmer's Copyright and Related Rights in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "License"). The License shall be deemed effective as of the date CC0 was applied by Affirmer to the Work. Should any part of the License for any reason be judged legally invalid or ineffective under applicable law, such partial invalidity or ineffectiveness shall not invalidate the remainder of the License, and in such case Affirmer hereby affirms that he or she will not (i) exercise any of his or her remaining Copyright and Related Rights in the Work or (ii) assert any associated claims and causes of action with respect to the Work, in either case contrary to Affirmer's express Statement of Purpose.
22

  
23
4. Limitations and Disclaimers.
24

  
25
    No trademark or patent rights held by Affirmer are waived, abandoned, surrendered, licensed or otherwise affected by this document.
26
    Affirmer offers the Work as-is and makes no representations or warranties of any kind concerning the Work, express, implied, statutory or otherwise, including without limitation warranties of title, merchantability, fitness for a particular purpose, non infringement, or the absence of latent or other defects, accuracy, or the present or absence of errors, whether or not discoverable, all to the greatest extent permissible under applicable law.
27
    Affirmer disclaims responsibility for clearing rights of other persons that may apply to the Work or any use thereof, including without limitation any person's Copyright and Related Rights in the Work. Further, Affirmer disclaims responsibility for obtaining any necessary consents, permissions or other rights required for any use of the Work.
28
    Affirmer understands and acknowledges that Creative Commons is not a party to this document and has no duty or obligation with respect to this CC0 or use of the Work.
ccan/check_type/check_type.h
1
/* CC0 (Public domain) - see LICENSE file for details */
2
#ifndef CCAN_CHECK_TYPE_H
3
#define CCAN_CHECK_TYPE_H
4

  
5
/**
6
 * check_type - issue a warning or build failure if type is not correct.
7
 * @expr: the expression whose type we should check (not evaluated).
8
 * @type: the exact type we expect the expression to be.
9
 *
10
 * This macro is usually used within other macros to try to ensure that a macro
11
 * argument is of the expected type.  No type promotion of the expression is
12
 * done: an unsigned int is not the same as an int!
13
 *
14
 * check_type() always evaluates to 0.
15
 *
16
 * If your compiler does not support typeof, then the best we can do is fail
17
 * to compile if the sizes of the types are unequal (a less complete check).
18
 *
19
 * Example:
20
 *	// They should always pass a 64-bit value to _set_some_value!
21
 *	#define set_some_value(expr)			\
22
 *		_set_some_value((check_type((expr), uint64_t), (expr)))
23
 */
24

  
25
/**
26
 * check_types_match - issue a warning or build failure if types are not same.
27
 * @expr1: the first expression (not evaluated).
28
 * @expr2: the second expression (not evaluated).
29
 *
30
 * This macro is usually used within other macros to try to ensure that
31
 * arguments are of identical types.  No type promotion of the expressions is
32
 * done: an unsigned int is not the same as an int!
33
 *
34
 * check_types_match() always evaluates to 0.
35
 *
36
 * If your compiler does not support typeof, then the best we can do is fail
37
 * to compile if the sizes of the types are unequal (a less complete check).
38
 *
39
 * Example:
40
 *	// Do subtraction to get to enclosing type, but make sure that
41
 *	// pointer is of correct type for that member.
42
 *	#define container_of(mbr_ptr, encl_type, mbr)			\
43
 *		(check_types_match((mbr_ptr), &((encl_type *)0)->mbr),	\
44
 *		 ((encl_type *)						\
45
 *		  ((char *)(mbr_ptr) - offsetof(enclosing_type, mbr))))
46
 */
47
#if HAVE_TYPEOF
48
#define check_type(expr, type)			\
49
	((typeof(expr) *)0 != (type *)0)
50

  
51
#define check_types_match(expr1, expr2)		\
52
	((typeof(expr1) *)0 != (typeof(expr2) *)0)
53
#else
54
#include "ccan/build_assert/build_assert.h"
55
/* Without typeof, we can only test the sizes. */
56
#define check_type(expr, type)					\
57
	BUILD_ASSERT_OR_ZERO(sizeof(expr) == sizeof(type))
58

  
59
#define check_types_match(expr1, expr2)				\
60
	BUILD_ASSERT_OR_ZERO(sizeof(expr1) == sizeof(expr2))
61
#endif /* HAVE_TYPEOF */
62

  
63
#endif /* CCAN_CHECK_TYPE_H */
ccan/container_of/LICENSE
1
Statement of Purpose
2

  
3
The laws of most jurisdictions throughout the world automatically confer exclusive Copyright and Related Rights (defined below) upon the creator and subsequent owner(s) (each and all, an "owner") of an original work of authorship and/or a database (each, a "Work").
4

  
5
Certain owners wish to permanently relinquish those rights to a Work for the purpose of contributing to a commons of creative, cultural and scientific works ("Commons") that the public can reliably and without fear of later claims of infringement build upon, modify, incorporate in other works, reuse and redistribute as freely as possible in any form whatsoever and for any purposes, including without limitation commercial purposes. These owners may contribute to the Commons to promote the ideal of a free culture and the further production of creative, cultural and scientific works, or to gain reputation or greater distribution for their Work in part through the use and efforts of others.
6

  
7
For these and/or other purposes and motivations, and without any expectation of additional consideration or compensation, the person associating CC0 with a Work (the "Affirmer"), to the extent that he or she is an owner of Copyright and Related Rights in the Work, voluntarily elects to apply CC0 to the Work and publicly distribute the Work under its terms, with knowledge of his or her Copyright and Related Rights in the Work and the meaning and intended legal effect of CC0 on those rights.
8

  
9
1. Copyright and Related Rights. A Work made available under CC0 may be protected by copyright and related or neighboring rights ("Copyright and Related Rights"). Copyright and Related Rights include, but are not limited to, the following:
10

  
11
    the right to reproduce, adapt, distribute, perform, display, communicate, and translate a Work;
12
    moral rights retained by the original author(s) and/or performer(s);
13
    publicity and privacy rights pertaining to a person's image or likeness depicted in a Work;
14
    rights protecting against unfair competition in regards to a Work, subject to the limitations in paragraph 4(a), below;
15
    rights protecting the extraction, dissemination, use and reuse of data in a Work;
16
    database rights (such as those arising under Directive 96/9/EC of the European Parliament and of the Council of 11 March 1996 on the legal protection of databases, and under any national implementation thereof, including any amended or successor version of such directive); and
17
    other similar, equivalent or corresponding rights throughout the world based on applicable law or treaty, and any national implementations thereof.
18

  
19
2. Waiver. To the greatest extent permitted by, but not in contravention of, applicable law, Affirmer hereby overtly, fully, permanently, irrevocably and unconditionally waives, abandons, and surrenders all of Affirmer's Copyright and Related Rights and associated claims and causes of action, whether now known or unknown (including existing as well as future claims and causes of action), in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each member of the public at large and to the detriment of Affirmer's heirs and successors, fully intending that such Waiver shall not be subject to revocation, rescission, cancellation, termination, or any other legal or equitable action to disrupt the quiet enjoyment of the Work by the public as contemplated by Affirmer's express Statement of Purpose.
20

  
21
3. Public License Fallback. Should any part of the Waiver for any reason be judged legally invalid or ineffective under applicable law, then the Waiver shall be preserved to the maximum extent permitted taking into account Affirmer's express Statement of Purpose. In addition, to the extent the Waiver is so judged Affirmer hereby grants to each affected person a royalty-free, non transferable, non sublicensable, non exclusive, irrevocable and unconditional license to exercise Affirmer's Copyright and Related Rights in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "License"). The License shall be deemed effective as of the date CC0 was applied by Affirmer to the Work. Should any part of the License for any reason be judged legally invalid or ineffective under applicable law, such partial invalidity or ineffectiveness shall not invalidate the remainder of the License, and in such case Affirmer hereby affirms that he or she will not (i) exercise any of his or her remaining Copyright and Related Rights in the Work or (ii) assert any associated claims and causes of action with respect to the Work, in either case contrary to Affirmer's express Statement of Purpose.
22

  
23
4. Limitations and Disclaimers.
24

  
25
    No trademark or patent rights held by Affirmer are waived, abandoned, surrendered, licensed or otherwise affected by this document.
26
    Affirmer offers the Work as-is and makes no representations or warranties of any kind concerning the Work, express, implied, statutory or otherwise, including without limitation warranties of title, merchantability, fitness for a particular purpose, non infringement, or the absence of latent or other defects, accuracy, or the present or absence of errors, whether or not discoverable, all to the greatest extent permissible under applicable law.
27
    Affirmer disclaims responsibility for clearing rights of other persons that may apply to the Work or any use thereof, including without limitation any person's Copyright and Related Rights in the Work. Further, Affirmer disclaims responsibility for obtaining any necessary consents, permissions or other rights required for any use of the Work.
28
    Affirmer understands and acknowledges that Creative Commons is not a party to this document and has no duty or obligation with respect to this CC0 or use of the Work.
ccan/container_of/container_of.h
1
/* CC0 (Public domain) - see LICENSE file for details */
2
#ifndef CCAN_CONTAINER_OF_H
3
#define CCAN_CONTAINER_OF_H
4
#include "ccan/check_type/check_type.h"
5

  
6
/**
7
 * container_of - get pointer to enclosing structure
8
 * @member_ptr: pointer to the structure member
9
 * @containing_type: the type this member is within
10
 * @member: the name of this member within the structure.
11
 *
12
 * Given a pointer to a member of a structure, this macro does pointer
13
 * subtraction to return the pointer to the enclosing type.
14
 *
15
 * Example:
16
 *	struct foo {
17
 *		int fielda, fieldb;
18
 *		// ...
19
 *	};
20
 *	struct info {
21
 *		int some_other_field;
22
 *		struct foo my_foo;
23
 *	};
24
 *
25
 *	static struct info *foo_to_info(struct foo *foo)
26
 *	{
27
 *		return container_of(foo, struct info, my_foo);
28
 *	}
29
 */
30
#define container_of(member_ptr, containing_type, member)		\
31
	 ((containing_type *)						\
32
	  ((char *)(member_ptr)						\
33
	   - container_off(containing_type, member))			\
34
	  + check_types_match(*(member_ptr), ((containing_type *)0)->member))
35

  
36
/**
37
 * container_off - get offset to enclosing structure
38
 * @containing_type: the type this member is within
39
 * @member: the name of this member within the structure.
40
 *
41
 * Given a pointer to a member of a structure, this macro does
42
 * typechecking and figures out the offset to the enclosing type.
43
 *
44
 * Example:
45
 *	struct foo {
46
 *		int fielda, fieldb;
47
 *		// ...
48
 *	};
49
 *	struct info {
50
 *		int some_other_field;
51
 *		struct foo my_foo;
52
 *	};
53
 *
54
 *	static struct info *foo_to_info(struct foo *foo)
55
 *	{
56
 *		size_t off = container_off(struct info, my_foo);
57
 *		return (void *)((char *)foo - off);
58
 *	}
59
 */
60
#define container_off(containing_type, member)	\
61
	offsetof(containing_type, member)
62

  
63
/**
64
 * container_of_var - get pointer to enclosing structure using a variable
65
 * @member_ptr: pointer to the structure member
66
 * @container_var: a pointer of same type as this member's container
67
 * @member: the name of this member within the structure.
68
 *
69
 * Given a pointer to a member of a structure, this macro does pointer
70
 * subtraction to return the pointer to the enclosing type.
71
 *
72
 * Example:
73
 *	static struct info *foo_to_i(struct foo *foo)
74
 *	{
75
 *		struct info *i = container_of_var(foo, i, my_foo);
76
 *		return i;
77
 *	}
78
 */
79
#if HAVE_TYPEOF
80
#define container_of_var(member_ptr, container_var, member) \
81
	container_of(member_ptr, typeof(*container_var), member)
82
#else
83
#define container_of_var(member_ptr, container_var, member)	\
84
	((void *)((char *)(member_ptr)	-			\
85
		  container_off_var(container_var, member)))
86
#endif
87

  
88
/**
89
 * container_off_var - get offset of a field in enclosing structure
90
 * @container_var: a pointer to a container structure
91
 * @member: the name of a member within the structure.
92
 *
93
 * Given (any) pointer to a structure and a its member name, this
94
 * macro does pointer subtraction to return offset of member in a
95
 * structure memory layout.
96
 *
97
 */
98
#if HAVE_TYPEOF
99
#define container_off_var(var, member)		\
100
	container_off(typeof(*var), member)
101
#else
102
#define container_off_var(var, member)			\
103
	((char *)&(var)->member - (char *)(var))
104
#endif
105

  
106
#endif /* CCAN_CONTAINER_OF_H */
ccan/list/LICENSE
1
Permission is hereby granted, free of charge, to any person obtaining a copy
2
of this software and associated documentation files (the "Software"), to deal
3
in the Software without restriction, including without limitation the rights
4
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
5
copies of the Software, and to permit persons to whom the Software is
6
furnished to do so, subject to the following conditions:
7

  
8
The above copyright notice and this permission notice shall be included in
9
all copies or substantial portions of the Software.
10

  
11
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
12
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
13
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
14
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
15
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
16
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
17
THE SOFTWARE.
ccan/list/list.h
1
/* Licensed under BSD-MIT - see LICENSE file for details */
2
#ifndef CCAN_LIST_H
3
#define CCAN_LIST_H
4
#include <assert.h>
5
#include "ccan/str/str.h"
6
#include "ccan/container_of/container_of.h"
7
#include "ccan/check_type/check_type.h"
8

  
9
/**
10
 * struct list_node - an entry in a doubly-linked list
11
 * @next: next entry (self if empty)
12
 * @prev: previous entry (self if empty)
13
 *
14
 * This is used as an entry in a linked list.
15
 * Example:
16
 *	struct child {
17
 *		const char *name;
18
 *		// Linked list of all us children.
19
 *		struct list_node list;
20
 *	};
21
 */
22
struct list_node
23
{
24
	struct list_node *next, *prev;
25
};
26

  
27
/**
28
 * struct list_head - the head of a doubly-linked list
29
 * @h: the list_head (containing next and prev pointers)
30
 *
31
 * This is used as the head of a linked list.
32
 * Example:
33
 *	struct parent {
34
 *		const char *name;
35
 *		struct list_head children;
36
 *		unsigned int num_children;
37
 *	};
38
 */
39
struct list_head
40
{
41
	struct list_node n;
42
};
43

  
44
#define LIST_LOC __FILE__  ":" stringify(__LINE__)
45
#define list_debug(h, loc) (h)
46
#define list_debug_node(n, loc) (n)
47

  
48
/**
49
 * LIST_HEAD_INIT - initializer for an empty list_head
50
 * @name: the name of the list.
51
 *
52
 * Explicit initializer for an empty list.
53
 *
54
 * See also:
55
 *	LIST_HEAD, list_head_init()
56
 *
57
 * Example:
58
 *	static struct list_head my_list = LIST_HEAD_INIT(my_list);
59
 */
60
#define LIST_HEAD_INIT(name) { { &name.n, &name.n } }
61

  
62
/**
63
 * LIST_HEAD - define and initialize an empty list_head
64
 * @name: the name of the list.
65
 *
66
 * The LIST_HEAD macro defines a list_head and initializes it to an empty
67
 * list.  It can be prepended by "static" to define a static list_head.
68
 *
69
 * See also:
70
 *	LIST_HEAD_INIT, list_head_init()
71
 *
72
 * Example:
73
 *	static LIST_HEAD(my_global_list);
74
 */
75
#define LIST_HEAD(name) \
76
	struct list_head name = LIST_HEAD_INIT(name)
77

  
78
/**
79
 * list_head_init - initialize a list_head
80
 * @h: the list_head to set to the empty list
81
 *
82
 * Example:
83
 *	...
84
 *	struct parent *parent = malloc(sizeof(*parent));
85
 *
86
 *	list_head_init(&parent->children);
87
 *	parent->num_children = 0;
88
 */
89
static inline void list_head_init(struct list_head *h)
90
{
91
	h->n.next = h->n.prev = &h->n;
92
}
93

  
94
/**
95
 * list_add - add an entry at the start of a linked list.
96
 * @h: the list_head to add the node to
97
 * @n: the list_node to add to the list.
98
 *
99
 * The list_node does not need to be initialized; it will be overwritten.
100
 * Example:
101
 *	struct child *child = malloc(sizeof(*child));
102
 *
103
 *	child->name = "marvin";
104
 *	list_add(&parent->children, &child->list);
105
 *	parent->num_children++;
106
 */
107
#define list_add(h, n) list_add_(h, n, LIST_LOC)
108
static inline void list_add_(struct list_head *h,
109
			     struct list_node *n,
110
			     const char *abortstr)
111
{
112
	n->next = h->n.next;
113
	n->prev = &h->n;
114
	h->n.next->prev = n;
115
	h->n.next = n;
116
	(void)list_debug(h, abortstr);
117
}
118

  
119
/**
120
 * list_add_tail - add an entry at the end of a linked list.
121
 * @h: the list_head to add the node to
122
 * @n: the list_node to add to the list.
123
 *
124
 * The list_node does not need to be initialized; it will be overwritten.
125
 * Example:
126
 *	list_add_tail(&parent->children, &child->list);
127
 *	parent->num_children++;
128
 */
129
#define list_add_tail(h, n) list_add_tail_(h, n, LIST_LOC)
130
static inline void list_add_tail_(struct list_head *h,
131
				  struct list_node *n,
132
				  const char *abortstr)
133
{
134
	n->next = &h->n;
135
	n->prev = h->n.prev;
136
	h->n.prev->next = n;
137
	h->n.prev = n;
138
	(void)list_debug(h, abortstr);
139
}
140

  
141
/**
142
 * list_empty - is a list empty?
143
 * @h: the list_head
144
 *
145
 * If the list is empty, returns true.
146
 *
147
 * Example:
148
 *	assert(list_empty(&parent->children) == (parent->num_children == 0));
149
 */
150
#define list_empty(h) list_empty_(h, LIST_LOC)
151
static inline int list_empty_(const struct list_head *h, const char* abortstr)
152
{
153
	(void)list_debug(h, abortstr);
154
	return h->n.next == &h->n;
155
}
156

  
157
/**
158
 * list_empty_nodebug - is a list empty (and don't perform debug checks)?
159
 * @h: the list_head
160
 *
161
 * If the list is empty, returns true.
162
 * This differs from list_empty() in that if CCAN_LIST_DEBUG is set it
163
 * will NOT perform debug checks. Only use this function if you REALLY
164
 * know what you're doing.
165
 *
166
 * Example:
167
 *	assert(list_empty_nodebug(&parent->children) == (parent->num_children == 0));
168
 */
169
#ifndef CCAN_LIST_DEBUG
170
#define list_empty_nodebug(h) list_empty(h)
171
#else
172
static inline int list_empty_nodebug(const struct list_head *h)
173
{
174
	return h->n.next == &h->n;
175
}
176
#endif
177

  
178
/**
179
 * list_del - delete an entry from an (unknown) linked list.
180
 * @n: the list_node to delete from the list.
181
 *
182
 * Note that this leaves @n in an undefined state; it can be added to
183
 * another list, but not deleted again.
184
 *
185
 * See also:
186
 *	list_del_from()
187
 *
188
 * Example:
189
 *	list_del(&child->list);
190
 *	parent->num_children--;
191
 */
192
#define list_del(n) list_del_(n, LIST_LOC)
193
static inline void list_del_(struct list_node *n, const char* abortstr)
194
{
195
	(void)list_debug_node(n, abortstr);
196
	n->next->prev = n->prev;
197
	n->prev->next = n->next;
198
#ifdef CCAN_LIST_DEBUG
199
	/* Catch use-after-del. */
200
	n->next = n->prev = NULL;
201
#endif
202
}
203

  
204
/**
205
 * list_del_from - delete an entry from a known linked list.
206
 * @h: the list_head the node is in.
207
 * @n: the list_node to delete from the list.
208
 *
209
 * This explicitly indicates which list a node is expected to be in,
210
 * which is better documentation and can catch more bugs.
211
 *
212
 * See also: list_del()
213
 *
214
 * Example:
215
 *	list_del_from(&parent->children, &child->list);
216
 *	parent->num_children--;
217
 */
218
static inline void list_del_from(struct list_head *h, struct list_node *n)
219
{
220
#ifdef CCAN_LIST_DEBUG
221
	{
222
		/* Thorough check: make sure it was in list! */
223
		struct list_node *i;
224
		for (i = h->n.next; i != n; i = i->next)
225
			assert(i != &h->n);
226
	}
227
#endif /* CCAN_LIST_DEBUG */
228

  
229
	/* Quick test that catches a surprising number of bugs. */
230
	assert(!list_empty(h));
231
	list_del(n);
232
}
233

  
234
/**
235
 * list_entry - convert a list_node back into the structure containing it.
236
 * @n: the list_node
237
 * @type: the type of the entry
238
 * @member: the list_node member of the type
239
 *
240
 * Example:
241
 *	// First list entry is children.next; convert back to child.
242
 *	child = list_entry(parent->children.n.next, struct child, list);
243
 *
244
 * See Also:
245
 *	list_top(), list_for_each()
246
 */
247
#define list_entry(n, type, member) container_of(n, type, member)
248

  
249
/**
250
 * list_top - get the first entry in a list
251
 * @h: the list_head
252
 * @type: the type of the entry
253
 * @member: the list_node member of the type
254
 *
255
 * If the list is empty, returns NULL.
256
 *
257
 * Example:
258
 *	struct child *first;
259
 *	first = list_top(&parent->children, struct child, list);
260
 *	if (!first)
261
 *		printf("Empty list!\n");
262
 */
263
#define list_top(h, type, member)					\
264
	((type *)list_top_((h), list_off_(type, member)))
265

  
266
static inline const void *list_top_(const struct list_head *h, size_t off)
267
{
268
	if (list_empty(h))
269
		return NULL;
270
	return (const char *)h->n.next - off;
271
}
272

  
273
/**
274
 * list_pop - remove the first entry in a list
275
 * @h: the list_head
276
 * @type: the type of the entry
277
 * @member: the list_node member of the type
278
 *
279
 * If the list is empty, returns NULL.
280
 *
281
 * Example:
282
 *	struct child *one;
283
 *	one = list_pop(&parent->children, struct child, list);
284
 *	if (!one)
285
 *		printf("Empty list!\n");
286
 */
287
#define list_pop(h, type, member)					\
288
	((type *)list_pop_((h), list_off_(type, member)))
289

  
290
static inline const void *list_pop_(const struct list_head *h, size_t off)
291
{
292
	struct list_node *n;
293

  
294
	if (list_empty(h))
295
		return NULL;
296
	n = h->n.next;
297
	list_del(n);
298
	return (const char *)n - off;
299
}
300

  
301
/**
302
 * list_tail - get the last entry in a list
303
 * @h: the list_head
304
 * @type: the type of the entry
305
 * @member: the list_node member of the type
306
 *
307
 * If the list is empty, returns NULL.
308
 *
309
 * Example:
310
 *	struct child *last;
311
 *	last = list_tail(&parent->children, struct child, list);
312
 *	if (!last)
313
 *		printf("Empty list!\n");
314
 */
315
#define list_tail(h, type, member) \
316
	((type *)list_tail_((h), list_off_(type, member)))
317

  
318
static inline const void *list_tail_(const struct list_head *h, size_t off)
319
{
320
	if (list_empty(h))
321
		return NULL;
322
	return (const char *)h->n.prev - off;
323
}
324

  
325
/**
326
 * list_for_each - iterate through a list.
327
 * @h: the list_head (warning: evaluated multiple times!)
328
 * @i: the structure containing the list_node
329
 * @member: the list_node member of the structure
330
 *
331
 * This is a convenient wrapper to iterate @i over the entire list.  It's
332
 * a for loop, so you can break and continue as normal.
333
 *
334
 * Example:
335
 *	list_for_each(&parent->children, child, list)
336
 *		printf("Name: %s\n", child->name);
337
 */
338
#define list_for_each(h, i, member)					\
339
	list_for_each_off(h, i, list_off_var_(i, member))
340

  
341
/**
342
 * list_for_each_rev - iterate through a list backwards.
343
 * @h: the list_head
344
 * @i: the structure containing the list_node
345
 * @member: the list_node member of the structure
346
 *
347
 * This is a convenient wrapper to iterate @i over the entire list.  It's
348
 * a for loop, so you can break and continue as normal.
349
 *
350
 * Example:
351
 *	list_for_each_rev(&parent->children, child, list)
352
 *		printf("Name: %s\n", child->name);
353
 */
354
#define list_for_each_rev(h, i, member)					\
355
	for (i = container_of_var(list_debug(h,	LIST_LOC)->n.prev, i, member); \
356
	     &i->member != &(h)->n;					\
357
	     i = container_of_var(i->member.prev, i, member))
358

  
359
/**
360
 * list_for_each_safe - iterate through a list, maybe during deletion
361
 * @h: the list_head
362
 * @i: the structure containing the list_node
363
 * @nxt: the structure containing the list_node
364
 * @member: the list_node member of the structure
365
 *
366
 * This is a convenient wrapper to iterate @i over the entire list.  It's
367
 * a for loop, so you can break and continue as normal.  The extra variable
368
 * @nxt is used to hold the next element, so you can delete @i from the list.
369
 *
370
 * Example:
371
 *	struct child *next;
372
 *	list_for_each_safe(&parent->children, child, next, list) {
373
 *		list_del(&child->list);
374
 *		parent->num_children--;
375
 *	}
376
 */
377
#define list_for_each_safe(h, i, nxt, member)				\
378
	list_for_each_safe_off(h, i, nxt, list_off_var_(i, member))
379

  
380
/**
381
 * list_next - get the next entry in a list
382
 * @h: the list_head
383
 * @i: a pointer to an entry in the list.
384
 * @member: the list_node member of the structure
385
 *
386
 * If @i was the last entry in the list, returns NULL.
387
 *
388
 * Example:
389
 *	struct child *second;
390
 *	second = list_next(&parent->children, first, list);
391
 *	if (!second)
392
 *		printf("No second child!\n");
393
 */
394
#define list_next(h, i, member)						\
395
	((list_typeof(i))list_entry_or_null(list_debug(h,		\
396
					    __FILE__ ":" stringify(__LINE__)), \
397
					    (i)->member.next,		\
398
					    list_off_var_((i), member)))
399

  
400
/**
401
 * list_prev - get the previous entry in a list
402
 * @h: the list_head
403
 * @i: a pointer to an entry in the list.
404
 * @member: the list_node member of the structure
405
 *
406
 * If @i was the first entry in the list, returns NULL.
407
 *
408
 * Example:
409
 *	first = list_prev(&parent->children, second, list);
410
 *	if (!first)
411
 *		printf("Can't go back to first child?!\n");
412
 */
413
#define list_prev(h, i, member)						\
414
	((list_typeof(i))list_entry_or_null(list_debug(h,		\
415
					    __FILE__ ":" stringify(__LINE__)), \
416
					    (i)->member.prev,		\
417
					    list_off_var_((i), member)))
418

  
419
/**
420
 * list_append_list - empty one list onto the end of another.
421
 * @to: the list to append into
422
 * @from: the list to empty.
423
 *
424
 * This takes the entire contents of @from and moves it to the end of
425
 * @to.  After this @from will be empty.
426
 *
427
 * Example:
428
 *	struct list_head adopter;
429
 *
430
 *	list_append_list(&adopter, &parent->children);
431
 *	assert(list_empty(&parent->children));
432
 *	parent->num_children = 0;
433
 */
434
#define list_append_list(t, f) list_append_list_(t, f,			\
435
				   __FILE__ ":" stringify(__LINE__))
436
static inline void list_append_list_(struct list_head *to,
437
				     struct list_head *from,
438
				     const char *abortstr)
439
{
440
	struct list_node *from_tail = list_debug(from, abortstr)->n.prev;
441
	struct list_node *to_tail = list_debug(to, abortstr)->n.prev;
442

  
443
	/* Sew in head and entire list. */
444
	to->n.prev = from_tail;
445
	from_tail->next = &to->n;
446
	to_tail->next = &from->n;
447
	from->n.prev = to_tail;
448

  
449
	/* Now remove head. */
450
	list_del(&from->n);
451
	list_head_init(from);
452
}
453

  
454
/**
455
 * list_prepend_list - empty one list into the start of another.
456
 * @to: the list to prepend into
457
 * @from: the list to empty.
458
 *
459
 * This takes the entire contents of @from and moves it to the start
460
 * of @to.  After this @from will be empty.
461
 *
462
 * Example:
463
 *	list_prepend_list(&adopter, &parent->children);
464
 *	assert(list_empty(&parent->children));
465
 *	parent->num_children = 0;
466
 */
467
#define list_prepend_list(t, f) list_prepend_list_(t, f, LIST_LOC)
468
static inline void list_prepend_list_(struct list_head *to,
469
				      struct list_head *from,
470
				      const char *abortstr)
471
{
472
	struct list_node *from_tail = list_debug(from, abortstr)->n.prev;
473
	struct list_node *to_head = list_debug(to, abortstr)->n.next;
474

  
475
	/* Sew in head and entire list. */
476
	to->n.next = &from->n;
477
	from->n.prev = &to->n;
478
	to_head->prev = from_tail;
479
	from_tail->next = to_head;
480

  
481
	/* Now remove head. */
482
	list_del(&from->n);
483
	list_head_init(from);
484
}
485

  
486
/**
487
 * list_for_each_off - iterate through a list of memory regions.
488
 * @h: the list_head
489
 * @i: the pointer to a memory region wich contains list node data.
490
 * @off: offset(relative to @i) at which list node data resides.
491
 *
492
 * This is a low-level wrapper to iterate @i over the entire list, used to
493
 * implement all oher, more high-level, for-each constructs. It's a for loop,
494
 * so you can break and continue as normal.
495
 *
496
 * WARNING! Being the low-level macro that it is, this wrapper doesn't know
497
 * nor care about the type of @i. The only assumtion made is that @i points
498
 * to a chunk of memory that at some @offset, relative to @i, contains a
499
 * properly filled `struct node_list' which in turn contains pointers to
500
 * memory chunks and it's turtles all the way down. Whith all that in mind
501
 * remember that given the wrong pointer/offset couple this macro will
502
 * happilly churn all you memory untill SEGFAULT stops it, in other words
503
 * caveat emptor.
504
 *
505
 * It is worth mentioning that one of legitimate use-cases for that wrapper
506
 * is operation on opaque types with known offset for `struct list_node'
507
 * member(preferably 0), because it allows you not to disclose the type of
508
 * @i.
509
 *
510
 * Example:
511
 *	list_for_each_off(&parent->children, child,
512
 *				offsetof(struct child, list))
513
 *		printf("Name: %s\n", child->name);
514
 */
515
#define list_for_each_off(h, i, off)                                    \
516
	for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.next,	\
517
				   (off));				\
518
       list_node_from_off_((void *)i, (off)) != &(h)->n;                \
519
       i = list_node_to_off_(list_node_from_off_((void *)i, (off))->next, \
520
                             (off)))
521

  
522
/**
523
 * list_for_each_safe_off - iterate through a list of memory regions, maybe
524
 * during deletion
525
 * @h: the list_head
526
 * @i: the pointer to a memory region wich contains list node data.
527
 * @nxt: the structure containing the list_node
528
 * @off: offset(relative to @i) at which list node data resides.
529
 *
530
 * For details see `list_for_each_off' and `list_for_each_safe'
531
 * descriptions.
532
 *
533
 * Example:
534
 *	list_for_each_safe_off(&parent->children, child,
535
 *		next, offsetof(struct child, list))
536
 *		printf("Name: %s\n", child->name);
537
 */
538
#define list_for_each_safe_off(h, i, nxt, off)                          \
539
	for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.next,	\
540
				   (off)),				\
541
         nxt = list_node_to_off_(list_node_from_off_(i, (off))->next,   \
542
                                 (off));                                \
543
       list_node_from_off_(i, (off)) != &(h)->n;                        \
544
       i = nxt,                                                         \
545
         nxt = list_node_to_off_(list_node_from_off_(i, (off))->next,   \
546
                                 (off)))
547

  
548

  
549
/* Other -off variants. */
550
#define list_entry_off(n, type, off)		\
551
	((type *)list_node_from_off_((n), (off)))
552

  
553
#define list_head_off(h, type, off)		\
554
	((type *)list_head_off((h), (off)))
555

  
556
#define list_tail_off(h, type, off)		\
557
	((type *)list_tail_((h), (off)))
558

  
559
#define list_add_off(h, n, off)                 \
560
	list_add((h), list_node_from_off_((n), (off)))
561

  
562
#define list_del_off(n, off)                    \
563
	list_del(list_node_from_off_((n), (off)))
564

  
565
#define list_del_from_off(h, n, off)			\
566
	list_del_from(h, list_node_from_off_((n), (off)))
567

  
568
/* Offset helper functions so we only single-evaluate. */
569
static inline void *list_node_to_off_(struct list_node *node, size_t off)
570
{
571
	return (void *)((char *)node - off);
572
}
573
static inline struct list_node *list_node_from_off_(void *ptr, size_t off)
574
{
575
	return (struct list_node *)((char *)ptr + off);
576
}
577

  
578
/* Get the offset of the member, but make sure it's a list_node. */
579
#define list_off_(type, member)					\
580
	(container_off(type, member) +				\
581
	 check_type(((type *)0)->member, struct list_node))
582

  
583
#define list_off_var_(var, member)			\
584
	(container_off_var(var, member) +		\
585
	 check_type(var->member, struct list_node))
586

  
587
#if HAVE_TYPEOF
588
#define list_typeof(var) typeof(var)
589
#else
590
#define list_typeof(var) void *
591
#endif
592

  
593
/* Returns member, or NULL if at end of list. */
594
static inline void *list_entry_or_null(const struct list_head *h,
595
				       const struct list_node *n,
596
				       size_t off)
597
{
598
	if (n == &h->n)
599
		return NULL;
600
	return (char *)n - off;
601
}
602
#endif /* CCAN_LIST_H */
ccan/str/LICENSE
1
Statement of Purpose
2

  
3
The laws of most jurisdictions throughout the world automatically confer exclusive Copyright and Related Rights (defined below) upon the creator and subsequent owner(s) (each and all, an "owner") of an original work of authorship and/or a database (each, a "Work").
4

  
5
Certain owners wish to permanently relinquish those rights to a Work for the purpose of contributing to a commons of creative, cultural and scientific works ("Commons") that the public can reliably and without fear of later claims of infringement build upon, modify, incorporate in other works, reuse and redistribute as freely as possible in any form whatsoever and for any purposes, including without limitation commercial purposes. These owners may contribute to the Commons to promote the ideal of a free culture and the further production of creative, cultural and scientific works, or to gain reputation or greater distribution for their Work in part through the use and efforts of others.
6

  
7
For these and/or other purposes and motivations, and without any expectation of additional consideration or compensation, the person associating CC0 with a Work (the "Affirmer"), to the extent that he or she is an owner of Copyright and Related Rights in the Work, voluntarily elects to apply CC0 to the Work and publicly distribute the Work under its terms, with knowledge of his or her Copyright and Related Rights in the Work and the meaning and intended legal effect of CC0 on those rights.
8

  
9
1. Copyright and Related Rights. A Work made available under CC0 may be protected by copyright and related or neighboring rights ("Copyright and Related Rights"). Copyright and Related Rights include, but are not limited to, the following:
10

  
11
    the right to reproduce, adapt, distribute, perform, display, communicate, and translate a Work;
12
    moral rights retained by the original author(s) and/or performer(s);
13
    publicity and privacy rights pertaining to a person's image or likeness depicted in a Work;
14
    rights protecting against unfair competition in regards to a Work, subject to the limitations in paragraph 4(a), below;
15
    rights protecting the extraction, dissemination, use and reuse of data in a Work;
16
    database rights (such as those arising under Directive 96/9/EC of the European Parliament and of the Council of 11 March 1996 on the legal protection of databases, and under any national implementation thereof, including any amended or successor version of such directive); and
17
    other similar, equivalent or corresponding rights throughout the world based on applicable law or treaty, and any national implementations thereof.
18

  
19
2. Waiver. To the greatest extent permitted by, but not in contravention of, applicable law, Affirmer hereby overtly, fully, permanently, irrevocably and unconditionally waives, abandons, and surrenders all of Affirmer's Copyright and Related Rights and associated claims and causes of action, whether now known or unknown (including existing as well as future claims and causes of action), in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each member of the public at large and to the detriment of Affirmer's heirs and successors, fully intending that such Waiver shall not be subject to revocation, rescission, cancellation, termination, or any other legal or equitable action to disrupt the quiet enjoyment of the Work by the public as contemplated by Affirmer's express Statement of Purpose.
20

  
21
3. Public License Fallback. Should any part of the Waiver for any reason be judged legally invalid or ineffective under applicable law, then the Waiver shall be preserved to the maximum extent permitted taking into account Affirmer's express Statement of Purpose. In addition, to the extent the Waiver is so judged Affirmer hereby grants to each affected person a royalty-free, non transferable, non sublicensable, non exclusive, irrevocable and unconditional license to exercise Affirmer's Copyright and Related Rights in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "License"). The License shall be deemed effective as of the date CC0 was applied by Affirmer to the Work. Should any part of the License for any reason be judged legally invalid or ineffective under applicable law, such partial invalidity or ineffectiveness shall not invalidate the remainder of the License, and in such case Affirmer hereby affirms that he or she will not (i) exercise any of his or her remaining Copyright and Related Rights in the Work or (ii) assert any associated claims and causes of action with respect to the Work, in either case contrary to Affirmer's express Statement of Purpose.
22

  
23
4. Limitations and Disclaimers.
24

  
25
    No trademark or patent rights held by Affirmer are waived, abandoned, surrendered, licensed or otherwise affected by this document.
26
    Affirmer offers the Work as-is and makes no representations or warranties of any kind concerning the Work, express, implied, statutory or otherwise, including without limitation warranties of title, merchantability, fitness for a particular purpose, non infringement, or the absence of latent or other defects, accuracy, or the present or absence of errors, whether or not discoverable, all to the greatest extent permissible under applicable law.
27
    Affirmer disclaims responsibility for clearing rights of other persons that may apply to the Work or any use thereof, including without limitation any person's Copyright and Related Rights in the Work. Further, Affirmer disclaims responsibility for obtaining any necessary consents, permissions or other rights required for any use of the Work.
28
    Affirmer understands and acknowledges that Creative Commons is not a party to this document and has no duty or obligation with respect to this CC0 or use of the Work.
ccan/str/str.h
1
/* CC0 (Public domain) - see LICENSE file for details */
2
#ifndef CCAN_STR_H
3
#define CCAN_STR_H
4
/**
5
 * stringify - Turn expression into a string literal
6
 * @expr: any C expression
7
 *
8
 * Example:
9
 *	#define PRINT_COND_IF_FALSE(cond) \
10
 *		((cond) || printf("%s is false!", stringify(cond)))
11
 */
12
#define stringify(expr)		stringify_1(expr)
13
/* Double-indirection required to stringify expansions */
14
#define stringify_1(expr)	#expr
15

  
16
#endif /* CCAN_STR_H */
common.mk
603 603
	@exit > $@
604 604

  
605 605
###
606
CCAN_DIR = {$(VPATH)}ccan
607
CCAN_INCLUDES = $(CCAN_DIR)/build_assert/build_assert.h \
608
		$(CCAN_DIR)/check_type/check_type.h \
609
		$(CCAN_DIR)/container_of/container_of.h \
610
		$(CCAN_DIR)/list/list.h \
611
		$(CCAN_DIR)/str/str.h
606 612

  
607 613
RUBY_H_INCLUDES    = {$(VPATH)}ruby.h {$(VPATH)}config.h {$(VPATH)}defines.h \
608 614
		     {$(VPATH)}intern.h {$(VPATH)}missing.h {$(VPATH)}st.h \
......
611 617
PROBES_H_INCLUDES  = {$(VPATH)}probes.h
612 618
VM_CORE_H_INCLUDES = {$(VPATH)}vm_core.h {$(VPATH)}thread_$(THREAD_MODEL).h \
613 619
		     {$(VPATH)}node.h {$(VPATH)}method.h {$(VPATH)}ruby_atomic.h \
614
	             {$(VPATH)}vm_debug.h {$(VPATH)}id.h {$(VPATH)}thread_native.h
620
	             {$(VPATH)}vm_debug.h {$(VPATH)}id.h {$(VPATH)}thread_native.h \
621
	             $(CCAN_INCLUDES)
615 622

  
616 623
###
617 624

  
thread.c
368 368
}
369 369

  
370 370
static int
371
terminate_i(st_data_t key, st_data_t val, rb_thread_t *main_thread)
371
terminate_i(rb_thread_t *th, void *main_thread)
372 372
{
373
    VALUE thval = key;
374
    rb_thread_t *th;
375
    GetThreadPtr(thval, th);
376

  
377 373
    if (th != main_thread) {
378 374
	thread_debug("terminate_i: %p\n", (void *)th);
379 375
	rb_threadptr_pending_interrupt_enque(th, eTerminateSignal);
......
433 429

  
434 430
  retry:
435 431
    thread_debug("rb_thread_terminate_all (main thread: %p)\n", (void *)th);
436
    st_foreach(vm->living_threads, terminate_i, (st_data_t)th);
432
    rb_vm_living_threads_foreach(vm, terminate_i, th);
437 433

  
438 434
    while (!rb_thread_alone()) {
439 435
	int state;
......
582 578
	}
583 579

  
584 580
	/* delete self other than main thread from living_threads */
585
	st_delete_wrap(th->vm->living_threads, th->self);
581
	rb_vm_living_threads_remove(th->vm, th);
586 582
	if (rb_thread_alone()) {
587 583
	    /* I'm last thread. wake up main thread from rb_thread_terminate_all */
588 584
	    rb_threadptr_interrupt(main_th);
......
654 650
	th->status = THREAD_KILLED;
655 651
	rb_raise(rb_eThreadError, "can't create Thread: %s", strerror(err));
656 652
    }
657
    st_insert(th->vm->living_threads, thval, (st_data_t) th->thread_id);
653
    rb_vm_living_threads_insert(th->vm, th);
658 654
    return thval;
659 655
}
660 656

  
......
2064 2060
}
2065 2061

  
2066 2062
static int
2067
thread_fd_close_i(st_data_t key, st_data_t val, st_data_t data)
2063
thread_fd_close_i(rb_thread_t *th, void *fdp)
2068 2064
{
2069
    int fd = (int)data;
2070
    rb_thread_t *th;
2071
    GetThreadPtr((VALUE)key, th);
2072

  
2073
    if (th->waiting_fd == fd) {
2065
    int *fd = fdp;
2066
    if (th->waiting_fd == *fd) {
2074 2067
	VALUE err = th->vm->special_exceptions[ruby_error_closed_stream];
2075 2068
	rb_threadptr_pending_interrupt_enque(th, err);
2076 2069
	rb_threadptr_interrupt(th);
......
2081 2074
void
2082 2075
rb_thread_fd_close(int fd)
2083 2076
{
2084
    st_foreach(GET_THREAD()->vm->living_threads, thread_fd_close_i, (st_index_t)fd);
2077
    rb_vm_living_threads_foreach(GET_THREAD()->vm, thread_fd_close_i, &fd);
2085 2078
}
2086 2079

  
2087 2080
/*
......
2301 2294
}
2302 2295

  
2303 2296
static int
2304
thread_list_i(st_data_t key, st_data_t val, void *data)
2297
thread_list_i(rb_thread_t *th, void *data)
2305 2298
{
2306 2299
    VALUE ary = (VALUE)data;
2307
    rb_thread_t *th;
2308
    GetThreadPtr((VALUE)key, th);
2309 2300

  
2310 2301
    switch (th->status) {
2311 2302
      case THREAD_RUNNABLE:
......
2344 2335
rb_thread_list(void)
2345 2336
{
2346 2337
    VALUE ary = rb_ary_new();
2347
    st_foreach(GET_THREAD()->vm->living_threads, thread_list_i, ary);
2338
    rb_vm_living_threads_foreach(GET_THREAD()->vm, thread_list_i, (void *)ary);
2348 2339
    return ary;
2349 2340
}
2350 2341

  
......
2922 2913
static int
2923 2914
vm_living_thread_num(rb_vm_t *vm)
2924 2915
{
2925
    return (int)vm->living_threads->num_entries;
2916
    return (int)vm->living_thread_num;
2926 2917
}
2927 2918

  
2928 2919
int
2929 2920
rb_thread_alone(void)
2930 2921
{
2931 2922
    int num = 1;
2932
    if (GET_THREAD()->vm->living_threads) {
2923
    if (!list_empty(&GET_THREAD()->vm->living_threads)) {
2933 2924
	num = vm_living_thread_num(GET_THREAD()->vm);
2934 2925
	thread_debug("rb_thread_alone: %d\n", num);
2935 2926
    }
......
3764 3755
}
3765 3756

  
3766 3757
static void
3767
rb_thread_atfork_internal(int (*atfork)(st_data_t, st_data_t, st_data_t))
3758
rb_thread_atfork_internal(int (*atfork)(rb_thread_t *, void *))
3768 3759
{
3769 3760
    rb_thread_t *th = GET_THREAD();
3770 3761
    rb_vm_t *vm = th->vm;
3771
    VALUE thval = th->self;
3772 3762
    vm->main_thread = th;
3773 3763

  
3774 3764
    gvl_atfork(th->vm);
3775
    st_foreach(vm->living_threads, atfork, (st_data_t)th);
3776
    st_clear(vm->living_threads);
3777
    st_insert(vm->living_threads, thval, (st_data_t)th->thread_id);
3765
    rb_vm_living_threads_foreach(vm, atfork, th);
3766
    rb_vm_living_threads_init(vm);
3767
    rb_vm_living_threads_insert(vm, th);
3778 3768
    vm->sleeper = 0;
3779 3769
    clear_coverage();
3780 3770
}
3781 3771

  
3782 3772
static int
3783
terminate_atfork_i(st_data_t key, st_data_t val, st_data_t current_th)
3773
terminate_atfork_i(rb_thread_t *th, void *current_th)
3784 3774
{
3785
    VALUE thval = key;
3786
    rb_thread_t *th;
3787
    GetThreadPtr(thval, th);
3788

  
3789 3775
    if (th != (rb_thread_t *)current_th) {
3790 3776
	rb_mutex_abandon_keeping_mutexes(th);
3791 3777
	rb_mutex_abandon_locking_mutex(th);
......
3805 3791
}
3806 3792

  
3807 3793
static int
3808
terminate_atfork_before_exec_i(st_data_t key, st_data_t val, st_data_t current_th)
3794
terminate_atfork_before_exec_i(rb_thread_t *th, void *current_th)
3809 3795
{
3810
    VALUE thval = key;
3811
    rb_thread_t *th;
3812
    GetThreadPtr(thval, th);
3813

  
3814 3796
    if (th != (rb_thread_t *)current_th) {
3815 3797
	thread_cleanup_func_before_exec(th);
3816 3798
    }
......
3878 3860
};
3879 3861

  
3880 3862
static int
3881
thgroup_list_i(st_data_t key, st_data_t val, st_data_t data)
3863
thgroup_list_i(rb_thread_t *th, void *arg)
3882 3864
{
3883
    VALUE thread = (VALUE)key;
3884
    VALUE ary = ((struct thgroup_list_params *)data)->ary;
3885
    VALUE group = ((struct thgroup_list_params *)data)->group;
3886
    rb_thread_t *th;
3887
    GetThreadPtr(thread, th);
3865
    struct thgroup_list_params *params = arg;
3866
    VALUE thread = th->self;
3867
    VALUE ary = params->ary;
3868
    VALUE group = params->group;
3888 3869

  
3889 3870
    if (th->thgroup == group) {
3890 3871
	rb_ary_push(ary, thread);
......
3909 3890

  
3910 3891
    param.ary = ary;
3911 3892
    param.group = group;
3912
    st_foreach(GET_THREAD()->vm->living_threads, thgroup_list_i, (st_data_t) & param);
3893
    rb_vm_living_threads_foreach(GET_THREAD()->vm, thgroup_list_i, &param);
3913 3894
    return ary;
3914 3895
}
3915 3896

  
......
5048 5029
}
5049 5030

  
5050 5031
static int
5051
check_deadlock_i(st_data_t key, st_data_t val, int *found)
5032
check_deadlock_i(rb_thread_t *th, void *arg)
5052 5033
{
5053
    VALUE thval = key;
5054
    rb_thread_t *th;
5055
    GetThreadPtr(thval, th);
5056

  
5034
    int *found = arg;
5057 5035
    if (th->status != THREAD_STOPPED_FOREVER || RUBY_VM_INTERRUPTED(th)) {
5058 5036
	*found = 1;
5059 5037
    }
......
5073 5051

  
5074 5052
#ifdef DEBUG_DEADLOCK_CHECK
5075 5053
static int
5076
debug_i(st_data_t key, st_data_t val, int *found)
5054
debug_i(rb_thread_t *th, int *found)
5077 5055
{
5078
    VALUE thval = key;
5079
    rb_thread_t *th;
5080
    GetThreadPtr(thval, th);
5081

  
5082 5056
    printf("th:%p %d %d", th, th->status, th->interrupt_flag);
5083 5057
    if (th->locking_mutex) {
5084 5058
	rb_mutex_t *mutex;
......
5104 5078
    if (vm_living_thread_num(vm) < vm->sleeper) rb_bug("sleeper must not be more than vm_living_thread_num(vm)");
5105 5079
    if (patrol_thread && patrol_thread != GET_THREAD()) return;
5106 5080

  
5107
    st_foreach(vm->living_threads, check_deadlock_i, (st_data_t)&found);
5081
    rb_vm_living_threads_foreach(vm, check_deadlock_i, &found);
5108 5082

  
5109 5083
    if (!found) {
5110 5084
	VALUE argv[2];
5111 5085
	argv[0] = rb_eFatal;
5112 5086
	argv[1] = rb_str_new2("No live threads left. Deadlock?");
5113 5087
#ifdef DEBUG_DEADLOCK_CHECK
5114
	printf("%d %d %p %p\n", vm->living_threads->num_entries, vm->sleeper, GET_THREAD(), vm->main_thread);
5115
	st_foreach(vm->living_threads, debug_i, (st_data_t)0);
5088
	printf("%d %d %p %p\n", vm_living_thread_num(vm), vm->sleeper, GET_THREAD(), vm->main_thread);
5089
	rb_vm_living_threads_foreach(vm, debug_i, 0);
5116 5090
#endif
5117 5091
	vm->sleeper--;
5118 5092
	rb_threadptr_raise(vm->main_thread, 2, argv);
vm.c
1672 1672
/* vm */
1673 1673

  
1674 1674
static int
1675
vm_mark_each_thread_func(st_data_t key, st_data_t value, st_data_t dummy)
1675
vm_mark_each_thread_func(rb_thread_t *th, void *dummy)
1676 1676
{
1677
    VALUE thval = (VALUE)key;
1678
    rb_gc_mark(thval);
1677
    rb_gc_mark(th->self);
1679 1678
    return ST_CONTINUE;
1680 1679
}
1681 1680

  
......
1690 1689
    RUBY_GC_INFO("-------------------------------------------------\n");
1691 1690
    if (ptr) {
1692 1691
	rb_vm_t *vm = ptr;
1693
	if (vm->living_threads) {
1694
	    st_foreach(vm->living_threads, vm_mark_each_thread_func, 0);
1695
	}
1692
	rb_vm_living_threads_foreach(vm, vm_mark_each_thread_func, 0);
1696 1693
	RUBY_MARK_UNLESS_NULL(vm->thgroup_default);
1697 1694
	RUBY_MARK_UNLESS_NULL(vm->mark_object_ary);
1698 1695
	RUBY_MARK_UNLESS_NULL(vm->load_path);
......
1752 1749
	    rb_fiber_reset_root_local_storage(th->self);
1753 1750
	    thread_free(th);
1754 1751
	}
1755
	if (vm->living_threads) {
1756
	    st_free_table(vm->living_threads);
1757
	    vm->living_threads = 0;
1758
	}
1752
	rb_vm_living_threads_init(vm);
1759 1753
	ruby_vm_run_at_exit_hooks(vm);
1760 1754
	rb_vm_gvl_destroy(vm);
1761 1755
#if defined(ENABLE_VM_OBJSPACE) && ENABLE_VM_OBJSPACE
......
1777 1771
    if (ptr) {
1778 1772
	const rb_vm_t *vmobj = ptr;
1779 1773
	size_t size = sizeof(rb_vm_t);
1780
	if (vmobj->living_threads) {
1781
	    size += st_memsize(vmobj->living_threads);
1782
	}
1774

  
1775
	size += vmobj->living_thread_num * sizeof(rb_thread_t);
1776

  
1783 1777
	if (vmobj->defined_strings) {
1784 1778
	    size += DEFINED_EXPR * sizeof(VALUE);
1785 1779
	}
......
1879 1873
vm_init2(rb_vm_t *vm)
1880 1874
{
1881 1875
    MEMZERO(vm, rb_vm_t, 1);
1876
    rb_vm_living_threads_init(vm);
1882 1877
    vm->src_encoding_index = -1;
1883 1878
    vm->at_exit.basic.flags = (T_ARRAY | RARRAY_EMBED_FLAG) & ~RARRAY_EMBED_LEN_MASK; /* len set 0 */
1884 1879
    rb_obj_hide((VALUE)&vm->at_exit);
......
2651 2646
	th->top_self = rb_vm_top_self();
2652 2647
	rb_thread_set_current(th);
2653 2648

  
2654
	vm->living_threads = st_init_numtable();
2655
	st_insert(vm->living_threads, th_self, (st_data_t) th->thread_id);
2649
	rb_vm_living_threads_insert(vm, th);
2656 2650

  
2657 2651
	rb_gc_register_mark_object(iseqval);
2658 2652
	GetISeqPtr(iseqval, iseq);
......
2980 2974
}
2981 2975
#endif
2982 2976

  
2977
void
2978
rb_vm_living_threads_foreach(rb_vm_t *vm,
2979
			    int (*fn)(rb_thread_t *, void*), void *arg)
2980
{
2981
    rb_thread_t *cur, *next;
2982
    list_for_each_safe(&vm->living_threads, cur, next, vmlt_node) {
2983
	int rc = fn(cur, arg);
2984
	switch (rc) {
2985
	  case ST_CHECK:
2986
	  case ST_CONTINUE: break;
2987
	  case ST_STOP: return;
2988
	  case ST_DELETE: /* untested */
2989
	    rb_vm_living_threads_remove(vm, cur);
2990
	    xfree(cur);
2991
	    break;
2992
	  default:
2993
	    rb_bug("rb_vm_living_threads_foreach: unexpected: %d", rc);
2994
	}
2995
    }
2996
}
vm_core.h
23 23
#include "id.h"
24 24
#include "method.h"
25 25
#include "ruby_atomic.h"
26

  
27 26
#include "thread_native.h"
27
#include "ccan/list/list.h"
28 28

  
29 29
#ifndef ENABLE_VM_OBJSPACE
30 30
#ifdef _WIN32
......
333 333
    struct rb_thread_struct *main_thread;
334 334
    struct rb_thread_struct *running_thread;
335 335

  
336
    st_table *living_threads;
336
    struct list_head living_threads;
337
    size_t living_thread_num;
337 338
    VALUE thgroup_default;
338 339

  
339 340
    int running;
......
500 501
    struct rb_ensure_entry entry;
501 502
} rb_ensure_list_t;
502 503

  
504
struct rb_thread_struct;
503 505
typedef struct rb_thread_struct {
506
    struct list_node vmlt_node;
504 507
    VALUE self;
505 508
    rb_vm_t *vm;
506 509

  
......
854 857
void rb_thread_reset_timer_thread(void);
855 858
void rb_thread_wakeup_timer_thread(void);
856 859

  
860
static inline void
861
rb_vm_living_threads_init(rb_vm_t *vm)
862
{
863
    list_head_init(&vm->living_threads);
864
    vm->living_thread_num = 0;
865
}
866

  
867
static inline void
868
rb_vm_living_threads_insert(rb_vm_t *vm, rb_thread_t *th)
869
{
870
    list_add(&vm->living_threads, &th->vmlt_node);
871
    vm->living_thread_num++;
872
}
873

  
874
static inline void
875
rb_vm_living_threads_remove(rb_vm_t *vm, rb_thread_t *th)
876
{
877
    list_del(&th->vmlt_node);
878
    vm->living_thread_num--;
879
}
880

  
881
void rb_vm_living_threads_foreach(rb_vm_t*, int (*)(rb_thread_t*, void*), void*);
857 882
int ruby_thread_has_gvl_p(void);
858 883
typedef int rb_backtrace_iter_func(void *, VALUE, int, VALUE);
859 884
rb_control_frame_t *rb_vm_get_ruby_level_next_cfp(rb_thread_t *th, const rb_control_frame_t *cfp);
vm_trace.c
213 213
}
... This diff was truncated because it exceeds the maximum size that can be displayed.