Galex

Author: Galex (page 2 of 4)

Linux内核中红黑树的实现

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

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

Read more

Linux内核中hash链表的实现

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

hash链表的结构和双链表一样,也是内嵌到需要作为hash链表表元素的结构中。不同的是,双链表的表头和表[......]

Read more

Linux内核中双链表的实现

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

Linux中的双链表

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

我们在用到双链表时,通常会这样定义结构体:
[crayon-5a35168d84ec586[......]

Read more

【APUE】线程

一、概念

Linux中,可以将进程看作只有一个线程(主线程),线程是一种“轻量级”的进程。一个进程可以有多个线程,每个线程处理各自独立的任务。也就是所谓的“并发(concurrency)”,但并不等同于“并行(parallelism)”。真正意义上的并行只存在于多处理器系统中,而并发也可以存在于单[......]

Read more

【APUE】信号

一、概念

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

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

Read more

【APUE】文件I/O

一、文件描述符

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

按照惯例,Unix系统的应用程序使用文件描述符0与标准输入关联,1和2分别与标准输出和标准错误输出关联。POSIX标准定义了符号常量STDIN_FILENO、STDOUT_FI[......]

Read more

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

一、简介

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

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

序列点(Sequence Point)

C标准规定代码中的某些点是序列点,当执行到一个序列点时,在此之前的副作用(Side Effect)必须全[......]

Read more

Older posts Newer posts

Copyright © 2017 Galex

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