kc3-lang/kc3

Browse

Commit 0f55d808bac6e555da289248fe06150064920c0b

Thomas de Grivel 2024-03-03T18:10:14

fix skiplist random height 

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148

diff --git a/libc3/skiplist.c.in b/libc3/skiplist.c.in
index 4559713..9c3b9e7 100644
--- a/libc3/skiplist.c.in
+++ b/libc3/skiplist.c.in
@@ -94,32 +94,35 @@ skiplist_find___NAME$ (s_skiplist___NAME$ *skiplist, _TYPE$ _NAME$)
   return NULL;
 }
 
-static void skiplist_height_table_init___NAME$ (s_skiplist___NAME$ *skiplist, f64 spacing)
+static s_skiplist___NAME$ *
+skiplist_height_table_init___NAME$ (s_skiplist___NAME$ *skiplist, f64 spacing)
 {
   t_skiplist_height *height_table;
   u8 h;
-  f64 w = spacing;
-  f64 end = w;
+  f128 w = spacing;
+  f128 end = w;
   height_table = SKIPLIST_HEIGHT_TABLE___NAME$(skiplist);
   for (h = 0; h < skiplist->max_height; h++) {
     w *= spacing;
     end += w;
-    assert(end <= (f64) SKIPLIST_HEIGHT_MAX);
+    if (end > (f128) SKIPLIST_HEIGHT_MAX)
+      return NULL;
     height_table[h] = end;
   }
+  return skiplist;
 }
 
 s_skiplist___NAME$ *
 skiplist_init___NAME$ (s_skiplist___NAME$ *skiplist, u8 max_height, f64 spacing)
 {
   assert(skiplist);
+  skiplist->max_height = max_height;
+  skiplist_height_table_init___NAME$(skiplist, spacing);
   skiplist->head = skiplist_node_new___NAME$(NULL, max_height);
   if (! skiplist->head)
     return NULL;
   skiplist->compare = compare__NAME$;
   skiplist->length = 0;
-  skiplist->max_height = max_height;
-  skiplist_height_table_init___NAME$(skiplist, spacing);
   return skiplist;
 }
 
@@ -183,19 +186,22 @@ skiplist_pred___NAME$ (s_skiplist___NAME$ *skiplist, _TYPE$ _NAME$)
 u8
 skiplist_random_height___NAME$ (s_skiplist___NAME$ *skiplist)
 {
-  u8 height;
+  u16 height;
   const t_skiplist_height *height_table;
   sw i;
-  u32 j;
+  u64 j;
   sw max;
   t_skiplist_height k;
   assert(skiplist);
+  assert(skiplist->max_height);
   height_table = SKIPLIST_HEIGHT_TABLE___NAME$(skiplist);
   max = height_table[skiplist->max_height - 1];
-  u32_random_uniform(&j, max);
+  u64_random_uniform(&j, max);
   k = j;
-  for (i = 0; i < skiplist->max_height && k > height_table[i]; i++)
-    ;
+  i = 0;
+  while (i < skiplist->max_height - 1 &&
+         k > height_table[i])
+    i++;
   height = skiplist->max_height - i;
   assert(height);
   return height;
diff --git a/libc3/skiplist__fact.c b/libc3/skiplist__fact.c
index 706bfeb..28549da 100644
--- a/libc3/skiplist__fact.c
+++ b/libc3/skiplist__fact.c
@@ -94,32 +94,35 @@ skiplist_find__fact (s_skiplist__fact *skiplist, s_fact * fact)
   return NULL;
 }
 
-static void skiplist_height_table_init__fact (s_skiplist__fact *skiplist, f64 spacing)
+static s_skiplist__fact *
+skiplist_height_table_init__fact (s_skiplist__fact *skiplist, f64 spacing)
 {
   t_skiplist_height *height_table;
   u8 h;
-  f64 w = spacing;
-  f64 end = w;
+  f128 w = spacing;
+  f128 end = w;
   height_table = SKIPLIST_HEIGHT_TABLE__fact(skiplist);
   for (h = 0; h < skiplist->max_height; h++) {
     w *= spacing;
     end += w;
-    assert(end <= (f64) SKIPLIST_HEIGHT_MAX);
+    if (end > (f128) SKIPLIST_HEIGHT_MAX)
+      return NULL;
     height_table[h] = end;
   }
+  return skiplist;
 }
 
 s_skiplist__fact *
 skiplist_init__fact (s_skiplist__fact *skiplist, u8 max_height, f64 spacing)
 {
   assert(skiplist);
+  skiplist->max_height = max_height;
+  skiplist_height_table_init__fact(skiplist, spacing);
   skiplist->head = skiplist_node_new__fact(NULL, max_height);
   if (! skiplist->head)
     return NULL;
   skiplist->compare = compare_fact;
   skiplist->length = 0;
-  skiplist->max_height = max_height;
-  skiplist_height_table_init__fact(skiplist, spacing);
   return skiplist;
 }
 
@@ -183,19 +186,22 @@ skiplist_pred__fact (s_skiplist__fact *skiplist, s_fact * fact)
 u8
 skiplist_random_height__fact (s_skiplist__fact *skiplist)
 {
-  u8 height;
+  u16 height;
   const t_skiplist_height *height_table;
   sw i;
-  u32 j;
+  u64 j;
   sw max;
   t_skiplist_height k;
   assert(skiplist);
+  assert(skiplist->max_height);
   height_table = SKIPLIST_HEIGHT_TABLE__fact(skiplist);
   max = height_table[skiplist->max_height - 1];
-  u32_random_uniform(&j, max);
+  u64_random_uniform(&j, max);
   k = j;
-  for (i = 0; i < skiplist->max_height && k > height_table[i]; i++)
-    ;
+  i = 0;
+  while (i < skiplist->max_height - 1 &&
+         k > height_table[i])
+    i++;
   height = skiplist->max_height - i;
   assert(height);
   return height;
kmx.io     mail     discord kmxgit v0.4.0