Re: Overlays as an AA-tree

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

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> BTW, in your new overlay representation, how many bytes (or words) does
> an overlay cost (in the master tree, if I count right, an overlay costs
> 3 Lisp_Misc objects, so that should be 3x 6words, i.e. 72 bytes on
> a 32bit system)?
>
> I'd expect the new representation to be no larger (the current
> representation has a lot of redundancy).  But I'm curious because,
> depending on the answer, the whole Lisp_Misc thingy might want to
> be reconsidered.
>

I don't' know how you're counting, so here is how I (or rtags) would. 

#+BEGIN_SRC c
  /* master */
  struct Lisp_Overlay
  {
      ENUM_BF (Lisp_Misc_Type) type : 16;
      bool_bf gcmarkbit : 1;
      unsigned spacer : 15;
      struct Lisp_Overlay *next;
      Lisp_Object start;          /* -> 40 bytes */
      Lisp_Object end;            /* -> 40 bytes */
      Lisp_Object plist;          /* -> 40 bytes */
  };  /* 40 bytes */
  /* Total: 40 + 3*40 = 160 */

  /* noverlay */
  struct Lisp_Overlay
  {
      ENUM_BF (Lisp_Misc_Type) type : 16;
      bool_bf gcmarkbit : 1;
      unsigned spacer : 15;
      Lisp_Object plist;          /* -> 40 bytes */
      struct buffer *buffer;
      struct interval_node *interval;
  };  /* 32 bytes */

  struct interval_node            /* layout tweaked */
  {
      struct interval_node *parent;
      struct interval_node *left;
      struct interval_node *right;
      ptrdiff_t begin;         /* The beginning of this interval. */
      ptrdiff_t end;           /* The end of the interval. */
      ptrdiff_t limit;         /* The maximum end in this subtree. */
      ptrdiff_t offset;        /* The amount of shift to apply to this subtree. */
      uintmax_t otick;         /* offset modified tick */
      Lisp_Object data;        /* Exclusively used by the client. */
      bool_bf visited : 1;     /* For traversal via generator. */
      bool_bf rear_advance : 1;   /* Same as for marker and overlays.  */
      bool_bf front_advance : 1;  /* Same as for marker and overlays.  */
      enum { ITREE_RED, ITREE_BLACK } color : 1;
  };  /* 80 bytes */
  /* Total: 32 + 40 + 80 = 152 */
#+END_SRC

-ap