数据结构与算法（第3版）

前言
第一篇　Android的前世今生——Android概述篇
第1章　Android的前世今生  2
1.1　Android的起源  2
1.2　开放手机联盟  2
1.3　开源与相关协议  3
1.4　系统的升级与发展  3
第2章　Android体系结构  4
2.1　四层空间基本结构  4
2.1.1　Android系统底层开发  6
2.1.2　应用程序开发  7
2.2　Android代码目录结构  7
2.3　Android开发环境搭建  8
第二篇　勿于浮砂筑高台——Linux驱动基础篇
第3章　Linux 内核综述  14
3.1　OS基本概念  14
3.1.1　多用户系统  15
3.1.2　用户和组  15
3.1.3　进程  16
3.1.4　Linux单核架构  16
3.2　Linux内核综述  18
3.2.1　进程/内核模型综述  18
3.2.2　内存管理综述  26
3.2.3　文件系统综述  29
3.2.4　设备驱动简述  34
第4章　Linux内核编程与内核模块  35
4.1　Linux内核源代码目录结构  35
4.2　Linux内核的编译与启动  36
4.3　Linux内核的C编程  37
4.4　Linux内核模块基础与骨架  43
4.5　Linux模块的加载与卸载  46
4.6　Linux模块的参数与导出符号  46
4.7　Linux模块的使用计数  48
第5章　Linux文件系统  50
5.1　Linux文件系统概述  50
5.1.1　Linux文件系统的目录结构  50
5.1.2　设备驱动与Linux文件系统的关联  51
5.2　Linux设备文件系统  55
5.2.1　devfs设备文件系统  55
5.2.2　udev设备文件系统  56
5.2.3　sysfs文件系统与Linux设备  57
5.2.4　udev的组成  67
5.2.5　udev规则文件  68
第6章　Linux字符设备驱动  70
6.1　Linux字符设备驱动结构  70
6.1.1　cdev结构体  70
6.1.2　分配和释放设备号  71
6.1.3　file_operations结构体  72
6.1.4　Linux字符设备驱动的组成  74
6.2　一个字符设备驱动例子——virtualchar  77
6.2.1　头文件、宏及设备结构体  77
6.2.2　加载与卸载设备驱动  78
6.2.3　驱动函数实现  79
6.2.4　驱动设备私有数据  83
6.3　对virtualchar设备的访问  90
第7章　Linux设备驱动中的内存与I/O访问  92
7.1　CPU与内存和I/O之间的故事  92
7.1.1内存空间与I/O空间  92
7.1.2　内存管理单元MMU  93
7.2　Linux内存管理  97
7.3　Linux内存访问  99
7.4　Linux I/O访问  102
7.4.1　访问I/O  102
7.4.2　申请与释放I/O资源  105
7.4.3　I/O访问流程  107
7.4.4　设备地址与用户空间的映射  107
7.5　DMA  114
7.5.1　DMA与Cache的一致性  114
7.5.2　Linux下的DMA编程  114
第8章　Linux设备驱动中的中断  125
8.1　Linux中断及中断处理架构  125
8.2　Linux中断编程  126
8.2.1　申请和释放中断  126
8.2.2　使能与屏蔽中断  127
8.2.3　底半部机制  127
8.2.4　中断共享  130
8.3　Linux定时器  132
8.4　Linux延时处理  134
8.4.1　短延时  135
8.4.2　长延时  135
8.4.3　睡眠延时  136
第9章　Linux设备驱动中的并发  138
9.1　Linux中的并发与竞争  138
9.2　Linux中常用的同步访问技术  139
9.2.1　中断屏蔽  139
9.2.2　原子操作  140
9.2.3　自旋锁  142
9.2.4　信号量  147
9.2.5　互斥灯  152
9.3　增加并发控制的virtualchar驱动  153
第10章　Linux设备的阻塞式与非阻塞式访问  157
10.1　阻塞式与非阻塞式访问  157
10.1.1　等待队列  158
10.1.2　支持阻塞操作的virtualfifo设备驱动  162
10.2　Linux的轮询访问  167
10.2.1　应用程序中的轮询编程  167
10.2.2　设备驱动中的轮询编程  168
10.2.3　支持轮询操作的virtualfifo驱动  169
第11章　Linux设备驱动中的异步访问  171
11.1　Linux 2.6 中的异步访问  171
11.1.1　异步访问概念与GNU C库函数  171
11.1.2　使用信号作为异步访问的通知  175
11.1.3　使用回调函数作为异步访问的通知  177
11.1.4　异步访问与设备驱动  178
11.2　异步Fifo驱动例子  180
11.2.1　在virtualfifo驱动中增加异步通知  180
11.2.2　在用户空间验证virtualfifo的异步通知  182
第12章　Linux块设备驱动  184
12.1　块设备的I/O操作特点  184
12.2　Linux块设备驱动结构  184
12.2.1　block_device_operations结构体  184
12.2.2　gendisk结构体  186
12.2.3　request与bio结构体  188
12.2.4　块设备驱动注册与注销  197
12.3　Linux块设备驱动的模块加载与卸载  198
12.4　块设备的打开/释放/IOCTL  200
第13章　Linux网络设备驱动  202
13.1　Linux网络设备驱动体系结构  202
13.2　Linux网络设备驱动结构  203
13.3　Linux网络设备驱动I/O实现  204
13.3.1　网络设备初始化  204
13.3.2　网络数据包的收发  205
第三篇　实践出真知——Android驱动实践篇
第14章　Android HAL层的设计  208
14.1　Android HAL概述  208
14.2　为Android开发虚拟驱动virtualio  209
14.3　Android集成C程序访问virtualio  220
14.4　Android通过HAL访问virtualio  222
14.4.1　virtualio HAL模块实现  222
14.4.2　实现访问virtualio HAL模块JNI  226
14.4.3　在Framework层增加virtualio服务  229
第15章　Framebuffer子系统  231
15.1　Linux Framebuffer一般子系统  231
15.1.1　Framebuffer数据结构  231
15.1.2　Framebuffer驱动  237
15.2　Android Framebuffer子系统实践  238
15.2.1　硬件基础  238
15.2.2　CPU侧显示驱动模块  240
15.2.3　LCM驱动模块  242
15.3　Android系统对Framebuffer的使用  247
第16章　Input子系统  249
16.1　Linux Input一般子系统  249
16.1.1　Input数据结构  250
16.1.2　Input内核模块  252
16.2　Android Input子系统实践  257
16.2.1　硬件基础  258
16.2.2　Input驱动模块  258
16.3　Android系统对Input的使用  263
第17章　V4L2子系统  266
17.1　Linux V4L2一般子系统  266
17.1.1　V4L2数据结构  266
17.1.2　V4L2接口  268
17.1.3　V4L2虚拟驱动vivi  273
17.2　Android V4L2实践  279
17.2.1　硬件基础  280
17.2.2　CPU侧CCIC驱动模块  281
17.2.3　OV5642模组驱动模块  283
17.3　Android系统对V4L2的使用  286
第18章　Binder IPC通信子系统  288
18.1　Binder驱动概述  288
18.2　Binder通信模型  288
18.3　Binder驱动  291
18.3.1　Binder相关的结构体  292
18.3.2　Android Binder子系统的架构设计  292
18.4　Binder的工作流程  293
第19章　USB子系统  295
19.1　USB协议基础知识  295
19.1.1　USB物理连接  295
19.1.2　USB通信协议  297
19.2　USB子系统底层  299
19.2.1　USB Core  299
19.2.2　Linux USB gadget三层架构  303
19.3　Android USB子系统实践  305
19.3.1　Android IPC通信补充  305
19.3.2　Android USB Mass Storage流程分析  309
第20章　Bootloader引导子系统  312
20.1　Bootloader流程分析  312
20.1.1　Bootloader概述  312
20.1.2　U-Boot启动流程分析  314
20.2　Bootloader修改指南  317
20.2.1　开机第一帧图的修改  317
20.2.2　开机模式的定制  318
参考文献  321