Mercurial > vim

comparison src/dict.c @ 9556:afaff1d283d3 v7.4.2055

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit https://github.com/vim/vim/commit/cd52459c387785796713826c63174cdeed295dd4 Author: Bram Moolenaar <Bram@vim.org> Date: Sun Jul 17 14:57:05 2016 +0200 patch 7.4.2055 Problem: eval.c is too big. Solution: Move Dictionary functions to dict.c.
author Christian Brabandt <cb@256bit.org>
date Sun, 17 Jul 2016 15:15:05 +0200
parents
children 1e68dfd7931b
comparison
equal deleted inserted replaced
9555:9560a5b782ee 9556:afaff1d283d3
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 * dict.c: Dictionary support
12 */
13 #define USING_FLOAT_STUFF
14
15 #include "vim.h"
16
17 #if defined(FEAT_EVAL) || defined(PROTO)
18
19 /* List head for garbage collection. Although there can be a reference loop
20 * from partial to dict to partial, we don't need to keep track of the partial,
21 * since it will get freed when the dict is unused and gets freed. */
22 static dict_T *first_dict = NULL; /* list of all dicts */
23
24 /*
25 * Allocate an empty header for a dictionary.
26 */
27 dict_T *
28 dict_alloc(void)
29 {
30 dict_T *d;
31
32 d = (dict_T *)alloc(sizeof(dict_T));
33 if (d != NULL)
34 {
35 /* Add the dict to the list of dicts for garbage collection. */
36 if (first_dict != NULL)
37 first_dict->dv_used_prev = d;
38 d->dv_used_next = first_dict;
39 d->dv_used_prev = NULL;
40 first_dict = d;
41
42 hash_init(&d->dv_hashtab);
43 d->dv_lock = 0;
44 d->dv_scope = 0;
45 d->dv_refcount = 0;
46 d->dv_copyID = 0;
47 }
48 return d;
49 }
50
51 /*
52 * Allocate an empty dict for a return value.
53 * Returns OK or FAIL.
54 */
55 int
56 rettv_dict_alloc(typval_T *rettv)
57 {
58 dict_T *d = dict_alloc();
59
60 if (d == NULL)
61 return FAIL;
62
63 rettv->vval.v_dict = d;
64 rettv->v_type = VAR_DICT;
65 rettv->v_lock = 0;
66 ++d->dv_refcount;
67 return OK;
68 }
69
70 /*
71 * Free a Dictionary, including all non-container items it contains.
72 * Ignores the reference count.
73 */
74 static void
75 dict_free_contents(dict_T *d)
76 {
77 int todo;
78 hashitem_T *hi;
79 dictitem_T *di;
80
81 /* Lock the hashtab, we don't want it to resize while freeing items. */
82 hash_lock(&d->dv_hashtab);
83 todo = (int)d->dv_hashtab.ht_used;
84 for (hi = d->dv_hashtab.ht_array; todo > 0; ++hi)
85 {
86 if (!HASHITEM_EMPTY(hi))
87 {
88 /* Remove the item before deleting it, just in case there is
89 * something recursive causing trouble. */
90 di = HI2DI(hi);
91 hash_remove(&d->dv_hashtab, hi);
92 clear_tv(&di->di_tv);
93 vim_free(di);
94 --todo;
95 }
96 }
97 hash_clear(&d->dv_hashtab);
98 }
99
100 static void
101 dict_free_dict(dict_T *d)
102 {
103 /* Remove the dict from the list of dicts for garbage collection. */
104 if (d->dv_used_prev == NULL)
105 first_dict = d->dv_used_next;
106 else
107 d->dv_used_prev->dv_used_next = d->dv_used_next;
108 if (d->dv_used_next != NULL)
109 d->dv_used_next->dv_used_prev = d->dv_used_prev;
110 vim_free(d);
111 }
112
113 static void
114 dict_free(dict_T *d)
115 {
116 if (!in_free_unref_items)
117 {
118 dict_free_contents(d);
119 dict_free_dict(d);
120 }
121 }
122
123 /*
124 * Unreference a Dictionary: decrement the reference count and free it when it
125 * becomes zero.
126 */
127 void
128 dict_unref(dict_T *d)
129 {
130 if (d != NULL && --d->dv_refcount <= 0)
131 dict_free(d);
132 }
133
134 /*
135 * Go through the list of dicts and free items without the copyID.
136 * Returns TRUE if something was freed.
137 */
138 int
139 dict_free_nonref(int copyID)
140 {
141 dict_T *dd;
142 int did_free = FALSE;
143
144 for (dd = first_dict; dd != NULL; dd = dd->dv_used_next)
145 if ((dd->dv_copyID & COPYID_MASK) != (copyID & COPYID_MASK))
146 {
147 /* Free the Dictionary and ordinary items it contains, but don't
148 * recurse into Lists and Dictionaries, they will be in the list
149 * of dicts or list of lists. */
150 dict_free_contents(dd);
151 did_free = TRUE;
152 }
153 return did_free;
154 }
155
156 void
157 dict_free_items(int copyID)
158 {
159 dict_T *dd, *dd_next;
160
161 for (dd = first_dict; dd != NULL; dd = dd_next)
162 {
163 dd_next = dd->dv_used_next;
164 if ((dd->dv_copyID & COPYID_MASK) != (copyID & COPYID_MASK))
165 dict_free_dict(dd);
166 }
167 }
168
169 /*
170 * Allocate a Dictionary item.
171 * The "key" is copied to the new item.
172 * Note that the value of the item "di_tv" still needs to be initialized!
173 * Returns NULL when out of memory.
174 */
175 dictitem_T *
176 dictitem_alloc(char_u *key)
177 {
178 dictitem_T *di;
179
180 di = (dictitem_T *)alloc((unsigned)(sizeof(dictitem_T) + STRLEN(key)));
181 if (di != NULL)
182 {
183 STRCPY(di->di_key, key);
184 di->di_flags = DI_FLAGS_ALLOC;
185 }
186 return di;
187 }
188
189 /*
190 * Make a copy of a Dictionary item.
191 */
192 static dictitem_T *
193 dictitem_copy(dictitem_T *org)
194 {
195 dictitem_T *di;
196
197 di = (dictitem_T *)alloc((unsigned)(sizeof(dictitem_T)
198 + STRLEN(org->di_key)));
199 if (di != NULL)
200 {
201 STRCPY(di->di_key, org->di_key);
202 di->di_flags = DI_FLAGS_ALLOC;
203 copy_tv(&org->di_tv, &di->di_tv);
204 }
205 return di;
206 }
207
208 /*
209 * Remove item "item" from Dictionary "dict" and free it.
210 */
211 void
212 dictitem_remove(dict_T *dict, dictitem_T *item)
213 {
214 hashitem_T *hi;
215
216 hi = hash_find(&dict->dv_hashtab, item->di_key);
217 if (HASHITEM_EMPTY(hi))
218 EMSG2(_(e_intern2), "dictitem_remove()");
219 else
220 hash_remove(&dict->dv_hashtab, hi);
221 dictitem_free(item);
222 }
223
224 /*
225 * Free a dict item. Also clears the value.
226 */
227 void
228 dictitem_free(dictitem_T *item)
229 {
230 clear_tv(&item->di_tv);
231 if (item->di_flags & DI_FLAGS_ALLOC)
232 vim_free(item);
233 }
234
235 /*
236 * Make a copy of dict "d". Shallow if "deep" is FALSE.
237 * The refcount of the new dict is set to 1.
238 * See item_copy() for "copyID".
239 * Returns NULL when out of memory.
240 */
241 dict_T *
242 dict_copy(dict_T *orig, int deep, int copyID)
243 {
244 dict_T *copy;
245 dictitem_T *di;
246 int todo;
247 hashitem_T *hi;
248
249 if (orig == NULL)
250 return NULL;
251
252 copy = dict_alloc();
253 if (copy != NULL)
254 {
255 if (copyID != 0)
256 {
257 orig->dv_copyID = copyID;
258 orig->dv_copydict = copy;
259 }
260 todo = (int)orig->dv_hashtab.ht_used;
261 for (hi = orig->dv_hashtab.ht_array; todo > 0 && !got_int; ++hi)
262 {
263 if (!HASHITEM_EMPTY(hi))
264 {
265 --todo;
266
267 di = dictitem_alloc(hi->hi_key);
268 if (di == NULL)
269 break;
270 if (deep)
271 {
272 if (item_copy(&HI2DI(hi)->di_tv, &di->di_tv, deep,
273 copyID) == FAIL)
274 {
275 vim_free(di);
276 break;
277 }
278 }
279 else
280 copy_tv(&HI2DI(hi)->di_tv, &di->di_tv);
281 if (dict_add(copy, di) == FAIL)
282 {
283 dictitem_free(di);
284 break;
285 }
286 }
287 }
288
289 ++copy->dv_refcount;
290 if (todo > 0)
291 {
292 dict_unref(copy);
293 copy = NULL;
294 }
295 }
296
297 return copy;
298 }
299
300 /*
301 * Add item "item" to Dictionary "d".
302 * Returns FAIL when out of memory and when key already exists.
303 */
304 int
305 dict_add(dict_T *d, dictitem_T *item)
306 {
307 return hash_add(&d->dv_hashtab, item->di_key);
308 }
309
310 /*
311 * Add a number or string entry to dictionary "d".
312 * When "str" is NULL use number "nr", otherwise use "str".
313 * Returns FAIL when out of memory and when key already exists.
314 */
315 int
316 dict_add_nr_str(
317 dict_T *d,
318 char *key,
319 varnumber_T nr,
320 char_u *str)
321 {
322 dictitem_T *item;
323
324 item = dictitem_alloc((char_u *)key);
325 if (item == NULL)
326 return FAIL;
327 item->di_tv.v_lock = 0;
328 if (str == NULL)
329 {
330 item->di_tv.v_type = VAR_NUMBER;
331 item->di_tv.vval.v_number = nr;
332 }
333 else
334 {
335 item->di_tv.v_type = VAR_STRING;
336 item->di_tv.vval.v_string = vim_strsave(str);
337 }
338 if (dict_add(d, item) == FAIL)
339 {
340 dictitem_free(item);
341 return FAIL;
342 }
343 return OK;
344 }
345
346 /*
347 * Add a list entry to dictionary "d".
348 * Returns FAIL when out of memory and when key already exists.
349 */
350 int
351 dict_add_list(dict_T *d, char *key, list_T *list)
352 {
353 dictitem_T *item;
354
355 item = dictitem_alloc((char_u *)key);
356 if (item == NULL)
357 return FAIL;
358 item->di_tv.v_lock = 0;
359 item->di_tv.v_type = VAR_LIST;
360 item->di_tv.vval.v_list = list;
361 if (dict_add(d, item) == FAIL)
362 {
363 dictitem_free(item);
364 return FAIL;
365 }
366 ++list->lv_refcount;
367 return OK;
368 }
369
370 /*
371 * Get the number of items in a Dictionary.
372 */
373 long
374 dict_len(dict_T *d)
375 {
376 if (d == NULL)
377 return 0L;
378 return (long)d->dv_hashtab.ht_used;
379 }
380
381 /*
382 * Find item "key[len]" in Dictionary "d".
383 * If "len" is negative use strlen(key).
384 * Returns NULL when not found.
385 */
386 dictitem_T *
387 dict_find(dict_T *d, char_u *key, int len)
388 {
389 #define AKEYLEN 200
390 char_u buf[AKEYLEN];
391 char_u *akey;
392 char_u *tofree = NULL;
393 hashitem_T *hi;
394
395 if (d == NULL)
396 return NULL;
397 if (len < 0)
398 akey = key;
399 else if (len >= AKEYLEN)
400 {
401 tofree = akey = vim_strnsave(key, len);
402 if (akey == NULL)
403 return NULL;
404 }
405 else
406 {
407 /* Avoid a malloc/free by using buf[]. */
408 vim_strncpy(buf, key, len);
409 akey = buf;
410 }
411
412 hi = hash_find(&d->dv_hashtab, akey);
413 vim_free(tofree);
414 if (HASHITEM_EMPTY(hi))
415 return NULL;
416 return HI2DI(hi);
417 }
418
419 /*
420 * Get a string item from a dictionary.
421 * When "save" is TRUE allocate memory for it.
422 * Returns NULL if the entry doesn't exist or out of memory.
423 */
424 char_u *
425 get_dict_string(dict_T *d, char_u *key, int save)
426 {
427 dictitem_T *di;
428 char_u *s;
429
430 di = dict_find(d, key, -1);
431 if (di == NULL)
432 return NULL;
433 s = get_tv_string(&di->di_tv);
434 if (save && s != NULL)
435 s = vim_strsave(s);
436 return s;
437 }
438
439 /*
440 * Get a number item from a dictionary.
441 * Returns 0 if the entry doesn't exist.
442 */
443 varnumber_T
444 get_dict_number(dict_T *d, char_u *key)
445 {
446 dictitem_T *di;
447
448 di = dict_find(d, key, -1);
449 if (di == NULL)
450 return 0;
451 return get_tv_number(&di->di_tv);
452 }
453
454 /*
455 * Return an allocated string with the string representation of a Dictionary.
456 * May return NULL.
457 */
458 char_u *
459 dict2string(typval_T *tv, int copyID, int restore_copyID)
460 {
461 garray_T ga;
462 int first = TRUE;
463 char_u *tofree;
464 char_u numbuf[NUMBUFLEN];
465 hashitem_T *hi;
466 char_u *s;
467 dict_T *d;
468 int todo;
469
470 if ((d = tv->vval.v_dict) == NULL)
471 return NULL;
472 ga_init2(&ga, (int)sizeof(char), 80);
473 ga_append(&ga, '{');
474
475 todo = (int)d->dv_hashtab.ht_used;
476 for (hi = d->dv_hashtab.ht_array; todo > 0 && !got_int; ++hi)
477 {
478 if (!HASHITEM_EMPTY(hi))
479 {
480 --todo;
481
482 if (first)
483 first = FALSE;
484 else
485 ga_concat(&ga, (char_u *)", ");
486
487 tofree = string_quote(hi->hi_key, FALSE);
488 if (tofree != NULL)
489 {
490 ga_concat(&ga, tofree);
491 vim_free(tofree);
492 }
493 ga_concat(&ga, (char_u *)": ");
494 s = echo_string_core(&HI2DI(hi)->di_tv, &tofree, numbuf, copyID,
495 FALSE, restore_copyID, TRUE);
496 if (s != NULL)
497 ga_concat(&ga, s);
498 vim_free(tofree);
499 if (s == NULL || did_echo_string_emsg)
500 break;
501 line_breakcheck();
502
503 }
504 }
505 if (todo > 0)
506 {
507 vim_free(ga.ga_data);
508 return NULL;
509 }
510
511 ga_append(&ga, '}');
512 ga_append(&ga, NUL);
513 return (char_u *)ga.ga_data;
514 }
515
516 /*
517 * Allocate a variable for a Dictionary and fill it from "*arg".
518 * Return OK or FAIL. Returns NOTDONE for {expr}.
519 */
520 int
521 get_dict_tv(char_u **arg, typval_T *rettv, int evaluate)
522 {
523 dict_T *d = NULL;
524 typval_T tvkey;
525 typval_T tv;
526 char_u *key = NULL;
527 dictitem_T *item;
528 char_u *start = skipwhite(*arg + 1);
529 char_u buf[NUMBUFLEN];
530
531 /*
532 * First check if it's not a curly-braces thing: {expr}.
533 * Must do this without evaluating, otherwise a function may be called
534 * twice. Unfortunately this means we need to call eval1() twice for the
535 * first item.
536 * But {} is an empty Dictionary.
537 */
538 if (*start != '}')
539 {
540 if (eval1(&start, &tv, FALSE) == FAIL) /* recursive! */
541 return FAIL;
542 if (*start == '}')
543 return NOTDONE;
544 }
545
546 if (evaluate)
547 {
548 d = dict_alloc();
549 if (d == NULL)
550 return FAIL;
551 }
552 tvkey.v_type = VAR_UNKNOWN;
553 tv.v_type = VAR_UNKNOWN;
554
555 *arg = skipwhite(*arg + 1);
556 while (**arg != '}' && **arg != NUL)
557 {
558 if (eval1(arg, &tvkey, evaluate) == FAIL) /* recursive! */
559 goto failret;
560 if (**arg != ':')
561 {
562 EMSG2(_("E720: Missing colon in Dictionary: %s"), *arg);
563 clear_tv(&tvkey);
564 goto failret;
565 }
566 if (evaluate)
567 {
568 key = get_tv_string_buf_chk(&tvkey, buf);
569 if (key == NULL)
570 {
571 /* "key" is NULL when get_tv_string_buf_chk() gave an errmsg */
572 clear_tv(&tvkey);
573 goto failret;
574 }
575 }
576
577 *arg = skipwhite(*arg + 1);
578 if (eval1(arg, &tv, evaluate) == FAIL) /* recursive! */
579 {
580 if (evaluate)
581 clear_tv(&tvkey);
582 goto failret;
583 }
584 if (evaluate)
585 {
586 item = dict_find(d, key, -1);
587 if (item != NULL)
588 {
589 EMSG2(_("E721: Duplicate key in Dictionary: \"%s\""), key);
590 clear_tv(&tvkey);
591 clear_tv(&tv);
592 goto failret;
593 }
594 item = dictitem_alloc(key);
595 clear_tv(&tvkey);
596 if (item != NULL)
597 {
598 item->di_tv = tv;
599 item->di_tv.v_lock = 0;
600 if (dict_add(d, item) == FAIL)
601 dictitem_free(item);
602 }
603 }
604
605 if (**arg == '}')
606 break;
607 if (**arg != ',')
608 {
609 EMSG2(_("E722: Missing comma in Dictionary: %s"), *arg);
610 goto failret;
611 }
612 *arg = skipwhite(*arg + 1);
613 }
614
615 if (**arg != '}')
616 {
617 EMSG2(_("E723: Missing end of Dictionary '}': %s"), *arg);
618 failret:
619 if (evaluate)
620 dict_free(d);
621 return FAIL;
622 }
623
624 *arg = skipwhite(*arg + 1);
625 if (evaluate)
626 {
627 rettv->v_type = VAR_DICT;
628 rettv->vval.v_dict = d;
629 ++d->dv_refcount;
630 }
631
632 return OK;
633 }
634
635 /*
636 * Go over all entries in "d2" and add them to "d1".
637 * When "action" is "error" then a duplicate key is an error.
638 * When "action" is "force" then a duplicate key is overwritten.
639 * Otherwise duplicate keys are ignored ("action" is "keep").
640 */
641 void
642 dict_extend(dict_T *d1, dict_T *d2, char_u *action)
643 {
644 dictitem_T *di1;
645 hashitem_T *hi2;
646 int todo;
647 char_u *arg_errmsg = (char_u *)N_("extend() argument");
648
649 todo = (int)d2->dv_hashtab.ht_used;
650 for (hi2 = d2->dv_hashtab.ht_array; todo > 0; ++hi2)
651 {
652 if (!HASHITEM_EMPTY(hi2))
653 {
654 --todo;
655 di1 = dict_find(d1, hi2->hi_key, -1);
656 if (d1->dv_scope != 0)
657 {
658 /* Disallow replacing a builtin function in l: and g:.
659 * Check the key to be valid when adding to any scope. */
660 if (d1->dv_scope == VAR_DEF_SCOPE
661 && HI2DI(hi2)->di_tv.v_type == VAR_FUNC
662 && var_check_func_name(hi2->hi_key, di1 == NULL))
663 break;
664 if (!valid_varname(hi2->hi_key))
665 break;
666 }
667 if (di1 == NULL)
668 {
669 di1 = dictitem_copy(HI2DI(hi2));
670 if (di1 != NULL && dict_add(d1, di1) == FAIL)
671 dictitem_free(di1);
672 }
673 else if (*action == 'e')
674 {
675 EMSG2(_("E737: Key already exists: %s"), hi2->hi_key);
676 break;
677 }
678 else if (*action == 'f' && HI2DI(hi2) != di1)
679 {
680 if (tv_check_lock(di1->di_tv.v_lock, arg_errmsg, TRUE)
681 || var_check_ro(di1->di_flags, arg_errmsg, TRUE))
682 break;
683 clear_tv(&di1->di_tv);
684 copy_tv(&HI2DI(hi2)->di_tv, &di1->di_tv);
685 }
686 }
687 }
688 }
689
690 /*
691 * Return the dictitem that an entry in a hashtable points to.
692 */
693 dictitem_T *
694 dict_lookup(hashitem_T *hi)
695 {
696 return HI2DI(hi);
697 }
698
699 /*
700 * Return TRUE when two dictionaries have exactly the same key/values.
701 */
702 int
703 dict_equal(
704 dict_T *d1,
705 dict_T *d2,
706 int ic, /* ignore case for strings */
707 int recursive) /* TRUE when used recursively */
708 {
709 hashitem_T *hi;
710 dictitem_T *item2;
711 int todo;
712
713 if (d1 == NULL && d2 == NULL)
714 return TRUE;
715 if (d1 == NULL || d2 == NULL)
716 return FALSE;
717 if (d1 == d2)
718 return TRUE;
719 if (dict_len(d1) != dict_len(d2))
720 return FALSE;
721
722 todo = (int)d1->dv_hashtab.ht_used;
723 for (hi = d1->dv_hashtab.ht_array; todo > 0; ++hi)
724 {
725 if (!HASHITEM_EMPTY(hi))
726 {
727 item2 = dict_find(d2, hi->hi_key, -1);
728 if (item2 == NULL)
729 return FALSE;
730 if (!tv_equal(&HI2DI(hi)->di_tv, &item2->di_tv, ic, recursive))
731 return FALSE;
732 --todo;
733 }
734 }
735 return TRUE;
736 }
737
738 /*
739 * Turn a dict into a list:
740 * "what" == 0: list of keys
741 * "what" == 1: list of values
742 * "what" == 2: list of items
743 */
744 void
745 dict_list(typval_T *argvars, typval_T *rettv, int what)
746 {
747 list_T *l2;
748 dictitem_T *di;
749 hashitem_T *hi;
750 listitem_T *li;
751 listitem_T *li2;
752 dict_T *d;
753 int todo;
754
755 if (argvars[0].v_type != VAR_DICT)
756 {
757 EMSG(_(e_dictreq));
758 return;
759 }
760 if ((d = argvars[0].vval.v_dict) == NULL)
761 return;
762
763 if (rettv_list_alloc(rettv) == FAIL)
764 return;
765
766 todo = (int)d->dv_hashtab.ht_used;
767 for (hi = d->dv_hashtab.ht_array; todo > 0; ++hi)
768 {
769 if (!HASHITEM_EMPTY(hi))
770 {
771 --todo;
772 di = HI2DI(hi);
773
774 li = listitem_alloc();
775 if (li == NULL)
776 break;
777 list_append(rettv->vval.v_list, li);
778
779 if (what == 0)
780 {
781 /* keys() */
782 li->li_tv.v_type = VAR_STRING;
783 li->li_tv.v_lock = 0;
784 li->li_tv.vval.v_string = vim_strsave(di->di_key);
785 }
786 else if (what == 1)
787 {
788 /* values() */
789 copy_tv(&di->di_tv, &li->li_tv);
790 }
791 else
792 {
793 /* items() */
794 l2 = list_alloc();
795 li->li_tv.v_type = VAR_LIST;
796 li->li_tv.v_lock = 0;
797 li->li_tv.vval.v_list = l2;
798 if (l2 == NULL)
799 break;
800 ++l2->lv_refcount;
801
802 li2 = listitem_alloc();
803 if (li2 == NULL)
804 break;
805 list_append(l2, li2);
806 li2->li_tv.v_type = VAR_STRING;
807 li2->li_tv.v_lock = 0;
808 li2->li_tv.vval.v_string = vim_strsave(di->di_key);
809
810 li2 = listitem_alloc();
811 if (li2 == NULL)
812 break;
813 list_append(l2, li2);
814 copy_tv(&di->di_tv, &li2->li_tv);
815 }
816 }
817 }
818 }
819
820 #endif /* defined(FEAT_EVAL) */