ARTS 第 4 周 - FileInputStream

发表于

Algorithm

这周做了一道 腾讯精选练习 50 题 中的中等题 LRU 缓存机制，容易想到的一个方案是：用一个 HashMap 存储数据 key 和 value，再用一个 LinkedList 放数据的 key，访问过的 key 移动到链表的头部（删除然后重新插入），满了就删除链表尾部的元素，但是这种方案由于移动到链表头部需要线性搜索，时间复杂度是 O(n)。其实有一种简单的时间复杂度是 O(1) 的解法：HashMap 仍然存储数据的 key，但是其 value 存储的是 LinkedList 节点的引用，LinkedList 的节点中存储数据的 key 和 value，这样移动到头部的操作就可以在 O(1) 时间完成了，我模仿 Java 的 LinkedList 实现了一个自己的 MyLinkedList，题解如下：

class LRUCache {
    private final Map<Integer, Node<Item>> map;
    private final MyLinkedList<Item> list;
    private final int capacity;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        list = new MyLinkedList<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node<Item> node = map.get(key);
            int value = node.item.value;
            moveToFirst(key, value);
            return value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            moveToFirst(key, value);
            return;
        }

        if (map.size() == capacity) {
            Item item = list.removeLast();
            map.remove(item.key);
        }

        addToFirst(key, value);
    }

    private void moveToFirst(int key, int value) {
        Node<Item> node = map.get(key);
        Item item = list.unlink(node);
        map.remove(item.key);
        addToFirst(key, value);
    }

    private void addToFirst(int key, int value) {
        Item item = new Item(key, value);
        Node<Item> node = list.addFirst(item);
        map.put(key, node);
    }

    private static class Item {
        private final int key;
        private final int value;

        public Item(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private static class Node<E> {
        private E item;
        private Node<E> next;
        private Node<E> prev;

        public Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    private static class MyLinkedList<E> {
        private Node<E> first, last;

        public Node<E> addFirst(E e) {
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            return newNode;
        }

        public E removeLast() {
            final Node<E> l = last;
            if (l == null)
                throw new RuntimeException("No such element");

            final E element = l.item;
            final Node<E> prev = l.prev;
            l.item = null;
            l.prev = null;
            last = prev;
            if (prev == null)
                first = null;
            else
                prev.next = null;
            return element;
        }

        private E unlink(Node<E> x) {
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;

            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }

            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }

            x.item = null;
            return element;
        }
    }
}

Review

因为想要研究下 Java 的 FileInputStream 的机制，这周读的是《The Linux Programming Interface》这本书的第 4 章《File I/O: The Universal I/O Model》，主要介绍了 open、read、write、close 这几个文件操作相关的系统调用。之所示称为 Universal I/O Model 是因为这些 API 适用于所有文件类型，例如管道、Socket 等，而不仅仅局限于磁盘上的文件。这本书的作者 Michael Kerrisk（1961-）是 Linux man-pages 的维护者，对 Linux 系统调用十分熟悉，这本书也写得非常好，被誉为 Linux 版的 APUE（Advanced Programming in the UNIX Environment），建议每个从事计算机后端相关工作的工程师都来读读。

Tip

Shell 中 for 循环的几种常见写法：

#!/bin/bash
 
for((i=1;i<=10;i++)); do echo ${i}; done
for i in {1..10}; do echo ${i}; done
for i in $(seq 1 10); do echo ${i}; done

for i in $(ls); do echo ${i}; done
for i in /Users/wind/*; do echo ${i}; done

Share

InputStream 这个抽象类是 Java 同步 IO 中的核心，读取操作都是基于 InputStream 的某个实现类做的，下图列出了常用的实现类，最近研究了一下 FileInputStream 这个实现类的机制，写篇文章总结一下。

FileInputStream

FileInputStream 用来读取文件，下面是一个按字节读取文件并打印的例子，其中 BufferedInputStream 是带缓冲的 Decorator，注意缓冲区的默认大小是 8192 字节：

public class FileInputStreamTest {
    public static void main(String[] args) throws IOException {
        // content: Test FileInputStream.
        String name = "/Users/wind/file.txt";
        try (BufferedInputStream in = new BufferedInputStream(new FileInputStream(name))) {
            while (true) {
                int b = in.read();
                if (b == -1) {
                    break;
                }
                // output: Test FileInputStream.
                System.out.print((char) b);
            }
        }
    }
}

接下来看一下 FileInputStream 的源码，它的 read 方法在内部直接调用了 native 方法 read0：

public class FileInputStream extends InputStream {
    ...
    public int read() throws IOException {
        return read0();
    }

    private native int read0() throws IOException;
    ...
}

Native Method

Java 通过 native 方法可以调用 C 或 C++ 的库函数，比较常见的用途是调用 glibc（The GNU C Library）中对系统调用的封装，就像上面说到的 read0 方法，最终会调用到 glibc 中的 read 函数，在追溯调用链之前先来看看 native 方法的机制：

NativeTest.java
// 生成字节码：javac NativeTest.java
// 生成头文件：javah -jni NativeTest
public class NativeTest {
    public native int plus(int i, int j);

    public static void main(String[] args) {
        System.loadLibrary("NativeTest");
        System.out.println(new NativeTest().plus(2, 40));
    }
}
NativeTest.h
/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class NativeTest */

#ifndef _Included_NativeTest
#define _Included_NativeTest
#ifdef __cplusplus
extern "C" {
#endif
/*
 * Class:     NativeTest
 * Method:    plus
 * Signature: (II)I
 */
JNIEXPORT jint JNICALL Java_NativeTest_plus
  (JNIEnv *, jobject, jint, jint);

#ifdef __cplusplus
}
#endif
#endif
NativeTest.c
// 设置 JAVA_HOME：JAVA_HOME=$(/usr/libexec/java_home)
// 生成动态链接库：gcc -dynamiclib -o libNativeTest.jnilib -I${JAVA_HOME}/include NativeTest.c
// MaxOS 下如果报找不到 jni_md.h 则：cd ${JAVA_HOME}/include; cp darwin/jni_md.h .
#include <jni.h>
#include "NativeTest.h"

JNIEXPORT jint JNICALL Java_NativeTest_plus(
    JNIEnv *env, jobject obj, jint i, jint j) {
  return i + j;
}

一切准备就绪之后，执行 Java NativeTest 如果看到输出 42，说明 Java 代码通过 native 方法正常调用到了 C 代码。

OpenJDK 8

从上面 native 方法的实验可以看到，Java 代码中只有 native 方法的签名，read0 的情况也正是这样，真正的实现在 C 代码中，可以查看 OpenJDK 8 的源文件 FileInputStream.c 一探究竟，其内部直接调用了 readSingle 函数，而 readSingle 的实现在 io_util.c 中：

// FileInputStream.c
...
NIEXPORT jint JNICALL
Java_java_io_FileInputStream_read(JNIEnv *env, jobject this) {
    return readSingle(env, this, fis_fd);
}
...
// io_util.c
...
jint
readSingle(JNIEnv *env, jobject this, jfieldID fid) {
    jint nread;
    char ret;
    FD fd = GET_FD(this, fid);
    if (fd == -1) {
        JNU_ThrowIOException(env, "Stream Closed");
        return -1;
    }
    nread = IO_Read(fd, &ret, 1);
    if (nread == 0) { /* EOF */
        return -1;
    } else if (nread == -1) { /* error */
        JNU_ThrowIOExceptionWithLastError(env, "Read error");
    }
    return ret & 0xFF;
}
...

readSingle 函数中的核心部分使用了 IO_Read 这个宏，在 io_util_md.h 可以看到宏定义 #define IO_Read handleRead，handleRead 函数实现在 io_util_md.c 中，调用的是 glibc 中的 read 函数：

// io_util_md.c
...
ssize_t
handleRead(FD fd, void *buf, jint len)
{
    ssize_t result;
    RESTARTABLE(read(fd, buf, len), result);
    return result;
}
...
#define RESTARTABLE(_cmd, _result) do { \
    do { \
        _result = _cmd; \
    } while((_result == -1) && (errno == EINTR)); \
} while(0)
...

GNU C Library

glibc 中的 read 函数定义在 unistd.h 头文件中，最后写一个直接使用这个 read 函数读取文件并输出的例子来结束这次 FileInputStream 的探索：

// unistd.h
...
ssize_t read(int fildes, void *buf, size_t nbyte);
...
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>

int main() {
    int fd = open("/Users/wind/file.txt", O_RDONLY);
    char c[2] = {'\0'};
    while (1) {
        ssize_t n = read(fd, c, 1);
        if (n == 0) {
            break;
        }
        // output: Test FileInputStream.
        printf("%s", c);
    }
    close(fd);
    return 0;
}

FileInputStream 还有两个重载的 read 方法，内部调用的都是 native 方法 readBytes，注意到 readBytes 在 io_util.c 的实现中优先使用一块栈内存 char stackBuf[8192]; 保存读取的结果，如果一次性读取的字节数超过 8192 就需要使用 malloc 分配堆内存，面临更多的开销。上面提到过 BufferedInputStream 缓冲区的默认大小是 8192 字节，这个数值的设置应该和 stackBuf 的默认大小是相关的。

0%