Steve is just a guy seeking happiness, value, and doing something good along the way.
- Email Me if you want, will reply though there may be some delay
- Stack Overflow
Blog repo.
Steve is just a guy seeking happiness, value, and doing something good along the way.
WARNING: This post is labeled
Uncertain/Unresolved
, read at your own risk.
Sparse file: There is a case where a file contains a large, continuous range of empty
bytes(a.k.a 0), so instead of allocating these useless zeros on the underlying
disks, we simply add some information to its metadata to indicate its existence.
Thus, such a sparse file will consume less storage compared with a normal file.
Hole: Refers to a sequence of empty zero bytes that are not allocated on the
disk.
Data: Bytes that are literally allocated on the disk.
Reading hole from a sparse file will return 0
as if you were reading a real block
filled with bytes 0. This process/conversion is done by the file system at runtime.
So there is no way for a normal application to tell if it is reading a hole or
real data.
Using lseek(2)
to reposition the offset beyond the end of the file and write(2)
some bytes here can create a sparse file
/*
* create_sparse_file.c
*
* error handling is omitted for simplicity
*/
#include <fcntl.h>
#include <unistd.h>
int main(void)
{
int fd = open("sparse_file", O_CREAT | O_WRONLY | O_TRUNC, 0666);
lseek(fd, 10000, SEEK_CUR);
write(fd, "HELLO", 5);
close(fd);
return 0;
}
Using truncate(1)
$ truncate -s 2k sparse_file
The above command will create a 2KiB file with contents 0
Using dd(1)
dd of=sparse_file bs=2K seek=1 count=0
If an existing file contains a large range of zeros, it can be converted into
a sparse file.
Using cp(1) --sparse=always
GNU cp
has an option sparse
which can be passed auto/always/never
. When
auto
is given, cp
will automatically detect the holes in the source file and
write them to the dest file, which is the default behavior of cp
.
Argument always
will make any bytes sequence that can be a hole be a hole. And never
will never create holes even though there are holes in the original file.
$ cp --sparse=always normal_file sparse_file
Using fallocate(1)
$ fallocate -d sparse file
Using find(1)
GNU find
can print a file's sparseness using -printf "%S"
, which is calculated
as (BLOCKSIZE*st_blocks / st_size).
For a partial sparse file, the return value should be less than 1, and for a total
sparse file, it will return 0.
$ find -type=f -printf"%S\t%p\n"
Using du(1)
Normally a sparse file's apparent size is smaller than its real size cause it
consumes less disk storage.
$ du -h sparse_file
0 sparse_file
$ du -h --apparent-size sparse_file
2k sparse_file
Using lseek(2)
and its arguments SEEK_HOLE
and SEEK_DATA
This program iterates over all the hole and data segments and prints it line
by line.
#define _GNU_SOURCE
#include <assert.h>
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
enum Type {
HOLE,
DATA,
};
void find_all_holes(int fd);
int main(int ac, char *av[])
{
int fd = open(av[1], O_RDONLY);
if (fd == -1) {
perror("open");
exit(EXIT_FAILURE);
}
find_all_holes(fd);
return 0;
}
void find_all_holes(int fd)
{
off_t cur_offset = 0; // current offset
enum Type cur_type; // current byte type
off_t file_size = lseek(fd, 0, SEEK_END);
off_t index_of_last_byte = file_size - 1;
printf("This file has %ld bytes\n", file_size);
// where are we? HOLE or DATA
off_t res = lseek(fd, 0, SEEK_HOLE);
if (res == 0) {
cur_type = HOLE;
} else if (res == file_size) {
printf("[0, %ld]: data(then exit)\n", index_of_last_byte);
exit(0);
} else {
cur_type = DATA;
cur_offset = res;
}
while (cur_offset <= index_of_last_byte) {
off_t new_offset =
lseek(fd, cur_offset,
((cur_type == DATA) ? SEEK_HOLE : SEEK_DATA));
if ((cur_type == HOLE && new_offset == -1 && errno == ENXIO) ||
(cur_type == DATA && new_offset == file_size)) {
// from current position to the end of this file: `cur_type`
printf("[%ld, %ld]: %s(end)\n", cur_offset,
index_of_last_byte,
((cur_type == DATA) ? "data" : "hole"));
break; // exit of while loop
} else {
// from current offset to the new offset: `cur_type`
printf("[%ld, %ld]: %s\n", cur_offset, new_offset - 1,
((cur_type == DATA) ? "data" : "hole"));
cur_offset = new_offset;
cur_type = (cur_type == DATA) ? HOLE : DATA;
}
}
}
It seems that whether we can create a sparse file using lseek(2)
is decided by
file system. For example creat("maybe_a_sparse_file");lseek(fd, 10);write(fd, "hello")
will not make a sparse file. Maybe fs thinks the overhead of making
such a sparse file is too expensive.
Currently, I have no idea in what cases it is suitable for fs to create a hole
instead of allocating blocks on disk.
Neovim has its own clipboard buffer, but I don't like it, so when using it, I always make it sync with my system clipboard through the following configuration:
vim.opt.clipboard:append("unnamedplus")
This morning, I needed to test an issue with multiple versions of Neovim, so I decided to give bob
a try. Honestly, this package manager is pretty good, download and switches are done within a few seconds, blazingly fast!
However, when using the nvim
installed through bob
, I found my system clipboard integration was no longer working. Alright, then let's try to figure out what's wrong here, Read The Fxxking Manual
, executing :help clipboard
inside nvim
tells us that:
Nvim has no direct connection to the system clipboard. Instead it depends on
a |provider| which transparently uses shell commands to communicate with the
system clipboard or any other clipboard "backend".
To ALWAYS use the clipboard for ALL operations (instead of interacting with
the "+" and/or "*" registers explicitly): >vim
set clipboard+=unnamedplus
See 'clipboard' for details and options.
*clipboard-tool*
The presence of a working clipboard tool implicitly enables the '+' and '*'
registers. Nvim looks for these clipboard tools, in order of priority:
- |g:clipboard|
- pbcopy, pbpaste (macOS)
- wl-copy, wl-paste (if $WAYLAND_DISPLAY is set)
- waycopy, waypaste (if $WAYLAND_DISPLAY is set)
- xclip (if $DISPLAY is set)
- xsel (if $DISPLAY is set)
- lemonade (for SSH) https://github.com/pocke/lemonade
- doitclient (for SSH) https://www.chiark.greenend.org.uk/~sgtatham/doit/
- win32yank (Windows)
- termux (via termux-clipboard-set, termux-clipboard-set)
- tmux (if $TMUX is set)
From the documentation, we can know that nvim
itself has no capacity to communicate with the system clipboard, it needs some external command line tools to help it handle that, and this documentation lists all the available tools in order of priority.
With this, I kinda think that maybe such a tool is missing on my machine, and my guess is right. :checkhealth
explicitly tells us that:
provider: health#provider#check
Clipboard (optional) ~
- WARNING No clipboard tool found. Clipboard registers (`"+` and `"*`) will not work.
- ADVICE:
- :help |clipboard|
This is weird, I don't recall that I have installed one of the above tools and all I did in the past is simply executing
sudo dnf install neovim
to install nvim
itself.
Is it possible that dnf
will help me install one of the above tools at the same time as installing nvim
, to verify this:
$ sudo dnf install neovim
[sudo] password for steve:
Last metadata expiration check: 2:30:56 ago on Mon 02 Jan 2023 01:55:22 PM CST.
Dependencies resolved.
================================================================================
Package Arch Version Repository Size
================================================================================
Installing:
neovim x86_64 0.8.1-1.fc36 updates 5.8 M
Installing dependencies:
compat-lua-libs x86_64 5.1.5-20.fc36 fedora 167 k
libtermkey x86_64 0.22-2.fc36 fedora 29 k
libtree-sitter x86_64 0.20.7-1.fc36 updates 97 k
libvterm x86_64 0.3-1.fc36 updates 43 k
luajit x86_64 2.1.0-0.25beta3.fc36 updates 402 k
luajit2.1-luv x86_64 1.44.2.1-1.fc36 updates 72 k
msgpack x86_64 3.1.0-9.fc36 fedora 30 k
unibilium x86_64 2.1.1-2.fc36 fedora 36 k
Installing weak dependencies:
xsel x86_64 1.2.0-30.fc36 fedora 28 k
Transaction Summary
================================================================================
Install 10 Packages
Total download size: 6.7 M
Installed size: 26 M
Is this ok [y/N]:
Everything is clear by now! dnf
will install xsel
when installing neovim
, when switched to bob
, I removed nvim
(installed
through dnf
) as well as xsel
from my machine, which means there is NO clipboard tool available to nvim
to use...
Now that we know the root of the problem, the solution is pretty simple, just install one clipboard tool that is listed in the documentation, I choose wl-clipboard
as I am using wayland. xsel
, as tested by Fedora package maintainers, will definitely work, so you can also install that:
$ sudo dnf install -y wl-clipboard
# To install `xsel`
$ sudo dnf install -y xsel
Let's run :checkhealth
again to give it a double check:
provider: health#provider#check
Clipboard (optional) ~
- OK Clipboard tool found: wl-copy
Yep, system clipboard integration is back:)
cppreference
is a site every cpp programmer relies on, but the search function it provides sucks. It uses duckduckgo to index the results, which is relatively slow, exhausting and thus hard to use.
devhelp
or QT help book
(not recommended)One solution is to download the archive and use the index functionality provided by devhelp
or QT help book
to navigate documents. And you need this tool to move these documents to the correct path so that devhelp
or QT help book
can find them. But I don't like it as it's a little bit complicated.
C/C++ Search Extension
(preferred way)A recommended way is to use C/C++ Search Extension
so that you can directly access those docs in your browser as if they were online and without losing the excellent indexing function. Here is the step-by-step process:
Download the archive.
Go to the archive page and click the .zip
file to download it.
unzip the file
If you don't have
unzip
installed, you can refer to this.
$ unzip html-book-20220730.zip
After the decompression, you will find a reference
directory under your current working directory and this is what we want.
$ ls -l
.rw-r--r--@ 2.2M steve steve 30 Jul 22:58 cppreference-doxygen-local.tag.xml
.rw-r--r--@ 2.2M steve steve 30 Jul 22:58 cppreference-doxygen-web.tag.xml
.rw-r--r--@ 47M steve steve 4 Sep 09:11 html-book-20220730.zip
drwxr-xr-x@ - steve steve 30 Jul 21:39 reference
move reference
to a location you preferred
For example, for me, it would be ~/Documents/tools-installed-from-src
$ mv reference ~/Documents/tools-installed-from-src
install C/C++ Search Extension
in your browser
Enable offline mode
Access chrome-extension://ifpcmhciihicaljnhgobnhoehoabidhd/popup/index.html
in your browser:
Toggle the Enable offline mode
button and input the local doc path, the path needed by this extension is the path of the en
subdirectory under reference
, in my case, the path will be /home/steve/Documents/tools-installed-from-src/reference/en/
NOTE: Do NOT forget to append a
/
to the path afteren
.
Done! Time to enjoy!
Open a new tab, type cc
and a space to enable this, then search everything
you want.
//! A single linked list implementation using safe Rust.
use std::fmt::{Debug, Display, Formatter};
type Link<T> = Option<Box<Node<T>>>;
#[derive(Debug)]
struct Node<T> {
data: T,
next: Link<T>,
}
impl<T> Node<T> {
fn new(data: T) -> Self {
Self { data, next: None }
}
}
#[derive(Debug)]
pub struct List<T> {
head: Link<T>,
}
pub struct IntoIter<T>(List<T>);
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.0.pop_front()
}
}
impl<T> IntoIterator for List<T> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> Self::IntoIter {
IntoIter(self)
}
}
impl<'node, T> IntoIterator for &'node List<T> {
type Item = &'node T;
type IntoIter = Iter<'node, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'node, T> IntoIterator for &'node mut List<T> {
type Item = &'node mut T;
type IntoIter = IterMut<'node, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<T> List<T> {
/// Returns an empty List
pub fn new() -> Self {
List::default()
}
/// Returns an iterator over the list.
pub fn iter(&self) -> Iter<'_, T> {
Iter {
cursor: self.head.as_deref(),
}
}
/// Returns an iterator that allows modifying each value.
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut {
cursor: self.head.as_deref_mut(),
}
}
/// Pushes an item to the end of the list.
pub fn push_back(&mut self, value: T) {
if let Some(ref mut head) = self.head {
let mut last_node = head;
while let Some(ref mut new_node) = last_node.next {
last_node = new_node;
}
last_node.next = Some(Box::new(Node::new(value)));
} else {
self.head = Some(Box::new(Node::new(value)));
}
}
/// Pushes an item to the front of the list.
pub fn push_front(&mut self, value: T) {
if self.head.is_some() {
let old_head = self.head.take();
let mut new_head = Node::new(value);
new_head.next = old_head;
self.head = Some(Box::new(new_head));
} else {
self.head = Some(Box::new(Node::new(value)));
}
}
/// Removes the last element from the list and returns it, or None if it is empty.
// The implementation of `pop_back()` depends on the situation of list and
// can be divided into three cases:
// 1. List is empty
// 2. List has 1 node
// 3. List has more than 1 node
pub fn pop_back(&mut self) -> Option<T> {
// case 3: List has more than 1 node
if self.head.is_some() && self.head.as_ref().unwrap().next.is_some() {
let mut node_before_last_node = self.head.as_deref_mut().unwrap();
// The impl in this branch is a bit awkward
// See this question for more detail
// https://stackoverflow.com/q/73789723/14092446
while node_before_last_node.next.is_some() {
if node_before_last_node.next.as_ref().unwrap().next.is_none() {
break;
}
node_before_last_node =
node_before_last_node.next.as_deref_mut().unwrap();
}
let last_node = node_before_last_node.next.take().unwrap();
Some(last_node.data)
}
// case 2: List has 1 node
else if self.head.is_some()
&& self.head.as_ref().unwrap().next.is_none()
{
Some(self.head.take().unwrap().data)
}
// case 1: List is empty
else {
None
}
}
/// Removes the first element from the list and returns it, or `None` if it is empty.
pub fn pop_front(&mut self) -> Option<T> {
self.head.take().map(|head| {
self.head = head.next;
head.data
})
}
/// Returns a reference to the first element in the List, or `None` if it is empty.
pub fn peek_front(&self) -> Option<&T> {
self.head.as_ref().map(|head| &head.data)
}
/// Returns a reference to the last element in the List, or `None` if it is empty.
pub fn peek_back(&self) -> Option<&T> {
if let Some(ref head) = self.head {
let mut last_node = head;
while let Some(ref next) = last_node.next {
last_node = next;
}
Some(&last_node.data)
} else {
None
}
}
/// Returns a mutable reference to the first element in the List, or `None` if
/// it is empty.
pub fn peek_mut_front(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|head| &mut head.data)
}
/// Returns a mutable reference to the last element in the List, or `None` if
/// it is empty.
pub fn peek_mut_back(&mut self) -> Option<&mut T> {
if let Some(ref mut head) = self.head {
let mut last_node = head;
while let Some(ref mut next) = last_node.next {
last_node = next;
}
Some(&mut last_node.data)
} else {
None
}
}
/// Returns the length of the List.
pub fn len(&self) -> usize {
let mut len = 0;
let mut p = self.head.as_ref();
while let Some(p_non_null) = p {
len += 1;
p = p_non_null.next.as_ref();
}
len
}
/// Returns `true` if the list is empty. Otherwise, returns `false`.
pub fn is_empty(&self) -> bool {
self.len().eq(&0)
}
/// Sort the list.
pub fn sort(&mut self) {
unimplemented!()
}
}
/// An iterator over the references of the elements in a [`List`]
pub struct Iter<'node_lifetime, T> {
cursor: Option<&'node_lifetime Node<T>>,
}
impl<'node_lifetime, T> Iterator for Iter<'node_lifetime, T> {
type Item = &'node_lifetime T;
fn next(&mut self) -> Option<Self::Item> {
self.cursor.map(|node| {
self.cursor = node.next.as_deref();
&node.data
})
}
}
/// An iterator over the mutable references of the elements in a [`List`]
pub struct IterMut<'lifetime_of_node, T> {
cursor: Option<&'lifetime_of_node mut Node<T>>,
}
impl<'node_lifetime, T> Iterator for IterMut<'node_lifetime, T> {
type Item = &'node_lifetime mut T;
fn next(&mut self) -> Option<Self::Item> {
// ```rust
// self.cursor.map(|node| {
// self.cursor = node.next.as_deref_mut();
// &mut node.data
// })
// ```
// `self.cursor` is of type `Option<&mut Node<T>>`, which is not `Copy`.
// `.map()` will move `self.cursor`, which is not allowed because `self.cursor`
// is behind a shared reference `&mut self`.
//
// What if we call `.as_mut()` on `self.cursor` first
//
// ```rust
// self.cursor.as_mut().map(|node| {
// // tries to update `self.cursor` in this closure
// self.cursor = node.next.as_deref_mut();
// &mut node.data
// })
// ```
// `.as_mut()` exclusively borrows `self.cursor` in this closure, and we
// are trying to write to `self.cursor` in this closure, which is obviously
// not safe, so Rust rejects this code.
//
// The accepted solution is to call `.take()` on `self.cursor` to takes its
// value out of option. By doing this, we will have two separate objects in
// the memory, one is `self.cursor`, which has the value `None`, another one
// is a new object constructed by `.take()`, then we write to `self.cursor`
// using the value from that new object, this is totally safe.
self.cursor.take().map(|node| {
self.cursor = node.next.as_deref_mut();
&mut node.data
})
}
}
impl<T> Default for List<T> {
fn default() -> Self {
Self { head: None }
}
}
impl<T: Debug> Display for List<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
write!(f, "List: ")?;
let mut p = self.head.as_ref();
while let Some(p_not_null) = p {
write!(f, "{:?} ", p_not_null.data)?;
p = p_not_null.next.as_ref();
}
Ok(())
}
}
impl<T> FromIterator<T> for List<T> {
fn from_iter<I>(iter: I) -> Self
where
I: IntoIterator<Item = T>,
{
let mut list = Self::new();
iter.into_iter().for_each(|value| list.push_back(value));
list
}
}
impl<T> Extend<T> for List<T> {
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
iter.into_iter().for_each(|value| self.push_back(value));
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_from_iter() {
let list = List::from_iter([1, 2, 3]);
list.into_iter().eq([1, 2, 3]);
}
#[test]
fn test_extend() {
let mut list = List::new();
list.extend([1, 2, 3]);
list.into_iter().eq([1, 2, 3]);
let mut list = List::from_iter([1, 2, 3]);
list.extend([4, 5, 6]);
list.into_iter().eq([1, 2, 3, 4, 5, 6]);
}
#[test]
fn test_iter() {
let list = List::from_iter([1, 2, 3]);
list.iter().eq([&1, &2, &3]);
}
#[test]
fn test_iter_mut() {
let mut list = List::from_iter([1, 2, 3]);
list.iter_mut().eq([&mut 1, &mut 2, &mut 3]);
}
#[test]
fn test_into_iter() {
let list = List::from_iter([1, 2, 3]);
list.into_iter().eq([1, 2, 3]);
}
#[test]
fn test_push_back() {
let mut list = List::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.into_iter().eq([1, 2, 3]);
}
#[test]
fn test_push_front() {
let mut list = List::new();
list.push_front(1);
list.push_front(2);
list.push_front(3);
list.into_iter().eq([3, 2, 1]);
}
#[test]
fn test_pop_back() {
let mut list = List::from_iter([1, 2, 3]);
assert_eq!(list.pop_back(), Some(3));
assert_eq!(list.pop_back(), Some(2));
assert_eq!(list.pop_back(), Some(1));
assert_eq!(list.pop_back(), None);
}
#[test]
fn test_pop_front() {
let mut list = List::from_iter([1, 2, 3]);
assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_front(), Some(2));
assert_eq!(list.pop_front(), Some(3));
assert_eq!(list.pop_front(), None);
}
#[test]
fn test_peek_front() {
let mut list = List::new();
assert_eq!(list.peek_front(), None);
list.push_front(1);
assert_eq!(list.peek_front(), Some(&1));
}
#[test]
fn test_peek_back() {
let mut list = List::new();
assert_eq!(list.peek_back(), None);
list.push_back(1);
assert_eq!(list.peek_back(), Some(&1));
list.push_front(0);
assert_eq!(list.peek_back(), Some(&1));
list.push_back(2);
assert_eq!(list.peek_back(), Some(&2));
}
#[test]
fn test_peek_mut_front() {
let mut list = List::new();
assert_eq!(list.peek_mut_front(), None);
list.push_front(1);
assert_eq!(list.peek_mut_front(), Some(&mut 1));
}
#[test]
fn test_peek_mut_back() {
let mut list = List::new();
assert_eq!(list.peek_back(), None);
list.push_back(1);
assert_eq!(list.peek_mut_back(), Some(&mut 1));
list.push_front(0);
assert_eq!(list.peek_mut_back(), Some(&mut 1));
list.push_back(2);
assert_eq!(list.peek_mut_back(), Some(&mut 2));
}
#[test]
fn test_len() {
let mut list = List::new();
assert_eq!(list.len(), 0);
list.push_back(0);
assert_eq!(list.len(), 1);
list.extend([1, 2, 3]);
assert_eq!(list.len(), 4);
list.pop_back();
assert_eq!(list.len(), 3);
}
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.