xemacs-beta: src/rangetab.c comparison

comparison src/rangetab.c @ 5168:cf900a2f1fa3

extract gap array from extents.c, use in range tables -------------------- ChangeLog entries follow: -------------------- src/ChangeLog addition: 2010-03-22 Ben Wing <ben@xemacs.org> * Makefile.in.in (objs): * array.c: * array.c (gap_array_adjust_markers): * array.c (gap_array_move_gap): * array.c (gap_array_make_gap): * array.c (gap_array_insert_els): * array.c (gap_array_delete_els): * array.c (gap_array_make_marker): * array.c (gap_array_delete_marker): * array.c (gap_array_delete_all_markers): * array.c (gap_array_clone): * array.h: * depend: * emacs.c (main_1): * extents.c: * extents.c (EXTENT_GAP_ARRAY_AT): * extents.c (extent_list_num_els): * extents.c (extent_list_locate): * extents.c (extent_list_at): * extents.c (extent_list_delete_all): * extents.c (allocate_extent_list): * extents.c (syms_of_extents): * extents.h: * extents.h (XEXTENT_LIST_MARKER): * lisp.h: * rangetab.c: * rangetab.c (mark_range_table): * rangetab.c (print_range_table): * rangetab.c (range_table_equal): * rangetab.c (range_table_hash): * rangetab.c (verify_range_table): * rangetab.c (get_range_table_pos): * rangetab.c (Fmake_range_table): * rangetab.c (Fcopy_range_table): * rangetab.c (Fget_range_table): * rangetab.c (put_range_table): * rangetab.c (Fclear_range_table): * rangetab.c (Fmap_range_table): * rangetab.c (unified_range_table_bytes_needed): * rangetab.c (unified_range_table_copy_data): * rangetab.c (unified_range_table_lookup): * rangetab.h: * rangetab.h (struct range_table_entry): * rangetab.h (struct Lisp_Range_Table): * rangetab.h (rangetab_gap_array_at): * symsinit.h: Rename dynarr.c to array.c. Move gap array from extents.c to array.c. Extract dynarr, gap array and stack-like malloc into new file array.h. Rename GAP_ARRAY_NUM_ELS -> gap_array_length(). Add gap_array_at(), gap_array_atp(). Rewrite range table code to use gap arrays. Make put_range_table() smarter so that its operation is O(log n) for adding a localized range. * gc.c (lispdesc_block_size_1): Don't ABORT() when two elements are located at the same place. This will happen with a size-0 gap array -- both parts of the array (before and after gap) are in the same place.

author	Ben Wing <ben@xemacs.org>
date	Mon, 22 Mar 2010 19:12:15 -0500
parents	88bd4f3ef8e4
children	6c6d78781d59

comparison

equal deleted inserted replaced

-:e374ea766cc1
+:cf900a2f1fa3
 mark_range_table (Lisp_Object obj)
 {
 Lisp_Range_Table *rt = XRANGE_TABLE (obj);
 int i;
-for (i = 0; i < Dynarr_length (rt->entries); i++)
+for (i = 0; i < gap_array_length (rt->entries); i++)
-mark_object (Dynarr_at (rt->entries, i).val);
+mark_object (rangetab_gap_array_at (rt->entries, i).val);
 return Qnil;
 }
 static void
 if (print_readably)
 write_fmt_string_lisp (printcharfun, "#s(range-table type %s data (",
 			   1, range_table_type_to_symbol (rt->type));
 else
 write_ascstring (printcharfun, "#<range-table ");
-for (i = 0; i < Dynarr_length (rt->entries); i++)
+for (i = 0; i < gap_array_length (rt->entries); i++)
 {
-struct range_table_entry *rte = Dynarr_atp (rt->entries, i);
+struct range_table_entry rte = rangetab_gap_array_at (rt->entries, i);
 int so, ec;
 if (i > 0)
 	write_ascstring (printcharfun, " ");
 switch (rt->type)
 	{
 	case RANGE_START_OPEN_END_CLOSED: so = 1; ec = 1; break;
 	default: ABORT (); so = 0, ec = 0; break;
 	}
 write_fmt_string (printcharfun, "%c%ld %ld%c ",
 			print_readably ? '(' : so ? '(' : '[',
-			(long) (rte->first - so),
+			(long) (rte.first - so),
-			(long) (rte->last - ec),
+			(long) (rte.last - ec),
 			print_readably ? ')' : ec ? ']' : ')'
 			);
-print_internal (rte->val, printcharfun, 1);
+print_internal (rte.val, printcharfun, 1);
 }
 if (print_readably)
 write_ascstring (printcharfun, "))");
 else
 write_fmt_string (printcharfun, " 0x%x>", LISP_OBJECT_UID (obj));
 {
 Lisp_Range_Table *rt1 = XRANGE_TABLE (obj1);
 Lisp_Range_Table *rt2 = XRANGE_TABLE (obj2);
 int i;
-if (Dynarr_length (rt1->entries) != Dynarr_length (rt2->entries))
+if (gap_array_length (rt1->entries) != gap_array_length (rt2->entries))
 return 0;
-for (i = 0; i < Dynarr_length (rt1->entries); i++)
+for (i = 0; i < gap_array_length (rt1->entries); i++)
 {
-struct range_table_entry *rte1 = Dynarr_atp (rt1->entries, i);
+struct range_table_entry *rte1 =
-struct range_table_entry *rte2 = Dynarr_atp (rt2->entries, i);
+	rangetab_gap_array_atp (rt1->entries, i);
+struct range_table_entry *rte2 =
+	rangetab_gap_array_atp (rt2->entries, i);
 if (rte1->first != rte2->first
 	  || rte1->last != rte2->last
 	  || !internal_equal_0 (rte1->val, rte2->val, depth + 1, foldcase))
 	return 0;
 static Hashcode
 range_table_hash (Lisp_Object obj, int depth)
 {
 Lisp_Range_Table *rt = XRANGE_TABLE (obj);
 int i;
-int size = Dynarr_length (rt->entries);
+int size = gap_array_length (rt->entries);
 Hashcode hash = size;
 /* approach based on internal_array_hash(). */
 if (size <= 5)
 {
 for (i = 0; i < size; i++)
 	hash = HASH2 (hash,
-		      range_table_entry_hash (Dynarr_atp (rt->entries, i),
+		      range_table_entry_hash
-					      depth));
+		      (rangetab_gap_array_atp (rt->entries, i), depth));
 return hash;
 }
 /* just pick five elements scattered throughout the array.
 A slightly better approach would be to offset by some
 noise factor from the points chosen below. */
 for (i = 0; i < 5; i++)
-hash = HASH2 (hash, range_table_entry_hash (Dynarr_atp (rt->entries,
+hash = HASH2 (hash,
-							    i*size/5),
+		  range_table_entry_hash
-						depth));
+		  (rangetab_gap_array_atp (rt->entries, i*size/5), depth));
 return hash;
 }
 static const struct memory_description rte_description_1[] = {
 { XD_LISP_OBJECT, offsetof (range_table_entry, val) },
 static const struct sized_memory_description rte_description = {
 sizeof (range_table_entry),
 rte_description_1
 };
-static const struct memory_description rted_description_1[] = {
+static const struct memory_description rtega_description_1[] = {
-XD_DYNARR_DESC (range_table_entry_dynarr, &rte_description),
+XD_GAP_ARRAY_DESC (&rte_description),
 { XD_END }
 };
-static const struct sized_memory_description rted_description = {
+static const struct sized_memory_description rtega_description = {
-sizeof (range_table_entry_dynarr),
+0, rtega_description_1
-rted_description_1
 };
 static const struct memory_description range_table_description[] = {
 { XD_BLOCK_PTR,  offsetof (Lisp_Range_Table, entries),  1,
-{ &rted_description } },
+{ &rtega_description } },
 { XD_END }
 };
 DEFINE_DUMPABLE_LISP_OBJECT ("range-table", range_table,
 			     mark_range_table, print_range_table, 0,
 static void
 verify_range_table (Lisp_Range_Table *rt)
 {
 int i;
-for (i = 0; i < Dynarr_length (rt->entries); i++)
+for (i = 0; i < gap_array_length (rt->entries); i++)
 {
-struct range_table_entry *rte = Dynarr_atp (rt->entries, i);
+struct range_table_entry *rte = rangetab_gap_array_atp (rt->entries, i);
 assert (rte->last >= rte->first);
 if (i > 0)
-	assert (Dynarr_at (rt->entries, i - 1).last <= rte->first);
+	assert (rangetab_gap_array_at (rt->entries, i - 1).last <= rte->first);
 }
 }
 #else
 #define verify_range_table(rt)
 #endif
-/* Look up in a range table without the Dynarr wrapper.
+/* Locate the range table entry corresponding to the value POS, and return
-Used also by the unified range table format. */
+it.  If found, FOUNDP is set to 1 and the return value specifies an entry
+that encloses POS.  Otherwise, FOUNDP is set to 0 and the return value
-static Lisp_Object
+specifies where an entry that encloses POS would be inserted. */
-get_range_table (EMACS_INT pos, int nentries, struct range_table_entry *tab,
-		 Lisp_Object default_)
+static Elemcount
-{
+get_range_table_pos (Elemcount pos, Elemcount nentries,
-int left = 0, right = nentries;
+		     struct range_table_entry *tab,
+		     Elemcount gappos, Elemcount gapsize,
+		     int *foundp)
+{
+Elemcount left = 0, right = nentries;
 /* binary search for the entry.  Based on similar code in
 extent_list_locate(). */
 while (left != right)
 {
 /* RIGHT might not point to a valid entry (i.e. it's at the end
 	 of the list), so NEWPOS must round down. */
-int newpos = (left + right) >> 1;
+Elemcount newpos = (left + right) >> 1;
-struct range_table_entry *entry = tab + newpos;
+struct range_table_entry *entry =
+	tab + GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (newpos, gappos, gapsize);
 if (pos >= entry->last)
 	left = newpos + 1;
 else if (pos < entry->first)
 	right = newpos;
 else
-	return entry->val;
+	{
+	  *foundp = 1;
+	  return newpos;
+	}
+}
+*foundp = 0;
+return left;
+}
+/* Look up in a range table without the gap array wrapper.
+Used also by the unified range table format. */
+static Lisp_Object
+get_range_table (Elemcount pos, Elemcount nentries,
+		 struct range_table_entry *tab,
+		 Elemcount gappos, Elemcount gapsize,
+		 Lisp_Object default_)
+{
+int foundp;
+Elemcount entrypos = get_range_table_pos (pos, nentries, tab, gappos,
+					    gapsize, &foundp);
+if (foundp)
+{
+struct range_table_entry *entry =
+	tab + GAP_ARRAY_ARRAY_TO_MEMORY_POS_1 (entrypos, gappos, gapsize);
+return entry->val;
 }
 return default_;
 }
 */
 (type))
 {
 Lisp_Object obj = ALLOC_NORMAL_LISP_OBJECT (range_table);
 Lisp_Range_Table *rt = XRANGE_TABLE (obj);
-rt->entries = Dynarr_new (range_table_entry);
+rt->entries = make_gap_array (sizeof (struct range_table_entry), 0);
 rt->type = range_table_symbol_to_type (type);
 return obj;
 }
 DEFUN ("copy-range-table", Fcopy_range_table, 1, 1, 0, /*
 */
 (range_table))
 {
 Lisp_Range_Table *rt, *rtnew;
 Lisp_Object obj;
+Elemcount i;
 CHECK_RANGE_TABLE (range_table);
 rt = XRANGE_TABLE (range_table);
 obj = ALLOC_NORMAL_LISP_OBJECT (range_table);
 rtnew = XRANGE_TABLE (obj);
-rtnew->entries = Dynarr_new (range_table_entry);
+rtnew->entries = make_gap_array (sizeof (struct range_table_entry), 0);
 rtnew->type = rt->type;
-Dynarr_add_many (rtnew->entries, Dynarr_begin (rt->entries),
+for (i = 0; i < gap_array_length (rt->entries); i++)
-		   Dynarr_length (rt->entries));
+rtnew->entries =
+gap_array_insert_els (rtnew->entries, i,
+			    rangetab_gap_array_atp (rt->entries, i), 1);
 return obj;
 }
 DEFUN ("get-range-table", Fget_range_table, 2, 3, 0, /*
 Find value for position POS in RANGE-TABLE.
 CHECK_RANGE_TABLE (range_table);
 rt = XRANGE_TABLE (range_table);
 CHECK_INT_COERCE_CHAR (pos);
-return get_range_table (XINT (pos), Dynarr_length (rt->entries),
+return get_range_table (XINT (pos), gap_array_length (rt->entries),
-			  Dynarr_begin (rt->entries), default_);
+			  gap_array_begin (rt->entries,
+					   struct range_table_entry),
+			  gap_array_gappos (rt->entries),
+			  gap_array_gapsize (rt->entries),
+			  default_);
 }
 static void
 external_to_internal_adjust_ends (enum range_table_type type,
 				  EMACS_INT *first, EMACS_INT *last)
 		 EMACS_INT last, Lisp_Object val)
 {
 int i;
 int insert_me_here = -1;
 Lisp_Range_Table *rt = XRANGE_TABLE (table);
+int foundp;
 external_to_internal_adjust_ends (rt->type, &first, &last);
 if (first == last)
 return;
 if (first > last)
 /* This will happen if originally first == last and both ends are
 open. #### Should we signal an error? */
 return;
+if (DUMPEDP (rt->entries))
+rt->entries = gap_array_clone (rt->entries);
+i = get_range_table_pos (first, gap_array_length (rt->entries),
+			   gap_array_begin (rt->entries,
+					    struct range_table_entry),
+			   gap_array_gappos (rt->entries),
+			   gap_array_gapsize (rt->entries), &foundp);
+#ifdef ERROR_CHECK_TYPES
+if (foundp)
+{
+if (i < gap_array_length (rt->entries))
+	{
+	  struct range_table_entry *entry =
+	    rangetab_gap_array_atp (rt->entries, i);
+	  assert (first >= entry->first && first < entry->last);
+	}
+}
+else
+{
+if (i < gap_array_length (rt->entries))
+	{
+	  struct range_table_entry *entry =
+	    rangetab_gap_array_atp (rt->entries, i);
+	  assert (first < entry->first);
+	}
+if (i > 0)
+	{
+	  struct range_table_entry *entry =
+	    rangetab_gap_array_atp (rt->entries, i - 1);
+	  assert (first >= entry->last);
+	}
+}
+#endif /* ERROR_CHECK_TYPES */
+/* If the beginning of the new range isn't within any existing range,
+it might still be just grazing the end of an end-open range (remember,
+internally all ranges are start-close end-open); so back up one
+so we consider this range. */
+if (!foundp && i > 0)
+i--;
 /* Now insert in the proper place.  This gets tricky because
 we may be overlapping one or more existing ranges and need
 to fix them up. */
 /* First delete all sections of any existing ranges that overlap
 the new range. */
-for (i = 0; i < Dynarr_length (rt->entries); i++)
+for (; i < gap_array_length (rt->entries); i++)
 {
-struct range_table_entry *entry = Dynarr_atp (rt->entries, i);
+struct range_table_entry *entry =
+	rangetab_gap_array_atp (rt->entries, i);
 /* We insert before the first range that begins at or after the
 	 new range. */
 if (entry->first >= first && insert_me_here < 0)
 	insert_me_here = i;
 if (entry->last < first)
 	  insert_me_too.first = last;
 	  insert_me_too.last = entry->last;
 	  insert_me_too.val = entry->val;
 	  entry->last = first;
-	  Dynarr_insert_many (rt->entries, &insert_me_too, 1, i + 1);
+	  rt->entries =
+	    gap_array_insert_els (rt->entries, i + 1, &insert_me_too, 1);
 	}
 else if (entry->last >= last)
 	{
 	  /* looks like:
 	  entry->first = last;
 	}
 else
 	{
 	  /* existing is entirely within new. */
-	  Dynarr_delete_many (rt->entries, i, 1);
+	  gap_array_delete_els (rt->entries, i, 1);
 	  i--; /* back up since everything shifted one to the left. */
 	}
 }
 /* Someone asked us to delete the range, not insert it. */
 insert_me.first = first;
 insert_me.last = last;
 insert_me.val = val;
-Dynarr_insert_many (rt->entries, &insert_me, 1, insert_me_here);
+rt->entries =
+gap_array_insert_els (rt->entries, insert_me_here, &insert_me, 1);
 }
 /* Now see if we can combine this entry with adjacent ones just
 before or after. */
 if (insert_me_here > 0)
 {
-struct range_table_entry *entry = Dynarr_atp (rt->entries,
+struct range_table_entry *entry =
-						    insert_me_here - 1);
+	rangetab_gap_array_atp (rt->entries, insert_me_here - 1);
 if (EQ (val, entry->val) && entry->last == first)
 	{
 	  entry->last = last;
-	  Dynarr_delete_many (rt->entries, insert_me_here, 1);
+	  gap_array_delete_els (rt->entries, insert_me_here, 1);
 	  insert_me_here--;
 	  /* We have morphed into a larger range.  Update our records
 	     in case we also combine with the one after. */
 	  first = entry->first;
 	}
 }
-if (insert_me_here < Dynarr_length (rt->entries) - 1)
+if (insert_me_here < gap_array_length (rt->entries) - 1)
 {
-struct range_table_entry *entry = Dynarr_atp (rt->entries,
+struct range_table_entry *entry =
-						    insert_me_here + 1);
+	rangetab_gap_array_atp (rt->entries, insert_me_here + 1);
 if (EQ (val, entry->val) && entry->first == last)
 	{
 	  entry->first = first;
-	  Dynarr_delete_many (rt->entries, insert_me_here, 1);
+	  gap_array_delete_els (rt->entries, insert_me_here, 1);
 	}
 }
 }
 DEFUN ("put-range-table", Fput_range_table, 4, 4, 0, /*
 Flush RANGE-TABLE.
 */
 (range_table))
 {
 CHECK_RANGE_TABLE (range_table);
-Dynarr_reset (XRANGE_TABLE (range_table)->entries);
+gap_array_delete_all_els (XRANGE_TABLE (range_table)->entries);
 return Qnil;
 }
 DEFUN ("map-range-table", Fmap_range_table, 2, 2, 0, /*
 Map FUNCTION over entries in RANGE-TABLE, calling it with three args,
 rt = XRANGE_TABLE (range_table);
 /* Do not "optimize" by pulling out the length computation below!
 FUNCTION may have changed the table. */
-for (i = 0; i < Dynarr_length (rt->entries); i++)
+for (i = 0; i < gap_array_length (rt->entries); i++)
 {
-struct range_table_entry *entry = Dynarr_atp (rt->entries, i);
+struct range_table_entry entry =
+	rangetab_gap_array_at (rt->entries, i);
 EMACS_INT first, last;
 Lisp_Object args[4];
 int oldlen;
 again:
-first = entry->first;
+first = entry.first;
-last = entry->last;
+last = entry.last;
-oldlen = Dynarr_length (rt->entries);
+oldlen = gap_array_length (rt->entries);
 args[0] = function;
 /* Fix up the numbers in accordance with the open/closedness of the
 	 table. */
 {
 	EMACS_INT premier = first, dernier = last;
 	internal_to_external_adjust_ends (rt->type, &premier, &dernier);
 	args[1] = make_int (premier);
 	args[2] = make_int (dernier);
 }
-args[3] = entry->val;
+args[3] = entry.val;
 Ffuncall (countof (args), args);
 /* Has FUNCTION removed the entry? */
-if (oldlen > Dynarr_length (rt->entries)
+if (oldlen > gap_array_length (rt->entries)
-	  && i < Dynarr_length (rt->entries)
+	  && i < gap_array_length (rt->entries)
-	  && (first != entry->first || last != entry->last))
+	  && (first != entry.first || last != entry.last))
 	goto again;
 }
 return Qnil;
 }
 int
 unified_range_table_bytes_needed (Lisp_Object rangetab)
 {
 return (sizeof (struct range_table_entry) *
-	  (Dynarr_length (XRANGE_TABLE (rangetab)->entries) - 1) +
+	  (gap_array_length (XRANGE_TABLE (rangetab)->entries) - 1) +
 	  sizeof (struct unified_range_table) +
 	  /* ALIGNOF a struct may be too big. */
 	  /* We have four bytes for the size numbers, and an extra
 	     four or eight bytes for making sure we get the alignment
 	     OK. */
 {
 /* We cast to the above structure rather than just casting to
 char * and adding sizeof(int), because that will lead to
 mis-aligned data on the Alpha machines. */
 struct unified_range_table *un;
-range_table_entry_dynarr *rted = XRANGE_TABLE (rangetab)->entries;
+Gap_Array *rtega = XRANGE_TABLE (rangetab)->entries;
 int total_needed = unified_range_table_bytes_needed (rangetab);
 void *new_dest = ALIGN_PTR ((char *) dest + 4, EMACS_INT);
+Elemcount i;
 * (char *) dest = (char) ((char *) new_dest - (char *) dest);
 * ((unsigned char *) dest + 1) = total_needed & 0xFF;
 total_needed >>= 8;
 * ((unsigned char *) dest + 2) = total_needed & 0xFF;
 total_needed >>= 8;
 * ((unsigned char *) dest + 3) = total_needed & 0xFF;
 un = (struct unified_range_table *) new_dest;
-un->nentries = Dynarr_length (rted);
+un->nentries = gap_array_length (rtega);
 un->type = XRANGE_TABLE (rangetab)->type;
-memcpy (&un->first, Dynarr_begin (rted),
+for (i = 0; i < gap_array_length (rtega); i++)
-	  sizeof (struct range_table_entry) * Dynarr_length (rted));
+(&un->first)[i] = rangetab_gap_array_at (rtega, i);
 }
 /* Return number of bytes actually used by a unified range table. */
 int
 align_the_damn_table (unrangetab);
 new_dest = (char *) unrangetab + * (char *) unrangetab;
 un = (struct unified_range_table *) new_dest;
-return get_range_table (pos, un->nentries, &un->first, default_);
+return get_range_table (pos, un->nentries, &un->first, 0, 0, default_);
 }
 /* Return number of entries in a unified range table. */
 int

Mercurial > hg > xemacs-beta

comparison src/rangetab.c @ 5168:cf900a2f1fa3