Posts

Linux 核心代码中，对链表的排序算法是一种归并排序的变种。采用的排序方式为自下而上 的排序，这种方式可以避免 cache thrashing。 合并时机 Linux 中的对归并排序的改进主要是改变了两个链表的合并时机。该算法会有一个 pending 链表用来记录排序好的子链表，且保证每个子链表的长度都为 $2^k$。当 pending 中 即将出现第三个 $2^k$ 长度的链表时，就会合并已存在的两个 $2^k$ 长度的链表使其 变为一个 $2^{k+1}$ 长度的链表，所以在 pending 链表中永远不会存在超过 2 个 长度为 $2^k$ 的链表。 使用一个变量 count 来追踪 pending 中 $2^k$ 长度链表的个数，可以通过 count 中 k+1 k k-1 这 3 个 bits 来确定 pending 中 $2^k$ 长度链表的个数。下表 中的 3 个 bits 分别表示 k+1 k k-1，当 k 为 0 时，认为 -1 bit 为 1。 count $2^k$ 长度链表个数 …000… 0 …001… 0 …010… 0 …011… 1 …100… 1 …101… 2 源码分析 __attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp) { struct list_head *list = head->next, *pending = NULL; size_t count = 0; /* Count of pending */ if (list == head->prev) /* Zero or one elements */ return; /* Convert to a null-terminated singly-linked list. */ head->prev->next = NULL; // .... } 函数的参数： ...

原作者：Bram Moolenaar 发表日期：November 2000 原文章：Seven habits of effective text editing 原作者的 Talk：Talk 如果你经常编辑文本文件(比如，写代码或HTML)，你可以通过高效的使用一个好的编辑器 来节省大量的时间。这篇文章将提供一些让你可以减少错误和更快速编辑文件的方法。 本文将使用开源文本编辑器 VIM(Vi IMproved) 来展示这些高效编辑方法，当然这些方法 同样适用于其它文本编辑器。选择一个正确的编辑器是迈向高效编辑的第一步。关于你 适合使用什么样的编辑器这样的讨论，是非常浪费时间的本文不对这个问题进行讨论。但 如果你想要寻找一个合适的编辑器，可以尝试一下 VIM，我相信它不会让你失望的。 NOTE: VIM 命令和选项使用 this (font) 显示 Part 1: 编辑单个文件 1. 在文件中快速移动 其实，大部分情况下，当我们在编辑一个文件时，并不是真的在编辑它(输入文本/改变文本)， 而仅仅是在阅读它(检查错误/寻找一个位置来编辑)。浏览整个文件才是我们经常做的事情， 因此如何在文件中快速移动是我们要学习的第一件事。 在浏览文件时，我们可能经常想要搜索一段文本在文件的什么位置出现了，或找到所有 包含一个特定单词或短语的所有行。在 VIM 中，可以简单的使用搜索命令 /pattern 来查找文本，但可以使用一些更高效的方式来代替： 如果你想要查找一个单词是否在该文件的其它位置出现了，可以使用 * 命令来快速 搜素光标下的单词出现的下一个位置。# 做同样的事，但方向相反。 设置 incsearch 选项，这个选项会告诉 VIM 实时地匹配你输入的字符，以便你可以 立刻发现你的输入错误。 设置 hlsearch 选项，这个选项会告诉 VIM 高亮全部的匹配结果，以便你可以清楚地 知道当你按下 n 和 N 时，你的光标将会跳转到哪里。在写代码时这个功能可以让你 在不移动光标的情况下，看到一个变量被使用的位置。 对于结构化的文件 VIM 提供了一些更加快速的移动方式。对于 C-like 文件，可以使用 使用一些特定的命令，在某些特定的结构中快速移动。 ...

如何求一个正整数的平方根，最直接的方法就是 int i_sqrt(int N) { int res = 1; while (res * res <= N) { res++; } return res - 1; } 但上面的计算方法非常的低效，而对于求正整数的平方根，已经有非常多的算法。 下面介绍一个常用的正整数开平方根的算法。 Digit by digit calculation Digit by digit calculation 假设 $x = \sqrt{N}$ 则 $x^2 = N$ 以二进制表示 $x$，则 $x^2$ 为 $$ x^2 = (000b_0b_1b_2 \cdots b_{n-1}b_n)^2 \tag{1} $$ 其中，$b_0$ 为 $x$ 的二进制表示中第一个为 1 的二进制位。但要注意 $b_1 \cdots b_n$ 并不一定全为 1。我们可以将公式 (1) 改为加法形式。$a_n$ 对应的为 $b_0$。 $$ x^2 = (a_n + a_{n-1} + \cdots + a_1 + a_0)^2 \tag{2} $$ 其中，$a_m = 2^m$ 或 $a_m = 0$，取决于对应二进制位的值为 1 还是 0。将其展开可以得到 ...

文中代码 如果c++的类有虚函数那么这个类的实例对象就会有一个虚表. 我们可以通过一下代码来 改变虚表. #include <cstring> #include <iostream> class A { public: virtual void vfoo_1() { std::cout << "a_vfoo_1\n"; } virtual void vfoo_2(long long a) { std::cout << "a_vfoo_2: " << a << std::endl; } virtual int vfoo_3(int a, int b) { return a + b; } }; typedef void (*void_pfunc_void)(); typedef void (*void_pfunc_int)(long long); typedef int (*int_pfunc_int_int)(int, int); struct other_vtable { void_pfunc_void pf1; void_pfunc_int pf2; int_pfunc_int_int pf3; }; void g_f1() { std::cout << "g_f1\n"; } void g_f2(long long a) { ((A *)a)->vfoo_1(); printf("%p\n", (void *)a); // std::cout << "g_f2: " << a << std::endl; } int g_f3(int a, int b) { return b * 10; } int main(void) { A *a = new A; other_vtable *ovt = new other_vtable; ovt->pf1 = g_f1; ovt->pf2 = g_f2; ovt->pf3 = g_f3; void *ptr = a; printf("%p\n", a); a->vfoo_1(); a->vfoo_2(10); printf("a->vfoo_3: %d\n", a->vfoo_3(2, 5)); puts("-------------------------------"); memcpy(ptr, &ovt, sizeof(void *)); a->vfoo_1(); a->vfoo_2(10); printf("a->vfoo_3: %d\n", a->vfoo_3(2, 5)); int breakpoint = 0; return 0; } 内存布局大致如下图所示: ...

文中代码 1. 使用info vtbl obj查看vtable vtable function class A { public: A() = default; ~A() = default; virtual void vfoo_1() {} virtual void vfoo_2() {} }; int main(void) { A *a = new A; int breakpoint = 0; return 0; } 当一个class有virtual function时, 这个类会有一个vtable(virtual table)来记录这些函数的入口. 编译上面的代码, 使用gdb来debug这个程序, 使用info vtbl a可以可视化该实例对象a的vtable. 如下图所示: vtable class // A // / \ // / \ // B C // \ / // \ / // D class A { public: ~A() = default; virtual void a_foo() {} }; class B : virtual public A { public: virtual void b_foo() {} }; class C : virtual public A { public: virtual void c_foo() {} }; class D : public B, public C { public: }; int main(void) { D *d = new D; int breakpoint = 0; return 0; } 同样使用info vtbl d可以查看实例对象d的vtable. 如下图所示: ...