數(shù)據(jù)結構與算法（第3版）

前言
第一篇　Android的前世今生——Android概述篇
第1章　Android的前世今生  2
1.1　Android的起源  2
1.2　開放手機聯(lián)盟  2
1.3　開源與相關協(xié)議  3
1.4　系統(tǒng)的升級與發(fā)展  3
第2章　Android體系結構  4
2.1　四層空間基本結構  4
2.1.1　Android系統(tǒng)底層開發(fā)  6
2.1.2　應用程序開發(fā)  7
2.2　Android代碼目錄結構  7
2.3　Android開發(fā)環(huán)境搭建  8
第二篇　勿于浮砂筑高臺——Linux驅(qū)動基礎篇
第3章　Linux 內(nèi)核綜述  14
3.1　OS基本概念  14
3.1.1　多用戶系統(tǒng)  15
3.1.2　用戶和組  15
3.1.3　進程  16
3.1.4　Linux單核架構  16
3.2　Linux內(nèi)核綜述  18
3.2.1　進程/內(nèi)核模型綜述  18
3.2.2　內(nèi)存管理綜述  26
3.2.3　文件系統(tǒng)綜述  29
3.2.4　設備驅(qū)動簡述  34
第4章　Linux內(nèi)核編程與內(nèi)核模塊  35
4.1　Linux內(nèi)核源代碼目錄結構  35
4.2　Linux內(nèi)核的編譯與啟動  36
4.3　Linux內(nèi)核的C編程  37
4.4　Linux內(nèi)核模塊基礎與骨架  43
4.5　Linux模塊的加載與卸載  46
4.6　Linux模塊的參數(shù)與導出符號  46
4.7　Linux模塊的使用計數(shù)  48
第5章　Linux文件系統(tǒng)  50
5.1　Linux文件系統(tǒng)概述  50
5.1.1　Linux文件系統(tǒng)的目錄結構  50
5.1.2　設備驅(qū)動與Linux文件系統(tǒng)的關聯(lián)  51
5.2　Linux設備文件系統(tǒng)  55
5.2.1　devfs設備文件系統(tǒng)  55
5.2.2　udev設備文件系統(tǒng)  56
5.2.3　sysfs文件系統(tǒng)與Linux設備  57
5.2.4　udev的組成  67
5.2.5　udev規(guī)則文件  68
第6章　Linux字符設備驅(qū)動  70
6.1　Linux字符設備驅(qū)動結構  70
6.1.1　cdev結構體  70
6.1.2　分配和釋放設備號  71
6.1.3　file_operations結構體  72
6.1.4　Linux字符設備驅(qū)動的組成  74
6.2　一個字符設備驅(qū)動例子——virtualchar  77
6.2.1　頭文件、宏及設備結構體  77
6.2.2　加載與卸載設備驅(qū)動  78
6.2.3　驅(qū)動函數(shù)實現(xiàn)  79
6.2.4　驅(qū)動設備私有數(shù)據(jù)  83
6.3　對virtualchar設備的訪問  90
第7章　Linux設備驅(qū)動中的內(nèi)存與I/O訪問  92
7.1　CPU與內(nèi)存和I/O之間的故事  92
7.1.1內(nèi)存空間與I/O空間  92
7.1.2　內(nèi)存管理單元MMU  93
7.2　Linux內(nèi)存管理  97
7.3　Linux內(nèi)存訪問  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設備驅(qū)動中的中斷  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設備驅(qū)動中的并發(fā)  138
9.1　Linux中的并發(fā)與競爭  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　增加并發(fā)控制的virtualchar驅(qū)動  153
第10章　Linux設備的阻塞式與非阻塞式訪問  157
10.1　阻塞式與非阻塞式訪問  157
10.1.1　等待隊列  158
10.1.2　支持阻塞操作的virtualfifo設備驅(qū)動  162
10.2　Linux的輪詢訪問  167
10.2.1　應用程序中的輪詢編程  167
10.2.2　設備驅(qū)動中的輪詢編程  168
10.2.3　支持輪詢操作的virtualfifo驅(qū)動  169
第11章　Linux設備驅(qū)動中的異步訪問  171
11.1　Linux 2.6 中的異步訪問  171
11.1.1　異步訪問概念與GNU C庫函數(shù)  171
11.1.2　使用信號作為異步訪問的通知  175
11.1.3　使用回調(diào)函數(shù)作為異步訪問的通知  177
11.1.4　異步訪問與設備驅(qū)動  178
11.2　異步Fifo驅(qū)動例子  180
11.2.1　在virtualfifo驅(qū)動中增加異步通知  180
11.2.2　在用戶空間驗證virtualfifo的異步通知  182
第12章　Linux塊設備驅(qū)動  184
12.1　塊設備的I/O操作特點  184
12.2　Linux塊設備驅(qū)動結構  184
12.2.1　block_device_operations結構體  184
12.2.2　gendisk結構體  186
12.2.3　request與bio結構體  188
12.2.4　塊設備驅(qū)動注冊與注銷  197
12.3　Linux塊設備驅(qū)動的模塊加載與卸載  198
12.4　塊設備的打開/釋放/IOCTL  200
第13章　Linux網(wǎng)絡設備驅(qū)動  202
13.1　Linux網(wǎng)絡設備驅(qū)動體系結構  202
13.2　Linux網(wǎng)絡設備驅(qū)動結構  203
13.3　Linux網(wǎng)絡設備驅(qū)動I/O實現(xiàn)  204
13.3.1　網(wǎng)絡設備初始化  204
13.3.2　網(wǎng)絡數(shù)據(jù)包的收發(fā)  205
第三篇　實踐出真知——Android驅(qū)動實踐篇
第14章　Android HAL層的設計  208
14.1　Android HAL概述  208
14.2　為Android開發(fā)虛擬驅(qū)動virtualio  209
14.3　Android集成C程序訪問virtualio  220
14.4　Android通過HAL訪問virtualio  222
14.4.1　virtualio HAL模塊實現(xiàn)  222
14.4.2　實現(xiàn)訪問virtualio HAL模塊JNI  226
14.4.3　在Framework層增加virtualio服務  229
第15章　Framebuffer子系統(tǒng)  231
15.1　Linux Framebuffer一般子系統(tǒng)  231
15.1.1　Framebuffer數(shù)據(jù)結構  231
15.1.2　Framebuffer驅(qū)動  237
15.2　Android Framebuffer子系統(tǒng)實踐  238
15.2.1　硬件基礎  238
15.2.2　CPU側顯示驅(qū)動模塊  240
15.2.3　LCM驅(qū)動模塊  242
15.3　Android系統(tǒng)對Framebuffer的使用  247
第16章　Input子系統(tǒng)  249
16.1　Linux Input一般子系統(tǒng)  249
16.1.1　Input數(shù)據(jù)結構  250
16.1.2　Input內(nèi)核模塊  252
16.2　Android Input子系統(tǒng)實踐  257
16.2.1　硬件基礎  258
16.2.2　Input驅(qū)動模塊  258
16.3　Android系統(tǒng)對Input的使用  263
第17章　V4L2子系統(tǒng)  266
17.1　Linux V4L2一般子系統(tǒng)  266
17.1.1　V4L2數(shù)據(jù)結構  266
17.1.2　V4L2接口  268
17.1.3　V4L2虛擬驅(qū)動vivi  273
17.2　Android V4L2實踐  279
17.2.1　硬件基礎  280
17.2.2　CPU側CCIC驅(qū)動模塊  281
17.2.3　OV5642模組驅(qū)動模塊  283
17.3　Android系統(tǒng)對V4L2的使用  286
第18章　Binder IPC通信子系統(tǒng)  288
18.1　Binder驅(qū)動概述  288
18.2　Binder通信模型  288
18.3　Binder驅(qū)動  291
18.3.1　Binder相關的結構體  292
18.3.2　Android Binder子系統(tǒng)的架構設計  292
18.4　Binder的工作流程  293
第19章　USB子系統(tǒng)  295
19.1　USB協(xié)議基礎知識  295
19.1.1　USB物理連接  295
19.1.2　USB通信協(xié)議  297
19.2　USB子系統(tǒng)底層  299
19.2.1　USB Core  299
19.2.2　Linux USB gadget三層架構  303
19.3　Android USB子系統(tǒng)實踐  305
19.3.1　Android IPC通信補充  305
19.3.2　Android USB Mass Storage流程分析  309
第20章　Bootloader引導子系統(tǒng)  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