Re: Overlays as an AA-tree

[Andreas Politz <politza@hochschule-trier.de>]

I think, I got mostly everything ready, from Fmake_overlay to
Fbuffer_swap_text. It compiles just fine after which it immediately dumps
core -- but that's another problem.

I am currently uncertain about how to properly allocate the memory I
need for

1. traversing the tree (log(n)) and
2. storing some nodes (n)

Number 1. isn't really a problem, since it can be allocated
when an overlay is created and kept for the life-time of the buffer,
since its size is pretty small.

The other storage I need due to the problem with front-advance overlays
while adjusting the overlays for insert. The size of this thing makes it
not so size to keep around.  So, is it save to call xmalloc at this
point ?

---

My data-structures look like this at the moment.

#+BEGIN_SRC c
  struct Lisp_Overlay
  {
      /* ... */
      struct buffer *buffer;
      struct interval_node *interval;
  };

  struct interval_node
  {
      ptrdiff_t begin, end;
      /* ... */
      Lisp_Object data; /* --> Lisp_Overlay */
  };


  struct buffer
  {
      /* ... */

      struct interval_tree *overlays;

      /* ... */
  };


#+END_SRC

The tree is xmalloc'd, when the first overlay of the buffer is created
and overlay's interval_tree in build_overlay when making it.  Both are
freed in their corresponding sweep function.

Does that sound alright ?

-ap