JDK8源码阅读Striped64
- Striped64是一个抽象类
- Striped64是jdk1.8提供的用于支持DoubleAdder、LongAdder、DoubleAccumulator、LongAccumulator这样机制的基础类。
- Striped64的设计核心思路就是通过内部的分散计算来避免竞争(比如多线程CAS操作时的竞争)。
- Striped64内部包含一个基础值和一个单元哈希表。没有竞争的情况下，要累加的数会累加到这个基础值上；
- 如果有竞争的话，会将要累加的数累加到单元哈希表中的某个单元里面。所以整个Striped64的值包括基础值和单元哈希表中所有单元的值的总和。
域及静态块
java
// CPU数量
static final int NCPU = Runtime.getRuntime().availableProcessors();
// 存放Cell的hash表，大小为2的幂。
transient volatile Cell[] cells;
// 基础值，没有竞争时会使用(更新)这个值，同时做为初始化竞争失败的回退方案。
transient volatile long base;
// 自旋锁，通过CAS操作加锁，用于保护创建或者扩展Cell表。
transient volatile int cellsBusy;
// Unsafe实例
private static final sun.misc.Unsafe UNSAFE;
// 基础值偏移量
private static final long BASE;
// 自旋锁偏移量
private static final long CELLSBUSY;
// Thread中threadLocalRandomProbe的偏移量
private static final long PROBE;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> sk = Striped64.class;
BASE = UNSAFE.objectFieldOffset
(sk.getDeclaredField("base"));
CELLSBUSY = UNSAFE.objectFieldOffset
(sk.getDeclaredField("cellsBusy"));
Class<?> tk = Thread.class;
PROBE = UNSAFE.objectFieldOffset
(tk.getDeclaredField("threadLocalRandomProbe"));
} catch (Exception e) {
throw new Error(e);
}
}// CPU数量
static final int NCPU = Runtime.getRuntime().availableProcessors();
// 存放Cell的hash表，大小为2的幂。
transient volatile Cell[] cells;
// 基础值，没有竞争时会使用(更新)这个值，同时做为初始化竞争失败的回退方案。
transient volatile long base;
// 自旋锁，通过CAS操作加锁，用于保护创建或者扩展Cell表。
transient volatile int cellsBusy;
// Unsafe实例
private static final sun.misc.Unsafe UNSAFE;
// 基础值偏移量
private static final long BASE;
// 自旋锁偏移量
private static final long CELLSBUSY;
// Thread中threadLocalRandomProbe的偏移量
private static final long PROBE;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> sk = Striped64.class;
BASE = UNSAFE.objectFieldOffset
(sk.getDeclaredField("base"));
CELLSBUSY = UNSAFE.objectFieldOffset
(sk.getDeclaredField("cellsBusy"));
Class<?> tk = Thread.class;
PROBE = UNSAFE.objectFieldOffset
(tk.getDeclaredField("threadLocalRandomProbe"));
} catch (Exception e) {
throw new Error(e);
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
静态内部类
java
@sun.misc.Contended
static final class Cell {
volatile long value;
Cell(long x) { value = x; }
// value的原子cas操作
final boolean cas(long cmp, long val) {
return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
}
// Unsafe mechanics
private static final sun.misc.Unsafe UNSAFE;
// value的偏移量
private static final long valueOffset;
// 静态块初始化
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> ak = Cell.class;
valueOffset = UNSAFE.objectFieldOffset
(ak.getDeclaredField("value"));
} catch (Exception e) {
throw new Error(e);
}
}
}@sun.misc.Contended
static final class Cell {
volatile long value;
Cell(long x) { value = x; }
// value的原子cas操作
final boolean cas(long cmp, long val) {
return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
}
// Unsafe mechanics
private static final sun.misc.Unsafe UNSAFE;
// value的偏移量
private static final long valueOffset;
// 静态块初始化
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> ak = Cell.class;
valueOffset = UNSAFE.objectFieldOffset
(ak.getDeclaredField("value"));
} catch (Exception e) {
throw new Error(e);
}
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
方法
boolean casBase(long cmp, long val)
java
// cas基础值
final boolean casBase(long cmp, long val) {
return UNSAFE.compareAndSwapLong(this, BASE, cmp, val);
}// cas基础值
final boolean casBase(long cmp, long val) {
return UNSAFE.compareAndSwapLong(this, BASE, cmp, val);
}1
2
3
4
2
3
4
boolean casCellsBusy()
java
// cas自旋锁
// cellsBusy从0->1获得锁
// 从1->0释放锁
final boolean casCellsBusy() {
return UNSAFE.compareAndSwapInt(this, CELLSBUSY, 0, 1);
}// cas自旋锁
// cellsBusy从0->1获得锁
// 从1->0释放锁
final boolean casCellsBusy() {
return UNSAFE.compareAndSwapInt(this, CELLSBUSY, 0, 1);
}1
2
3
4
5
6
2
3
4
5
6
int getProbe()
java
// 获得当前线程threadLocalRandomProbe的值
static final int getProbe() {
return UNSAFE.getInt(Thread.currentThread(), PROBE);
}// 获得当前线程threadLocalRandomProbe的值
static final int getProbe() {
return UNSAFE.getInt(Thread.currentThread(), PROBE);
}1
2
3
4
2
3
4
int advanceProbe(int probe)
java
// threadLocalRandomProbe根据xorshift算法赋值
static final int advanceProbe(int probe) {
probe ^= probe << 13; // xorshift
probe ^= probe >>> 17;
probe ^= probe << 5;
UNSAFE.putInt(Thread.currentThread(), PROBE, probe);
return probe;
}// threadLocalRandomProbe根据xorshift算法赋值
static final int advanceProbe(int probe) {
probe ^= probe << 13; // xorshift
probe ^= probe >>> 17;
probe ^= probe << 5;
UNSAFE.putInt(Thread.currentThread(), PROBE, probe);
return probe;
}1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
void longAccumulate(long x, LongBinaryOperator fn, boolean wasUncontended)
java
// long累加核心方法
final void longAccumulate(long x, LongBinaryOperator fn,
boolean wasUncontended) {
int h;
// 获取当前线程的probe值作为hash值
if ((h = getProbe()) == 0) {
// 如果hash值为0强制初始化当前线程的hash值
ThreadLocalRandom.current(); // force initialization
// 获得计算的hash值
h = getProbe();
// 设置为竞非争标识为true
wasUncontended = true;
}
// True if last slot nonempty
// 索引位置的Cell是否hash碰撞
boolean collide = false;
for (;;) {
// 当前hash表的快照
Cell[] as;
// 存(n-1) & h索引的Cell
Cell a;
// hash表长度
int n;
// 当前base快照
long v;
// hash表不为null且长度大于0
if ((as = cells) != null && (n = as.length) > 0) {
// 根据hash值取得一个Cell
if ((a = as[(n - 1) & h]) == null) {
// 双重判断hash表是否在使用
if (cellsBusy == 0) { // Try to attach new Cell
Cell r = new Cell(x); // Optimistically create
// 再次判断并获得锁
if (cellsBusy == 0 && casCellsBusy()) {
// 是否计算成功
boolean created = false;
try { // Recheck under lock
Cell[] rs; int m, j;
if ((rs = cells) != null && // hash表非空
// hash表长度大于0
(m = rs.length) > 0 &&
// hash表索引位置为null
rs[j = (m - 1) & h] == null) {
rs[j] = r; // 设置新建的Cell到该位置
created = true; // 创建成功
}
} finally {
cellsBusy = 0; // 释放锁
}
if (created)
// 创建成功 方法结束
break;
// 没创建成功 说明该位置已经被其他线程创建的Cell占用
// 继续尝试
continue; // Slot is now non-empty
}
}
// 没获取到cellsBusy锁
collide = false;
}
/**
* 以下条件说明通过hash表索引(n - 1) & h位置已经存在一个Cell且非空
* a = as[(n - 1) & h] 即a
*/
// 说明cas失败 为竞争状态
// 如果非竞争为false 设置为true
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
// 尝试将x的值计算到cell的value上 成功则方法结束
else if (a.cas(v = a.value, ((fn == null) ? v + x :
fn.applyAsLong(v, x))))
break;
// 如果hash表长度已到最大即CPU数量
// 或者hash表已经发生变化(as是hash表的一个快照)
// 设置冲突为false
else if (n >= NCPU || cells != as)
collide = false; // At max size or stale
// 如果为非冲突 设置冲突标识
else if (!collide)
collide = true;
// 尝试获取cellsBusy锁
else if (cellsBusy == 0 && casCellsBusy()) {
try {
// 如果hash表快照未过时
if (cells == as) { // Expand table unless stale
// 将hash表扩容1倍
Cell[] rs = new Cell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
cells = rs;
}
} finally {
// 释放锁
cellsBusy = 0;
}
// 设置冲突标识为false并重试
collide = false;
continue; // Retry with expanded table
}
// rehash
h = advanceProbe(h);
}
/**
* 以下条件说明hash表未初始化
*/
// 尝试获得cellsBusy锁
else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
// 初始化成功标识
boolean init = false;
try { // Initialize table
if (cells == as) {
// 初始化hash表长度为2
Cell[] rs = new Cell[2];
// 并将h & 1位置设置的Cell
rs[h & 1] = new Cell(x);
cells = rs;
init = true;
}
} finally {
// 释放锁
cellsBusy = 0;
}
// 如果初始化成功 方法结束
if (init)
break;
}
// 如果尝试初始化hash表失败
// 尝试将x计算到base上
else if (casBase(v = base, ((fn == null) ? v + x :
fn.applyAsLong(v, x))))
// 计算成功 方法结束
break; // Fall back on using base
}
}// long累加核心方法
final void longAccumulate(long x, LongBinaryOperator fn,
boolean wasUncontended) {
int h;
// 获取当前线程的probe值作为hash值
if ((h = getProbe()) == 0) {
// 如果hash值为0强制初始化当前线程的hash值
ThreadLocalRandom.current(); // force initialization
// 获得计算的hash值
h = getProbe();
// 设置为竞非争标识为true
wasUncontended = true;
}
// True if last slot nonempty
// 索引位置的Cell是否hash碰撞
boolean collide = false;
for (;;) {
// 当前hash表的快照
Cell[] as;
// 存(n-1) & h索引的Cell
Cell a;
// hash表长度
int n;
// 当前base快照
long v;
// hash表不为null且长度大于0
if ((as = cells) != null && (n = as.length) > 0) {
// 根据hash值取得一个Cell
if ((a = as[(n - 1) & h]) == null) {
// 双重判断hash表是否在使用
if (cellsBusy == 0) { // Try to attach new Cell
Cell r = new Cell(x); // Optimistically create
// 再次判断并获得锁
if (cellsBusy == 0 && casCellsBusy()) {
// 是否计算成功
boolean created = false;
try { // Recheck under lock
Cell[] rs; int m, j;
if ((rs = cells) != null && // hash表非空
// hash表长度大于0
(m = rs.length) > 0 &&
// hash表索引位置为null
rs[j = (m - 1) & h] == null) {
rs[j] = r; // 设置新建的Cell到该位置
created = true; // 创建成功
}
} finally {
cellsBusy = 0; // 释放锁
}
if (created)
// 创建成功 方法结束
break;
// 没创建成功 说明该位置已经被其他线程创建的Cell占用
// 继续尝试
continue; // Slot is now non-empty
}
}
// 没获取到cellsBusy锁
collide = false;
}
/**
* 以下条件说明通过hash表索引(n - 1) & h位置已经存在一个Cell且非空
* a = as[(n - 1) & h] 即a
*/
// 说明cas失败 为竞争状态
// 如果非竞争为false 设置为true
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
// 尝试将x的值计算到cell的value上 成功则方法结束
else if (a.cas(v = a.value, ((fn == null) ? v + x :
fn.applyAsLong(v, x))))
break;
// 如果hash表长度已到最大即CPU数量
// 或者hash表已经发生变化(as是hash表的一个快照)
// 设置冲突为false
else if (n >= NCPU || cells != as)
collide = false; // At max size or stale
// 如果为非冲突 设置冲突标识
else if (!collide)
collide = true;
// 尝试获取cellsBusy锁
else if (cellsBusy == 0 && casCellsBusy()) {
try {
// 如果hash表快照未过时
if (cells == as) { // Expand table unless stale
// 将hash表扩容1倍
Cell[] rs = new Cell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
cells = rs;
}
} finally {
// 释放锁
cellsBusy = 0;
}
// 设置冲突标识为false并重试
collide = false;
continue; // Retry with expanded table
}
// rehash
h = advanceProbe(h);
}
/**
* 以下条件说明hash表未初始化
*/
// 尝试获得cellsBusy锁
else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
// 初始化成功标识
boolean init = false;
try { // Initialize table
if (cells == as) {
// 初始化hash表长度为2
Cell[] rs = new Cell[2];
// 并将h & 1位置设置的Cell
rs[h & 1] = new Cell(x);
cells = rs;
init = true;
}
} finally {
// 释放锁
cellsBusy = 0;
}
// 如果初始化成功 方法结束
if (init)
break;
}
// 如果尝试初始化hash表失败
// 尝试将x计算到base上
else if (casBase(v = base, ((fn == null) ? v + x :
fn.applyAsLong(v, x))))
// 计算成功 方法结束
break; // Fall back on using base
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
void doubleAccumulate(double x, DoubleBinaryOperator fn, boolean wasUncontended)
java
// double累加核心方法
final void doubleAccumulate(double x, DoubleBinaryOperator fn,
boolean wasUncontended) {
int h;
// 获取当前线程的probe值作为hash值
if ((h = getProbe()) == 0) {
// 如果hash值为0强制初始化当前线程的hash值
ThreadLocalRandom.current(); // force initialization
// 获得计算的hash值
h = getProbe();
// 设置为竞非争标识为true
wasUncontended = true;
}
// True if last slot nonempty
// 索引位置的Cell是否hash碰撞
boolean collide = false; // True if last slot nonempty
for (;;) {
Cell[] as; Cell a; int n; long v;
// hash表已经初始化
if ((as = cells) != null && (n = as.length) > 0) {
// hash表(n - 1) & h位置的Cell为null
if ((a = as[(n - 1) & h]) == null) {
// 锁可以获取
if (cellsBusy == 0) { // Try to attach new Cell
// 以x初始化一个Cell
Cell r = new Cell(Double.doubleToRawLongBits(x));
// 尝试获得锁
if (cellsBusy == 0 && casCellsBusy()) {
// 是否创建成功
boolean created = false;
try { // Recheck under lock
Cell[] rs; int m, j;
if ((rs = cells) != null && // hash表最新快照非空
// hash表最新快照长度大于0
(m = rs.length) > 0 &&
// hash表快照(m - 1) & h索引Cell为null
rs[j = (m - 1) & h] == null) {
rs[j] = r; // 设置该索引Cell为r
created = true; // 设置创建成功标识
}
} finally {
// 释放锁
cellsBusy = 0;
}
if (created) // 创建成功 方法结束
break;
// 没创建成功 说明该位置已经被其他线程创建的Cell占用
// 继续尝试
continue; // Slot is now non-empty
}
}
// 设置碰撞标识为false
collide = false;
}
/**
* 以下条件表示hash表(n - 1) & h位置的Cell为非null
*/
// 说明cas失败 为竞争状态
// 如果非竞争为false 设置为true
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
// 尝试将x计算到a的value上
else if (a.cas(v = a.value,
((fn == null) ?
Double.doubleToRawLongBits
(Double.longBitsToDouble(v) + x) :
Double.doubleToRawLongBits
(fn.applyAsDouble
(Double.longBitsToDouble(v), x)))))
// 计算成功 方法结束
break;
// 如果hash表满了或者hash表快照已过时
else if (n >= NCPU || cells != as)
// 设置hash碰撞标识
collide = false; // At max size or stale
// 如果为非冲突 设置冲突标识
else if (!collide)
collide = true;
// 尝试获得锁
else if (cellsBusy == 0 && casCellsBusy()) {
try {
// 如果快照为过时 对hash表进行扩容
// 容量增加1倍
if (cells == as) { // Expand table unless stale
Cell[] rs = new Cell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
cells = rs;
}
} finally {
// 释放锁
cellsBusy = 0;
}
// 设置碰撞标识为false
collide = false;
// 继续尝试计算
continue; // Retry with expanded table
}
// rehash
h = advanceProbe(h);
}
// 尝试获得锁
else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
boolean init = false;
try { // Initialize table
if (cells == as) { // 如果快照未过期
// 初始化hash表
Cell[] rs = new Cell[2];
rs[h & 1] = new Cell(Double.doubleToRawLongBits(x));
cells = rs;
init = true;
}
} finally {
// 释放锁
cellsBusy = 0;
}
if (init) // 初始化成功 方法结束
break;
}
// 初始化hash表失败 尝试将x计算到base上
else if (casBase(v = base,
((fn == null) ?
Double.doubleToRawLongBits
(Double.longBitsToDouble(v) + x) :
Double.doubleToRawLongBits
(fn.applyAsDouble
(Double.longBitsToDouble(v), x)))))
// 计算成功 方法结束
break; // Fall back on using base
}
}// double累加核心方法
final void doubleAccumulate(double x, DoubleBinaryOperator fn,
boolean wasUncontended) {
int h;
// 获取当前线程的probe值作为hash值
if ((h = getProbe()) == 0) {
// 如果hash值为0强制初始化当前线程的hash值
ThreadLocalRandom.current(); // force initialization
// 获得计算的hash值
h = getProbe();
// 设置为竞非争标识为true
wasUncontended = true;
}
// True if last slot nonempty
// 索引位置的Cell是否hash碰撞
boolean collide = false; // True if last slot nonempty
for (;;) {
Cell[] as; Cell a; int n; long v;
// hash表已经初始化
if ((as = cells) != null && (n = as.length) > 0) {
// hash表(n - 1) & h位置的Cell为null
if ((a = as[(n - 1) & h]) == null) {
// 锁可以获取
if (cellsBusy == 0) { // Try to attach new Cell
// 以x初始化一个Cell
Cell r = new Cell(Double.doubleToRawLongBits(x));
// 尝试获得锁
if (cellsBusy == 0 && casCellsBusy()) {
// 是否创建成功
boolean created = false;
try { // Recheck under lock
Cell[] rs; int m, j;
if ((rs = cells) != null && // hash表最新快照非空
// hash表最新快照长度大于0
(m = rs.length) > 0 &&
// hash表快照(m - 1) & h索引Cell为null
rs[j = (m - 1) & h] == null) {
rs[j] = r; // 设置该索引Cell为r
created = true; // 设置创建成功标识
}
} finally {
// 释放锁
cellsBusy = 0;
}
if (created) // 创建成功 方法结束
break;
// 没创建成功 说明该位置已经被其他线程创建的Cell占用
// 继续尝试
continue; // Slot is now non-empty
}
}
// 设置碰撞标识为false
collide = false;
}
/**
* 以下条件表示hash表(n - 1) & h位置的Cell为非null
*/
// 说明cas失败 为竞争状态
// 如果非竞争为false 设置为true
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
// 尝试将x计算到a的value上
else if (a.cas(v = a.value,
((fn == null) ?
Double.doubleToRawLongBits
(Double.longBitsToDouble(v) + x) :
Double.doubleToRawLongBits
(fn.applyAsDouble
(Double.longBitsToDouble(v), x)))))
// 计算成功 方法结束
break;
// 如果hash表满了或者hash表快照已过时
else if (n >= NCPU || cells != as)
// 设置hash碰撞标识
collide = false; // At max size or stale
// 如果为非冲突 设置冲突标识
else if (!collide)
collide = true;
// 尝试获得锁
else if (cellsBusy == 0 && casCellsBusy()) {
try {
// 如果快照为过时 对hash表进行扩容
// 容量增加1倍
if (cells == as) { // Expand table unless stale
Cell[] rs = new Cell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
cells = rs;
}
} finally {
// 释放锁
cellsBusy = 0;
}
// 设置碰撞标识为false
collide = false;
// 继续尝试计算
continue; // Retry with expanded table
}
// rehash
h = advanceProbe(h);
}
// 尝试获得锁
else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
boolean init = false;
try { // Initialize table
if (cells == as) { // 如果快照未过期
// 初始化hash表
Cell[] rs = new Cell[2];
rs[h & 1] = new Cell(Double.doubleToRawLongBits(x));
cells = rs;
init = true;
}
} finally {
// 释放锁
cellsBusy = 0;
}
if (init) // 初始化成功 方法结束
break;
}
// 初始化hash表失败 尝试将x计算到base上
else if (casBase(v = base,
((fn == null) ?
Double.doubleToRawLongBits
(Double.longBitsToDouble(v) + x) :
Double.doubleToRawLongBits
(fn.applyAsDouble
(Double.longBitsToDouble(v), x)))))
// 计算成功 方法结束
break; // Fall back on using base
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131