还是得用Google的.com啊。
//--------------------drivers/base/Bus.c----------------------------------
....
.....
/**
* bus_for_each_dev - device iterator.
* @bus: bus type.
* @start: device to start iterating from.
* @data: data for the callback.
* @fn: function to be called for each device.
*
* Iterate over @bus's list of devices, and call @fn for each,
* passing it @data. If @start is not NULL, we use that device to
* begin iterating from.
*
* We check the return of @fn each time. If it returns anything
* other than 0, we break out and return that value.
*
* NOTE: The device that returns a non-zero value is not retained
* in any way, nor is its refcount incremented. If the caller needs
* to retain this data, it should do so, and increment the reference
* count in the supplied callback.
*/
int bus_for_each_dev(struct bus_type *bus, struct device *start,
void *data, int (*fn)(struct device *, void *))
{
struct klist_iter i;
struct device *dev;
int error = 0;
if (!bus)
return -EINVAL;
klist_iter_init_node(&bus->p->klist_devices, &i,
(start ? &start->p->knode_bus : NULL));
while ((dev = next_device(&i)) && !error)
error = fn(dev, data);
klist_iter_exit(&i);
return error;
}
-----------------------------------------------------------------------------------------------------
C/IteratorsThe problem
Suppose
we have an abstract data type that represents some sort of container,
such as a list or dictionary. We'd like to be able to do something to
every element of the container; say, count them up. How can we write
operations on the abstract data type to allow this, without exposing
the implementation?
To
make the problem more concrete, let's suppose we have an abstract data
type that represents the set of all non-negative numbers less than some
fixed bound. The core of its interface might look like this:
nums.h
function isnumbered(obj) {
return obj.childNodes.length && obj.firstChild.childNodes.length && obj.firstChild.firstChild.className == 'LineNumber';
}
function nformat(num,chrs,add) {
var nlen = Math.max(0,chrs-(''+num).length), res = '';
while (nlen>0) { res += ' '; nlen-- }
return res+num+add;
}
function addnumber(did, nstart, nstep) {
var c = document.getElementById(did), l = c.firstChild, n = 1;
if (!isnumbered(c))
if (typeof nstart == 'undefined') nstart = 1;
if (typeof nstep == 'undefined') nstep = 1;
n = nstart;
while (l != null) {
if (l.tagName == 'SPAN') {
var s = document.createElement('SPAN');
s.className = 'LineNumber'
s.appendChild(document.createTextNode(nformat(n,4,' ')));
n += nstep;
if (l.childNodes.length)
l.insertBefore(s, l.firstChild)
else
l.appendChild(s)
}
l = l.nextSibling;
}
return false;
}
function remnumber(did) {
var c = document.getElementById(did), l = c.firstChild;
if (isnumbered(c))
while (l != null) {
if (l.tagName == 'SPAN' && l.firstChild.className == 'LineNumber') l.removeChild(l.firstChild);
l = l.nextSibling;
}
return false;
}
function togglenumber(did, nstart, nstep) {
var c = document.getElementById(did);
if (isnumbered(c)) {
remnumber(did);
} else {
addnumber(did,nstart,nstep);
}
return false;
}
document.write('
切换行号显示');
切换行号显示
1 2 3 4 5 typedef struct nums *Nums; 6 7 8 Nums nums_create(int bound); 9 10 11 void nums_destroy(Nums); 12 13 14 int nums_contains(Nums nums, int element); 15
nums.c
document.write('
切换行号显示');
切换行号显示
1 #include <stdlib.h> 2 #include "nums.h" 3 4 struct nums { 5 int bound; 6 }; 7 8 Nums nums_create(int bound) 9 { 10 struct nums *n; 11 n = malloc(sizeof(*n)); 12 n->bound = bound; 13 return n; 14 } 15 16 void nums_destroy(Nums n) { free(n); } 17 18 int nums_contains(Nums n, int element) 19 { 20 return element >= 0 && element < n->bound; 21 } 22 From the outside, a Nums acts like the set of numbers from 0 to bound - 1; nums_contains will insist that it contains any int that is in this set and contains no int that is not in this set.
Let's suppose now that we want to loop over all elements of some Nums, say to add them together. In particular, we'd like to implement the following pseudocode, where nums is some Nums instance:
document.write('
切换行号显示');
切换行号显示
1 sum = 0; 2 for(each i in nums) { 3 sum += i; 4 } 5 One way to do this would be to build the loop into some operation in nums.c, including its body. But we'd like to be able to substitute any body for the sum += i line. Since we can't see the inside of a Nums, we need to have some additional operation or operations on a Nums that lets us write the loop. How can we do this?
Option 1: Function that returns a sequence
A data-driven approach might be to add a nums_contents
function that returns a sequence of all elements of some instance,
perhaps in the form of an array or linked list. The advantage of this
approach is that once you have the sequence, you don't need to worry
about changes to (or destruction of) the original object. The
disadvantage is that you have to deal with storage management issues,
and have to pay the costs in time and space of allocating and filling
in the sequence. This can be particularly onerous for a "virtual"
container like Nums, since we could conceivably have a Nums instance with billions of elements.
Bearing these facts in mind, let's see what this approach might look like. We'll define a new function nums_contents that returns an array of ints, terminated by a -1 sentinel:
document.write('
切换行号显示');
切换行号显示
1 int * 2 nums_contents(Nums n) 3 { 4 int *a; 5 int i; 6 a = malloc(sizeof(*a) * (n->bound + 1)); 7 for(i = 0; i < n->bound; i++) a[i] = i; 8 a[n->bound] = -1; 9 return a; 10 } 11 We might use it like this:
document.write('
切换行号显示');
切换行号显示
1 sum = 0; 2 contents = nums_contents(nums); 3 for(p = contents; *p != -1; p++) { 4 sum += *p; 5 } 6 free(contents); 7 Despite the naturalness of the approach, returning a sequence in this case leads to the most code complexity of the options we will examine.
Option 2: Iterator with first/done/next operations
If we don't want to look at all the elements at once, but just want to process them one at a time, we can build an iterator.
An iterator is an object that allows you to step through the contents
of another object, by providing convenient operations for getting the
first element, testing when you are done, and getting the next element
if you are not. In C, we try to design iterators to have operations
that fit well in the top of a for loop.
For the Nums type, we'll make each Nums its own iterator. The new operations are given here:
document.write('
切换行号显示');
切换行号显示
1 int nums_first(Nums n) { return 0; } 2 int nums_done(Nums n, int val) { return val >= n->bound; } 3 int nums_next(Nums n, int val) { return val+1; } 4 And we use them like this:
document.write('
切换行号显示');
切换行号显示
1 sum = 0; 2 for(i = nums_first(nums); !nums_done(nums, i); i = nums_next(nums, i)) { 3 sum += i; 4 } 5 Not
only do we completely avoid the overhead of building a sequence, we
also get much cleaner code. It helps in this case that all we need to
find the next value is the previous one; for a more complicated problem
we might have to create and destroy a separate iterator object that
holds the state of the loop. But for many tasks in C, the
first/done/next idiom is a pretty good one.
Option 3: Iterator with function argument
Suppose
we have a very complicated iteration, say one that might require
several nested loops or even a recursion to span all the elements. In
this case it might be very difficult to provide first/done/next
operations, because it would be hard to encode the state of the
iteration so that we could easily pick up in the next operation where
we previously left off. What we'd really like to do is to be able to
plug arbitrary code into the innermost loop of our horrible iteration
procedure, and do it in a way that is reasonably typesafe and doesn't
violate our abstraction barrier. This is a job for function pointers,
and an example of the functional programming style in action.
We'll define a nums_foreach function that takes a function as an argument:
document.write('
切换行号显示');
切换行号显示
1 void nums_foreach(Nums n, void (*f)(int, void *), void *f_data) 2 { 3 int i; 4 for(i = 0; i < n->bound; i++) f(i, f_data); 5 } 6 The f_data argument is used to pass extra state into the passed-in function f; it's a void * because we want to let f work on any sort of extra state it likes.
Now to do our summation, we first define an extra function sum_helper, which adds each element to an accumulator pointed to by f_data:
document.write('
切换行号显示');
切换行号显示
1 static void sum_helper(int i, void *f_data) 2 { 3 *((int *) f_data) += i; 4 } 5 We then feed sum_helper to the nums_foreach function:
document.write('
切换行号显示');
切换行号显示
1 sum = 0; 2 nums_foreach(nums, sum_helper, (void *) &sum); 3 There is a bit of a nuisance in having to define the auxiliary sum_helper function and in all the casts to and from void,
but on the whole the complexity of this solution is not substantially
greater than the first/done/next approach. Which you should do depends
on whether it's harder to encapsulate the state of the iterator (in
which case the functional approach is preferable) or of the loop body
(in which case the first/done/next approach is preferable), and whether
you need to bail out of the loop early (which would require special
support from the foreach procedure, perhaps checking a return
value from the function). However, it's almost always straightforward
to encapsulate the state of a loop body; just build a struct containing all the variables that it uses, and pass a pointer to this struct as f_data.
Appendix: Complete code for Nums
Here's a grand unified Nums implementation that provides all the interfaces we've discussed:
nums.h
document.write('
切换行号显示');
切换行号显示
1 2 3 4 5 typedef struct nums *Nums; 6 7 8 Nums nums_create(int bound); 9 10 11 void nums_destroy(Nums); 12 13 14 int nums_contains(Nums nums, int element); 15 16 17 18 19 int *nums_contents(Nums n); 20 21 22 int nums_first(Nums n); 23 int nums_done(Nums n, int val); 24 int nums_next(Nums n, int val); 25 26 27 void nums_foreach(Nums n, void (*f)(int, void *f_data), void *f_data); 28
nums.c
document.write('
切换行号显示');
切换行号显示
1 #include <stdlib.h> 2 #include "nums.h" 3 4 struct nums { 5 int bound; 6 }; 7 8 Nums nums_create(int bound) 9 { 10 struct nums *n; 11 n = malloc(sizeof(*n)); 12 n->bound = bound; 13 return n; 14 } 15 16 void nums_destroy(Nums n) { free(n); } 17 18 int nums_contains(Nums n, int element) 19 { 20 return element >= 0 && element < n->bound; 21 } 22 23 int * 24 nums_contents(Nums n) 25 { 26 int *a; 27 int i; 28 a = malloc(sizeof(*a) * (n->bound + 1)); 29 for(i = 0; i < n->bound; i++) a[i] = i; 30 a[n->bound] = -1; 31 return a; 32 } 33 34 int nums_first(Nums n) { return 0; } 35 int nums_done(Nums n, int val) { return val >= n->bound; } 36 int nums_next(Nums n, int val) { return val+1; } 37 38 void nums_foreach(Nums n, void (*f)(int, void *), void *f_data) 39 { 40 int i; 41 for(i = 0; i < n->bound; i++) f(i, f_data); 42 } 43 And here's some test code to see if it all works:
test-nums.c
document.write('
切换行号显示');
切换行号显示
1 #include <stdio.h> 2 #include <setjmp.h> 3 #include <signal.h> 4 #include <unistd.h> 5 #include <stdlib.h> 6 7 #include "nums.h" 8 #include "tester.h" 9 10 static void sum_helper(int i, void *f_data) 11 { 12 *((int *) f_data) += i; 13 } 14 15 int 16 main(int argc, char **argv) 17 { 18 Nums nums; 19 int sum; 20 int *contents; 21 int *p; 22 int i; 23 24 tester_init(); 25 26 TRY { nums = nums_create(100); } ENDTRY; 27 TEST(nums_contains(nums, -1), 0); 28 TEST(nums_contains(nums, 0), 1); 29 TEST(nums_contains(nums, 1), 1); 30 TEST(nums_contains(nums, 98), 1); 31 TEST(nums_contains(nums, 99), 1); 32 TEST(nums_contains(nums, 100), 0); 33 34 sum = 0; 35 contents = nums_contents(nums); 36 for(p = contents; *p != -1; p++) { 37 sum += *p; 38 } 39 free(contents); 40 TEST(sum, 4950); 41 42 sum = 0; 43 for(i = nums_first(nums); !nums_done(nums, i); i = nums_next(nums, i)) { 44 sum += i; 45 } 46 TEST(sum, 4950); 47 48 sum = 0; 49 nums_foreach(nums, sum_helper, (void *) &sum); 50 TEST(sum, 4950); 51 tester_report(stdout, argv[0]); 52 return tester_result(); 53 } 54
$ make test
gcc -g3 -ansi -pedantic -Wall -c -o test-nums.o test-nums.c
gcc -g3 -ansi -pedantic -Wall -c -o nums.o nums.c
gcc -g3 -ansi -pedantic -Wall -c -o tester.o tester.c
gcc -g3 -ansi -pedantic -Wall -o test-nums test-nums.o nums.o tester.o
./test-nums
OK!
CategoryProgrammingNotes