简介：这个快速指南将向你展示所有的基础 Git 命令以及用法。你可以下载这些命令作为快速参考。

我们在早先一篇文章中已经快速介绍过 Vi 速查表了。在这篇文章里，我们将会介绍开始使用 Git 时所需要的基础命令。

Git

Git 是一个分布式版本控制系统，它被用在大量开源项目中。它是在 2005 年由 Linux 创始人 Linus Torvalds 写就的。这个程序允许非线性的项目开发，并且能够通过存储在本地服务器高效处理大量数据。在这个教程里，我们将要和 Git 愉快玩耍并学习如何开始使用它。

我在这个教程里使用 Ubuntu，但你可以使用你选择的任何发行版。除了安装以外，剩下的所有命令在任何 Linux 发行版上都是一样的。

安装 Git

要安装 git 执行以下命令：

sudo apt-get install git-core

在它完成下载之后，你就安装好了 Git 并且可以使用了。

设置 Git

在 Git 安装之后，不论是从 apt-get 还是从源码安装，你需要将你的用户名和邮箱地址复制到 gitconfig 文件。你可以访问 ~/.gitconfig 这个文件。

全新安装 Git 之后打开它会是完全空白的：

sudo vim ~/.gitconfig

你也可以使用以下命令添加所需的信息。将‘user’替换成你的用户名，‘[email protected]’替换成你的邮箱。

git config --global user.name "User"
git config --global user.email [email protected]

然后你就完成设置了。现在让我们开始 Git。

仓库

创建一个新目录，打开它并运行以下命令：

git init

这个命令会创建一个新的 Git 仓库 （ repository ） 。你的本地仓库由三个 Git 维护的“树”组成。

第一个是你的 工作目录 （ Working Directory ） ，保存实际的文件。第二个是索引，实际上扮演的是 暂存区 （ staging area ） ，最后一个是 HEAD，它指向你最后一个 commit 提交。使用 git clone /path/to/repository 签出你的仓库（从你刚创建的仓库或服务器上已存在的仓库）。

添加文件并提交

你可以用以下命令添加改动：

git add <filename>

这会添加一个新文件到暂存区以提交。如果你想添加每个新文件，输入：

git add --all

添加文件之后可以使用以下命令检查状态：

git status

正如你看到的，那里已经有一些变化但还没有提交。现在你需要提交这些变化，使用：

git commit -m "提交信息"

你也可以这么做（首选）：

git commit -a

然后写下你的提交信息。现在你的文件提交到了 HEAD，但还不在你的远程仓库中。

推送你的改动

你的改动在你本地工作副本的 HEAD 中。如果你还没有从一个已存在的仓库克隆，或想将你的仓库连接到远程服务器，你需要先添加它：

git remote add origin <服务器地址>

现在你可以将改动推送到指定的远程服务器。要将改动发送到远程服务器，运行：

git push -u origin master

分支

分支用于开发特性，分支之间是互相独立的。主分支 master 是你创建一个仓库时的“默认”分支。使用其它分支用于开发，在完成时将它合并回主分支。

创建一个名为“mybranch”的分支并切换到它之上：

git checkout -b mybranch

你可以使用这个命令切换回主分支：

git checkout master

如果你想删除这个分支，执行：

git branch -d mybranch

除非你将分支推送到远程服务器上，否则该分支对其他人是不可用的，所以只需把它推送上去：

git push origin <分支名>

更新和合并

要将你本地仓库更新到最新的提交上，运行：

git pull

在你的工作目录获取并合并远程变动。要合并其它分支到你的活动分支（如 master），使用：

git merge <分支>

在这两种情况下，git 会尝试 自动合并 （ auto-merge ） 改动。不幸的是，这不总是可能的，可能会导致冲突。你需要通过编辑 git 所显示的文件，手动合并那些冲突。改动之后，你需要用以下命令将它们标记为已合并：

git add <文件名>

在合并改动之前，你也可以使用以下命令预览：

git diff <源分支> <目标分支>

Git 日志

你可以这么查看仓库历史：

git log

要以每个提交一行的样式查看日志，你可以用：

git log --pretty=oneline

或者也许你想要看一个所有分支的 ASCII 艺术树，带有标签和分支名：

git log --graph --oneline --decorate --all

如果你只想看哪些文件改动过：

git log --name-status

在这整个过程中如果你需要任何帮助，你可以用 git --help。

Git 棒不棒？！祝贺你你已经会 Git 基础了。如果你愿意的话，你可以从下面这个链接下载这些基础 Git 命令作为快速参考：

• 下载 Git 速查表

via: http://itsfoss.com/basic-git-commands-cheat-sheet/

作者：Rakhi Sharma 译者：alim0x 校对：wxy

本文由 LCTT 原创编译，Linux中国 荣誉推出

算法复杂度这件事

这篇文章覆盖了计算机科学里面常见算法的时间和空间的 大 O （ Big-O ） 复杂度。我之前在参加面试前，经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣，以便我在面试时不会被问住。最近这几年，我面试了几家硅谷的初创企业和一些更大一些的公司，如 Yahoo、eBay、LinkedIn 和 Google，每次我都需要准备这个，我就在问自己，“为什么没有人创建一个漂亮的大 O 速查表呢？”所以，为了节省大家的时间，我就创建了这个，希望你喜欢！

--- Eric

图例

数据结构操作

数组排序算法

图操作

堆操作

大 O 复杂度图表

推荐阅读

• Cracking the Coding Interview: 150 Programming Questions and Solutions
• Introduction to Algorithms, 3rd Edition
• Data Structures and Algorithms in Java (2nd Edition)
• High Performance JavaScript (Build Faster Web Application Interfaces)

贡献者

1. Eric Rowell, creator of Concrete.js, an HTML5 Canvas Framework
2. Quentin Pleple
3. Michael Abed
4. Nick Dizazzo
5. Adam Forsyth
6. David Dorfman
7. Jay Engineer
8. Jennifer Hamon
9. Josh Davis
10. Nodir Turakulov
11. Bart Massey
12. Vinnie Magro
13. Miguel Amigot
14. Drew Bailey
15. Aneel Nazareth
16. Rahul Chowdhury
17. Robert Burke
18. steven41292
19. Brandon Amos
20. Mike Davis
21. Casper Van Gheluwe
22. Joel Friedly
23. Oleg
24. Renfred Harper
25. Piper Chester
26. Eric Lefevre-Ardant
27. Jonathan McElroy
28. Si Pham
29. mcverry
30. Max Hoffmann
31. Alejandro Ramirez
32. Damon Davison
33. Alvin Wan
34. Alan Briolat
35. Drew Hannay
36. Andrew Rasmussen
37. Dennis Tsang
38. Bahador Saket

Credit: Moini

作为一个程序员，我知道我肯定会犯错误——怎么可能不犯错！程序员也是人啊。有的错误能在编码过程中及时发现，而有些却得等到软件测试了才能显露出来。然而，还有一类错误并不能在这两个阶段被解决，这就导致软件不能正常运行，甚至是提前终止。

如果你还没猜出是那种错误，我说的就是和内存相关的错误。手动调试这些错误不仅耗时，而且很难发现并纠正。值得一提的是，这种错误很常见，特别是在用 C/C++ 这类允许手动管理内存的语言编写的软件里。

幸运的是，现在有一些编程工具能够帮你在软件程序中找到这些和内存相关的错误。在这些工具集中，我评估了五款支持 Linux 的、流行的、自由开源的内存调试器： Dmalloc 、 Electric Fence 、 Memcheck 、 Memwatch 以及 Mtrace 。在日常编码中，我已经用过这五个调试器了，所以这些评估是建立在我的实际体验之上的。

Dmalloc

开发者：Gray Watson

评估版本：5.5.2

支持的 Linux 版本：所有种类

许可： CC 3.0

Dmalloc 是 Gray Watson 开发的一款内存调试工具。它是作为库来实现的，封装了标准内存管理函数如malloc() , calloc() , free()等，使程序员得以检测出有问题的代码。

Dmalloc

如同工具的网页所示，这个调试器提供的特性包括内存泄漏跟踪、 重复释放内存 （ double free ） 错误跟踪、以及 越界写入 （ fence-post write ） 检测。其它特性包括报告错误的文件/行号、通用的数据统计记录。

更新内容

5.5.2 版本是一个 bug 修正发行版，修复了几个有关构建和安装的问题。

有何优点

Dmalloc 最大的优点就是高度可配置性。比如说，你可以配置它以支持 C++ 程序和多线程应用。 Dmalloc 还提供一个有用的功能：运行时可配置，这表示在 Dmalloc 执行时，可以轻易地启用或者禁用它提供的一些特性。

你还可以配合 GNU Project Debugger (GDB)来使用 Dmalloc ，只需要将dmalloc.gdb文件（位于 Dmalloc 源码包中的 contrib 子目录里）的内容添加到你的主目录中的.gdbinit文件里即可。

另外一个让我对 Dmalloc 爱不释手的优点是它有大量的资料文献。前往官网的 Documentation 栏目，可以获取所有关于如何下载、安装、运行、怎样使用库，和 Dmalloc 所提供特性的细节描述，及其生成的输出文件的解释。其中还有一个章节介绍了一般问题的解决方法。

注意事项

跟 Mtrace 一样， Dmalloc 需要程序员改动他们的源代码。比如说你可以（也是必须的）添加头文件dmalloc.h，工具就能汇报产生问题的调用的文件或行号。这个功能非常有用，因为它节省了调试的时间。

除此之外，还需要在编译你的程序时，把 Dmalloc 库（编译 Dmalloc 源码包时产生的）链接进去。

然而，还有点更麻烦的事，需要设置一个环境变量，命名为DMALLOC_OPTION，以供工具在运行时配置内存调试特性，比如定义输出文件的路径。可以手动为该环境变量分配一个值，不过初学者可能会觉得这个过程有点困难，因为该值的一部分用来表示要启用的 Dmalloc 特性——以十六进制值的累加值表示。这里有详细介绍。

一个比较简单方法设置这个环境变量是使用 Dmalloc 实用指令，这是专为这个目的设计的方法。

总结

Dmalloc 真正的优势在于它的可配置选项。而且高度可移植，曾经成功移植到多种操作系统如 AIX 、 BSD/OS 、 DG/UX 、 Free/Net/OpenBSD 、 GNU/Hurd 、 HPUX 、 Irix 、 Linux 、 MS-DOG 、 NeXT 、 OSF 、 SCO 、 Solaris 、 SunOS 、 Ultrix 、 Unixware 甚至 Unicos（运行在 Cray T3E 主机上）。虽然使用 Dmalloc 需要学习许多知识，但是它所提供的特性值得为之付出。

Electric Fence

开发者：Bruce Perens

评估版本：2.2.3

支持的 Linux 版本：所有种类

许可：GPL v2

Electric Fence 是 Bruce Perens 开发的一款内存调试工具，它以库的形式实现，你的程序需要链接它。Electric Fence 能检测出堆内存溢出和访问已经释放的内存。

Electric Fence

顾名思义， Electric Fence 在每个所申请的缓存边界建立了虚拟围栏，这样一来任何非法的内存访问都会导致段错误。这个调试工具同时支持 C 和 C++ 程序。

更新内容

2.2.3 版本修复了工具的构建系统，使得 -fno-builtin-malloc 选项能真正传给 GNU Compiler Collection (GCC)。

有何优点

我喜欢 Electric Fence 的首要一点是它不同于 Memwatch 、 Dmalloc 和 Mtrace ，不需要对你的源码做任何的改动，你只需要在编译的时候把它的库链接进你的程序即可。

其次， Electric Fence 的实现保证了产生越界访问的第一个指令就会引起段错误。这比在后面再发现问题要好多了。

不管是否有检测出错误， Electric Fence 都会在输出产生版权信息。这一点非常有用，由此可以确定你所运行的程序已经启用了 Electric Fence 。

注意事项

另一方面，我对 Electric Fence 真正念念不忘的是它检测内存泄漏的能力。内存泄漏是 C/C++ 软件最常见也是最不容易发现的问题之一。不过， Electric Fence 不能检测出栈溢出，而且也不是线程安全的。

由于 Electric Fence 会在用户分配内存区的前后分配禁止访问的虚拟内存页，如果你过多的进行动态内存分配，将会导致你的程序消耗大量的额外内存。

Electric Fence 还有一个局限是不能明确指出错误代码所在的行号。它所能做只是在检测到内存相关错误时产生段错误。想要定位错误的行号，需要借助 GDB这样的调试工具来调试启用了 Electric Fence 的程序。

最后一点，尽管 Electric Fence 能检测出大部分的缓冲区溢出，有一个例外是，如果所申请的缓冲区大小不是系统字长的倍数，这时候溢出（即使只有几个字节）就不能被检测出来。

总结

尽管局限性较大， Electric Fence 的易用性仍然是加分项。只要链接一次程序， Electric Fence 就可以在监测出内存相关问题的时候报警。不过，如同前面所说， Electric Fence 需要配合像 GDB 这样的源码调试器使用。

Memcheck

开发者：Valgrind 开发团队

评估版本：3.10.1

支持的 Linux 发行版：所有种类

许可：GPL

Valgrind 是一个提供好几款调试和分析 Linux 程序性能的工具的套件。虽然 Valgrind 能和不同语言——Java 、 Perl 、 Python 、 Assembly code 、 ortran 、 Ada 等——编写的程序一起工作，但是它主要还是针对使用 C/C++ 所编写的程序。

Memcheck ，一款内存错误检测器，是其中最受欢迎的工具。它能够检测出如内存泄漏、无效的内存访问、未定义变量的使用以及堆内存分配和释放相关的问题等诸多问题。

更新内容

工具套件( 3.10.1 )主要修复了 3.10.0 版本发现的 bug 。除此之外，“从主干开发版本向后移植的一些补丁，修复了缺失的 AArch64 ARMv8 指令和系统调用”。

有何优点

同其它所有 Valgrind 工具一样， Memcheck 也是命令行程序。它的操作非常简单：通常我们会使用诸如 prog arg1 arg2 格式的命令来运行程序，而 Memcheck 只要求你多加几个值即可，如 valgrind --leak-check=full prog arg1 arg2 。

Memcheck

（注意：因为 Memcheck 是 Valgrind 的默认工具，所以在命令行执行命令时无需提及 Memcheck。但是，需要在编译程序之初带上 -g 参数选项，这一步会添加调试信息，使得 Memcheck 的错误信息会包含正确的行号。）

我真正倾心于 Memcheck 的是它提供了很多命令行选项（如上所述的--leak-check选项），如此不仅能控制工具运转还可以控制它的输出。

举个例子，可以开启--track-origins选项，以查看程序源码中未初始化的数据；可以开启--show-mismatched-frees选项让 Memcheck 匹配内存的分配和释放技术。对于 C 语言所写的代码， Memcheck 会确保只能使用free()函数来释放内存，malloc()函数来申请内存。而对 C++ 所写的源码， Memcheck 会检查是否使用了delete或delete[]操作符来释放内存，以及new或者new[]来申请内存。

Memcheck 最好的特点，尤其是对于初学者来说，是它会给用户建议使用哪个命令行选项能让输出更加有意义。比如说，如果你不使用基本的--leak-check选项， Memcheck 会在输出时给出建议：“使用 --leak-check=full 重新运行以查看更多泄漏内存细节”。如果程序有未初始化的变量， Memcheck 会产生信息：“使用 --track-origins=yes 以查看未初始化变量的定位”。

Memcheck 另外一个有用的特性是它可以创建 抑制文件 （ suppression files ） ，由此可以略过特定的不能修正的错误，这样 Memcheck 运行时就不会每次都报警了。值得一提的是， Memcheck 会去读取默认抑制文件来忽略系统库（比如 C 库）中的报错，这些错误在系统创建之前就已经存在了。可以选择创建一个新的抑制文件，或是编辑现有的文件(通常是/usr/lib/valgrind/default.supp)。

Memcheck 还有高级功能，比如可以使用定制内存分配器来检测内存错误。除此之外， Memcheck 提供监控命令，当用到 Valgrind 内置的 gdbserver ，以及客户端请求机制（不仅能把程序的行为告知 Memcheck ，还可以进行查询）时可以使用。

注意事项

毫无疑问， Memcheck 可以节省很多调试时间以及省去很多麻烦。但是它使用了很多内存，导致程序执行变慢（由文档可知，大概会花费 20 至 30 倍时间）。

除此之外， Memcheck 还有其它局限。根据用户评论， Memcheck 很明显不是线程安全的；它不能检测出 静态缓冲区溢出；还有就是，一些 Linux 程序如 GNU Emacs 目前还不能配合 Memcheck 工作。

如果有兴趣，可以在这里查看 Valgrind 局限性的详细说明。

总结

无论是对于初学者还是那些需要高级特性的人来说， Memcheck 都是一款便捷的内存调试工具。如果你仅需要基本调试和错误检查， Memcheck 会非常容易上手。而当你想要使用像抑制文件或者监控指令这样的特性，就需要花一些功夫学习了。

虽然罗列了大量的局限性，但是 Valgrind（包括 Memcheck ）在它的网站上声称全球有成千上万程序员使用了此工具。开发团队称收到来自超过 30 个国家的用户反馈，而这些用户的工程代码有的高达两千五百万行。

Memwatch

开发者：Johan Lindh

评估版本：2.71

支持的 Linux 发行版：所有种类

许可：GNU GPL

Memwatch 是由 Johan Lindh 开发的内存调试工具，虽然它扮演的主要角色是内存泄漏检测器，但是（根据网页介绍）它也具有检测其它如内存重复释放和错误释放、缓冲区溢出和下溢、野指针写入等等内存相关问题的能力。

Memwatch 支持用 C 语言所编写的程序。也可以在 C++ 程序中使用它，但是这种做法并不提倡（由 Memwatch 源码包随附的 Q&A 文件中可知）。

更新内容

这个版本添加了ULONG_LONG_MAX以区分 32 位和 64 位程序。

有何优点

跟 Dmalloc 一样， Memwatch 也有优秀的文档资料。参考 USING 文件，可以学习如何使用 Memwatch ，可以了解 Memwatch 是如何初始化、如何清理以及如何进行 I/O 操作，等等。还有一个 FAQ 文件，旨在帮助用户解决使用过程遇到的一般问题。最后还有一个test.c文件提供工作案例参考。

Memwatch

不同于 Mtrace ， Memwatch 产生的日志文件（通常是memwatch.log）是人类可阅读的格式。而且， Memwatch 每次运行时总会把内存调试结果拼接到输出该文件的末尾。如此便可在需要之时轻松查看之前的输出信息。

同样值得一提的是当你执行了启用 Memwatch 的程序， Memwatch 会在标准输出中产生一个单行输出，告知发现了错误，然后你可以在日志文件中查看输出细节。如果没有产生错误信息，就可以确保日志文件不会写入任何错误，多次运行的话确实能节省时间。

另一个我喜欢的优点是 Memwatch 还提供了在源码中获取其输出信息的方式，你可以获取信息，然后任由你进行处理（参考 Memwatch 源码中的mwSetOutFunc()函数获取更多有关的信息）。

注意事项

跟 Mtrace 和 Dmalloc 一样， Memwatch 也需要你往你的源文件里增加代码：你需要把memwatch.h这个头文件包含进你的代码。而且，编译程序的时候，你需要连同memwatch.c一块编译；或者你可以把已经编译好的目标模块包含起来，然后在命令行定义MEMWATCH和MW_STDIO变量。不用说，想要在输出中定位行号， -g 编译器选项也少不了。

此外， Memwatch 缺少一些特性。比如 Memwatch 不能检测出对一块已经被释放的内存进行写入操作，或是在分配的内存块之外的进行读取操作。而且， Memwatch 也不是线程安全的。还有一点，正如我在开始时指出，在 C++ 程序上运行 Memwatch 的结果是不能预料的。

总结

Memcheck 可以检测很多内存相关的问题，在处理 C 程序时是非常便捷的调试工具。因为源码小巧，所以可以从中了解 Memcheck 如何运转，有需要的话可以调试它，甚至可以根据自身需求扩展升级它的功能。

Mtrace

开发者: Roland McGrath 和 Ulrich Drepper

评估版本: 2.21

支持的 Linux 发行版：所有种类

许可：GNU GPL

Mtrace 是 GNU C 库中的一款内存调试工具，同时支持 Linux 上的 C 和 C++ 程序，可以检测由函数malloc()和free()不匹配的调用所引起的内存泄漏问题。

Mtrace

Mtrace 实际上是实现了一个名为mtrace()的函数，它可以跟踪程序中所有 malloc/free 调用，并在用户指定的文件中记录相关信息。文件以一种机器可读的格式记录数据，所以有一个 Perl 脚本——同样命名为 mtrace ——用来把文件转换并为人类可读格式。

更新内容

Mtrace 源码和 Perl 文件同 GNU C 库( 2.21 版本)一起释出，除了更新版权日期，其它别无改动。

有何优点

Mtrace 最好的地方是它非常简单易学。你只需要了解在你的源码中如何以及何处添加 mtrace() 及对应的 muntrace() 函数，还有如何使用 Mtrace 的 Perl 脚本。后者非常简单，只需要运行指令mtrace <program-executable> <log-file-generated-upon-program-execution>（例子见开头截图最后一条指令）。

Mtrace 另外一个优点是它的可伸缩性，这体现在不仅可以使用它来调试完整的程序，还可以使用它来检测程序中独立模块的内存泄漏。只需在每个模块里调用mtrace()和muntrace()即可。

最后一点，因为 Mtrace 会在mtrace()——在源码中添加的函数——执行时被触发，因此可以很灵活地使用信号动态地（在程序执行时）使能 Mtrace 。

注意事项

因为mtrace()和mauntrace()函数 —— 声明在mcheck.h文件中，所以必须在源码中包含此头文件 —— 的调用是 Mtrace 工作的基础（mauntrace()函数并非总是必要），因此 Mtrace 要求程序员至少改动源码一次。

需要注意的是，在编译程序的时候带上 -g 选项（ GCC 和 G++ 编译器均有提供），才能使调试工具在输出结果时展示正确的行号。除此之外，有些程序（取决于源码体积有多大）可能会花很长时间进行编译。最后，带 -g 选项编译会增加了可执行文件的大小（因为提供了额外的调试信息），因此记得程序需要在测试结束后，不带 -g 选项重新进行编译。

使用 Mtrace ，你需要掌握 Linux 环境变量的基本知识，因为在程序执行之前，需要把用户把环境变量MALLOC_TRACE的值设为指定的文件（mtrace()函数将会记录全部信息到其中）路径。

Mtrace 在检测内存泄漏和试图释放未经过分配的内存方面存在局限。它不能检测其它内存相关问题如非法内存访问、使用未初始化内存。而且，有人抱怨 Mtrace 不是线程安全的。

总结

不言自明，我在此讨论的每款内存调试器都有其优点和局限。所以，哪一款适合你取决于你所需要的特性，虽然有时候容易安装和使用也是一个决定因素。

要想捕获软件程序中的内存泄漏， Mtrace 最适合不过了。它还可以节省时间。由于 Linux 系统已经预装了此工具，对于不能联网或者不可以下载第三方调试调试工具的情况， Mtrace 也是极有助益的。

另一方面，相比 Mtrace ， Dmalloc 不仅能检测更多错误类型，还提供更多特性，比如运行时可配置、 GDB 集成。而且， Dmalloc 不像这里所说的其它工具，它是线程安全的。更不用说它的详细资料了，这让 Dmalloc 成为初学者的理想选择。

虽然 Memwatch 的资料比 Dmalloc 的更加丰富，而且还能检测更多的错误种类，但是你只能在 C 语言写就的程序中使用它。一个让 Memwatch 脱颖而出的特性是它允许在你的程序源码中处理它的输出，这对于想要定制输出格式来说是非常有用的。

如果改动程序源码非你所愿，那么使用 Electric Fence 吧。不过，请记住， Electric Fence 只能检测两种错误类型，而此二者均非内存泄漏。还有就是，需要基本了解 GDB 以最大化发挥这款内存调试工具的作用。

Memcheck 可能是其中综合性最好的了。相比这里提及的其它工具，它能检测更多的错误类型，提供更多的特性，而且不需要你的源码做任何改动。但请注意，基本功能并不难上手，但是想要使用它的高级特性，就必须学习相关的专业知识了。

via: http://www.computerworld.com/article/3003957/linux/review-5-memory-debuggers-for-linux-coding.html

作者：Himanshu Arora 译者：soooogreen 校对：PurlingNayuki,ezio

本文由 LCTT 原创编译，Linux中国 荣誉推出

基数树 （ Radix tree ）

正如你所知道的，Linux内核提供了许多不同的库和函数，它们实现了不同的数据结构和算法。在这部分，我们将研究其中一种数据结构—— 基数树 （ Radix tree ） 。在 Linux 内核中，有两个文件与基数树的实现和API相关：

• include/linux/radix-tree.h
• lib/radix-tree.c

让我们先说说什么是 基数树 吧。基数树是一种 压缩的字典树 （ compressed trie ） ，而字典树是实现了关联数组接口并允许以 键值对 方式存储值的一种数据结构。这里的键通常是字符串，但可以使用任意数据类型。字典树因为它的节点而与 n叉树 不同。字典树的节点不存储键，而是存储单个字符的标签。与一个给定节点关联的键可以通过从根遍历到该节点获得。举个例子：

               +-----------+
               |           |
               |    " "    |
               |           |
        +------+-----------+------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    g      |            |     c     |
   |           |            |           |
   +-----------+            +-----------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +-----------+            +-----------+
                                  |
                                  |
                            +-----v-----+
                            |           |
                            |     t     |
                            |           |
                            +-----------+

因此在这个例子中，我们可以看到一个有着两个键 go 和 cat 的 字典树 。压缩的字典树也叫做 基数树 ，它和 字典树 的不同之处在于，所有只有一个子节点的中间节点都被删除。

Linux 内核中的基数树是把值映射到整形键的一种数据结构。include/linux/radix-tree.h文件中的以下结构体描述了基数树：

struct radix_tree_root {
         unsigned int            height;
         gfp_t                   gfp_mask;
         struct radix_tree_node  __rcu *rnode;
};

这个结构体描述了一个基数树的根，它包含了3个域成员：

• height - 树的高度;
• gfp_mask - 告知如何执行动态内存分配;
• rnode - 孩子节点指针.

我们第一个要讨论的字段是 gfp_mask ：

底层内核的内存动态分配函数以一组标志作为 gfp_mask ，用于描述如何执行动态内存分配。这些控制分配进程的 GFP_ 标志拥有以下值：( GF_NOIO 标志)意味着睡眠以及等待内存，( __GFP_HIGHMEM 标志)意味着高端内存能够被使用，( GFP_ATOMIC 标志)意味着分配进程拥有高优先级并不能睡眠等等。

• GFP_NOIO - 睡眠等待内存
• __GFP_HIGHMEM - 高端内存能够被使用;
• GFP_ATOMIC - 分配进程拥有高优先级并且不能睡眠;

等等。

下一个字段是rnode：

struct radix_tree_node {
        unsigned int    path;
        unsigned int    count;
        union {
                struct {
                        struct radix_tree_node *parent;
                        void *private_data;
                };
                struct rcu_head rcu_head;
        };
        /* For tree user */
        struct list_head private_list;
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

这个结构体包含的信息有父节点中的偏移以及到底端(叶节点)的高度、子节点的个数以及用于访问和释放节点的字段成员。这些字段成员描述如下：

• path - 父节点中的偏移和到底端(叶节点)的高度
• count - 子节点的个数;
• parent - 父节点指针;
• private_data - 由树的用户使用;
• rcu_head - 用于释放节点;
• private_list - 由树的用户使用;

radix_tree_node 的最后两个成员—— tags 和 slots 非常重要且令人关注。Linux 内核基数树的每个节点都包含了一组 指针槽 （ slots ） ，槽里存储着指向数据的指针。在Linux内核基数树的实现中，空槽存储的是 NULL 。Linux内核中的基数树也支持 标签 （ tags ） ，它与 radix_tree_node 结构体的 tags 字段相关联。有了标签，我们就可以对基数树中存储的记录以单个 比特位 （ bit ） 进行设置。

既然我们了解了基数树的结构，那么该是时候看一下它的API了。

Linux内核基数树API

我们从结构体的初始化开始。有两种方法初始化一个新的基数树。第一种是使用 RADIX_TREE 宏：

RADIX_TREE(name, gfp_mask);

正如你所看到的，我们传递了 name 参数，所以通过 RADIX_TREE 宏，我们能够定义和初始化基数树为给定的名字。RADIX_TREE 的实现很简单：

#define RADIX_TREE(name, mask) \
         struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define RADIX_TREE_INIT(mask)   { \
        .height = 0,              \
        .gfp_mask = (mask),       \
        .rnode = NULL,            \
}

在 RADIX_TREE 宏的开始，我们使用给定的名字定义 radix_tree_root 结构体实例，并使用给定的 mask 调用 RADIX_TREE_INIT 宏。 而 RADIX_TREE_INIT 宏则是使用默认值和给定的mask对 radix_tree_root 结构体进行了初始化。

第二种方法是手动定义radix_tree_root结构体，并且将它和mask传给 INIT_RADIX_TREE 宏：

struct radix_tree_root my_radix_tree;
INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

INIT_RADIX_TREE 宏的定义如下:

#define INIT_RADIX_TREE(root, mask)  \
do {                                 \
        (root)->height = 0;          \
        (root)->gfp_mask = (mask);   \
        (root)->rnode = NULL;        \
} while (0)

和RADIX_TREE_INIT宏所做的初始化工作一样，INIT_RADIX_TREE 宏使用默认值和给定的 mask 完成初始化工作。

接下来是用于向基数树插入和删除数据的两个函数：

• radix_tree_insert;
• radix_tree_delete;

第一个函数 radix_tree_insert 需要3个参数：

• 基数树的根;
• 索引键;
• 插入的数据;

radix_tree_delete 函数需要和 radix_tree_insert 一样的一组参数，但是不需要传入要删除的数据。

基数树的搜索以两种方法实现：

• radix_tree_lookup;
• radix_tree_gang_lookup;
• radix_tree_lookup_slot.

第一个函数radix_tree_lookup需要两个参数：

• 基数树的根;
• 索引键;

这个函数尝试在树中查找给定的键，并返回和该键相关联的记录。第二个函数 radix_tree_gang_lookup 有以下的函数签名：

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
                                    void **results,
                                    unsigned long first_index,
                                    unsigned int max_items);

它返回的是记录的个数。 results 中的结果，按键排序，并从第一个索引开始。返回的记录个数将不会超过 max_items 的值。

最后一个函数radix_tree_lookup_slot将会返回包含数据的指针槽。

链接

• Radix tree
• Trie

via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/radix-tree.md

作者：[0xAX] 译者：cposture 校对：Mr小眼儿

本文由 LCTT 原创翻译，Linux中国 荣誉推出

Linux 内核中自己实现了双向链表，可以在 include/linux/list.h 找到定义。我们将会首先从双向链表数据结构开始介绍内核里的数据结构。为什么？因为它在内核里使用的很广泛，你只需要在 free-electrons.com 检索一下就知道了。

首先让我们看一下在 include/linux/types.h 里的主结构体：

struct list_head {
    struct list_head *next, *prev;
};

你可能注意到这和你以前见过的双向链表的实现方法是不同的。举个例子来说，在 glib 库里是这样实现的：

struct GList {
  gpointer data;
  GList *next;
  GList *prev;
};

通常来说一个链表结构会包含一个指向某个项目的指针。但是 Linux 内核中的链表实现并没有这样做。所以问题来了：链表在哪里保存数据呢？。实际上，内核里实现的链表是侵入式链表（Intrusive list）。侵入式链表并不在节点内保存数据-它的节点仅仅包含指向前后节点的指针，以及指向链表节点数据部分的指针——数据就是这样附加在链表上的。这就使得这个数据结构是通用的，使用起来就不需要考虑节点数据的类型了。

比如：

struct nmi_desc {
    spinlock_t lock;
    struct list_head head;
};

让我们看几个例子来理解一下在内核里是如何使用 list_head 的。如上所述，在内核里有很多很多不同的地方都用到了链表。我们来看一个在杂项字符驱动里面的使用的例子。在 drivers/char/misc.c 的杂项字符驱动 API 被用来编写处理小型硬件或虚拟设备的小驱动。这些驱动共享相同的主设备号：

#define MISC_MAJOR              10

但是都有各自不同的次设备号。比如：

ls -l /dev |  grep 10
crw-------   1 root root     10, 235 Mar 21 12:01 autofs
drwxr-xr-x  10 root root         200 Mar 21 12:01 cpu
crw-------   1 root root     10,  62 Mar 21 12:01 cpu_dma_latency
crw-------   1 root root     10, 203 Mar 21 12:01 cuse
drwxr-xr-x   2 root root         100 Mar 21 12:01 dri
crw-rw-rw-   1 root root     10, 229 Mar 21 12:01 fuse
crw-------   1 root root     10, 228 Mar 21 12:01 hpet
crw-------   1 root root     10, 183 Mar 21 12:01 hwrng
crw-rw----+  1 root kvm      10, 232 Mar 21 12:01 kvm
crw-rw----   1 root disk     10, 237 Mar 21 12:01 loop-control
crw-------   1 root root     10, 227 Mar 21 12:01 mcelog
crw-------   1 root root     10,  59 Mar 21 12:01 memory_bandwidth
crw-------   1 root root     10,  61 Mar 21 12:01 network_latency
crw-------   1 root root     10,  60 Mar 21 12:01 network_throughput
crw-r-----   1 root kmem     10, 144 Mar 21 12:01 nvram
brw-rw----   1 root disk      1,  10 Mar 21 12:01 ram10
crw--w----   1 root tty       4,  10 Mar 21 12:01 tty10
crw-rw----   1 root dialout   4,  74 Mar 21 12:01 ttyS10
crw-------   1 root root     10,  63 Mar 21 12:01 vga_arbiter
crw-------   1 root root     10, 137 Mar 21 12:01 vhci

现在让我们看看它是如何使用链表的。首先看一下结构体 miscdevice：

struct miscdevice
{
      int minor;
      const char *name;
      const struct file_operations *fops;
      struct list_head list;
      struct device *parent;
      struct device *this_device;
      const char *nodename;
      mode_t mode;
};

可以看到结构体miscdevice的第四个变量list 是所有注册过的设备的链表。在源代码文件的开始可以看到这个链表的定义：

static LIST_HEAD(misc_list);

它实际上是对用list_head 类型定义的变量的扩展。

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

然后使用宏 LIST_HEAD_INIT 进行初始化，这会使用变量name 的地址来填充prev和next 结构体的两个变量。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

现在来看看注册杂项设备的函数misc_register。它在一开始就用函数 INIT_LIST_HEAD 初始化了miscdevice->list。

INIT_LIST_HEAD(&misc->list);

作用和宏LIST_HEAD_INIT一样。

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

接下来，在函数device_create 创建了设备后，我们就用下面的语句将设备添加到设备链表：

list_add(&misc->list, &misc_list);

内核文件list.h 提供了向链表添加新项的 API 接口。我们来看看它的实现：

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

实际上就是使用3个指定的参数来调用了内部函数__list_add：

• new - 新项。
• head - 新项将会插在head的后面
• head->next - 插入前，head 后面的项。

__list_add的实现非常简单：

static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

这里，我们在prev和next 之间添加了一个新项。所以我们开始时用宏LIST_HEAD_INIT定义的misc 链表会包含指向miscdevice->list 的向前指针和向后指针。

这儿还有一个问题：如何得到列表的内容呢？这里有一个特殊的宏：

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

使用了三个参数：

• ptr - 指向结构 list_head 的指针；
• type - 结构体类型;
• member - 在结构体内类型为list_head 的变量的名字；

比如说：

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

然后我们就可以使用p->minor 或者 p->name来访问miscdevice。让我们来看看list_entry 的实现：

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

如我们所见，它仅仅使用相同的参数调用了宏container_of。初看这个宏挺奇怪的：

#define container_of(ptr, type, member) ({                      \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

首先你可以注意到花括号内包含两个表达式。编译器会执行花括号内的全部语句，然后返回最后的表达式的值。

举个例子来说：

#include <stdio.h>

int main() {
    int i = 0;
    printf("i = %d\n", ({++i; ++i;}));
    return 0;
}

最终会打印出2。

下一点就是typeof,它也很简单。就如你从名字所理解的，它仅仅返回了给定变量的类型。当我第一次看到宏container_of的实现时，让我觉得最奇怪的就是表达式((type *)0)中的0。实际上这个指针巧妙的计算了从结构体特定变量的偏移，这里的0刚好就是位宽里的零偏移。让我们看一个简单的例子：

#include <stdio.h>

struct s {
        int field1;
        char field2;
     char field3;
};

int main() {
    printf("%p\n", &((struct s*)0)->field3);
    return 0;
}

结果显示0x5。

下一个宏offsetof会计算从结构体起始地址到某个给定结构字段的偏移。它的实现和上面类似：

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

现在我们来总结一下宏container_of。只需给定结构体中list_head类型 字段的地址、名字和结构体容器的类型，它就可以返回结构体的起始地址。在宏定义的第一行，声明了一个指向结构体成员变量ptr的指针__mptr，并且把ptr 的地址赋给它。现在ptr 和__mptr 指向了同一个地址。从技术上讲我们并不需要这一行，但是它可以方便地进行类型检查。第一行保证了特定的结构体（参数type）包含成员变量member。第二行代码会用宏offsetof计算成员变量相对于结构体起始地址的偏移，然后从结构体的地址减去这个偏移，最后就得到了结构体。

当然了list_add 和 list_entry不是<linux/list.h>提供的唯一功能。双向链表的实现还提供了如下API：

• list\_add
• list\_add\_tail
• list\_del
• list\_replace
• list\_move
• list\_is\_last
• list\_empty
• list\_cut\_position
• list\_splice
• list\_for\_each
• list\_for\_each\_entry

等等很多其它API。

via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/dlist.md

译者：Ezio 校对：Mr小眼儿

本文由 LCTT 原创编译，Linux中国 荣誉推出

Eclipse 高级脚本环境（EASE）项目虽然还在开发中，但是必须要承认它非常强大，它让我们可以快速打造自己的Eclipse 开发环境。

依据 Eclipse 强大的框架，可以通过其内建的插件系统全方面的扩展 Eclipse。然而，编写和部署一个新的插件还是十分麻烦，即使你只是需要一个额外的小功能。不过，现在依托于 EASE，你可以不用写任何一行 Java 代码就可以方便的做到这点。EASE 是一种使用 Python 或者 Javascript 这样的脚本语言自动实现这些功能的平台。

本文中，根据我在今年北美的 EclipseCon 大会上的演讲，我将介绍如何用 Python 和 EASE 设置你的 Eclipse 环境，并告诉如何发挥 Python 的能量让你的 IDE 跑的飞起。

安装并运行 "Hello World"

本文中的例子使用 Python 的 Java 实现 Jython。你可以将 EASE 直接安装到你已有的 Eclipse IDE 中。本例中使用Eclipse Mars，并安装 EASE 环境本身以及它的模块和 Jython 引擎。

使用 Eclipse 安装对话框(Help>Install New Software...)，安装 EASE：http://download.eclipse.org/ease/update/nightly，

选择下列组件：

• EASE Core feature
• EASE core UI feature
• EASE Python Developer Resources
• EASE modules (Incubation)

这会安装 EASE 及其模块。这里我们要注意一下 Resource 模块，此模块可以访问 Eclipse 工作空间、项目和文件 API。

成功安装后，接下来安装 EASE Jython 引擎 https://dl.bintray.com/pontesegger/ease-jython/ 。完成后，测试下。新建一个项目并新建一个 hello.py 文件，输入：

print "hello world"

选中这个文件，右击并选择“Run as -> EASE script”。这样就可以在控制台看到“Hello world”的输出。

现在就可以编写 Python 脚本来访问工作空间和项目了。这种方法可以用于各种定制，下面只是一些思路。

提升你的代码质量

管理良好的代码质量本身是一件非常烦恼的事情，尤其是当需要处理一个大型代码库或者要许多工程师参与的时候。而这些痛苦可以通过脚本来减轻，比如批量格式化一些文件，或者去掉文件中的 unix 式的行结束符来使得在 git 之类的源代码控制系统中比较差异更加容易。另外一个更好的用途是使用脚本来生成 Eclipse markers 以高亮你可以改善的代码。这里有一些示例脚本，你可以用来在 java 文件中所有找到的“printStackTrace”方法中加入task markers 。请看源码。

拷贝该文件到工作空间来运行，右击并选择“Run as -> EASE script”。

loadModule('/System/Resources')

from org.eclipse.core.resources import IMarker

for ifile in findFiles("*.java"):
    file_name = str(ifile.getLocation())
    print "Processing " + file_name
    with open(file_name) as f:
        for line_no, line in enumerate(f, start=1):
            if "printStackTrace" in line:
                marker = ifile.createMarker(IMarker.TASK)
                marker.setAttribute(IMarker.TRANSIENT, True)
                marker.setAttribute(IMarker.LINE_NUMBER, line_no)
                marker.setAttribute(IMarker.MESSAGE, "Fix in Sprint 2: " + line.strip())

如果你的 java 文件中包含了 printStackTraces，你就可以看见任务视图和编辑器侧边栏上自动新加的标记。

自动构建繁琐任务

当同时工作在多个项目的时候，肯定需要完成许多繁杂、重复的任务。可能你需要在所有源文件头上加入版权信息，或者采用新框架时候自动更新文件。例如，当首次切换到 Tycho 和 Maven 的时候，我们需要 giel每个项目添加 pom.xml 文件。使用几行 Python 代码可以很轻松的完成这个任务。然后当 Tycho 支持无 pom 构建后，我们需要移除不要的 pom 文件。同样，几行代码就可以搞定这个任务，例如，这里有个脚本可以在每一个打开的工作空间项目上加入 README.md。请看源代码 add\_readme.py。

拷贝该文件到工作空间来运行，右击并选择“Run as -> EASE script”。

loadModule('/System/Resources')  
  
for iproject in getWorkspace().getProjects():
    if not iproject.isOpen():
        continue

    ifile = iproject.getFile("README.md")

    if not ifile.exists():
        contents = "# " + iproject.getName() + "\n\n" 
        if iproject.hasNature("org.eclipse.jdt.core.javanature"):
            contents += "A Java Project\n"
        elif iproject.hasNature("org.python.pydev.pythonNature"):
            contents += "A Python Project\n"
        writeFile(ifile, contents)

脚本运行的结果会在每个打开的项目中加入 README.md，java 和 Python 的项目还会自动加上一行描述。

构建新功能

你可以使用 Python 脚本来快速构建一些急需的功能，或者做个原型给团队和用户演示你想要的功能。例如，一个 Eclipse 目前不支持的功能是自动保存你正在工作的文件。即使这个功能将会很快提供，但是你现在就可以马上拥有一个能每隔 30 秒或处于后台时自动保存的编辑器。以下是主要方法的片段。请看下列代码：autosave.py。

def save_dirty_editors():
    workbench = getService(org.eclipse.ui.IWorkbench)
    for window in workbench.getWorkbenchWindows():
        for page in window.getPages():
            for editor_ref in page.getEditorReferences():
                part = editor_ref.getPart(False)
                if part and part.isDirty():
                    print "Auto-Saving", part.getTitle()
                    part.doSave(None)

在运行脚本之前，你需要勾选 'Allow Scripts to run code in UI thread' 设定，这个设定在 Window > Preferences > Scripting 中。然后添加该脚本到工作空间，右击并选择“Run as > EASE Script”。每次编辑器自动保存时，控制台就会输出一个保存的信息。要关掉自动保存脚本，只需要点击控制台的红色方块的停止按钮即可。

快速扩展用户界面

EASE 最棒的事情是可以将你的脚本与 IDE 界面上元素（比如一个新的按钮或菜单）结合起来。不需要编写 java 代码或者安装新的插件，只需要在你的脚本前面增加几行代码。

下面是一个简单的脚本示例，用来创建三个新项目。

# name      : Create fruit projects
# toolbar   : Project Explorer
# description   : Create fruit projects

loadModule("/System/Resources")

for name in ["banana", "pineapple", "mango"]:
    createProject(name)

上述注释会专门告诉 EASE 增加了一个按钮到 Project Explorer 工具条。下面这个脚本是用来增加一个删除这三个项目的按钮的。请看源码 createProjects.py 和 deleteProjects.py。

# name            :Delete fruit projects
# toolbar        : Project Explorer
# description    : Get rid of the fruit projects

loadModule("/System/Resources")

for name in ["banana", "pineapple", "mango"]:
    project = getProject(name)
    project.delete(0, None)

为了使按钮显示出来，增加这两个脚本到一个新的项目，假如叫做 'ScriptsProject'。然后到 Windows > Preference > Scripting > Script Location，点击 'Add Workspace' 按钮并选择 ScriptProject 项目。这个项目现在会成为放置脚本的默认位置。你可以发现 Project Explorer 上出现了这两个按钮，这样你就可以通过这两个新加的按钮快速增加和删除项目。

整合第三方工具

不管怎么说，你可能需要除了 Eclipse 生态系统以外的工具（这是真的，虽然 Eclipse 已经很丰富了，但是不是什么都有）。这些时候你会发现将他们包装在一个脚本来调用会非常方便。这里有一个简单的例子让你整合资源管理器，并将它加入到右键菜单栏，这样点击图标就可以打开资源管理器浏览当前文件。请看源码 explorer.py。

# name      : Explore from here
# popup     : enableFor(org.eclipse.core.resources.IResource)
# description   : Start a file browser using current selection
loadModule("/System/Platform")
loadModule('/System/UI')

selection = getSelection()
if isinstance(selection, org.eclipse.jface.viewers.IStructuredSelection):
    selection = selection.getFirstElement()

if not isinstance(selection, org.eclipse.core.resources.IResource):
    selection = adapt(selection, org.eclipse.core.resources.IResource)

if isinstance(selection, org.eclipse.core.resources.IFile):
    selection = selection.getParent()

if isinstance(selection, org.eclipse.core.resources.IContainer):
    runProcess("explorer.exe", [selection.getLocation().toFile().toString()])

为了让这个菜单显示出来，像之前一样将该文件加入一个新项目，比如说 'ScriptProject'。然后到 Windows > Preference > Scripting > Script Locations，点击“Add Workspace”并选择 'ScriptProject' 项目。当你在文件上右击鼠标键，你会看到弹出菜单出现了新的菜单项。点击它就会出现资源管理器。（注意，这个功能已经出现在 Eclipse 中了，但是你可以在这个例子中换成其它第三方工具。）

Eclipse 高级基本环境 （EASE）提供一套很棒的扩展功能，使得 Eclipse IDE 能使用 Python 来轻松扩展。虽然这个项目还在早期，但是关于这个项目更多更棒的功能也正在加紧开发中，如果你想为它做出贡献，请到论坛讨论。

我会在 2016 年的 Eclipsecon North America 会议上发布更多 EASE 细节。我的演讲 Scripting Eclipse with Python 也会不单会介绍 Jython，也包括 C-Python 和这个功能在科学领域是如何扩展的。

via: https://opensource.com/life/16/2/how-use-python-hack-your-ide

作者：Tracy Miranda 译者：VicYu/Vic020 校对：wxy

本文由 LCTT 原创编译，Linux中国 荣誉推出