Galex

Page 2 of 4

Linux内核中红黑树的实现

红黑树(Red–black tree)是一种自平衡的二叉搜索树。一棵红黑树具有下列性质:

  1. 结点颜色要么是红色,要么是黑色
  2. 根节点是黑色
  3. 所有叶子结点(位于树最底层的NULL结点)都是黑色
  4. 红色结点的孩子必须是黑色
  5. 每个结点到以它为根的子树的所有叶节点的路径上都包含相同数目的黑结点

下图既是一棵红黑树:红黑树的例子

红黑树的这些性质保证了从根结点到最远叶节点的距离不超过它到最近叶结点的距离的两倍。它是怎么保证的呢?假设根结点到叶结点的最短路径上黑结点的个数为N,根据性质5,最长路径上的黑结点也是N;又根据性质4,不可能有两个连续的红结点,所以最长路径上的总结点数最多为2N[......]

Read more

Linux内核中hash链表的实现

上一篇中介绍了双链表的实现,现在来看下hash链表是如何实现的。注意这里所说的“hash链表”和“hash表”的不同,hash链表是指映射到hash表中同一位置的所有元素组成的溢出链表。

hash链表的结构和双链表一样,也是内嵌到需要作为hash链表表元素的结构中。不同的是,双链表的表头和表元素是用相同的结构表示的(struct list_head),hash链表使用了不同的结构:

因为hash链表没有要求在O(1)时间内访问表尾,所以表头只需要一个指针,这样就节省了一个指针的空间。 hash表的特点是查找快速,前提[......]

Read more

Linux内核中双链表的实现

双链表是最常用的数据结构之一,在Linux内核中也不例外。下图表示了双链表在内核中的实现:

Linux中的双链表

可以看出,链表的组织是循环的,即第一个元素的前一项是链表中的最后一项,最后一项的下一项是链表的第一项。

我们在用到双链表时,通常会这样定义结构体:

内核提供了下列结构:

这样在需要双链表的结构中只需要加入一个 struct list_head 结构的成员:

在两个连续的链表项中间插入一[......]

Read more

【APUE】线程

一、概念

Linux中,可以将进程看作只有一个线程(主线程),线程是一种“轻量级”的进程。一个进程可以有多个线程,每个线程处理各自独立的任务。也就是所谓的“并发(concurrency)”,但并不等同于“并行(parallelism)”。真正意义上的并行只存在于多处理器系统中,而并发也可以存在于单处理器中。并行要求程序能够同时执行多个操作,而并发只要求程序能够假装同时执行多个操作,处理器的数量并不影响程序结构。

各线程有独自的线程ID、寄存器值、栈、调度优先级和策略、信号屏蔽字、errno变量以及线程私有数据,而进程的可执行的程序文本、全局内存和堆内存、栈以及文件描述符对该进程的所有线[......]

Read more

【APUE】信号

一、概念

信号是什么?信号本质上是在软件层次上对中断的一种模拟,即软件中断。提供了一种处理异步事件的方法。例如,在终端运行一个程序然后输入中断键,则会通过信号机制终止这个进程。

每个信号都有一个名字,这些名字都以SIG开头。在终端运行 kill -l 可以查看系统支持的所有信号。下面是在Linux中查看的结果:

可以看到,Linux支持62个信号。比较奇怪的是,紧接着31号的是34号,而且从34号开始,名字都是SIGRTMIN加或SIGRTMAX减去一个整数。

实际上,过去Linux系统是只支持前31个信号的,也就是所谓了经典信号,SIGRTMIN和SIGRTMAX[......]

Read more

【APUE】文件I/O

一、文件描述符

文件描述符是一个非负整数,用于标识一个文件。当打开或创建一个文件时,内核向进程返回一个文件描述符。

按照惯例,Unix系统的应用程序使用文件描述符0与标准输入关联,1和2分别与标准输出和标准错误输出关联。POSIX标准定义了符号常量STDIN_FILENO、STDOUT_FILENO、STDERR_FILENO分别代替0,1,2(在程序中使用符号常量而不是魔数是一个好的习惯)。它们定义在<unistd.h>中。

文件描述符的范围是0-OPEN_MAX,默认情况下,Linux允许每个进程打开1024个文件。

二、打开/关闭文件

#includ[......]

Read more

【C语言】表达式与操作符

一、简介

简单地说,一个表达式就是操作符和操作数组成的序列。例如,x = y +3

一个对象在一个表达式中的两个序列点之间只能被修改一次。

序列点(Sequence Point)

C标准规定代码中的某些点是序列点,当执行到一个序列点时,在此之前的副作用(Side Effect)必须全部作用完毕,在此之后的副作用必须一个都没发生。

标准中提到的序列点有:

  • 调用一个函数时,在所有准备工作做完之后、函数调用开始之前。比如调用foo(f(), g()) 时,foo 、f() 、g() 这三个表达式哪个先开始求值哪个后开始求值是未定义的(undefined),但是必须都求值[......]

Read more

« Older posts Newer posts »

Copyright © 2017 Galex

署名-非商业性使用-禁止演绎 3.0 | Creative Commons BY-NC-ND 3.0