aboutsummaryrefslogtreecommitdiffstats
path: root/net/ipv4/fib_trie.c
diff options
context:
space:
mode:
authorYOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org>2007-02-09 09:24:47 -0500
committerDavid S. Miller <davem@sunset.davemloft.net>2007-02-11 02:19:39 -0500
commite905a9edab7f4f14f9213b52234e4a346c690911 (patch)
tree9e52a5f47eec47c5685c347ff7af22290a10305b /net/ipv4/fib_trie.c
parent642656518b2e64fd59d9bbd15b6885cac5fe99b1 (diff)
[NET] IPV4: Fix whitespace errors.
Signed-off-by: YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r--net/ipv4/fib_trie.c98
1 files changed, 49 insertions, 49 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 1e589b91605e..004a437bd7b5 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -7,13 +7,13 @@
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet 7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences. 8 * & Swedish University of Agricultural Sciences.
9 * 9 *
10 * Jens Laas <jens.laas@data.slu.se> Swedish University of 10 * Jens Laas <jens.laas@data.slu.se> Swedish University of
11 * Agricultural Sciences. 11 * Agricultural Sciences.
12 * 12 *
13 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet 13 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
14 * 14 *
15 * This work is based on the LPC-trie which is originally descibed in: 15 * This work is based on the LPC-trie which is originally descibed in:
16 * 16 *
17 * An experimental study of compression methods for dynamic tries 17 * An experimental study of compression methods for dynamic tries
18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002. 18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19 * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/ 19 * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
@@ -224,34 +224,34 @@ static inline int tkey_mismatch(t_key a, int offset, t_key b)
224} 224}
225 225
226/* 226/*
227 To understand this stuff, an understanding of keys and all their bits is 227 To understand this stuff, an understanding of keys and all their bits is
228 necessary. Every node in the trie has a key associated with it, but not 228 necessary. Every node in the trie has a key associated with it, but not
229 all of the bits in that key are significant. 229 all of the bits in that key are significant.
230 230
231 Consider a node 'n' and its parent 'tp'. 231 Consider a node 'n' and its parent 'tp'.
232 232
233 If n is a leaf, every bit in its key is significant. Its presence is 233 If n is a leaf, every bit in its key is significant. Its presence is
234 necessitated by path compression, since during a tree traversal (when 234 necessitated by path compression, since during a tree traversal (when
235 searching for a leaf - unless we are doing an insertion) we will completely 235 searching for a leaf - unless we are doing an insertion) we will completely
236 ignore all skipped bits we encounter. Thus we need to verify, at the end of 236 ignore all skipped bits we encounter. Thus we need to verify, at the end of
237 a potentially successful search, that we have indeed been walking the 237 a potentially successful search, that we have indeed been walking the
238 correct key path. 238 correct key path.
239 239
240 Note that we can never "miss" the correct key in the tree if present by 240 Note that we can never "miss" the correct key in the tree if present by
241 following the wrong path. Path compression ensures that segments of the key 241 following the wrong path. Path compression ensures that segments of the key
242 that are the same for all keys with a given prefix are skipped, but the 242 that are the same for all keys with a given prefix are skipped, but the
243 skipped part *is* identical for each node in the subtrie below the skipped 243 skipped part *is* identical for each node in the subtrie below the skipped
244 bit! trie_insert() in this implementation takes care of that - note the 244 bit! trie_insert() in this implementation takes care of that - note the
245 call to tkey_sub_equals() in trie_insert(). 245 call to tkey_sub_equals() in trie_insert().
246 246
247 if n is an internal node - a 'tnode' here, the various parts of its key 247 if n is an internal node - a 'tnode' here, the various parts of its key
248 have many different meanings. 248 have many different meanings.
249 249
250 Example: 250 Example:
251 _________________________________________________________________ 251 _________________________________________________________________
252 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C | 252 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
253 ----------------------------------------------------------------- 253 -----------------------------------------------------------------
254 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 254 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
255 255
256 _________________________________________________________________ 256 _________________________________________________________________
257 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u | 257 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
@@ -263,23 +263,23 @@ static inline int tkey_mismatch(t_key a, int offset, t_key b)
263 n->pos = 15 263 n->pos = 15
264 n->bits = 4 264 n->bits = 4
265 265
266 First, let's just ignore the bits that come before the parent tp, that is 266 First, let's just ignore the bits that come before the parent tp, that is
267 the bits from 0 to (tp->pos-1). They are *known* but at this point we do 267 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
268 not use them for anything. 268 not use them for anything.
269 269
270 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the 270 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
271 index into the parent's child array. That is, they will be used to find 271 index into the parent's child array. That is, they will be used to find
272 'n' among tp's children. 272 'n' among tp's children.
273 273
274 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits 274 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
275 for the node n. 275 for the node n.
276 276
277 All the bits we have seen so far are significant to the node n. The rest 277 All the bits we have seen so far are significant to the node n. The rest
278 of the bits are really not needed or indeed known in n->key. 278 of the bits are really not needed or indeed known in n->key.
279 279
280 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into 280 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
281 n's child array, and will of course be different for each child. 281 n's child array, and will of course be different for each child.
282 282
283 283
284 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown 284 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
285 at this point. 285 at this point.
@@ -294,7 +294,7 @@ static inline void check_tnode(const struct tnode *tn)
294static int halve_threshold = 25; 294static int halve_threshold = 25;
295static int inflate_threshold = 50; 295static int inflate_threshold = 50;
296static int halve_threshold_root = 15; 296static int halve_threshold_root = 15;
297static int inflate_threshold_root = 25; 297static int inflate_threshold_root = 25;
298 298
299 299
300static void __alias_free_mem(struct rcu_head *head) 300static void __alias_free_mem(struct rcu_head *head)
@@ -355,7 +355,7 @@ static inline void tnode_free(struct tnode *tn)
355 struct leaf *l = (struct leaf *) tn; 355 struct leaf *l = (struct leaf *) tn;
356 call_rcu_bh(&l->rcu, __leaf_free_rcu); 356 call_rcu_bh(&l->rcu, __leaf_free_rcu);
357 } 357 }
358 else 358 else
359 call_rcu(&tn->rcu, __tnode_free_rcu); 359 call_rcu(&tn->rcu, __tnode_free_rcu);
360} 360}
361 361
@@ -461,7 +461,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
461 int inflate_threshold_use; 461 int inflate_threshold_use;
462 int halve_threshold_use; 462 int halve_threshold_use;
463 463
464 if (!tn) 464 if (!tn)
465 return NULL; 465 return NULL;
466 466
467 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n", 467 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
@@ -556,7 +556,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
556 556
557 if(!tn->parent) 557 if(!tn->parent)
558 inflate_threshold_use = inflate_threshold_root; 558 inflate_threshold_use = inflate_threshold_root;
559 else 559 else
560 inflate_threshold_use = inflate_threshold; 560 inflate_threshold_use = inflate_threshold;
561 561
562 err = 0; 562 err = 0;
@@ -587,7 +587,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
587 587
588 if(!tn->parent) 588 if(!tn->parent)
589 halve_threshold_use = halve_threshold_root; 589 halve_threshold_use = halve_threshold_root;
590 else 590 else
591 halve_threshold_use = halve_threshold; 591 halve_threshold_use = halve_threshold;
592 592
593 err = 0; 593 err = 0;
@@ -665,10 +665,10 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn)
665 right = tnode_new(inode->key|m, inode->pos + 1, 665 right = tnode_new(inode->key|m, inode->pos + 1,
666 inode->bits - 1); 666 inode->bits - 1);
667 667
668 if (!right) { 668 if (!right) {
669 tnode_free(left); 669 tnode_free(left);
670 goto nomem; 670 goto nomem;
671 } 671 }
672 672
673 put_child(t, tn, 2*i, (struct node *) left); 673 put_child(t, tn, 2*i, (struct node *) left);
674 put_child(t, tn, 2*i+1, (struct node *) right); 674 put_child(t, tn, 2*i+1, (struct node *) right);
@@ -890,23 +890,23 @@ static inline struct list_head * get_fa_head(struct leaf *l, int plen)
890 890
891static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new) 891static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
892{ 892{
893 struct leaf_info *li = NULL, *last = NULL; 893 struct leaf_info *li = NULL, *last = NULL;
894 struct hlist_node *node; 894 struct hlist_node *node;
895 895
896 if (hlist_empty(head)) { 896 if (hlist_empty(head)) {
897 hlist_add_head_rcu(&new->hlist, head); 897 hlist_add_head_rcu(&new->hlist, head);
898 } else { 898 } else {
899 hlist_for_each_entry(li, node, head, hlist) { 899 hlist_for_each_entry(li, node, head, hlist) {
900 if (new->plen > li->plen) 900 if (new->plen > li->plen)
901 break; 901 break;
902 902
903 last = li; 903 last = li;
904 } 904 }
905 if (last) 905 if (last)
906 hlist_add_after_rcu(&last->hlist, &new->hlist); 906 hlist_add_after_rcu(&last->hlist, &new->hlist);
907 else 907 else
908 hlist_add_before_rcu(&new->hlist, &li->hlist); 908 hlist_add_before_rcu(&new->hlist, &li->hlist);
909 } 909 }
910} 910}
911 911
912/* rcu_read_lock needs to be hold by caller from readside */ 912/* rcu_read_lock needs to be hold by caller from readside */
@@ -1700,7 +1700,7 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1700 /* Decend if tnode */ 1700 /* Decend if tnode */
1701 while (IS_TNODE(c)) { 1701 while (IS_TNODE(c)) {
1702 p = (struct tnode *) c; 1702 p = (struct tnode *) c;
1703 idx = 0; 1703 idx = 0;
1704 1704
1705 /* Rightmost non-NULL branch */ 1705 /* Rightmost non-NULL branch */
1706 if (p && IS_TNODE(p)) 1706 if (p && IS_TNODE(p))
@@ -2303,9 +2303,9 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
2303 2303
2304 seq_indent(seq, iter->depth-1); 2304 seq_indent(seq, iter->depth-1);
2305 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n", 2305 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2306 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children, 2306 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2307 tn->empty_children); 2307 tn->empty_children);
2308 2308
2309 } else { 2309 } else {
2310 struct leaf *l = (struct leaf *) n; 2310 struct leaf *l = (struct leaf *) n;
2311 int i; 2311 int i;