2011-12-24

網絡學堂feeds2mail

用網頁來看網絡學堂的公告很費時間，就打算像 rss2email 那樣，把消息製作成郵件。用 Ruby 的 mechanize 來和網站交互，讀取“課程公告”和“課程文件”中的消息，把鏈接 sha1 後判斷是否生成過提示郵件，沒有則跟蹤鏈接，用 w3m 輸出成純文本，生成的郵件用 sendmail 投遞。

2011-12-18

八數碼

八數碼問題，已訪問狀態採用 factorial number system 表示，未訪問的未使用（簡化代碼）實現了 Breadth First Search 和 Heuristic Search 兩種算法。帶上命令行選項 -g 能輸出 Graphviz 的 dot 格式的狀態樹。比較滿意的地方是把兩種搜索算法的共同部分抽象出來了，寫成了單獨的 search 函數。

2011-11-30

我的xmonad配置

缺點

依賴的模塊較多，升級 ghc 或被 xmonad/xmonad-contrib 依賴的包後需要按照拓撲序更新整個被 xmonad 依賴的樹。如果平時不大升級的就不用在意這一點。
沒有 systray 等其他 desktop environment 集成的組件，這方面 tiling window manager 世界中的 Awesome 可謂是佼佼者，其他 wm 都需要手動配置很多組件，Xmonad 也不例外。

優點

Xmonad 用 Haskell 配置，因為這一點註定了當配置復雜到一定程度後，會遠遠勝過那些自定義配置語言的 wm。
得到 monad transformer 精髓的 layout transformer 使得復合 layout 變得非常容易，可以輕易定製出在其他 wm 中不可能實現的 layout。

2011-09-28

Haskell實現的Splay樹

三週的軍訓總算挺過去了，這裏的網絡條件比想象中要糟糕不少。其實有很多要說，還是等到“十一長假”回家了再慢慢說吧。

廢話不多說了，這是一個用 Haskell 實現的 Top-down Splay tree：

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

2011-08-16

脫離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：

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

2011-08-13

用Perl的正則表達式分析csv文件

問題來自這個帖子。我沒理解錯的話，樓主的要求是替換分隔符。

這裏假設 csv 的規範是逗號分隔字段，允許字段中有雙引號引用的字符串，如果串內要表示雙引號，那麼用兩個雙引號代替。

2011-08-12

用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/ 下的某個文件。

2011-08-11