Single_Linked_List.t

-- Single_Linked_List.t: Implementation in "Terra"

local C = terralib.includecstring [[
        #include <stdio.h>
        #include <stdlib.h>
]]

local function List(T, Options)

    local function check_allocator(opt)
        return opt and opt.allocator and opt.allocator.alloc and opt.allocator.dealloc
    end

    local alloc = macro(
        function(arg)
            if check_allocator(Options) then
                return `Options.allocator.alloc(arg)
            else
                print("DEBUG: macro alloc  : Using default C.malloc")
                return `C.malloc(arg)
            end
        end
    )

    local dealloc = macro(
        function(arg)
            if check_allocator(Options) then
                return `Options.allocator.dealloc(arg)
            else
                print("DEBUG: macro dealloc: Using default C.free")
                return `C.free(arg)
            end
        end
    )

    local log = macro(
        function(fmt, arg)
            if Options and Options.allocator and Options.allocator.logging then
                return `C.printf(fmt, arg)
            else
                print("DEBUG: macro log    : Disabling logging (default)")
                return `nil
            end
        end
    )

    local print_data = macro(
        function(arg)
            if Options and Options.print and Options.print.data then
                return `Options.print.data(arg)
            elseif T:isintegral() then
                if T == uint64 then
                    return `C.printf("%llu", arg)
                else
                    return `C.printf("%lld", [int64](arg))
                end
            elseif T:isfloat() then
                return `C.printf("%.1lf", [double](arg))
            elseif T == &int8 then
                return `C.printf("\"%s\"", arg)
            else
                print("WARN: print_data macro: Fall back to generic '<val>'")
                return `C.printf("<val>")
            end
        end
    )

    local function print_max_nodes()
        if Options and Options.print and Options.print.max_nodes then
            return Options.print.max_nodes
        else
            return 3
        end
    end

    local function Node(T)
        local struct Node {
            data: T
            next: &Node
        }

        terra Node:init(data: T, next: &Node)
            self.data = data
            self.next = next
        end

        terra Node:get_data(): T
            return self.data
        end

        terra Node:get_next(): &Node
            return self.next
        end

        terra Node:print_debug()
            var p_node: &Node = self
            var count: uint32 = 0
            while (p_node ~= nil) and (count < [ print_max_nodes() ]) do
                C.printf("Node { data: ")
                print_data(p_node.data)
                C.printf(", next: ")
                p_node = p_node.next
                count = count + 1
            end
            if p_node == nil then -- reached end
                C.printf("NULL")
            else -- count reached limit
                C.printf("...")
            end
            if count > 0 then
                C.printf(" ")
                for i = 0, count do
                    C.printf("}")
                end
            end
        end

        terra Node:print()
            var p_node: &Node = self
            var count: uint32 = 0
            while (p_node ~= nil) and (count < [ print_max_nodes() ]) do
                print_data(p_node.data)
                p_node = p_node.next
                if p_node ~= nil then
                    C.printf(", ")
                end
                count = count + 1
            end
            if p_node ~= nil then --count reached limit
                C.printf("...")
            end
        end

        return Node
    end -- Node(T)

    local Node_of_T = Node(T)

    local struct List {
        head: &Node_of_T
        len: int
    }

    terra List:init()
        self.head = nil
        self.len  = 0
    end

    terra List:get_head(): &Node_of_T
        return self.head
    end

    terra List:get_len(): int
        return self.len
    end

    terra List:cons(data: T): bool
        var ptr: &opaque = alloc(sizeof(Node_of_T))
        if ptr == nil then
            C.printf("\nERROR: terra List:cons() : Could not alloc Node_of_T\n")
            return false
        else
            var p_node: &Node_of_T = [&Node_of_T](ptr)
            log("DEBUG: terra List:cons(): ALLOC node at %p\n", p_node)
            p_node:init(data, self.head)
            self.head = p_node
            self.len = self.len + 1
            return true
        end
    end

    terra List:dealloc()
        var p_node: &Node_of_T = self.head
        while p_node ~= nil do
            self.head = (self.head):get_next()
            log("DEBUG: terra List:dealloc(): DEALLOC node at %p\n", p_node)
            dealloc(p_node)
            p_node = self.head
        end
    end

    terra List:print_debug()
        C.printf("List { head: ")
        (self.head):print_debug()
        C.printf(", len: %d }", self.len)
    end

    terra List:print()
        C.printf("[")
        (self.head):print()
        C.printf("] (len: %d)", self.len)
    end

    return List
end -- List(T)

------------------------------- TESTING --------------------------------------

print("\nDEBUG: List_int")
local List_int = List(int)

terra print_custom_float(data: float)
    C.printf("%+0.3f", data)
end

print("\nDEBUG: List_float")
local List_float = List(float, {
    allocator = { alloc = C.malloc, dealloc = C.free, logging = true },
    print     = { data = print_custom_float, max_nodes = 4 }
})

print("\nDEBUG: List_string")
local List_string = List(&int8, {
    allocator = { logging = true }
})

print("\nDEBUG: terra test_single_linked_list()")
terra test_single_linked_list()
    var int_list: List_int
    int_list:init()

    var float_list: List_float
    float_list:init()

    var string_list: List_string
    string_list:init()

    var err_msg: &int8 = nil
    ------
    C.printf("\nDEBUG: int_list:initial state:\n")
    int_list:print()

    C.printf("\n\nDEBUG: int_list (dbg) = ")
    int_list:print_debug()

    C.printf("\n\nDEBUG: int_list:cons(i) for i in range(0, 100):\n")
    for i = 0, 100 do
        if not (int_list:cons(i)) then
            err_msg = "ERROR: int_list:cons(i) FAILED"
            goto cleanup
        end
    end
    int_list:print()

    C.printf("\n\nDEBUG: int_list (dbg) = ")
    int_list:print_debug()
    ------
    C.printf("\n\nDEBUG: float_list:initial state:\n")
    float_list:print()

    C.printf("\n\nDEBUG: float_list (dbg) = ")
    float_list:print_debug()

    C.printf("\n\nDEBUG: float_list:cons(i) for i in range(0, 6):\n")
    for i = 0, 6 do
        if not (float_list:cons(i)) then
            err_msg = "ERROR: float_list:cons(i) FAILED"
            goto cleanup
        end
    end
    float_list:print()

    C.printf("\n\nDEBUG: float_list (dbg) = ")
    float_list:print_debug()
    ------
    C.printf("\n\nDEBUG: string_list:initial state:\n")
    string_list:print()

    C.printf("\n\nDEBUG: string_list (dbg) = ")
    string_list:print_debug()
    C.printf("\n\nDEBUG: string_list (after cons: 'abc', 'def', 'ghi'):\n")

    err_msg = "ERROR: string_list:cons(...) FAILED"
    if not (string_list:cons("abc")) then goto cleanup end
    if not (string_list:cons("def")) then goto cleanup end
    if not (string_list:cons("ghi")) then goto cleanup end
    err_msg = nil

    string_list:print()

    C.printf("\n\nDEBUG: string_list (dbg) = ")
    string_list:print_debug()
    ------
    ::cleanup::
    C.printf("\n\nDEBUG: int_list:dealloc()\n")
    int_list:dealloc()
    C.printf("\n\nDEBUG: float_list:dealloc()\n")
    float_list:dealloc()
    C.printf("\n\nDEBUG: string_list:dealloc()\n")
    string_list:dealloc()

    if err_msg ~= nil then
        C.printf(err_msg)
        return C.EXIT_FAILURE
    else
        return C.EXIT_SUCCESS
    end
end

--test_single_linked_list:printpretty()
--test_single_linked_list:disas()

test_single_linked_list()

terralib.saveobj("test_single_linked_list.exe", {
    main = test_single_linked_list
})