3 * Copyright (c) 2001-2002, Biswapesh Chattopadhyay
4 * Copyright 2005 The Geany contributors
6 * This source code is released for free distribution under the terms of the
7 * GNU General Public License.
13 #include <glib-object.h>
19 #define TAG_NEW(T) ((T) = g_slice_new0(TMTag))
20 #define TAG_FREE(T) g_slice_free(TMTag, (T))
25 static GHashTable
*alive_tags
= NULL
;
27 static void foreach_tags_log(gpointer key
, gpointer value
, gpointer data
)
29 gsize
*ref_count
= data
;
30 const TMTag
*tag
= value
;
32 *ref_count
+= (gsize
) tag
->refcount
;
33 g_debug("Leaked TMTag (%d refs): %s", tag
->refcount
, tag
->name
);
36 static void log_refs_at_exit(void)
40 g_hash_table_foreach(alive_tags
, foreach_tags_log
, &ref_count
);
41 g_debug("TMTag references left at exit: %lu", ref_count
);
44 static TMTag
*log_tag_new(void)
50 alive_tags
= g_hash_table_new(g_direct_hash
, g_direct_equal
);
51 atexit(log_refs_at_exit
);
54 g_hash_table_insert(alive_tags
, tag
, tag
);
59 static void log_tag_free(TMTag
*tag
)
61 g_return_if_fail(alive_tags
!= NULL
);
63 if (! g_hash_table_remove(alive_tags
, tag
)) {
64 g_critical("Freeing invalid TMTag pointer %p", (void *) tag
);
72 #define TAG_NEW(T) ((T) = log_tag_new())
73 #define TAG_FREE(T) log_tag_free(T)
75 #endif /* DEBUG_TAG_REFS */
82 const GPtrArray
*tags_array
;
86 /** Gets the GType for a TMTag.
89 * @since 1.32 (API 233) */
91 GType
tm_tag_get_type(void)
93 static GType gtype
= 0;
94 if (G_UNLIKELY (gtype
== 0))
96 gtype
= g_boxed_type_register_static("TMTag", (GBoxedCopyFunc
)tm_tag_ref
,
97 (GBoxedFreeFunc
)tm_tag_unref
);
103 Creates a new tag structure and returns a pointer to it.
104 @return the new TMTag structure. This should be free()-ed using tm_tag_free()
106 TMTag
*tm_tag_new(void)
117 Destroys a TMTag structure, i.e. frees all elements except the tag itself.
118 @param tag The TMTag structure to destroy
121 static void tm_tag_destroy(TMTag
*tag
)
124 g_free(tag
->arglist
);
126 g_free(tag
->inheritance
);
127 g_free(tag
->var_type
);
132 Drops a reference from a TMTag. If the reference count reaches 0, this function
133 destroys all data in the tag and frees the tag structure as well.
134 @param tag Pointer to a TMTag structure
136 void tm_tag_unref(TMTag
*tag
)
138 /* be NULL-proof because tm_tag_free() was NULL-proof and we indent to be a
139 * drop-in replacment of it */
140 if (NULL
!= tag
&& g_atomic_int_dec_and_test(&tag
->refcount
))
148 Adds a reference to a TMTag.
149 @param tag Pointer to a TMTag structure
150 @return the passed-in TMTag
152 TMTag
*tm_tag_ref(TMTag
*tag
)
154 g_atomic_int_inc(&tag
->refcount
);
159 Inbuilt tag comparison function.
161 static gint
tm_tag_compare(gconstpointer ptr1
, gconstpointer ptr2
, gpointer user_data
)
163 unsigned int *sort_attr
;
165 TMTag
*t1
= *((TMTag
**) ptr1
);
166 TMTag
*t2
= *((TMTag
**) ptr2
);
167 TMSortOptions
*sort_options
= user_data
;
169 if ((NULL
== t1
) || (NULL
== t2
))
171 g_warning("Found NULL tag");
174 if (NULL
== sort_options
->sort_attrs
)
176 if (sort_options
->partial
)
177 return strncmp(FALLBACK(t1
->name
, ""), FALLBACK(t2
->name
, ""), strlen(FALLBACK(t1
->name
, "")));
179 return strcmp(FALLBACK(t1
->name
, ""), FALLBACK(t2
->name
, ""));
182 for (sort_attr
= sort_options
->sort_attrs
; returnval
== 0 && *sort_attr
!= tm_tag_attr_none_t
; ++ sort_attr
)
186 case tm_tag_attr_name_t
:
187 if (sort_options
->partial
)
188 returnval
= strncmp(FALLBACK(t1
->name
, ""), FALLBACK(t2
->name
, ""), strlen(FALLBACK(t1
->name
, "")));
190 returnval
= strcmp(FALLBACK(t1
->name
, ""), FALLBACK(t2
->name
, ""));
192 case tm_tag_attr_file_t
:
193 returnval
= t1
->file
- t2
->file
;
195 case tm_tag_attr_line_t
:
196 returnval
= t1
->line
- t2
->line
;
198 case tm_tag_attr_type_t
:
199 returnval
= t1
->type
- t2
->type
;
201 case tm_tag_attr_scope_t
:
202 returnval
= strcmp(FALLBACK(t1
->scope
, ""), FALLBACK(t2
->scope
, ""));
204 case tm_tag_attr_arglist_t
:
205 returnval
= strcmp(FALLBACK(t1
->arglist
, ""), FALLBACK(t2
->arglist
, ""));
208 int line_diff
= (t1
->line
- t2
->line
);
210 returnval
= line_diff
? line_diff
: returnval
;
213 case tm_tag_attr_vartype_t
:
214 returnval
= strcmp(FALLBACK(t1
->var_type
, ""), FALLBACK(t2
->var_type
, ""));
221 gboolean
tm_tags_equal(const TMTag
*a
, const TMTag
*b
)
226 return (a
->line
== b
->line
&&
227 a
->file
== b
->file
/* ptr comparison */ &&
228 strcmp(FALLBACK(a
->name
, ""), FALLBACK(b
->name
, "")) == 0 &&
229 a
->type
== b
->type
&&
230 a
->local
== b
->local
&&
231 a
->flags
== b
->flags
&&
232 a
->access
== b
->access
&&
233 a
->impl
== b
->impl
&&
234 a
->lang
== b
->lang
&&
235 strcmp(FALLBACK(a
->scope
, ""), FALLBACK(b
->scope
, "")) == 0 &&
236 strcmp(FALLBACK(a
->arglist
, ""), FALLBACK(b
->arglist
, "")) == 0 &&
237 strcmp(FALLBACK(a
->inheritance
, ""), FALLBACK(b
->inheritance
, "")) == 0 &&
238 strcmp(FALLBACK(a
->var_type
, ""), FALLBACK(b
->var_type
, "")) == 0);
242 Removes NULL tag entries from an array of tags. Called after tm_tags_dedup() since
243 this function substitutes duplicate entries with NULL
244 @param tags_array Array of tags to dedup
246 void tm_tags_prune(GPtrArray
*tags_array
)
250 g_return_if_fail(tags_array
);
252 for (i
=0, count
= 0; i
< tags_array
->len
; ++i
)
254 if (NULL
!= tags_array
->pdata
[i
])
255 tags_array
->pdata
[count
++] = tags_array
->pdata
[i
];
257 tags_array
->len
= count
;
261 Deduplicates an array on tags using the inbuilt comparison function based on
262 the attributes specified. Called by tm_tags_sort() when dedup is TRUE.
263 @param tags_array Array of tags to dedup.
264 @param sort_attributes Attributes the array is sorted on. They will be deduped
265 on the same criteria.
267 void tm_tags_dedup(GPtrArray
*tags_array
, TMTagAttrType
*sort_attributes
, gboolean unref_duplicates
)
269 TMSortOptions sort_options
;
272 g_return_if_fail(tags_array
);
273 if (tags_array
->len
< 2)
276 sort_options
.sort_attrs
= sort_attributes
;
277 sort_options
.partial
= FALSE
;
278 for (i
= 1; i
< tags_array
->len
; ++i
)
280 if (0 == tm_tag_compare(&(tags_array
->pdata
[i
- 1]), &(tags_array
->pdata
[i
]), &sort_options
))
282 if (unref_duplicates
)
283 tm_tag_unref(tags_array
->pdata
[i
-1]);
284 tags_array
->pdata
[i
-1] = NULL
;
287 tm_tags_prune(tags_array
);
291 Sort an array of tags on the specified attribuites using the inbuilt comparison
293 @param tags_array The array of tags to be sorted
294 @param sort_attributes Attributes to be sorted on (int array terminated by 0)
295 @param dedup Whether to deduplicate the sorted array
297 void tm_tags_sort(GPtrArray
*tags_array
, TMTagAttrType
*sort_attributes
,
298 gboolean dedup
, gboolean unref_duplicates
)
300 TMSortOptions sort_options
;
302 g_return_if_fail(tags_array
);
304 sort_options
.sort_attrs
= sort_attributes
;
305 sort_options
.partial
= FALSE
;
306 g_ptr_array_sort_with_data(tags_array
, tm_tag_compare
, &sort_options
);
308 tm_tags_dedup(tags_array
, sort_attributes
, unref_duplicates
);
311 void tm_tags_remove_file_tags(TMSourceFile
*source_file
, GPtrArray
*tags_array
)
315 /* Now we choose between an algorithm with complexity O(tags_array->len) and
316 * O(source_file->tags_array->len * log(tags_array->len)). The latter algorithm
317 * is better when tags_array contains many times more tags than
318 * source_file->tags_array so instead of trying to find the removed tags
319 * linearly, binary search is used. The constant 20 is more or less random
320 * but seems to work well. It's exact value isn't so critical because it's
321 * the extremes where the difference is the biggest: when
322 * source_file->tags_array->len == tags_array->len (single file open) and
323 * source_file->tags_array->len << tags_array->len (the number of tags
324 * from the file is a small fraction of all tags).
326 if (source_file
->tags_array
->len
!= 0 &&
327 tags_array
->len
/ source_file
->tags_array
->len
< 20)
329 for (i
= 0; i
< tags_array
->len
; i
++)
331 TMTag
*tag
= tags_array
->pdata
[i
];
333 if (tag
->file
== source_file
)
334 tags_array
->pdata
[i
] = NULL
;
339 GPtrArray
*to_delete
= g_ptr_array_sized_new(source_file
->tags_array
->len
);
341 for (i
= 0; i
< source_file
->tags_array
->len
; i
++)
346 TMTag
*tag
= source_file
->tags_array
->pdata
[i
];
348 found
= tm_tags_find(tags_array
, tag
->name
, FALSE
, &tag_count
);
350 for (j
= 0; j
< tag_count
; j
++)
352 if (*found
!= NULL
&& (*found
)->file
== source_file
)
354 /* we cannot set the pointer to NULL now because the search wouldn't work */
355 g_ptr_array_add(to_delete
, found
);
356 /* no break - if there are multiple tags of the same name, we would
357 * always find the first instance and wouldn't remove others; duplicates
358 * in the to_delete list aren't a problem */
364 for (i
= 0; i
< to_delete
->len
; i
++)
366 TMTag
**tag
= to_delete
->pdata
[i
];
369 g_ptr_array_free(to_delete
, TRUE
);
372 tm_tags_prune(tags_array
);
375 /* Optimized merge sort for merging sorted values from one array to another
376 * where one of the arrays is much smaller than the other.
377 * The merge complexity depends mostly on the size of the small array
378 * and is almost independent of the size of the big array.
379 * In addition, get rid of the duplicates (if both big_array and small_array are duplicate-free). */
380 static GPtrArray
*merge(GPtrArray
*big_array
, GPtrArray
*small_array
,
381 TMSortOptions
*sort_options
, gboolean unref_duplicates
) {
382 guint i1
= 0; /* index to big_array */
383 guint i2
= 0; /* index to small_array */
386 GPtrArray
*res_array
= g_ptr_array_sized_new(big_array
->len
+ small_array
->len
);
391 /* swap the arrays if len(small) > len(big) */
392 if (small_array
->len
> big_array
->len
)
394 GPtrArray
*tmp
= small_array
;
395 small_array
= big_array
;
399 /* on average, we are merging a value from small_array every
400 * len(big_array) / len(small_array) values - good approximation for fast jump
402 initial_step
= (small_array
->len
> 0) ? big_array
->len
/ small_array
->len
: 1;
403 initial_step
= initial_step
> 4 ? initial_step
: 1;
406 while (i1
< big_array
->len
&& i2
< small_array
->len
)
409 gpointer val2
= small_array
->pdata
[i2
];
411 if (step
> 4) /* fast path start */
413 guint j1
= (i1
+ step
< big_array
->len
) ? i1
+ step
: big_array
->len
- 1;
415 val1
= big_array
->pdata
[j1
];
419 /* if the value in big_array after making the big step is still smaller
420 * than the value in small_array, we can copy all the values inbetween
421 * into the result without making expensive string comparisons */
422 if (tm_tag_compare(&val1
, &val2
, sort_options
) < 0)
426 val1
= big_array
->pdata
[i1
];
427 g_ptr_array_add(res_array
, val1
);
433 /* lower the step and try again */
436 } /* fast path end */
444 val1
= big_array
->pdata
[i1
];
445 cmpval
= tm_tag_compare(&val1
, &val2
, sort_options
);
448 g_ptr_array_add(res_array
, val1
);
453 g_ptr_array_add(res_array
, val2
);
455 /* value from small_array gets merged - reset the step size */
459 i1
++; /* remove the duplicate, keep just the newly merged value */
460 if (unref_duplicates
)
467 /* end of one of the arrays reached - copy the rest from the other array */
468 while (i1
< big_array
->len
)
469 g_ptr_array_add(res_array
, big_array
->pdata
[i1
++]);
470 while (i2
< small_array
->len
)
471 g_ptr_array_add(res_array
, small_array
->pdata
[i2
++]);
474 printf("cmpnums: %u\n", cmpnum
);
475 printf("total tags: %u\n", big_array
->len
);
476 printf("merged tags: %u\n\n", small_array
->len
);
482 GPtrArray
*tm_tags_merge(GPtrArray
*big_array
, GPtrArray
*small_array
,
483 TMTagAttrType
*sort_attributes
, gboolean unref_duplicates
)
485 GPtrArray
*res_array
;
486 TMSortOptions sort_options
;
488 sort_options
.sort_attrs
= sort_attributes
;
489 sort_options
.partial
= FALSE
;
490 res_array
= merge(big_array
, small_array
, &sort_options
, unref_duplicates
);
495 This function will extract the tags of the specified types from an array of tags.
496 The returned value is a GPtrArray which should be free-d with a call to
497 g_ptr_array_free(array, TRUE). However, do not free the tags themselves since they
499 @param tags_array The original array of tags
500 @param tag_types - The tag types to extract. Can be a bitmask. For example, passing
501 (tm_tag_typedef_t | tm_tag_struct_t) will extract all typedefs and structures from
503 @return an array of tags (NULL on failure)
505 GPtrArray
*tm_tags_extract(GPtrArray
*tags_array
, TMTagType tag_types
)
510 g_return_val_if_fail(tags_array
, NULL
);
512 new_tags
= g_ptr_array_new();
513 for (i
=0; i
< tags_array
->len
; ++i
)
515 if (NULL
!= tags_array
->pdata
[i
])
517 if (tag_types
& (((TMTag
*) tags_array
->pdata
[i
])->type
))
518 g_ptr_array_add(new_tags
, tags_array
->pdata
[i
]);
525 Completely frees an array of tags.
526 @param tags_array Array of tags to be freed.
527 @param free_array Whether the GptrArray is to be freed as well.
529 void tm_tags_array_free(GPtrArray
*tags_array
, gboolean free_all
)
534 for (i
= 0; i
< tags_array
->len
; ++i
)
535 tm_tag_unref(tags_array
->pdata
[i
]);
537 g_ptr_array_free(tags_array
, TRUE
);
539 g_ptr_array_set_size(tags_array
, 0);
543 /* copy/pasted bsearch() from libc extended with user_data for comparison function
544 * and using glib types */
545 static gpointer
binary_search(gpointer key
, gpointer base
, size_t nmemb
,
546 GCompareDataFunc compar
, gpointer user_data
)
557 p
= (gpointer
) (((const gchar
*) base
) + (idx
* sizeof(gpointer
)));
558 comparison
= (*compar
) (key
, p
, user_data
);
561 else if (comparison
> 0)
570 static gint
tag_search_cmp(gconstpointer ptr1
, gconstpointer ptr2
, gpointer user_data
)
572 gint res
= tm_tag_compare(ptr1
, ptr2
, user_data
);
576 TMSortOptions
*sort_options
= user_data
;
577 const GPtrArray
*tags_array
= sort_options
->tags_array
;
578 TMTag
**tag
= (TMTag
**) ptr2
;
580 /* if previous/next (depending on sort options) tag equal, we haven't
581 * found the first/last tag in a sequence of equal tags yet */
582 if (sort_options
->first
&& ptr2
!= &tags_array
->pdata
[0]) {
583 if (tm_tag_compare(ptr1
, tag
- 1, user_data
) == 0)
586 else if (!sort_options
->first
&& ptr2
!= &tags_array
->pdata
[tags_array
->len
-1])
588 if (tm_tag_compare(ptr1
, tag
+ 1, user_data
) == 0)
596 Returns a pointer to the position of the first matching tag in a (sorted) tags array.
597 The passed array of tags must be already sorted by name (searched with binary search).
598 @param tags_array Tag array (sorted on name)
599 @param name Name of the tag to locate.
600 @param partial If TRUE, matches the first part of the name instead of doing exact match.
601 @param tagCount Return location of the matched tags.
603 TMTag
**tm_tags_find(const GPtrArray
*tags_array
, const char *name
,
604 gboolean partial
, guint
*tagCount
)
607 TMSortOptions sort_options
;
610 if (!tags_array
|| !tags_array
->len
)
613 tag
= g_new0(TMTag
, 1);
614 tag
->name
= (char *) name
;
616 sort_options
.sort_attrs
= NULL
;
617 sort_options
.partial
= partial
;
618 sort_options
.tags_array
= tags_array
;
619 sort_options
.first
= TRUE
;
620 first
= (TMTag
**)binary_search(&tag
, tags_array
->pdata
, tags_array
->len
,
621 tag_search_cmp
, &sort_options
);
628 sort_options
.first
= FALSE
;
629 first_pos
= first
- (TMTag
**)tags_array
->pdata
;
630 /* search between the first element and end */
631 last
= (TMTag
**)binary_search(&tag
, first
, tags_array
->len
- first_pos
,
632 tag_search_cmp
, &sort_options
);
633 *tagCount
= last
- first
+ 1;
637 return (TMTag
**) first
;
640 /* Returns TMTag which "own" given line
641 @param line Current line in edited file.
642 @param file_tags A GPtrArray of edited file TMTag pointers.
643 @param tag_types the tag types to include in the match
644 @return TMTag pointers to owner tag. */
646 tm_get_current_tag (GPtrArray
* file_tags
, const gulong line
, const TMTagType tag_types
)
648 TMTag
*matching_tag
= NULL
;
649 if (file_tags
&& file_tags
->len
)
652 gulong matching_line
= 0;
654 for (i
= 0; (i
< file_tags
->len
); ++i
)
656 TMTag
*tag
= TM_TAG (file_tags
->pdata
[i
]);
657 if (tag
&& tag
->type
& tag_types
&&
658 tag
->line
<= line
&& tag
->line
> matching_line
)
661 matching_line
= tag
->line
;
669 gboolean
tm_tag_is_anon(const TMTag
*tag
)
671 return tag
->flags
& tm_tag_flag_anon_t
;
675 #ifdef TM_DEBUG /* various debugging functions */
678 Returns the type of tag as a string
679 @param tag The tag whose type is required
681 const char *tm_tag_type_name(const TMTag
*tag
)
683 g_return_val_if_fail(tag
, NULL
);
685 return tm_ctags_get_kind_name(tm_parser_get_tag_kind(tag
->type
, tag
->lang
), tag
->lang
);
689 Returns the TMTagType given the name of the type. Reverse of tm_tag_type_name.
690 @param tag_name Name of the tag type
692 TMTagType
tm_tag_name_type(const char* tag_name
, TMParserType lang
)
694 g_return_val_if_fail(tag_name
, tm_tag_undef_t
);
696 return tm_parser_get_tag_type(tm_ctags_get_kind_from_name(tag_name
, lang
), lang
);
699 static const char *tm_tag_impl_name(TMTag
*tag
)
701 g_return_val_if_fail(tag
, NULL
);
702 if (TAG_IMPL_VIRTUAL
== tag
->impl
)
708 static const char *tm_tag_access_name(TMTag
*tag
)
710 g_return_val_if_fail(tag
, NULL
);
711 if (TAG_ACCESS_PUBLIC
== tag
->access
)
713 else if (TAG_ACCESS_PROTECTED
== tag
->access
)
715 else if (TAG_ACCESS_PRIVATE
== tag
->access
)
722 Prints information about a tag to the given file pointer.
723 @param tag The tag whose info is required.
724 @param fp The file pointer of the file to print the info to.
726 void tm_tag_print(TMTag
*tag
, FILE *fp
)
728 const char *laccess
, *impl
, *type
;
731 laccess
= tm_tag_access_name(tag
);
732 impl
= tm_tag_impl_name(tag
);
733 type
= tm_tag_type_name(tag
);
735 fprintf(fp
, "%s ", laccess
);
737 fprintf(fp
, "%s ", impl
);
739 fprintf(fp
, "%s ", type
);
741 fprintf(fp
, "%s ", tag
->var_type
);
743 fprintf(fp
, "%s::", tag
->scope
);
744 fprintf(fp
, "%s", tag
->name
);
746 fprintf(fp
, "%s", tag
->arglist
);
747 if (tag
->inheritance
)
748 fprintf(fp
, " : from %s", tag
->inheritance
);
749 if ((tag
->file
) && (tag
->line
> 0))
750 fprintf(fp
, "[%s:%ld]", tag
->file
->file_name
756 Prints info about all tags in the array to the given file pointer.
758 void tm_tags_array_print(GPtrArray
*tags
, FILE *fp
)
762 if (!(tags
&& (tags
->len
> 0) && fp
))
764 for (i
= 0; i
< tags
->len
; ++i
)
766 tag
= TM_TAG(tags
->pdata
[i
]);
767 tm_tag_print(tag
, fp
);
772 Returns the depth of tag scope (useful for finding tag hierarchy
774 gint
tm_tag_scope_depth(const TMTag
*t
)
776 const gchar
*context_sep
= tm_parser_scope_separator(t
->lang
);
781 for (s
= t
->scope
, depth
= 0; s
; s
= strstr(s
, context_sep
))
789 #endif /* TM_DEBUG */