Mercurial > vim

comparison src/list.c @ 9560:1e68dfd7931b v7.4.2057

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit https://github.com/vim/vim/commit/da861d631d7e22654faee2789286c685ad548911 Author: Bram Moolenaar <Bram@vim.org> Date: Sun Jul 17 15:46:27 2016 +0200 patch 7.4.2057 Problem: eval.c is too big. Solution: Move List functions to list.c
author Christian Brabandt <cb@256bit.org>
date Sun, 17 Jul 2016 16:00:05 +0200
parents
children 5eaa708ab50d
comparison
equal deleted inserted replaced
9559:354168ab1997 9560:1e68dfd7931b
1 /* vi:set ts=8 sts=4 sw=4:
2 *
3 * VIM - Vi IMproved by Bram Moolenaar
4 *
5 * Do ":help uganda" in Vim to read copying and usage conditions.
6 * Do ":help credits" in Vim to see a list of people who contributed.
7 * See README.txt for an overview of the Vim source code.
8 */
9
10 /*
11 * list.c: List support
12 */
13
14 #include "vim.h"
15
16 #if defined(FEAT_EVAL) || defined(PROTO)
17
18 /* List heads for garbage collection. */
19 static list_T *first_list = NULL; /* list of all lists */
20
21 /*
22 * Add a watcher to a list.
23 */
24 void
25 list_add_watch(list_T *l, listwatch_T *lw)
26 {
27 lw->lw_next = l->lv_watch;
28 l->lv_watch = lw;
29 }
30
31 /*
32 * Remove a watcher from a list.
33 * No warning when it isn't found...
34 */
35 void
36 list_rem_watch(list_T *l, listwatch_T *lwrem)
37 {
38 listwatch_T *lw, **lwp;
39
40 lwp = &l->lv_watch;
41 for (lw = l->lv_watch; lw != NULL; lw = lw->lw_next)
42 {
43 if (lw == lwrem)
44 {
45 *lwp = lw->lw_next;
46 break;
47 }
48 lwp = &lw->lw_next;
49 }
50 }
51
52 /*
53 * Just before removing an item from a list: advance watchers to the next
54 * item.
55 */
56 void
57 list_fix_watch(list_T *l, listitem_T *item)
58 {
59 listwatch_T *lw;
60
61 for (lw = l->lv_watch; lw != NULL; lw = lw->lw_next)
62 if (lw->lw_item == item)
63 lw->lw_item = item->li_next;
64 }
65
66 /*
67 * Allocate an empty header for a list.
68 * Caller should take care of the reference count.
69 */
70 list_T *
71 list_alloc(void)
72 {
73 list_T *l;
74
75 l = (list_T *)alloc_clear(sizeof(list_T));
76 if (l != NULL)
77 {
78 /* Prepend the list to the list of lists for garbage collection. */
79 if (first_list != NULL)
80 first_list->lv_used_prev = l;
81 l->lv_used_prev = NULL;
82 l->lv_used_next = first_list;
83 first_list = l;
84 }
85 return l;
86 }
87
88 /*
89 * Allocate an empty list for a return value, with reference count set.
90 * Returns OK or FAIL.
91 */
92 int
93 rettv_list_alloc(typval_T *rettv)
94 {
95 list_T *l = list_alloc();
96
97 if (l == NULL)
98 return FAIL;
99
100 rettv->vval.v_list = l;
101 rettv->v_type = VAR_LIST;
102 rettv->v_lock = 0;
103 ++l->lv_refcount;
104 return OK;
105 }
106
107 /*
108 * Unreference a list: decrement the reference count and free it when it
109 * becomes zero.
110 */
111 void
112 list_unref(list_T *l)
113 {
114 if (l != NULL && --l->lv_refcount <= 0)
115 list_free(l);
116 }
117
118 /*
119 * Free a list, including all non-container items it points to.
120 * Ignores the reference count.
121 */
122 static void
123 list_free_contents(list_T *l)
124 {
125 listitem_T *item;
126
127 for (item = l->lv_first; item != NULL; item = l->lv_first)
128 {
129 /* Remove the item before deleting it. */
130 l->lv_first = item->li_next;
131 clear_tv(&item->li_tv);
132 vim_free(item);
133 }
134 }
135
136 /*
137 * Go through the list of lists and free items without the copyID.
138 * But don't free a list that has a watcher (used in a for loop), these
139 * are not referenced anywhere.
140 */
141 int
142 list_free_nonref(int copyID)
143 {
144 list_T *ll;
145 int did_free = FALSE;
146
147 for (ll = first_list; ll != NULL; ll = ll->lv_used_next)
148 if ((ll->lv_copyID & COPYID_MASK) != (copyID & COPYID_MASK)
149 && ll->lv_watch == NULL)
150 {
151 /* Free the List and ordinary items it contains, but don't recurse
152 * into Lists and Dictionaries, they will be in the list of dicts
153 * or list of lists. */
154 list_free_contents(ll);
155 did_free = TRUE;
156 }
157 return did_free;
158 }
159
160 static void
161 list_free_list(list_T *l)
162 {
163 /* Remove the list from the list of lists for garbage collection. */
164 if (l->lv_used_prev == NULL)
165 first_list = l->lv_used_next;
166 else
167 l->lv_used_prev->lv_used_next = l->lv_used_next;
168 if (l->lv_used_next != NULL)
169 l->lv_used_next->lv_used_prev = l->lv_used_prev;
170
171 vim_free(l);
172 }
173
174 void
175 list_free_items(int copyID)
176 {
177 list_T *ll, *ll_next;
178
179 for (ll = first_list; ll != NULL; ll = ll_next)
180 {
181 ll_next = ll->lv_used_next;
182 if ((ll->lv_copyID & COPYID_MASK) != (copyID & COPYID_MASK)
183 && ll->lv_watch == NULL)
184 {
185 /* Free the List and ordinary items it contains, but don't recurse
186 * into Lists and Dictionaries, they will be in the list of dicts
187 * or list of lists. */
188 list_free_list(ll);
189 }
190 }
191 }
192
193 void
194 list_free(list_T *l)
195 {
196 if (!in_free_unref_items)
197 {
198 list_free_contents(l);
199 list_free_list(l);
200 }
201 }
202
203 /*
204 * Allocate a list item.
205 * It is not initialized, don't forget to set v_lock.
206 */
207 listitem_T *
208 listitem_alloc(void)
209 {
210 return (listitem_T *)alloc(sizeof(listitem_T));
211 }
212
213 /*
214 * Free a list item. Also clears the value. Does not notify watchers.
215 */
216 void
217 listitem_free(listitem_T *item)
218 {
219 clear_tv(&item->li_tv);
220 vim_free(item);
221 }
222
223 /*
224 * Remove a list item from a List and free it. Also clears the value.
225 */
226 void
227 listitem_remove(list_T *l, listitem_T *item)
228 {
229 vimlist_remove(l, item, item);
230 listitem_free(item);
231 }
232
233 /*
234 * Get the number of items in a list.
235 */
236 long
237 list_len(list_T *l)
238 {
239 if (l == NULL)
240 return 0L;
241 return l->lv_len;
242 }
243
244 /*
245 * Return TRUE when two lists have exactly the same values.
246 */
247 int
248 list_equal(
249 list_T *l1,
250 list_T *l2,
251 int ic, /* ignore case for strings */
252 int recursive) /* TRUE when used recursively */
253 {
254 listitem_T *item1, *item2;
255
256 if (l1 == NULL || l2 == NULL)
257 return FALSE;
258 if (l1 == l2)
259 return TRUE;
260 if (list_len(l1) != list_len(l2))
261 return FALSE;
262
263 for (item1 = l1->lv_first, item2 = l2->lv_first;
264 item1 != NULL && item2 != NULL;
265 item1 = item1->li_next, item2 = item2->li_next)
266 if (!tv_equal(&item1->li_tv, &item2->li_tv, ic, recursive))
267 return FALSE;
268 return item1 == NULL && item2 == NULL;
269 }
270
271 /*
272 * Locate item with index "n" in list "l" and return it.
273 * A negative index is counted from the end; -1 is the last item.
274 * Returns NULL when "n" is out of range.
275 */
276 listitem_T *
277 list_find(list_T *l, long n)
278 {
279 listitem_T *item;
280 long idx;
281
282 if (l == NULL)
283 return NULL;
284
285 /* Negative index is relative to the end. */
286 if (n < 0)
287 n = l->lv_len + n;
288
289 /* Check for index out of range. */
290 if (n < 0 || n >= l->lv_len)
291 return NULL;
292
293 /* When there is a cached index may start search from there. */
294 if (l->lv_idx_item != NULL)
295 {
296 if (n < l->lv_idx / 2)
297 {
298 /* closest to the start of the list */
299 item = l->lv_first;
300 idx = 0;
301 }
302 else if (n > (l->lv_idx + l->lv_len) / 2)
303 {
304 /* closest to the end of the list */
305 item = l->lv_last;
306 idx = l->lv_len - 1;
307 }
308 else
309 {
310 /* closest to the cached index */
311 item = l->lv_idx_item;
312 idx = l->lv_idx;
313 }
314 }
315 else
316 {
317 if (n < l->lv_len / 2)
318 {
319 /* closest to the start of the list */
320 item = l->lv_first;
321 idx = 0;
322 }
323 else
324 {
325 /* closest to the end of the list */
326 item = l->lv_last;
327 idx = l->lv_len - 1;
328 }
329 }
330
331 while (n > idx)
332 {
333 /* search forward */
334 item = item->li_next;
335 ++idx;
336 }
337 while (n < idx)
338 {
339 /* search backward */
340 item = item->li_prev;
341 --idx;
342 }
343
344 /* cache the used index */
345 l->lv_idx = idx;
346 l->lv_idx_item = item;
347
348 return item;
349 }
350
351 /*
352 * Get list item "l[idx]" as a number.
353 */
354 long
355 list_find_nr(
356 list_T *l,
357 long idx,
358 int *errorp) /* set to TRUE when something wrong */
359 {
360 listitem_T *li;
361
362 li = list_find(l, idx);
363 if (li == NULL)
364 {
365 if (errorp != NULL)
366 *errorp = TRUE;
367 return -1L;
368 }
369 return (long)get_tv_number_chk(&li->li_tv, errorp);
370 }
371
372 /*
373 * Get list item "l[idx - 1]" as a string. Returns NULL for failure.
374 */
375 char_u *
376 list_find_str(list_T *l, long idx)
377 {
378 listitem_T *li;
379
380 li = list_find(l, idx - 1);
381 if (li == NULL)
382 {
383 EMSGN(_(e_listidx), idx);
384 return NULL;
385 }
386 return get_tv_string(&li->li_tv);
387 }
388
389 /*
390 * Locate "item" list "l" and return its index.
391 * Returns -1 when "item" is not in the list.
392 */
393 long
394 list_idx_of_item(list_T *l, listitem_T *item)
395 {
396 long idx = 0;
397 listitem_T *li;
398
399 if (l == NULL)
400 return -1;
401 idx = 0;
402 for (li = l->lv_first; li != NULL && li != item; li = li->li_next)
403 ++idx;
404 if (li == NULL)
405 return -1;
406 return idx;
407 }
408
409 /*
410 * Append item "item" to the end of list "l".
411 */
412 void
413 list_append(list_T *l, listitem_T *item)
414 {
415 if (l->lv_last == NULL)
416 {
417 /* empty list */
418 l->lv_first = item;
419 l->lv_last = item;
420 item->li_prev = NULL;
421 }
422 else
423 {
424 l->lv_last->li_next = item;
425 item->li_prev = l->lv_last;
426 l->lv_last = item;
427 }
428 ++l->lv_len;
429 item->li_next = NULL;
430 }
431
432 /*
433 * Append typval_T "tv" to the end of list "l".
434 * Return FAIL when out of memory.
435 */
436 int
437 list_append_tv(list_T *l, typval_T *tv)
438 {
439 listitem_T *li = listitem_alloc();
440
441 if (li == NULL)
442 return FAIL;
443 copy_tv(tv, &li->li_tv);
444 list_append(l, li);
445 return OK;
446 }
447
448 /*
449 * Add a dictionary to a list. Used by getqflist().
450 * Return FAIL when out of memory.
451 */
452 int
453 list_append_dict(list_T *list, dict_T *dict)
454 {
455 listitem_T *li = listitem_alloc();
456
457 if (li == NULL)
458 return FAIL;
459 li->li_tv.v_type = VAR_DICT;
460 li->li_tv.v_lock = 0;
461 li->li_tv.vval.v_dict = dict;
462 list_append(list, li);
463 ++dict->dv_refcount;
464 return OK;
465 }
466
467 /*
468 * Make a copy of "str" and append it as an item to list "l".
469 * When "len" >= 0 use "str[len]".
470 * Returns FAIL when out of memory.
471 */
472 int
473 list_append_string(list_T *l, char_u *str, int len)
474 {
475 listitem_T *li = listitem_alloc();
476
477 if (li == NULL)
478 return FAIL;
479 list_append(l, li);
480 li->li_tv.v_type = VAR_STRING;
481 li->li_tv.v_lock = 0;
482 if (str == NULL)
483 li->li_tv.vval.v_string = NULL;
484 else if ((li->li_tv.vval.v_string = (len >= 0 ? vim_strnsave(str, len)
485 : vim_strsave(str))) == NULL)
486 return FAIL;
487 return OK;
488 }
489
490 /*
491 * Append "n" to list "l".
492 * Returns FAIL when out of memory.
493 */
494 int
495 list_append_number(list_T *l, varnumber_T n)
496 {
497 listitem_T *li;
498
499 li = listitem_alloc();
500 if (li == NULL)
501 return FAIL;
502 li->li_tv.v_type = VAR_NUMBER;
503 li->li_tv.v_lock = 0;
504 li->li_tv.vval.v_number = n;
505 list_append(l, li);
506 return OK;
507 }
508
509 /*
510 * Insert typval_T "tv" in list "l" before "item".
511 * If "item" is NULL append at the end.
512 * Return FAIL when out of memory.
513 */
514 int
515 list_insert_tv(list_T *l, typval_T *tv, listitem_T *item)
516 {
517 listitem_T *ni = listitem_alloc();
518
519 if (ni == NULL)
520 return FAIL;
521 copy_tv(tv, &ni->li_tv);
522 list_insert(l, ni, item);
523 return OK;
524 }
525
526 void
527 list_insert(list_T *l, listitem_T *ni, listitem_T *item)
528 {
529 if (item == NULL)
530 /* Append new item at end of list. */
531 list_append(l, ni);
532 else
533 {
534 /* Insert new item before existing item. */
535 ni->li_prev = item->li_prev;
536 ni->li_next = item;
537 if (item->li_prev == NULL)
538 {
539 l->lv_first = ni;
540 ++l->lv_idx;
541 }
542 else
543 {
544 item->li_prev->li_next = ni;
545 l->lv_idx_item = NULL;
546 }
547 item->li_prev = ni;
548 ++l->lv_len;
549 }
550 }
551
552 /*
553 * Extend "l1" with "l2".
554 * If "bef" is NULL append at the end, otherwise insert before this item.
555 * Returns FAIL when out of memory.
556 */
557 int
558 list_extend(list_T *l1, list_T *l2, listitem_T *bef)
559 {
560 listitem_T *item;
561 int todo = l2->lv_len;
562
563 /* We also quit the loop when we have inserted the original item count of
564 * the list, avoid a hang when we extend a list with itself. */
565 for (item = l2->lv_first; item != NULL && --todo >= 0; item = item->li_next)
566 if (list_insert_tv(l1, &item->li_tv, bef) == FAIL)
567 return FAIL;
568 return OK;
569 }
570
571 /*
572 * Concatenate lists "l1" and "l2" into a new list, stored in "tv".
573 * Return FAIL when out of memory.
574 */
575 int
576 list_concat(list_T *l1, list_T *l2, typval_T *tv)
577 {
578 list_T *l;
579
580 if (l1 == NULL || l2 == NULL)
581 return FAIL;
582
583 /* make a copy of the first list. */
584 l = list_copy(l1, FALSE, 0);
585 if (l == NULL)
586 return FAIL;
587 tv->v_type = VAR_LIST;
588 tv->vval.v_list = l;
589
590 /* append all items from the second list */
591 return list_extend(l, l2, NULL);
592 }
593
594 /*
595 * Make a copy of list "orig". Shallow if "deep" is FALSE.
596 * The refcount of the new list is set to 1.
597 * See item_copy() for "copyID".
598 * Returns NULL when out of memory.
599 */
600 list_T *
601 list_copy(list_T *orig, int deep, int copyID)
602 {
603 list_T *copy;
604 listitem_T *item;
605 listitem_T *ni;
606
607 if (orig == NULL)
608 return NULL;
609
610 copy = list_alloc();
611 if (copy != NULL)
612 {
613 if (copyID != 0)
614 {
615 /* Do this before adding the items, because one of the items may
616 * refer back to this list. */
617 orig->lv_copyID = copyID;
618 orig->lv_copylist = copy;
619 }
620 for (item = orig->lv_first; item != NULL && !got_int;
621 item = item->li_next)
622 {
623 ni = listitem_alloc();
624 if (ni == NULL)
625 break;
626 if (deep)
627 {
628 if (item_copy(&item->li_tv, &ni->li_tv, deep, copyID) == FAIL)
629 {
630 vim_free(ni);
631 break;
632 }
633 }
634 else
635 copy_tv(&item->li_tv, &ni->li_tv);
636 list_append(copy, ni);
637 }
638 ++copy->lv_refcount;
639 if (item != NULL)
640 {
641 list_unref(copy);
642 copy = NULL;
643 }
644 }
645
646 return copy;
647 }
648
649 /*
650 * Remove items "item" to "item2" from list "l".
651 * Does not free the listitem or the value!
652 * This used to be called list_remove, but that conflicts with a Sun header
653 * file.
654 */
655 void
656 vimlist_remove(list_T *l, listitem_T *item, listitem_T *item2)
657 {
658 listitem_T *ip;
659
660 /* notify watchers */
661 for (ip = item; ip != NULL; ip = ip->li_next)
662 {
663 --l->lv_len;
664 list_fix_watch(l, ip);
665 if (ip == item2)
666 break;
667 }
668
669 if (item2->li_next == NULL)
670 l->lv_last = item->li_prev;
671 else
672 item2->li_next->li_prev = item->li_prev;
673 if (item->li_prev == NULL)
674 l->lv_first = item2->li_next;
675 else
676 item->li_prev->li_next = item2->li_next;
677 l->lv_idx_item = NULL;
678 }
679
680 /*
681 * Return an allocated string with the string representation of a list.
682 * May return NULL.
683 */
684 char_u *
685 list2string(typval_T *tv, int copyID, int restore_copyID)
686 {
687 garray_T ga;
688
689 if (tv->vval.v_list == NULL)
690 return NULL;
691 ga_init2(&ga, (int)sizeof(char), 80);
692 ga_append(&ga, '[');
693 if (list_join(&ga, tv->vval.v_list, (char_u *)", ",
694 FALSE, restore_copyID, copyID) == FAIL)
695 {
696 vim_free(ga.ga_data);
697 return NULL;
698 }
699 ga_append(&ga, ']');
700 ga_append(&ga, NUL);
701 return (char_u *)ga.ga_data;
702 }
703
704 typedef struct join_S {
705 char_u *s;
706 char_u *tofree;
707 } join_T;
708
709 static int
710 list_join_inner(
711 garray_T *gap, /* to store the result in */
712 list_T *l,
713 char_u *sep,
714 int echo_style,
715 int restore_copyID,
716 int copyID,
717 garray_T *join_gap) /* to keep each list item string */
718 {
719 int i;
720 join_T *p;
721 int len;
722 int sumlen = 0;
723 int first = TRUE;
724 char_u *tofree;
725 char_u numbuf[NUMBUFLEN];
726 listitem_T *item;
727 char_u *s;
728
729 /* Stringify each item in the list. */
730 for (item = l->lv_first; item != NULL && !got_int; item = item->li_next)
731 {
732 s = echo_string_core(&item->li_tv, &tofree, numbuf, copyID,
733 echo_style, restore_copyID, FALSE);
734 if (s == NULL)
735 return FAIL;
736
737 len = (int)STRLEN(s);
738 sumlen += len;
739
740 (void)ga_grow(join_gap, 1);
741 p = ((join_T *)join_gap->ga_data) + (join_gap->ga_len++);
742 if (tofree != NULL || s != numbuf)
743 {
744 p->s = s;
745 p->tofree = tofree;
746 }
747 else
748 {
749 p->s = vim_strnsave(s, len);
750 p->tofree = p->s;
751 }
752
753 line_breakcheck();
754 if (did_echo_string_emsg) /* recursion error, bail out */
755 break;
756 }
757
758 /* Allocate result buffer with its total size, avoid re-allocation and
759 * multiple copy operations. Add 2 for a tailing ']' and NUL. */
760 if (join_gap->ga_len >= 2)
761 sumlen += (int)STRLEN(sep) * (join_gap->ga_len - 1);
762 if (ga_grow(gap, sumlen + 2) == FAIL)
763 return FAIL;
764
765 for (i = 0; i < join_gap->ga_len && !got_int; ++i)
766 {
767 if (first)
768 first = FALSE;
769 else
770 ga_concat(gap, sep);
771 p = ((join_T *)join_gap->ga_data) + i;
772
773 if (p->s != NULL)
774 ga_concat(gap, p->s);
775 line_breakcheck();
776 }
777
778 return OK;
779 }
780
781 /*
782 * Join list "l" into a string in "*gap", using separator "sep".
783 * When "echo_style" is TRUE use String as echoed, otherwise as inside a List.
784 * Return FAIL or OK.
785 */
786 int
787 list_join(
788 garray_T *gap,
789 list_T *l,
790 char_u *sep,
791 int echo_style,
792 int restore_copyID,
793 int copyID)
794 {
795 garray_T join_ga;
796 int retval;
797 join_T *p;
798 int i;
799
800 if (l->lv_len < 1)
801 return OK; /* nothing to do */
802 ga_init2(&join_ga, (int)sizeof(join_T), l->lv_len);
803 retval = list_join_inner(gap, l, sep, echo_style, restore_copyID,
804 copyID, &join_ga);
805
806 /* Dispose each item in join_ga. */
807 if (join_ga.ga_data != NULL)
808 {
809 p = (join_T *)join_ga.ga_data;
810 for (i = 0; i < join_ga.ga_len; ++i)
811 {
812 vim_free(p->tofree);
813 ++p;
814 }
815 ga_clear(&join_ga);
816 }
817
818 return retval;
819 }
820
821 /*
822 * Allocate a variable for a List and fill it from "*arg".
823 * Return OK or FAIL.
824 */
825 int
826 get_list_tv(char_u **arg, typval_T *rettv, int evaluate)
827 {
828 list_T *l = NULL;
829 typval_T tv;
830 listitem_T *item;
831
832 if (evaluate)
833 {
834 l = list_alloc();
835 if (l == NULL)
836 return FAIL;
837 }
838
839 *arg = skipwhite(*arg + 1);
840 while (**arg != ']' && **arg != NUL)
841 {
842 if (eval1(arg, &tv, evaluate) == FAIL) /* recursive! */
843 goto failret;
844 if (evaluate)
845 {
846 item = listitem_alloc();
847 if (item != NULL)
848 {
849 item->li_tv = tv;
850 item->li_tv.v_lock = 0;
851 list_append(l, item);
852 }
853 else
854 clear_tv(&tv);
855 }
856
857 if (**arg == ']')
858 break;
859 if (**arg != ',')
860 {
861 EMSG2(_("E696: Missing comma in List: %s"), *arg);
862 goto failret;
863 }
864 *arg = skipwhite(*arg + 1);
865 }
866
867 if (**arg != ']')
868 {
869 EMSG2(_("E697: Missing end of List ']': %s"), *arg);
870 failret:
871 if (evaluate)
872 list_free(l);
873 return FAIL;
874 }
875
876 *arg = skipwhite(*arg + 1);
877 if (evaluate)
878 {
879 rettv->v_type = VAR_LIST;
880 rettv->vval.v_list = l;
881 ++l->lv_refcount;
882 }
883
884 return OK;
885 }
886
887 #endif /* defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) */