DiskLinkedList

Keep data as a linked list on disk. An alternative way to reduce redundant operation for DiskLruCache

Use-case

Android have build-in DiskLruCache.java, but it has too many redundant operations on runtime,
DiskLinkedList using memory-mapped file mechanism to keep data on disk as a linked list.

Advantage

  • Compatible with all systems running Java (Android, JVM, Kotlin/JVM).
  • Get existed / remove (move / free): O(1).
  • New put / get (allocation): O(n) on worst fragment or O(1) on defragmented.
  • High performance.
  • Inconsiderable I/O execution.
  • Easy to use.

File data structure

1 byte (B) to make use or not | 4B prev | 4B next | 4B length | extra byte array

Each entry, DiskLinkedList storage as a node and keep as structure above.

Usage

Create new disk linked list data

val diskLinkedList = DiskLinkedList.open(
    file = File("data.dm"),       // file on disk.
    initialByteSize = 20 * 1024L, // initial size of file.
    scaleFactor = 0.75f           // file size scale factor on data larger than current size.
)

// Create new record.
diskLinkedList.addFirst("Hello, World!".toData())
diskLinkedList.log()              // 0=Hello, World!

Data on disk

img_2.png

More and more

// Add "Second Node" to first.
diskLinkedList.addFirst("Second Node".toData())
diskLinkedList.log()
// Output: 26=Second Node > 0=Hello, World!

// Keep "Second Node" to move later.
val second = diskLinkedList.first!!

// Add 3 nodes to first.
repeat(3) { index ->
    diskLinkedList.addFirst("Hello $index".toData())
}
diskLinkedList.log()
// Output: 90=Hello 2 > 70=Hello 1 > 50=Hello 0 > 26=Second Node > 0=Hello, World!

// Move "Second Node" to first.
diskLinkedList.moveToFirst(second)
diskLinkedList.log()
// Output: 26=Second Node > 90=Hello 2 > 70=Hello 1 > 50=Hello 0 > 0=Hello, World!

Sync and de-fragment

  • DiskLinkedList NOT auto-sync to file, it only sync to file
    after synchronize executed.
  • Beside of that, to avoid fragment on file, DiskLinkedList support defragment function to do.

// Remove last.
diskLinkedList.removeLast()
diskLinkedList.log()
// Output: 26=Second Node > 90=Hello 2 > 70=Hello 1 > 50=Hello 0

// Then continue to add 2 nodes at first.
repeat(2) { index ->
    diskLinkedList.addFirst("Bye $index".toData())
}
diskLinkedList.log()
// Output: 110=Bye 1 > 0=Bye 0 > 26=Second Node > 90=Hello 2 > 70=Hello 1 > 50=Hello 0
// New node "Bye 1" will add at pointer 110 instead of 0 -> FRAGMENTED!!!

// Defragment data.
diskLinkedList.defragment()
diskLinkedList.log()
// Output: 0=Bye 1 > 18=Bye 0 > 36=Second Node > 60=Hello 2 > 80=Hello 1 > 100=Hello 0

// Sync every change to disk.
diskLinkedList.synchronize()

Dependency

Maven

<dependency>
    <groupId>org.cuongnv.disklinkedlist</groupId>
    <artifactId>disklinkedlist</artifactId>
    <version>0.5.0</version>
</dependency>

Gradle Kotlin DSL

implementation("org.cuongnv.disklinkedlist:disklinkedlist:0.5.0")

Gradle Groovy

implementation 'org.cuongnv.disklinkedlist:disklinkedlist:0.5.0'

License

Copyright 2021 Cuong V. Nguyen (github.com/cuongnv126).

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

   http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

GitHub

https://github.com/cuongnv126/disklinkedlist