将二叉树写到磁盘上

背景

有一阵子很好奇一个问题：MySQL到底是如何将内存中的B+树写入到磁盘文件中的。明明是一棵树，要怎样才能存储成线性的字节流呢？干脆自己动手，试着实现一个简单的版本，来帮助自己摸点门道。虽然想法很不错，不过一上来就面对噩梦级别的B+树也太为难人了，因此就先从简单的二叉树入手吧。

出来吧，二叉搜索树

本文使用Common Lisp进行开发。

首先定义这棵二叉搜索树的节点的类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defclass <node> ()
  ((data
    :accessor node-data
    :initarg :data
    :documentation "节点中的数据")
   (left
    :accessor node-left
    :initarg :left
    :documentation "左子树")
   (right
    :accessor node-right
    :initarg :right
    :documentation "右子树"))
  (:documentation "二叉搜索树的节点"))

基于节点进一步定义二叉树的类型

1
(deftype <bst> () '(or <node> null))

如此一来，要创建节点和空树都是浑然天成的事情了

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun make-node (data left right)
  "创建一个二叉搜索树的节点"
  (check-type data integer)
  (check-type left <bst>)
  (check-type right <bst>)
  (make-instance '<node>
                 :data data
                 :left left
                 :right right))

(defun make-empty-bst ()
  "创建一颗空树"
  nil)

要判断一颗二叉树是否为空树只需要简单包装一下cl:null函数即可

1
2
3
(defun empty-bst-p (bst)
  "检查BST是否为一个空的二叉搜索树"
  (null bst))

为了生成必要的测试数据，需要提供一个往二叉树中添加数据的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defun insert-node (bst data)
  "往一颗现有的二叉搜索树BST中加入一个数据，并返回这颗新的二叉搜索树"
  (check-type bst <bst>)
  (check-type data integer)
  (when (empty-bst-p bst)
    (return-from insert-node
      (make-node data
                 (make-empty-bst)
                 (make-empty-bst))))

  (cond ((< data (node-data bst))
         (setf (node-left bst)
               (insert-node (node-left bst) data))
         bst)
        (t
         (setf (node-right bst)
               (insert-node (node-right bst) data))
         bst)))

有了insert-node便可以从空树开始构筑起一棵二叉搜索树

1
2
3
4
5
6
7
(defun create-bst (numbers)
  "根据NUMBERS中的数值构造一棵二叉搜索树。相当于NUMBERS中的数字从左往右地插入到一棵空的二叉搜索树中"
  (check-type numbers list)
  (reduce #'(lambda (bst data)
              (insert-node bst data))
          numbers
          :initial-value (make-empty-bst)))

现在来生成稍后测试用的二叉树

1
(defvar *bst* (create-bst '(2 1 3)))

模仿命令行工具tree的格式，提供一个打印二叉树的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(defun print-spaces (n)
  "打印N个空格"
  (dotimes (i n)
    (declare (ignorable i))
    (format t " ")))

(defun print-bst (bst)
  "打印二叉树BST到标准输出"
  (check-type bst <bst>)
  (labels ((aux (bst depth)
             (cond ((empty-bst-p bst)
                    (format t "^~%"))
                   (t
                    (format t "~D~%" (node-data bst))
                    (print-spaces (* 2 depth))
                    (format t "|-")
                    (aux (node-left bst) (1+ depth))
                    (print-spaces (* 2 depth))
                    (format t "`-")
                    (aux (node-right bst) (1+ depth))))))
    (aux bst 0)))

二叉树*bst*的打印结果如下

1
2
3
4
5
6
7
2
|-1
  |-^
  `-^
`-3
  |-^
  `-^

接下来终于要写盘了

总算要开始实现将二叉树写入磁盘文件的功能了。将内存中的二叉树写入到文件中，相当于将树形的数据结构转换为线性的存储结构——毕竟磁盘上的文件可以认为就是线性的字节流。在这块字节流中，除了要保存每一个节点的数据之外，同样重要的还有节点间的父子关系。

有很多种写盘的方法。比如说，可以模仿树的顺序存储结构将二叉树序列化到磁盘上。以上面的二叉树*bst*为例，它是一棵满二叉树，如果采用顺序存储，那么首先分配一个长度为3的数组，在下标为0的位置存储根节点的数字2，在下标为1的位置存储左孩子的数字1，在下标为2的位置存储右孩子的数字3，如下图所示

推广到高度为h的二叉树，则需要长度为$2^h-1$的数组来存储所有节点的数据。假设每一个节点的数据都是32位整数类型，那么一棵高度为h的二叉树在磁盘上便需要占据$4·(2^h-1)$个字节。这个做法虽然可行，但比较浪费存储空间。它将节点间的父子关系用隐式的下标关系来代替，节省了存储左右子树的“指针”所需的空间，比较适合存储满二叉树或接近满的二叉树。

对于稀疏的二叉树，如果在序列化后的字节流中显式地记录节点间的父子关系，便可以节省很多不存在的节点所占据的存储空间。比如说，对于每一个节点，都序列化为磁盘上的12个字节：

  1. 下标为0到3的4个字节，存储的是节点中的数据；
  2. 下标为4到7的4个字节，存储的是节点的左子树在文件中的偏移；
  3. 下标为8到11的4个字节，存储的是节点的右子树在文件中的偏移

如下图所示

上面的数组表示磁盘上的一个文件，每一个方格为一个字节，每个方格在文件内的偏移从左往右依次增大。由于采用后序遍历的方式依次序列化二叉树中的节点数据和指针，因此左孩子首先被写入文件，然后是右孩子，最后才是根节点。推广到所有的二叉树，便是先将左右子树追加写入磁盘文件，再将根节点的数据、左子树根节点在文件内的偏移，以及右子树根节点在文件内的偏移追加到文件末尾；如果左右子树是空的，那么以偏移0表示。

这是一个递归的过程，而每一次递归调用应当返回两个值：

  1. 写入的总字节数bytes
  2. 根节点所占据的字节数root-bytes

bytes便是右子树开始写入时的文件偏移，必须依靠这个信息确定右子树的每一个节点在文件内的偏移；使用bytes减去root-bytes，再加上左子树开始写入时的偏移量，便可以得知左子树的根节点在文件内的位置。最终实现写盘功能的代码如下

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
57
58
;;; 定义序列化二叉树的函数
(defun write-fixnum/32 (n stream)
  "将定长数字N输出为32位的比特流"
  (check-type n fixnum)
  (check-type stream stream)
  (let ((octets (bit-smasher:octets<- n)))
    (setf octets (coerce octets 'list))
    (dotimes (i (- 4 (length octets)))
      (declare (ignorable i))
      (push 0 octets))
    (dolist (n octets)
      (write-byte n stream))))

;;; 这是一个递归的函数，写入一棵二叉树的逻辑，就是先写入左子树，再写入右子树，最后写入根节点，也就是后序遍历
;;; 由于要序列化为字节流，因此需要用字节流中的偏移的形式代替内存中的指针，实现从根节点指向左右子树
;;; offset是开始序列化bst的时候，在字节流中所处的偏移，同时也是这颗树第一个被写入的节点在字节流中的偏移
;;; 每次调用write-bst-bytes后的返回值有两个，分别为二叉树一共写入的字节数，以及根节点所占的字节数
(defun write-bst-bytes (bst stream offset)
  "将二叉树BST序列化为字节写入到流STREAM中。OFFSET表示BST的第一个字节距离文件头的偏移"
  (check-type bst <bst>)
  (check-type stream stream)
  (check-type offset integer)
  (when (empty-bst-p bst)
    (return-from write-bst-bytes
      (values 0 0)))

  ;; 以后序遍历的方式处理整棵二叉树
  (multiple-value-bind (left-bytes left-root-bytes)
      (write-bst-bytes (node-left bst) stream offset)

    (multiple-value-bind (right-bytes right-root-bytes)
        (write-bst-bytes (node-right bst) stream (+ offset left-bytes))

      (write-fixnum/32 (node-data bst) stream)
      (if (zerop left-bytes)
          (write-fixnum/32 0 stream)
          (write-fixnum/32 (- (+ offset left-bytes) left-root-bytes) stream))
      (if (zerop right-bytes)
          (write-fixnum/32 0 stream)
          (write-fixnum/32 (- (+ offset left-bytes right-bytes) right-root-bytes) stream))
      ;; 之所以要加上12个字节，是因为在写完了左右子树之后，就紧邻着写根节点了。因此，根节点就是在从right-node-offset的位置，接着写完右子树的根节点后的位置，而右子树的根节点占12个字节
      (let ((root-bytes (* 3 4)))
        (values (+ left-bytes right-bytes root-bytes)
                root-bytes)))))

(defun write-bst-to-file (bst filespec)
  "将二叉树BST序列化为字节流并写入到文件中"
  (check-type bst <bst>)
  (with-open-file (stream filespec
                          :direction :output
                          :element-type '(unsigned-byte 8)
                          :if-exists :supersede)
    (write-fixnum/32 (char-code #\m) stream)
    (write-fixnum/32 (char-code #\y) stream)
    (write-fixnum/32 (char-code #\b) stream)
    (write-fixnum/32 (char-code #\s) stream)
    (write-fixnum/32 (char-code #\t) stream)
    (write-bst-bytes bst stream (* 5 4))))

现在可以将*bst*写入文件了

1
(write-bst-to-file *bst* "/tmp/bst.dat")

使用hexdump验证写入的效果

文件最开始的五个字节依次存储着字符串"mybst"的ASCII码，为的就是让最早被写入文件中的根节点——也就是二叉树最左下角的节点——的偏移不为0，以免在后续反序列化的时候，从该节点的父节点中读到左子树的偏移为0——这样会被误认为是一棵空树的。

有哪里写得不好的还请各位读者不吝赐教。

在Emacs中搭建笔记查阅系统的尝试

给Emacs写插件有种痛并快乐着的感觉。虽然这个发挥创意的过程很有趣，但是Elisp写起来总有种别扭的感觉。一方面，我把它当成是Common Lisp，写的时候没有觉得“这个用法可能会有问题”；另一方面，它又不是普通的写lisp代码，还要一边写一边摸索Emacs中的一些概念。不过总体而言，还是挺好玩的，除了没有一个像模像样的REPL之外。

来龙去脉

我用Emacs记录了不少的“笔记”。虽说我自己将其称为笔记，但是它们更像是我把遇到的一些问题和解决方法给记录下来，而没有太多自己的感悟。它们的外观倒是高度的一致，见下图

（第一次尝试给自己的图片打水印，有点好玩）每一个一级条目都是一个问题，并且这个文件中只有一级条目。而条目下的内容则是对标题的问题的回答。其中还有代码块——也就是写着BEGIN_SRC和END_SRC的那部分。用org-mode来记录笔记有几个好处，其中一个便是可以在笔记中插入任何Emacs支持的编程语言代码片段并具备语法高亮。当然了，还有一个巨大的优势，便是org-mode尽管看似花里胡哨，骨子里却是正统的纯文本文件，它可以很方便地在其它工具中处理。

而我用来处理的其中一个工具便是ElasticSearch。比如说，上图的第一条笔记，在ElasticSearch中存成了下面这样的结构

本来我是写了一个Alfred的Workflow来查询ElasticSearch的，但是奈何Workflow那种一行行的方式展示org-mode格式的笔记不太友好，因此便打算直接在Emacs中查询并查看笔记内容。

牛刀小试

为了可以在Emacs中查看笔记内容，我打算借助于Helm的力量。Helm是Emacs的一个补全的框架，可以用来呈现一系列的候选项，然后选中后触发一些什么动作。我期望的形式，是在Emacs中按下某种快捷键或者输入某个命令行，可以在minibuffer中输入自己要查询的内容，然后Emacs查询ElasticSearch并最终通过Helm来呈现这些查询内容匹配的笔记条目。目前的成果是下面这样子的

具体的做法其实也很简单。首先，要知道Helm是如何被使用的。通过这篇文档，初步了解到只需要定一个变量，并通过:sources关键字参数传递给helm这个函数即可。我所定义的传递给helm函数的“source”如下

1
2
3
4
5
6
(setq faq-helm-sources
      `((name . "FAQ at Emacs")
        (candidates . faq-candidates)
        (action . (lambda (candidate)
                    (let ((url (format "http://localhost:9200/faq/_doc/%s" candidate)))
                      (browse-url url))))))

其中faq-candidates的作用便是根据minibuffer中的关键字查询ElasticSearch并组织好一个结构返回给helm。需要注意的是，faq-candidates必须是一个无参的函数才行，但输入的数据又偏偏需要从minibuffer中获取。因此，我的做法是约定一个变量faq-query，在调用helm之前首先调用read-from-minibuffer函数读取输入，然后将输入的字符串赋值给faq-query，之后当helm开始使用这个source的时候，faq-candidates函数便不需要参数，而可以直接从faq-query中拿到自己需要的搜索内容向ElasticSearch请求了。当然了，如果有像Common Lisp动态作用域的话，也就不需要定义这么一个全局变量了，对Emacs全局的侵入会更少一点。

目前能够做到的也仅仅是查询ElasticSearch，并在选中某个条目并按下回车的时候打开浏览器来查看而已，之后应该会继续完善。目前的完整代码如下

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
;;; 调用ElasticSearch查询笔记
(require 'request)

(defun faq (query)
  "向ElasticSearch查询QUERY匹配的笔记"
  (let ((response))
    (request
     "http://localhost:9200/faq/_search"
     :data (encode-coding-string
            (json-encode
             (list
              (cons "query" (list
                             (cons "multi_match" (list
                                                  (cons "fields" (list "answer" "question"))
                                                  (cons "query" query)))))))
            'utf-8)
     :headers '(("Content-Type" . "application/json"))
     :parser 'buffer-string
     :success (cl-function
               (lambda (&key data &allow-other-keys)
                 (setq data (decode-coding-string data 'utf-8))
                 (setq response (json-read-from-string data))))
     :sync t)
    response))

(defun make-faq-candidates (response)
  "将查询ElasticSearch的结果构造为helm可以识别的candidates格式"
  (let ((hits (cdr (assoc 'hits (cdr (assoc 'hits response))))))
    (mapcar (lambda (doc)
              (let ((_source (cdr (assoc '_source doc))))
                (cons (cdr (assoc 'question _source))
                      (cdr (assoc '_id doc)))))
            hits)))

(defvar faq-query nil)

(defun faq-candidates ()
  (make-faq-candidates (faq faq-query)))

(setq faq-helm-sources
      `((name . "FAQ at Emacs")
        (candidates . faq-candidates)
        (action . (lambda (candidate)
                    (let ((url (format "http://localhost:9200/faq/_doc/%s" candidate)))
                      (browse-url url))))))

(defun lt-ask ()
  "交互式地从minibuffer中读取笔记的关键词并展示选项"
  (interactive)
  (let ((content (read-from-minibuffer "笔记关键词：")))
    (setq faq-query content)
    (helm :sources '(faq-helm-sources))))

有不少值得吐槽的地方，不过都先按下不表吧，各位读者有兴趣的话可以留言交流一下XD

如何编译defun

本文讲解如何编译defun。在Common Lisp中，defun用于定义函数。例如，下列的代码定义了函数foo

1
2
3
4
(defun foo (a)
  "一个名为FOO的函数"
  (declare (ignorable a))
  (1+ 1))

在defun的语法中，第一行的字符串是这个函数的文档，可以用documentation函数获取；第二行是declaration。（不管是documentation还是declaration，也许要等到自举的那一天才能够支持了）目前只打算支持如下这般朴素的defun用法：

Read More

编译return语句

Common Lisp中有一个叫做return的宏，它的作用和平常在C、Java，或者Node.js里面见到的return关键字完全不一样。Common Lisp中的return用于从一个块（block）中返的，而不是从一个函数中返回。用return可以写出下面这样的代码，符号YOU-WILL-NOT-SEE-ME永远不会被打印

1
2
3
4
(defun foo ()
  (block nil
    (return 123)
    (print 'you-will-not-see-me)))

求值return，就将123作为block的返回值从中返回了，后面的print并没有机会执行——在SBCL中编译上面这段defun的时候，编译器甚至已经给出了提醒

Read More

一个有用的org-agenda-custom-commands的例子

好久没有写了，文章的开头，照例还是要吹吹水的。

自从更新了基于org-mode的待办事项的管理模式后，感觉整个人都日益神清气爽起来。究其原因，大概是因为现在处理inbox.org和安排第二天的行程的时候，有一个相对可行的操作方法可以参考了，所以每次处理这两件事情的时候，也就没有那么纠结了。同时，还因为采取了一种尽量goal-oriented的TODO管理方法，最大程度上杜绝了一些不必要的TODO被收集起来，从而也减轻了内心的焦虑感。

言归正传，这篇文章是要讲一个我自定义的org-mode的Agenda视图的command的。这条命令是下面这样子的

1
2
3
(setq org-agenda-custom-commands
      '(("f" "查看TODO条目（按创建时间排序）" todo "TODO"
         ((org-agenda-sorting-strategy '(priority-down time-up))))))

俗话说的好，要检验自己是不是懂得某个东西，只要看看自己能不能把这个东西给别人讲清楚就可以了。如果讲清楚了，没有哪里需要emmmm的地方，那么就可以认为这个东西基本上自己是真的懂得了。

那么org-agenda-custom-commands是干嘛用的呢。官方文档的链接在这里：https://orgmode.org/worg/org-tutorials/org-custom-agenda-commands.html ——哎哟喂，其实如果你们身处在Emacs之中来看这篇文章的话，只要按下C-h v，然后在minibuffer中输入org-agenda-custom-commands的话，也就可以看到关于这个变量的说明了啦。不过上面这个文档的好处是它有附赠一些例子。

总而言之，org-agenda-custom-commands是一个变量，通过给这个变量赋值，可以在org-mode的Agenda视图中，添加一些自定义的功能及对应的快捷键。例如，如果在Emacs中求值我上面所给的Elisp代码，然后按下C-c a，便会看到类似于下面这样的提示

这时候，如果按下f键，Emacs就会按照上面代码中描述的那样找出所有关键字为TODO的条目，然后按照【先优先级降序，然后时间戳升序】的方式来排列它们。在我的电脑上的效果如下图所示

可以看到，首先出现的条目是标注为最高的A优先级的两条，然后是在heading内容的开头含有时间戳的条目。

对我来说，这样的一个好处是可以将未处理过的TODO按照时间顺序列出来，从而避免了所有的TODO条目先是按照文件的名称集中起来，然后又按照它们在文件中的顺序从上往下地排列起来。毕竟文件内的TODO都是聚合在各自不同的更高级的heading之下的，它们之间的上下关系体现不出什么东西。

调用C标准库的exit函数

在上一篇文章中，实现了对大于号（>）的处理，那么对if表达式的编译也就是信手拈来的事了，不解释太多。在本篇中，将会讲述一下如何产生可以调用来自于C语言标准库的exit(3)函数的汇编代码。

在Common Lisp中并没有一个叫做EXIT的内置函数，所以如同之前实现的_exit一样，我会新增一种需要识别的(first expr)，即符号exit。为了可以调用C语言标准库中的exit函数，需要遵循调用约定。对于exit这种只有一个参数的函数而言，情形比较简单，只需要跟对_exit一样处理即可。刚开始，我写下的代码是这样的

Read More

编译大于运算符

原定的计划中这一篇应当是要讲如何编译if表达式的，但是我发现没什么东西可以作为if的test-form的部分的表达式，所以觉得，要不还是先实现一下比较两个数字这样子的功能吧。说干就干，我决定用大于运算符来作为例子——大于运算符就是指>啦。所以，我的目标是要编译下面这样的代码

1
(> 1 2)

Read More

inside-out/aux如何支持对_exit的调用

在上一篇文章中，新增了两个函数：inside-out以及inside-out/aux——曾经想过将inside-out/aux放到前者的函数中用labels来定义，但担心不好调试，所以剥离了出来成为一个独立的函数——inside-out基本上只是驱动了后者，真正地将嵌套表达式拆解开来的还是inside-out/aux。因此，为了让让这个编译器最终可以处理如下形式的代码

1
(_exit (+ (+ 1 2) 3))

就需要先对inside-out/aux进行一番改造，使其可以处理上述代码。

在此之前，先处理一下inside-out/aux目前的一些问题。在之前的实现中，由于使用了setf对输入参数expr进行了修改，因此在example3中的列表实际上在第二次运行的时候已经不是代码中看到的那样子了。所以，先将inside-out/aux改写为更pure的形式

Read More

时序图绘制工具走马观花

为什么我会需要绘制时序图

我司在做一些咋看之下比较复杂的需求的时候，都需要先写设计文档，不过我猜想这种规矩应该在很多公司都有才对，我并没有其它公司没有这种规矩的言外之意。然后呢，我个人比较习惯按照“从外到内”的方式来写设计文档，因此，在文档的开篇我总是会描述一下一个需求的全局视图，一般来说，就是用绘图的方式。对于一些复杂的活动需求里的流程，咋一看觉得会涉及到多个系统间的调用的时候，我就会选择画一幅时序图了。

需要事先说明的是，我没有正儿八经地系统学习过UML方面的内容，所以我画出来的图都只是一些不算很规范的野鸡时序图，当然了，我也不知道这世界上到底有没有规范的时序图画法。

为了画时序图，用过几款工具。它们的共同点，就是都是“语绘”的，也就是通过写代码的方式来描述所想要的图，然后让这些工具帮你把这张图给“画出来”。我个人更喜欢这种方式，而不是拖拖拉拉，不过这纯粹是个人喜好的问题而已。

走马观花

www.websequencediagrams.com是我接触到的第一个“语绘”时序图的工具。打开它之后，就会看到它的实例代码和效果图了，截图如下

用这个网站的工具画出来的时序图会有一种【手绘】的感觉

sdedit是我第二款使用的绘图工具，是一款用Java开发的本地工具，只需要编写好一个.sd文件，然后用下列的命令处理即可

1
sdedit -t png -o a.png a.sd

sdedit绘制时序图的代码的语法跟WebSequenceDiagrams不同，在Emacs中似乎也没有找到别人写好的适合编辑.sd文件的主模式，后来我自己定义了一个简陋的主模式来用，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(setq sdedit-highlights
      '(("Actor\\|Node" . font-lock-function-name-face)))

(define-derived-mode sdedit-mode fundamental-mode "sdedit"
  "编辑.sd文件的主模式"
  (setq font-lock-defaults '(sdedit-highlights)))

;;; 代码是从下面这个网页给的例子改动来的
;;; https://www.emacswiki.org/emacs/CompileCommand
(add-hook 'sdedit-mode-hook
          (lambda ()
            (unless (file-exists-p "Makefile")
              (set (make-local-variable 'compile-command)
                   (let* ((buffer-name (buffer-name))
                          (base-name (car (split-string buffer-name "\\."))))
                     (format "/usr/local/bin/sdedit -t png -o %s.png %s.sd" base-name base-name))))))

(add-to-list 'auto-mode-alist
             '("\\.sd$" . sdedit-mode))

勉勉强强可以接受

sequencediagram.org则是最近刚发掘到的一个不错的绘制时序图的在线工具。它的绘制语法跟WebSequenceDiagrams是一样的，并且它还有一个不错的教程。打开它的网站后，点击左侧的这个图标

便可以看到详尽的语法教程。

sequencediagram.org绘制出来的时序图是这三个工具中最符合我的审美的，今后应当会成为我绘制时序图的主力工具。