Databases
StackOverflow2013
Postsdbo
POHow to efficiently reference count cons cells (detecting cycles)?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to efficiently reference count cons cells (detecting cycles)?
    primarykey
    data
    text
    <p>I need to make some sort of <code>liblisp</code> (in C11), and it will need to handle the basic functions, pretty much like what <code>libobjc</code> does for the Objective-C language.</p> <h1>Edit</h1> <p>I'm rewritting the question to something less generic.</p> <p>I got an implementation like this:</p> <pre><code>typedef struct cons { void *car, *cdr; } *cons_t; cons_t cons_init(void *, void *); void *cons_get_car(cons_t); void *cons_get_cdr(cons_t); void cons_set_car(cons_t, void *); void cons_set_cdr(cons_t, void *); void cons_free(cons_t); bool cons_is_managed(cons_t); </code></pre> <p>So I can make a cons cell (it uses a memory pool with reference counted objects). I can also use <code>cons_is_managed</code> to check if the cons cell is inside the memory pool (so you can use externally defined cells, not created with <code>cons_init</code> (like static data).</p> <p>How could I efficiently implement an automatic reference counting here, making if someone calls <code>cons_set_car</code> or <code>cons_set_cdr</code> it would increment the reference count if the <code>void *</code> argument is a managed cons cell?</p> <p>The harem and the tortoise problem wouldn't be useful here, because each cell have two possible ways to go (and it could go nowhere if car nor cdr are conses), they can be lists, trees, or graphs.</p> <p>I should probably register external (non-managed) conses used in on <code>cons_set_car</code>/<code>cons_set_cdr</code> in order to find cycles that involve them, but I'm still not sure how to do this <em>efficiently</em>.</p> <p>Since this is a more controled context then general cycles in graphs (max of two vertices on a node), is there any chance I could do this in linear time and avoid a garbage collection (which will be my plan B)?</p> <p>The main problem is that this is the core of any functional languages, so those functions will be called <strong>a lot</strong> of times (like <code>obj_msgSend</code>), they are <strong>the</strong> bottleneck.</p> <p>Thanks.</p> <hr> <p>On a different approach, to simplify the question: how could one implement a cons cell on a language based on reference counting, like Objective-C + ARC or Vala?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USpaulotorrens
    1. USpaulotorrens
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. POHow to efficiently reference count cons cells (detecting cycles)?
      1. USpaulotorrens
      1. VTBountyStart
    2. VO
      singulars
      1. POHow to efficiently reference count cons cells (detecting cycles)?
      1. This table or related slice is empty.
      1. VTBountyClose
    3. VO
      singulars
      1. POHow to efficiently reference count cons cells (detecting cycles)?
      1. This table or related slice is empty.
      1. VTUpMod
    1. CODo you actually need to write this, or do you just need to use one? There are some Lisps that compile down to C code and, I think, expose their data structures in C. You might be able to simply reuse some of them.
      singulars
      1. POHow to efficiently reference count cons cells (detecting cycles)?
      1. USJoshua Taylor
    2. COYeah, I actually need to write this. The Lisp compilers I found that make C code use raw structs to make this work, they don't use a runtime library, so the behaviour/optimizations is hardcoded on the compiler.
      singulars
      1. POHow to efficiently reference count cons cells (detecting cycles)?
      1. USpaulotorrens
    3. COWhatever you do, you just have to name the library `isp`. What way, you can use it from the command line with `-lisp`.
      singulars
      1. POHow to efficiently reference count cons cells (detecting cycles)?
      1. USLars Brinkhoff
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload