diff options
author | YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org> | 2007-02-09 09:24:47 -0500 |
---|---|---|
committer | David S. Miller <davem@sunset.davemloft.net> | 2007-02-11 02:19:39 -0500 |
commit | e905a9edab7f4f14f9213b52234e4a346c690911 (patch) | |
tree | 9e52a5f47eec47c5685c347ff7af22290a10305b /net/ipv4/fib_trie.c | |
parent | 642656518b2e64fd59d9bbd15b6885cac5fe99b1 (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.c | 98 |
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) | |||
294 | static int halve_threshold = 25; | 294 | static int halve_threshold = 25; |
295 | static int inflate_threshold = 50; | 295 | static int inflate_threshold = 50; |
296 | static int halve_threshold_root = 15; | 296 | static int halve_threshold_root = 15; |
297 | static int inflate_threshold_root = 25; | 297 | static int inflate_threshold_root = 25; |
298 | 298 | ||
299 | 299 | ||
300 | static void __alias_free_mem(struct rcu_head *head) | 300 | static 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 | ||
891 | static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new) | 891 | static 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; |