Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-js

Source of release 0.6.1

0.6.1 / src / cutils / list.lucb

#==============================================================================================
#
#   list - Intrusive doubly linked circular lists (Linux klist like system)
#
#   DESCRIPTION:
#       Port of QuickJS list.h (lines 28-97). The iteration macros have no Luce spelling;
#       the loops are written out where they are used, as `ListHead` shows.
#
#       Copyright (c) 2016-2017 Fabrice Bellard. MIT licence, as cutils.
#
#==============================================================================================

## A link in an intrusive circular list; a list is a `ListHead` whose `next` is its first
## element and whose `prev` is its last. `prev`/`next` are none only in a zeroed or deleted
## link (list_del's fail safe).
##
## `list_entry(el, T, member)` is `(T*)((u8*)el - offsetof(T, member))`.
##
## `list_for_each(el, head)`:
##
## ```luce
## var el = head.next else trap("unlinked")
## while el != head:
##     let obj = (Object*)((u8*)el - offsetof(Object, link))
##     ...
##     el = el.next else trap("unlinked")
## ```
##
## `list_for_each_safe(el, el1, head)`, where the body may `list_del(el)`:
##
## ```luce
## var el = head.next else trap("unlinked")
## while el != head:
##     let el1 = el.next else trap("unlinked")
##     ...
##     el = el1
## ```
##
## The `_prev` forms are the same over `prev`.
pub struct ListHead:
    ## The previous link, or none when unlinked.
    pub var prev: ListHead*?
    ## The next link, or none when unlinked.
    pub var next: ListHead*?

## Make `head` an empty list (C `LIST_HEAD_INIT` / `init_list_head`).
pub func init_list_head(head: ListHead*):
    head.prev = head
    head.next = head

## insert 'el' between 'prev' and 'next' (C `__list_add`).
pub func list_add_raw(el: ListHead*, prev: ListHead*, next: ListHead*):
    prev.next = el
    el.prev = prev
    el.next = next
    next.prev = el

## add 'el' at the head of the list 'head' (= after element head)
pub func list_add(el: ListHead*, head: ListHead*):
    list_add_raw(el, head, head.next else trap("list_add: unlinked head"))

## add 'el' at the end of the list 'head' (= before element head)
pub func list_add_tail(el: ListHead*, head: ListHead*):
    list_add_raw(el, head.prev else trap("list_add_tail: unlinked head"), head)

## Unlink `el`; its links become none (fail safe).
pub func list_del(el: ListHead*):
    let prev = el.prev else trap("list_del: unlinked element")
    let next = el.next else trap("list_del: unlinked element")
    prev.next = next
    next.prev = prev
    el.prev = none  # fail safe
    el.next = none  # fail safe

## Whether the list `el` is empty.
pub func list_empty(el: const ListHead*) -> bool:
    if let next = el.next:
        return next == el
    return false