Haskell实现的Splay树

三周的军训总算挺过去了,这里的网络条件比想象中要糟糕不少。 其实有很多要说,还是等到“十一长假”回家了再慢慢说吧。

废话不多说了,这是一个用 Haskell 实现的 Top-down Splay tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
module SplayTree (
SplayTree,
splay,
insert,
delete,
empty,
) where

data SplayTree a = Nil | Node a (SplayTree a) (SplayTree a)
deriving (Eq, Show)

splay :: (Ord a) => (a -> Ordering) -> SplayTree a -> SplayTree a
splay comp t = walk t Nil Nil
where
walk Nil _ _ = Nil
walk t@(Node nx l r) lspine rspine =
case comp nx of
LT -> case l of
Nil -> final t lspine rspine
Node nl a b -> if comp nl == LT && a /= Nil then walk a lspine (Node nl rspine (Node nx b r))
else walk l lspine (Node nx rspine r)
GT -> case r of
Nil -> final t lspine rspine

Node nr c d -> if comp nr == GT && d /= Nil then walk d (Node nr (Node nx l c) lspine) rspine
else walk r (Node nx l lspine) rspine
EQ -> final t lspine rspine

final g@(Node x l r) lspine rspine = Node x (lfinal l lspine) (rfinal r rspine)
lfinal l Nil = l
lfinal l (Node y a b) = lfinal (Node y a l) b
rfinal r Nil = r
rfinal r (Node y a b) = rfinal (Node y r b) a

insert :: (Ord a) => a -> SplayTree a -> SplayTree a
insert key Nil = Node key Nil Nil
insert key t =
let t'@(Node nx l r) = splay (compare key) t
in if key < nx then Node key l (Node nx Nil r)
else Node key (Node nx l Nil) r

delete :: (Ord a) => a -> SplayTree a -> SplayTree a
delete key Nil = Nil
delete key t =
let t'@(Node nx l r) = splay (compare key) t
in case compare key nx of
EQ -> if l == Nil then r
else (\(Node nl a _) -> Node nl a r) $ splay (const GT) l
_ -> t'

empty = Nil

-- Test.QuickCheck

prop_insert_delete :: [Int] -> Bool
prop_insert_delete xs = foldr delete (foldr insert empty xs) xs == Nil

脱离chroot的枷锁

2015年8月更新

《The Linux Programming Interface》的Chapter 18 Directories and Links提到chroot jail有几个注意点:

  • chroot()不改变工作目录。因此通常在调用chroot()之后会紧跟chdir("/"),把工作目录设定到新的root;否则仍可使用工作目录访问jail外的文件。只是之后访问jail外的文件不可以用绝对路径了,因为root目录还在jail里。
  • 可以使用jail外文件的文件描述符脱离jail,使用fchdir()即可改变工作目录到jail外。如果是特权进程的话(精确地,指拥有CAP_SYS_CHROOT权限),还可以在fchdir()后使用chroot(".")以把root目录设置到jail外。倘若多chdir("..")几次,可以回到原先的root目录。
  • Unix domain socket提供了进程间传递文件描述符的方法。限定在chroot jail内的进程可以从外部获取文件描述符,之后即可fchdir()使工作目录脱离jail。

下面的例子展示如何使用jail外的文件描述符脱离jail:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <fcntl.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

int main(void)
{
int fd = open(".", O_RDONLY), i; // jail外的文件描述符,供之后脱离
mkdir("tempdir", 0755);
if (fd == -1) return 1;
if (chroot("tempdir") == -1) return 1; // chroot
if (fchdir(fd) == -1) return 1; // 脱离
for (i = 0; i < 1024; i++) // 回到原先的root目录。这里不能使用绝对路径`/`,只能逐步上移
chdir("..");
if (chroot(".") == -1) return 1; // 若是特权进程,则可进一步,把root设回去;不是的话也足以访问jail外的文件
system("ls");
return 0;
}

用udev自动挂载usb设备

前几天看了 udev 的介绍,今天正好 #ubuntu-cn@freenode 里有人问,就把这个老大难问题解决掉了。

代码如下:

KERNEL!="sd[b-z]?", GOTO="automount_exit"
ACTION=="add", SUBSYSTEM=="block", RUN+="/bin/mkdir /media/%E{ID_FS_LABEL}-%E{ID_FS_UUID}", RUN+="/bin/mount -o uid=1000,user,codepage=936,utf8 $root/%k /media/%E{ID_FS_LABEL}-%E{ID_FS_UUID}"
ACTION=="remove", SUBSYSTEM=="block", RUN+="/bin/umount /media/%E{ID_FS_LABEL}-%E{ID_FS_UUID}", RUN+="/bin/rmdir /media/%E{ID_FS_LABEL}-%E{ID_FS_UUID}"
LABEL="automount_exit"

保存为 /etc/udev/rules.d/ 下的某个文件。

Read More

在Makefile中自动生成依赖

论坛里有人写了一个用于自动生成C/C++依赖的脚本。但是他的脚本处理不同目录的源文件时会有些问题,.o 会生成在当前目录,而不是和 .cc 同一个目录。

gcc 其实有一些生成用于 Makefile 规则的选项,-M 等,说明如下:

  • -MM,忽略依赖中的系统头文件

  • -MF,指定生成的规则文件的路径

  • -MT,指定规则的目标

  • -MP,对每一个依赖创建一个 force target,典型输出:

    test.o: test.c test.h
    test.h:

    没有这个选项的话是不会有 test.h:

Read More

用rss2email阅读feeds

很久没用rss的阅读器了,以前曾用过 emacs 的 newsticker ,不支持HTML。也用过Google Reader,打开速度太慢,而且对Pentadactyl不友好。

把feeds转成邮件来阅读

我的想法是找一款工具,把feeds转换成邮件,由本地的procmail处理(归类),然后再用mutt阅读。

Read More

用Makefile搭建博客

缘起

我几乎不会 HTML,不会使用 Perl、Python 的库,不会 PHP 和 Ruby,不懂 JavaScript,但也想搭个博客。

尝试 WordPress

首先选择的是 WordPress,基本上是照着 这篇文章 做的,在 tusooa 和 phoenixlzx 的大力帮助下,注册了个 .tk 的域名和一个免费服务器,基本上算是搭起来了。不过有些不满意的地方,最讨厌的是它不是用标记语言写的,有些繁琐。

Read More

用Expect连接无线网络

垃圾的无线网卡驱动

我的无线网卡是 Broadcom BCM57780,这个东西,Linux下的无线驱动做得非常烂。以前我用Gentoo Portage中的net-wireless/broadcom-sta,后来听 microcai 的,直接在 menuconfig 里配置。这个驱动对应的模块名称是 brcmsmac,必须编译成模块(编译进内核的话,我没成功打开无线过)。它还需要 firmware,而且路径是定死的(使用其他名称是不行的,至少我没成功)。它在 dmesg 中的信息非常简略,如果你 firmware 的路径配置错的话,每次启动有一定机率 dmesg 会提示你正确的路径(这个……)。

Read More