FD.io VPP  v17.04-9-g99c0734
Vector Packet Processing
fheap.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 #include <vppinfra/fheap.h>
16 
17 /* Fibonacci heaps. */
20 {
21  return i != ~0 ? vec_elt_at_index (f->nodes, i) : 0;
22 }
23 
26 {
27  return fheap_get_node (f, f->min_root);
28 }
29 
30 static void
32 {
33  fheap_node_t *n, *m;
34  uword ni, si;
35 
36  if (!CLIB_DEBUG || !f->enable_validate)
37  return;
38 
39  vec_foreach_index (ni, f->nodes)
40  {
41  n = vec_elt_at_index (f->nodes, ni);
42 
43  if (!n->is_valid)
44  continue;
45 
46  /* Min root must have minimal key. */
47  m = vec_elt_at_index (f->nodes, f->min_root);
48  ASSERT (n->key >= m->key);
49 
50  /* Min root must have no parent. */
51  if (ni == f->min_root)
52  ASSERT (n->parent == ~0);
53 
54  /* Check sibling linkages. */
55  if (n->next_sibling == ~0)
56  ASSERT (n->prev_sibling == ~0);
57  else if (n->prev_sibling == ~0)
58  ASSERT (n->next_sibling == ~0);
59  else
60  {
61  fheap_node_t *prev, *next;
62  u32 si = n->next_sibling, si_start = si;
63  do
64  {
65  m = vec_elt_at_index (f->nodes, si);
66  prev = vec_elt_at_index (f->nodes, m->prev_sibling);
67  next = vec_elt_at_index (f->nodes, m->next_sibling);
68  ASSERT (prev->next_sibling == si);
69  ASSERT (next->prev_sibling == si);
70  si = m->next_sibling;
71  }
72  while (si != si_start);
73  }
74 
75  /* Loop through all siblings. */
76  {
77  u32 n_siblings = 0;
78 
80  {
81  m =
82  vec_elt_at_index
83  (f->nodes, si);
84  /* All siblings must have same parent. */
85  ASSERT (m->parent
86  ==
87  n->
88  parent);
89  n_siblings += 1;}
90  ));
91 
92  /* Either parent is non-empty or there are siblings present. */
93  if (n->parent == ~0 && ni != f->min_root)
94  ASSERT (n_siblings > 0);
95  }
96 
97  /* Loop through all children. */
98  {
99  u32 found_first_child = n->first_child == ~0;
100  u32 n_children = 0;
101 
103  {
104  m =
105  vec_elt_at_index
106  (f->nodes, si);
107  /* Children must have larger keys than their parent. */
108  ASSERT (m->key >=
109  n->key);
110  if
111  (!found_first_child)
112  found_first_child =
113  si ==
114  n->first_child;
115  n_children += 1;}
116  ));
117 
118  /* Check that first child is present on list. */
119  ASSERT (found_first_child);
120 
121  /* Make sure rank is correct. */
122  ASSERT (n->rank == n_children);
123  }
124  }
125 
126  /* Increment serial number for each successful validate.
127  Failure can be used as condition for gdb breakpoints. */
128  f->validate_serial++;
129 }
130 
131 always_inline void
132 fheap_node_add_sibling (fheap_t * f, u32 ni, u32 ni_to_add)
133 {
134  fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
135  fheap_node_t *n_to_add = vec_elt_at_index (f->nodes, ni_to_add);
136  fheap_node_t *n_next = fheap_get_node (f, n->next_sibling);
137  fheap_node_t *parent;
138 
139  /* Empty list? */
140  if (n->next_sibling == ~0)
141  {
142  ASSERT (n->prev_sibling == ~0);
143  n->next_sibling = n->prev_sibling = ni_to_add;
144  n_to_add->next_sibling = n_to_add->prev_sibling = ni;
145  }
146  else
147  {
148  /* Add node after existing node. */
149  n_to_add->prev_sibling = ni;
150  n_to_add->next_sibling = n->next_sibling;
151 
152  n->next_sibling = ni_to_add;
153  n_next->prev_sibling = ni_to_add;
154  }
155 
156  n_to_add->parent = n->parent;
157  parent = fheap_get_node (f, n->parent);
158  if (parent)
159  parent->rank += 1;
160 }
161 
162 void
163 fheap_add (fheap_t * f, u32 ni, u32 key)
164 {
165  fheap_node_t *r, *n;
166  u32 ri;
167 
168  n = vec_elt_at_index (f->nodes, ni);
169 
170  memset (n, 0, sizeof (n[0]));
171  n->parent = n->first_child = n->next_sibling = n->prev_sibling = ~0;
172  n->key = key;
173 
174  r = fheap_get_root (f);
175  ri = f->min_root;
176  if (!r)
177  {
178  /* No root? Add node as new root. */
179  f->min_root = ni;
180  }
181  else
182  {
183  /* Add node as sibling of current root. */
184  fheap_node_add_sibling (f, ri, ni);
185 
186  /* New node may become new root. */
187  if (r->key > n->key)
188  f->min_root = ni;
189  }
190 
191  fheap_validate (f);
192 }
193 
196 {
197  fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
198  u32 prev_ni = n->prev_sibling;
199  u32 next_ni = n->next_sibling;
200  u32 list_has_single_element = prev_ni == ni;
201  fheap_node_t *prev = fheap_get_node (f, prev_ni);
202  fheap_node_t *next = fheap_get_node (f, next_ni);
203  fheap_node_t *p = fheap_get_node (f, n->parent);
204 
205  if (p)
206  {
207  ASSERT (p->rank > 0);
208  p->rank -= 1;
209  p->first_child = list_has_single_element ? ~0 : next_ni;
210  }
211 
212  if (prev)
213  {
214  ASSERT (prev->next_sibling == ni);
215  prev->next_sibling = next_ni;
216  }
217  if (next)
218  {
219  ASSERT (next->prev_sibling == ni);
220  next->prev_sibling = prev_ni;
221  }
222 
223  n->prev_sibling = n->next_sibling = ni;
224  n->parent = ~0;
225  n->is_valid = invalidate == 0;
226 
227  return list_has_single_element ? ~0 : next_ni;
228 }
229 
232 {
233  return fheap_node_remove_internal (f, ni, /* invalidate */ 0);
234 }
235 
238 {
239  return fheap_node_remove_internal (f, ni, /* invalidate */ 1);
240 }
241 
242 static void
244 {
245  fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
246  fheap_node_t *r, *lo, *hi;
247  u32 ri, lo_i, hi_i, k;
248 
249  while (1)
250  {
251  k = n->rank;
253  ri = f->root_list_by_rank[k];
254  r = fheap_get_node (f, ri);
255  if (!r)
256  {
257  f->root_list_by_rank[k] = ni;
258  return;
259  }
260 
261  f->root_list_by_rank[k] = ~0;
262 
263  /* Sort n/r into lo/hi by their keys. */
264  lo = r, lo_i = ri;
265  hi = n, hi_i = ni;
266  if (hi->key < lo->key)
267  {
268  u32 ti;
269  fheap_node_t *tn;
270  ti = lo_i, tn = lo;
271  lo = hi, lo_i = hi_i;
272  hi = tn, hi_i = ti;
273  }
274 
275  /* Remove larger key. */
276  fheap_node_remove (f, hi_i);
277 
278  /* Add larger key as child of smaller one. */
279  if (lo->first_child == ~0)
280  {
281  hi->parent = lo_i;
282  lo->first_child = hi_i;
283  lo->rank = 1;
284  }
285  else
286  fheap_node_add_sibling (f, lo->first_child, hi_i);
287 
288  /* Following Fredman & Trajan: "When making a root node X a child of another node in a linking step,
289  we unmark X". */
290  hi->is_marked = 0;
291 
292  ni = lo_i;
293  n = lo;
294  }
295 }
296 
297 u32
298 fheap_del_min (fheap_t * f, u32 * min_key)
299 {
300  fheap_node_t *r = fheap_get_root (f);
301  u32 to_delete_min_ri = f->min_root;
302  u32 ri, ni;
303 
304  /* Empty heap? */
305  if (!r)
306  return ~0;
307 
308  /* Root's children become siblings. Call this step a; see below. */
309  if (r->first_child != ~0)
310  {
311  u32 ci, cni, rni;
312  fheap_node_t *c, *cn, *rn;
313 
314  /* Splice child & root circular lists together. */
315  ci = r->first_child;
316  c = vec_elt_at_index (f->nodes, ci);
317 
318  cni = c->next_sibling;
319  rni = r->next_sibling;
320  cn = vec_elt_at_index (f->nodes, cni);
321  rn = vec_elt_at_index (f->nodes, rni);
322 
323  r->next_sibling = cni;
324  c->next_sibling = rni;
325  cn->prev_sibling = to_delete_min_ri;
326  rn->prev_sibling = ci;
327  }
328 
329  /* Remove min root. */
330  ri = fheap_node_remove_and_invalidate (f, to_delete_min_ri);
331 
332  /* Find new min root from among siblings including the ones we've just added. */
333  f->min_root = ~0;
334  if (ri != ~0)
335  {
336  u32 ri_last, ri_next, i, min_ds;
337 
338  r = fheap_get_node (f, ri);
339  ri_last = r->prev_sibling;
340  while (1)
341  {
342  /* Step a above can put children (with r->parent != ~0) on root list. */
343  r->parent = ~0;
344 
345  ri_next = r->next_sibling;
346  fheap_link_root (f, ri);
347  if (ri == ri_last)
348  break;
349  ri = ri_next;
350  r = fheap_get_node (f, ri);
351  }
352 
353  min_ds = ~0;
355  {
356  ni = f->root_list_by_rank[i];
357  if (ni == ~0)
358  continue;
359  f->root_list_by_rank[i] = ~0;
360  r = fheap_get_node (f, ni);
361  if (r->key < min_ds)
362  {
363  f->min_root = ni;
364  min_ds = r->key;
365  ASSERT (r->parent == ~0);
366  }
367  }
368  }
369 
370  /* Return deleted min root. */
371  r = vec_elt_at_index (f->nodes, to_delete_min_ri);
372  if (min_key)
373  *min_key = r->key;
374 
375  fheap_validate (f);
376 
377  return to_delete_min_ri;
378 }
379 
380 static void
382 {
383  fheap_node_t *p = vec_elt_at_index (f->nodes, pi);
384 
385  /* Parent is a root: do nothing. */
386  if (p->parent == ~0)
387  return;
388 
389  /* If not marked, mark it. */
390  if (!p->is_marked)
391  {
392  p->is_marked = 1;
393  return;
394  }
395 
396  /* Its a previously marked, non-root parent.
397  Cut edge to its parent and add to root list. */
398  fheap_node_remove (f, pi);
399  fheap_node_add_sibling (f, f->min_root, pi);
400 
401  /* Unmark it since its now a root node. */
402  p->is_marked = 0;
403 
404  /* "Cascading cuts": check parent. */
405  if (p->parent != ~0)
406  fheap_mark_parent (f, p->parent);
407 }
408 
409 /* Set key to new smaller value. */
410 void
411 fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key)
412 {
413  fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
414  fheap_node_t *r = fheap_get_root (f);
415 
416  n->key = new_key;
417 
418  if (n->parent != ~0)
419  {
420  fheap_mark_parent (f, n->parent);
421 
422  /* Remove node and add to root list. */
423  fheap_node_remove (f, ni);
424  fheap_node_add_sibling (f, f->min_root, ni);
425  }
426 
427  if (n->key < r->key)
428  f->min_root = ni;
429 
430  fheap_validate (f);
431 }
432 
433 void
435 {
436  fheap_node_t *n;
437 
438  n = vec_elt_at_index (f->nodes, ni);
439 
440  if (n->parent == ~0)
441  {
442  ASSERT (ni == f->min_root);
443  fheap_del_min (f, 0);
444  }
445  else
446  {
447  u32 ci;
448 
449  fheap_mark_parent (f, n->parent);
450 
451  /* Add children to root list. */
453  {
454  fheap_node_remove
455  (f, ci);
456  fheap_node_add_sibling
457  (f, f->min_root,
458  ci);}
459  ));
460 
462  }
463 
464  fheap_validate (f);
465 }
466 
467 /*
468  * fd.io coding-style-patch-verification: ON
469  *
470  * Local Variables:
471  * eval: (c-set-style "gnu")
472  * End:
473  */
vmrglw vmrglh hi
#define vec_foreach_index(var, v)
Iterate over vector indices.
u32 parent
Definition: fheap.h:26
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
void fheap_add(fheap_t *f, u32 ni, u32 key)
Definition: fheap.c:163
static u32 fheap_node_remove_and_invalidate(fheap_t *f, u32 ni)
Definition: fheap.c:237
fheap_node_t * nodes
Definition: fheap.h:76
#define always_inline
Definition: clib.h:84
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
static u32 fheap_node_remove_internal(fheap_t *f, u32 ni, u32 invalidate)
Definition: fheap.c:195
u32 prev_sibling
Definition: fheap.h:32
static void fheap_link_root(fheap_t *f, u32 ni)
Definition: fheap.c:243
#define foreach_fheap_node_sibling(f, ni, first_ni, body)
Definition: fheap.h:47
u32 * root_list_by_rank
Definition: fheap.h:78
u32 validate_serial
Definition: fheap.h:82
static fheap_node_t * fheap_get_node(fheap_t *f, u32 i)
Definition: fheap.c:19
u32 is_valid
Definition: fheap.h:44
svmdb_client_t * c
static u32 fheap_node_remove(fheap_t *f, u32 ni)
Definition: fheap.c:231
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
static void fheap_node_add_sibling(fheap_t *f, u32 ni, u32 ni_to_add)
Definition: fheap.c:132
u32 rank
Definition: fheap.h:39
u32 next_sibling
Definition: fheap.h:32
u64 uword
Definition: types.h:112
static fheap_node_t * fheap_get_root(fheap_t *f)
Definition: fheap.c:25
static void fheap_mark_parent(fheap_t *f, u32 pi)
Definition: fheap.c:381
void fheap_del(fheap_t *f, u32 ni)
Definition: fheap.c:434
u32 enable_validate
Definition: fheap.h:80
Definition: fheap.h:71
u32 first_child
Definition: fheap.h:29
void fheap_decrease_key(fheap_t *f, u32 ni, u32 new_key)
Definition: fheap.c:411
u32 fheap_del_min(fheap_t *f, u32 *min_key)
Definition: fheap.c:298
u32 is_marked
Definition: fheap.h:41
#define vec_validate_init_empty(V, I, INIT)
Make sure vector is long enough for given index and initialize empty space (no header, unspecified alignment)
Definition: vec.h:485
static void fheap_validate(fheap_t *f)
Definition: fheap.c:31
u32 min_root
Definition: fheap.h:73
u32 key
Definition: fheap.h:36