Design an image loading library.

package com.androidinterview.imageloader;

// Stands in for android.graphics.Bitmap so the pipeline compiles off device.
// byteCount is the only part the library itself cares about, because it is
// what the memory cache budgets against. Four bytes a pixel is ARGB_8888, the
// worst case and therefore the right one to budget against.
public record Bitmap(int width, int height) {

    public int byteCount() {
        return width * height * 4;
    }
}

package com.androidinterview.imageloader;

import java.nio.ByteBuffer;

// The fourth stage, and the one that decides how much memory this image is
// going to cost for as long as it is on screen.
public final class Decoder {

    private Decoder() {
    }

    public static Bitmap decode(byte[] encoded, int targetWidth, int targetHeight) {
        // Pass one, BitmapFactory.Options with inJustDecodeBounds set, which
        // reads the header and allocates no pixels at all. That is what makes
        // it safe to ask a four thousand pixel photo how big it is before
        // committing to keeping any of it.
        int[] bounds = readBounds(encoded);
        int sample = sampleSizeFor(bounds[0], bounds[1], targetWidth, targetHeight);
        // Pass two, the same options with inSampleSize set, so the decoder
        // never allocates the full sized bitmap in the first place. Handing it
        // a pooled buffer through inBitmap belongs here too, which is what
        // keeps a fast scroll from feeding the collector.
        return new Bitmap(bounds[0] / sample, bounds[1] / sample);
    }

    // Powers of two, halving while both dimensions would still cover the
    // target. A two thousand pixel square source into a four hundred pixel
    // view comes back at five hundred, one sixteenth of the pixels the naive
    // decode would have allocated.
    static int sampleSizeFor(int sourceWidth, int sourceHeight, int targetWidth, int targetHeight) {
        int sample = 1;
        while (sourceHeight / (sample * 2) >= targetHeight && sourceWidth / (sample * 2) >= targetWidth) {
            sample *= 2;
        }
        return sample;
    }

    // A PNG carries its width and height as two big endian integers at byte
    // sixteen, which is enough to show the shape of the two pass decode
    // without pulling in a real image codec.
    private static int[] readBounds(byte[] encoded) {
        ByteBuffer header = ByteBuffer.wrap(encoded, 16, 8);
        return new int[] {header.getInt(), header.getInt()};
    }
}

package com.androidinterview.imageloader;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicBoolean;

// Four stages, each one there to make the next unnecessary, plus the three
// things that decide whether a fast scrolling list stays smooth and correct,
// cancellation, deduplication and the stale delivery check.
public final class ImageLoader {

    // Three ports, all of them things this library orchestrates rather than
    // implements. The memory cache is an LRU budgeted in bytes, the disk cache
    // is a DiskLruCache, and the fetcher is whatever networking library the
    // app already has.
    public interface MemoryCache {
        Bitmap get(String key);

        void put(String key, Bitmap bitmap);

        // What onTrimMemory calls. A cache that cannot shrink on demand is the
        // reason an app gets killed in the background for hogging memory.
        void trimTo(long budgetBytes);
    }

    public interface DiskCache {
        byte[] read(String url);

        void write(String url, byte[] encoded);
    }

    public interface Fetcher {
        byte[] fetch(String url) throws IOException;
    }

    // Where a bitmap lands, an ImageView in a real app. The tag is the fix for
    // the RecyclerView wrong image bug. A holder is rebound to a new URL while
    // the old fetch is still running, and without the tag the old bitmap lands
    // later and draws over the new row. The loader tags the target with the
    // request when load is called and checks the tag again before drawing.
    public interface Target {
        void setTag(ImageRequest request);

        ImageRequest tag();

        void onBitmap(Bitmap bitmap);

        void onError(Exception cause);
    }

    public interface Disposable {
        void dispose();
    }

    // One pipeline per key, shared by every target waiting on it. The
    // cancelled flag is cooperative. Future.cancel does not interrupt a task
    // already running on a plain pool, so the pipeline checks the flag between
    // stages instead, which is what stops the decode from ever starting.
    private static final class InFlight {
        final ImageRequest request;
        final AtomicBoolean started = new AtomicBoolean();
        private final List<Target> targets = new ArrayList<>();
        private boolean done;
        private volatile boolean cancelled;

        InFlight(ImageRequest request) {
            this.request = request;
        }

        // False once the job has delivered, so a late joiner starts a new one
        // rather than waiting on a list that has already been drained.
        synchronized boolean attach(Target target) {
            if (done) {
                return false;
            }
            targets.add(target);
            return true;
        }

        // Detaching one view never cancels work another view is still waiting
        // on. The job dies only when the last caller leaves, which is exactly
        // what a fling through a list produces.
        synchronized boolean detach(Target target) {
            if (!targets.remove(target) || done || !targets.isEmpty()) {
                return false;
            }
            cancelled = true;
            return true;
        }

        boolean isCancelled() {
            return cancelled;
        }

        synchronized List<Target> finish() {
            done = true;
            List<Target> waiting = new ArrayList<>(targets);
            targets.clear();
            return waiting;
        }
    }

    private final MemoryCache memory;
    private final DiskCache disk;
    private final Fetcher fetcher;
    // Results are handed back through this, a Handler on the main looper
    // wrapped as an Executor on Android. Touching an ImageView from a pool
    // thread is an immediate crash, so delivery on the right thread is the
    // library's job and not the caller's.
    private final Executor mainThread;
    private final Map<String, InFlight> inFlight = new ConcurrentHashMap<>();

    // Decoding is CPU bound and downloading is not, so they get different
    // pools. One pool sized for either job is the wrong size for the other,
    // and sharing it means a burst of downloads starves the decoder.
    private final ExecutorService network = Executors.newFixedThreadPool(4);
    private final ExecutorService decode =
            Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

    public ImageLoader(MemoryCache memory, DiskCache disk, Fetcher fetcher, Executor mainThread) {
        this.memory = memory;
        this.disk = disk;
        this.fetcher = fetcher;
        this.mainThread = mainThread;
    }

    // The returned handle is what a view holder calls when it is recycled, and
    // what a lifecycle observer calls on destroy. Without it a fast scroll
    // queues far more work than the device can finish, and every abandoned
    // request keeps burning CPU long after its view is gone.
    public Disposable load(ImageRequest request, Target target) {
        String key = request.key();
        target.setTag(request);
        Bitmap hot = memory.get(key);
        if (hot != null) {
            // Stage one, and the only stage that answers on the calling
            // thread. A synchronous hit is what stops a scrolled back row from
            // flickering through its placeholder on the way to a bitmap that
            // was in memory the whole time.
            target.onBitmap(hot);
            return () -> {
            };
        }

        // The lambda only allocates. Starting the work inside computeIfAbsent
        // would let a fast disk hit finish and call inFlight.remove while the
        // map still holds the lock for this key, which ConcurrentHashMap
        // forbids. The loop covers a job that delivered between being found
        // and being joined.
        InFlight job;
        do {
            job = inFlight.computeIfAbsent(key, absent -> new InFlight(request));
        } while (!job.attach(target));
        InFlight joined = job;
        if (joined.started.compareAndSet(false, true)) {
            network.execute(() -> fetchThenDecode(joined));
        }

        return () -> {
            // The two argument remove only evicts this job. Without it a stale
            // handle from an earlier load could remove a newer job for the
            // same key, and every later caller would miss the dedup.
            if (joined.detach(target)) {
                inFlight.remove(key, joined);
            }
        };
    }

    public void shutdown() {
        network.shutdownNow();
        decode.shutdownNow();
    }

    private void fetchThenDecode(InFlight job) {
        // Checked before the fetch, so a request whose holder was recycled
        // while it sat in the queue costs no network at all.
        if (job.isCancelled()) {
            return;
        }
        byte[] encoded;
        try {
            encoded = encodedBytes(job.request);
        } catch (IOException failure) {
            finish(job, null, failure);
            return;
        }
        // Checked again between the stages. The decode is the expensive part,
        // and the flag is what guarantees it never runs for a view that left.
        if (job.isCancelled()) {
            return;
        }
        decode.execute(() -> {
            if (job.isCancelled()) {
                return;
            }
            try {
                Bitmap bitmap = Decoder.decode(encoded, job.request.width(), job.request.height());
                memory.put(job.request.key(), bitmap);
                finish(job, bitmap, null);
            } catch (RuntimeException failure) {
                finish(job, null, failure);
            }
        });
    }

    private void finish(InFlight job, Bitmap bitmap, Exception failure) {
        // Remove first, then drain. A caller that joins in between still lands
        // in the list, and one that arrives after finds no entry and starts a
        // fresh job. The other order would leave a drained job in the map.
        inFlight.remove(job.request.key(), job);
        List<Target> waiting = job.finish();
        mainThread.execute(() -> {
            for (Target target : waiting) {
                // The stale delivery check. The holder may have been rebound to
                // another URL since it asked for this one, and then this bitmap
                // belongs to a row that is no longer on screen.
                if (!job.request.equals(target.tag())) {
                    continue;
                }
                if (bitmap != null) {
                    target.onBitmap(bitmap);
                } else {
                    target.onError(failure);
                }
            }
        });
    }

    private byte[] encodedBytes(ImageRequest request) throws IOException {
        // Stage two. A disk hit still costs a decode, which is why it sits
        // behind the memory cache rather than in front of it.
        byte[] cached = disk.read(request.url());
        if (cached != null) {
            return cached;
        }
        // Stage three, and the only one that can fail slowly. Writing to disk
        // before decoding means a killed process still leaves the bytes behind
        // for the next launch.
        byte[] fetched = fetcher.fetch(request.url());
        disk.write(request.url(), fetched);
        return fetched;
    }
}

package com.androidinterview.imageloader;

public record ImageRequest(String url, int width, int height) {

    // The target size is part of the key. The same URL decoded for a list
    // thumbnail and for a full screen header are two different bitmaps, and
    // one key for both means either a blurry header or a thumbnail that costs
    // full screen memory. The disk cache is keyed by URL alone, because the
    // encoded bytes are the same file whatever it will be drawn into.
    public String key() {
        return url + "@" + width + "x" + height;
    }
}

package com.androidinterview.imageloader

import java.nio.ByteBuffer

// The fourth stage, and the one that decides how much memory this image costs
// for as long as it is on screen.
object Decoder {

    fun decode(encoded: ByteArray, targetWidth: Int, targetHeight: Int): Bitmap {
        // Pass one, BitmapFactory.Options with inJustDecodeBounds set, which
        // reads the header and allocates no pixels at all. That is what makes
        // it safe to ask a four thousand pixel photo how big it is before
        // committing to keep any of it.
        val (sourceWidth, sourceHeight) = readBounds(encoded)
        val sample = sampleSizeFor(sourceWidth, sourceHeight, targetWidth, targetHeight)
        // Pass two, the same options with inSampleSize set, so the decoder
        // never allocates the full sized bitmap at all. Handing it a pooled
        // buffer through inBitmap belongs here too, which is what keeps a fast
        // scroll from feeding the collector.
        return Bitmap(sourceWidth / sample, sourceHeight / sample)
    }

    // Powers of two, halving while both dimensions would still cover the
    // target. A two thousand pixel square source into a four hundred pixel
    // view comes back at five hundred, one sixteenth of the pixels the naive
    // decode would have allocated.
    fun sampleSizeFor(sourceWidth: Int, sourceHeight: Int, targetWidth: Int, targetHeight: Int): Int {
        var sample = 1
        while (sourceHeight / (sample * 2) >= targetHeight && sourceWidth / (sample * 2) >= targetWidth) {
            sample *= 2
        }
        return sample
    }

    // A PNG carries its width and height as two big endian integers at byte
    // sixteen, which is enough to show the shape of the two pass decode
    // without pulling in a real image codec.
    private fun readBounds(encoded: ByteArray): Pair<Int, Int> =
        ByteBuffer.wrap(encoded, 16, 8).let { it.int to it.int }
}

package com.androidinterview.imageloader

import java.io.IOException
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.Executor
import java.util.concurrent.Executors
import java.util.concurrent.atomic.AtomicBoolean

fun interface Disposable {
    fun dispose()
}

// Four stages, each one there to make the next unnecessary, plus the three
// things that decide whether a fast scrolling list stays smooth and correct,
// cancellation, deduplication and the stale delivery check.
class ImageLoader(
    private val memory: MemoryCache,
    private val disk: DiskCache,
    private val fetcher: Fetcher,
    // A Handler on the main looper wrapped as an Executor on Android. Touching
    // an ImageView from a pool thread is an immediate crash, so delivering on
    // the right thread is the library's job and not the caller's.
    private val mainThread: Executor,
) {
    // One pipeline per key, shared by every target waiting on it. The
    // cancelled flag is cooperative. Future.cancel does not interrupt a task
    // already running on a plain pool, so the pipeline checks the flag between
    // stages instead, which is what stops the decode from ever starting.
    private class InFlight(val request: ImageRequest) {
        val started = AtomicBoolean()
        private val targets = mutableListOf<Target>()
        private var done = false

        @Volatile
        var cancelled = false
            private set

        // False once the job has delivered, so a late joiner starts a new one
        // rather than waiting on a list that has already been drained.
        @Synchronized
        fun attach(target: Target) = !done && targets.add(target)

        // Detaching one view never cancels work another view is still waiting
        // on. The job dies only when the last caller leaves, which is exactly
        // what a fling through a list produces.
        @Synchronized
        fun detach(target: Target): Boolean {
            if (!targets.remove(target) || done || targets.isNotEmpty()) return false
            cancelled = true
            return true
        }

        @Synchronized
        fun finish(): List<Target> = targets.toList().also {
            done = true
            targets.clear()
        }
    }

    // Decoding is CPU bound and downloading is not, so they get different
    // pools. One pool sized for either job is the wrong size for the other,
    // and sharing it means a burst of downloads starves the decoder.
    private val network = Executors.newFixedThreadPool(4)
    private val decode = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors())

    private val inFlight = ConcurrentHashMap<String, InFlight>()

    // The returned handle is what a view holder calls when it is recycled and
    // what a lifecycle observer calls on destroy. Without it a fast scroll
    // queues far more work than the device can finish, and every abandoned
    // request burns CPU long after its view is gone.
    fun load(request: ImageRequest, target: Target): Disposable {
        val key = request.key
        target.tag = request
        memory[key]?.let {
            // Stage one, and the only stage that answers on the calling
            // thread. A synchronous hit is what stops a scrolled back row from
            // flickering through its placeholder on the way to a bitmap that
            // was in memory the whole time.
            target.onBitmap(it)
            return Disposable { }
        }

        // The lambda only allocates. Starting the work inside computeIfAbsent
        // would let a fast disk hit finish and call inFlight.remove while the
        // map still holds the lock for this key, which ConcurrentHashMap
        // forbids. The loop covers a job that delivered between being found
        // and being joined.
        var job: InFlight
        do {
            job = inFlight.computeIfAbsent(key) { InFlight(request) }
        } while (!job.attach(target))
        if (job.started.compareAndSet(false, true)) network.execute { fetchThenDecode(job) }

        return Disposable {
            // The two argument remove only evicts this job. Without it a stale
            // handle from an earlier load could remove a newer job for the
            // same key, and every later caller would miss the dedup.
            if (job.detach(target)) inFlight.remove(key, job)
        }
    }

    fun shutdown() {
        network.shutdownNow()
        decode.shutdownNow()
    }

    private fun fetchThenDecode(job: InFlight) {
        // Checked before the fetch, so a request whose holder was recycled
        // while it sat in the queue costs no network at all.
        if (job.cancelled) return
        val encoded = try {
            encodedBytes(job.request)
        } catch (failure: IOException) {
            return finish(job, null, failure)
        }
        // Checked again between the stages. The decode is the expensive part,
        // and the flag is what guarantees it never runs for a view that left.
        if (job.cancelled) return
        decode.execute {
            if (job.cancelled) return@execute
            try {
                val bitmap = Decoder.decode(encoded, job.request.width, job.request.height)
                memory[job.request.key] = bitmap
                finish(job, bitmap, null)
            } catch (failure: RuntimeException) {
                finish(job, null, failure)
            }
        }
    }

    private fun finish(job: InFlight, bitmap: Bitmap?, failure: Exception?) {
        // Remove first, then drain. A caller that joins in between still lands
        // in the list, and one that arrives after finds no entry and starts a
        // fresh job. The other order would leave a drained job in the map.
        inFlight.remove(job.request.key, job)
        val waiting = job.finish()
        mainThread.execute {
            // The stale delivery check. The holder may have been rebound to
            // another URL since it asked for this one, and then this bitmap
            // belongs to a row that is no longer on screen.
            waiting.filter { it.tag == job.request }.forEach { target ->
                if (bitmap != null) target.onBitmap(bitmap) else target.onError(failure!!)
            }
        }
    }

    private fun encodedBytes(request: ImageRequest): ByteArray =
        // Stage two. A disk hit still costs a decode, which is why it sits
        // behind the memory cache rather than in front of it. Stage three
        // writes the bytes down before decoding them, so a killed process
        // still leaves them behind for the next launch.
        disk.read(request.url) ?: fetcher.fetch(request.url).also { disk.write(request.url, it) }
}

package com.androidinterview.imageloader

data class ImageRequest(val url: String, val width: Int, val height: Int) {

    // The target size is part of the key. The same URL decoded for a list
    // thumbnail and for a full screen header are two different bitmaps, and
    // one key for both means either a blurry header or a thumbnail that costs
    // full screen memory. The disk cache is keyed by URL alone, because the
    // encoded bytes are the same file whatever it is drawn into.
    val key get() = "$url@${width}x$height"
}

// Stands in for android.graphics.Bitmap so the pipeline compiles off device.
// byteCount is the only part the library cares about, because it is what the
// memory cache budgets against. Four bytes a pixel is ARGB_8888, the worst
// case and therefore the right one to budget against.
data class Bitmap(val width: Int, val height: Int) {
    val byteCount get() = width * height * 4
}

// Three ports, all of them things this library orchestrates rather than
// implements. The memory cache is an LRU budgeted in bytes, the disk cache is
// a DiskLruCache, and the fetcher is whatever networking library the app
// already has.
interface MemoryCache {
    operator fun get(key: String): Bitmap?
    operator fun set(key: String, bitmap: Bitmap)

    // What onTrimMemory calls. A cache that cannot shrink on demand is the
    // reason an app gets killed in the background for hogging memory.
    fun trimTo(budgetBytes: Long)
}

interface DiskCache {
    fun read(url: String): ByteArray?
    fun write(url: String, encoded: ByteArray)
}

fun interface Fetcher {
    fun fetch(url: String): ByteArray
}

// Where a bitmap lands, an ImageView in a real app. The tag is the fix for the
// RecyclerView wrong image bug. A holder is rebound to a new URL while the old
// fetch is still running, and without the tag the old bitmap lands later and
// draws over the new row. The loader sets the tag when load is called and
// checks it again before drawing.
interface Target {
    var tag: ImageRequest?
    fun onBitmap(bitmap: Bitmap)
    fun onError(cause: Exception)
}