Introduction

Welcome to my collection module! I bet you will feel shocked at my design. This is the recommended collection which the one of collections in my library. It's negative stack. Do you believe the indexes of my stack is decreasing from -1? (Like -1,-2,-3,-4,-5,...) Do you believe the top pointer of my stack is less than the bottom pointer? Do you believe the index of the bottom element is -1? It's negative stack! The bottom pointer is at the high address. You need to index negative integer number to get elements. It's the origin of the name of negative stack. More shocking is, it's more efficient than normal dynamic collections. I swear. If you suspect it, please go on.

Create

Let's create an empty stack.

var stack = cos.stack.negStack(u8).new();

If I tell you it's stored in the thread stack, do you believe it? Let's reveal this secret.

Layout

If left is low address, right is high address, the layout in memory of empty negative stack is like: |top pointer|bottom pointer&stack pointer| The bottom pointer is equal to stack pointer in it. And the size of every cells is equal to the size of element. Now, you will believe it is effecient. Because it's not need the memory allocator to resize. Each methods of stack is all even inline. Why? I will tell you. Besides, if you want to specify aligned elements, you can use cos.stack.negStackAligned.

Push

Now, let's push some elements to the stack.

stack.push(73);
stack.push(42);
stack.push(211);

Now, the memory layout is like: |top pointer|211|42|73|bottom pointer&stack pointer|

Pop

Let's pop an element and print it.

std.debug.print("value: {}\n", .{stack.pop().?});

You will see 211. The method pop will check whether the length of stack is empty. If it's empty, will return null. If you are sure that it's not undefined behavior not to check length, please use popUnchecked method. In the fact, many methods of stack have their matched unchecked method.

Risk

Well, We print it successfully. Shall we print 42? Let's try.

std.debug.print("value: {}\n", .{stack.pop().?});

Are you shocking? The result is unexpected barely. Because we called the function std.debug.print, it created some local variables on the stack and pushed the return address into the stack.(Maybe pushed frame pointer too.) Now, the layout is like: |top pointer|a part of return address|bottom pointer&stack pointer| Our data was covered by std.debug.print function! It means the elements are might undefined now. In this situation, we can say it's ill. Thus, we should be careful to use stacks. Because the function might cover our data. But we need only notice not inline function. Because inline function can't cover our data. It's the reason why the method of stack is all inline.

Clear

Never mind. Let's rebuild the stack. We can use clear method to clear the stack.

stack.clear();

Now the stack is empty. Let's push some elements.

stack.push(73);
stack.push(42);
stack.push(211);

Save

If we hope the result is expected, we shouldn't cover the data until the stack is useless. Let transfer data to the current frame(or registers)!

const third = stack.pop();
const second = stack.pop();

Now useful data was transfered from the stack. Now the stack is useless.

std.debug.print("second: {}, third: {}\n", .{second.?, third.?});

Now we print them successfully. Congratulations!

At

Let me demostrate something else. I should rebuild the stack.

stack.clear();
stack.push(73);
stack.push(42);
stack.push(211);

We can get the element at a specified index.

const v2 = stack.at(-2);
const v3 = stack.at(-3);

Please care the order of indexes. It's decreasing from -1. Why? Because it base on the bottom pointer, and the bottom pointer is at top address. It returns a optional pointer to element. If it's besides the range that stack can access, will return null. If you are sure that the index is in the range of stack, you can use atUnchecked method.

std.debug.print("value at index -2: {}, value at index -3: {}\n", .{v2.?.*, v3.?.*});

Will print 42 and 211.

Basic

We can get the bottom pointer and the length of stack.

const ptr = stack.ptr; // The bottom pointer, it's a multipointer, you can use `bottom` method too.
const limit = stack.limit; // The limit of the stack.

Be careful, in order to compare to length conveniently, we saved the limit that the bitwise NOT of length.

const length = stack.len(); // Use method `len` to get the length of stack.
std.debug.print("ptr: {*}, limit: {}, length: {}\n", .{ptr, limit, length});

Follow

We can construct another stack in the same frame.

var s2: cos.stack.negStack(u32) = stack.follow(cos.stack.negStack(u32).fromPtr);
s2.push(42);
s2.push(212);
std.debug.print("second: {}, first: {}\n", .{s2.pop().?, s2.pop().?});

Be careful, because the direction of increasing is occupied by second stack, the max length of the first stack will be the current length until the second stack is released. That time, you can use the memory space of the second stack for the first stack.

Iterator

Rebuild the stack.

stack.clear();
stack.push(3);
stack.push(21);
stack.push(114);

The stack support iterator. You can create an iterator.

var iter = stack.iter();

This iterator can yield pointers to elements. Now, let's use it!

while (iter.next()) |v| {
    v.* += 1;
}

Now, let's print the stack!

std.debug.print("{}, {}, {}\n", .{stack.at(-1).?.*, stack.at(-2).?.*, stack.at(-3).?.*});

Adjust

stack.clear();
stack.push(42);
stack.push(211);

If you want to save elements but you won't to move elemnts out, you can try to use adjust method.

stack.adjust(struct {
    fn print () void {
        std.debug.print("Hello world!\n", .{});
    }
}.print);

It will receive a function without parameters.

std.debug.print("first: {}, second: {}\n", .{stack.at(-1).?.*, stack.at(-2).?.*});

It will print correctly.

End

Now, you can use negative stack. By the way, negative stack has an alia "sos". It will save your program when you shout SOS. I suggest you use "sos" in your code. Have a nice time!

Support

Now, cos just support x86/x86-64.

Platform

It's in GitCode.GitCode URL