八数码问题，已访问状态采用 factorial number system 表示，未访问的未使用（简化代码） 实现了 Breadth First Search 和 Heuristic Search 两种算法。 带上命令行选项 -g 能输出 Graphviz 的 dot 格式的状态树。 比较满意的地方是把两种搜索算法的共同部分抽象出来了，写成了单独的 search 函数。

Read More

缺点

• 依赖的模块较多，升级 ghc 或被 xmonad/xmonad-contrib 依赖的包后需要按照拓扑序更新整个被 xmonad 依赖的树。 如果平时不大升级的就不用在意这一点。
• 没有 systray 等其他 desktop environment 集成的组件，这方面 tiling window manager 世界中的 Awesome 可谓是佼佼者， 其他 wm 都需要手动配置很多组件，Xmonad 也不例外。

优点

• Xmonad 用 Haskell 配置，因为这一点注定了当配置复杂到一定程度后，会远远胜过 那些自定义配置语言的 wm。
• 得到 monad transformer 精髓的 layout transformer 使得复合 layout 变得非常容易， 可以轻易定制出在其他 wm 中不可能实现的 layout。

Read More

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

废话不多说了，这是一个用 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

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;
}

问题来自这个帖子。我没理解错的话，楼主的要求是替换分隔符。

这里假设 csv 的规范是逗号分隔字段，允许字段中有双引号引用的字符串，如果串内要表示双引号，那么用两个双引号代替。

Read More

前几天看了 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

论坛里有人写了一个用于自动生成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

给别人打广告

tusooa 的脚本，主要用 Bash 和 Perl 写的，用了类似 GoboLinux 的组织方式，大家可以去看看。围观地址：[[https://github.com/tusooa/tusooa]] 。

Read More

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

把feeds转成邮件来阅读

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

Read More

缘起

前一篇用Makefile搭建博客说到我用inotifywait监控目录下文件的写操作来更新目录的修改时间，以后只要把make inotify放到启动脚本中就行了。但当时就发现了一个问题，一直拖到今天才解决掉。

Read More