Page 1 of 1

Doubly-linked list utility in 65C02 assembly

Posted: Wed Jun 14, 2023 11:25 pm
by StephenHorn
After going on for quite some length in the C linked-list thread, I became interested in just how easily a human could potentially implement a faster linked list than what CC65 can be coaxed into generating. Because cc65 seems to ultimately want to perform 16-bit arithmetic at the slightest provocation, meaning a human can do much better for linked lists involving less than 256 elements.

The result is a linked list library/utility I've written for use in ca65 projects, and can be used to instance, implement, and use my linked list approach: https://github.com/indigodarkwolf/x16-linkedlist-asm

The joy of macros, making life easier for everyone except the macro author. :lol:

I have some basic documentation in linkedlist.inc in the github repo, but will follow up on this thread later with additional documentation.

Re: Doubly-linked list utility in 65C02 assembly

Posted: Thu Jun 15, 2023 12:45 am
by StephenHorn
Actually, as I was writing some documentation, I came to realize that my implementation wasn't all that fast... it could be faster! So I'm going to keep working on it.

In the meanwhile, the main thing is that this is designed to be used almost entirely through its macro set, which is creating a distinct implementation for each linked list that one wants to create in their program. The distinct implementation is intended to avoid the cost of indirection -- if memory size is more of a concern, then one would need to replace a bunch of immediate-mode or immediate-indexed instructions with various forms of indirection.

Simply place linkedlist.inc into your project and .include it into a file where you want to use its macros. The bare minimum would be to invoke LIST_INSTANTIATE where you want your list data to exist, and invoke LIST_IMPLEMENT where you want the handling code to exist. From there, you would use the public API documented in linkedlist.inc. Be sure to initialize the list with LIST_INITIALIZE before making use of it!