1 /*
2 * list.c -- list utility functions.
3 *
4 * Copyright (C) 1998 by Massimiliano Ghilardi
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string.h>
16 #include <unistd.h>
17 #include <time.h>
18 #include <sys/types.h>
19 #include <sys/time.h>
20
21 #ifdef USE_REGEXP
22 # include <regex.h>
23 #endif
24
25 #include "defines.h"
26 #include "main.h"
27 #include "utils.h"
28 #include "cmd2.h"
29 #include "tty.h"
30 #include "eval.h"
31
32 /*
33 * compare two times, return -1 if t1 < t2, 1 if t1 > t2, 0 if t1 == t2
34 */
__P2(vtime *,t1,vtime *,t2)35 int cmp_vtime __P2 (vtime *,t1, vtime *,t2)
36 {
37 int i;
38 i = t1->tv_sec < t2->tv_sec ? -1 : t1->tv_sec > t2->tv_sec ? 1 : 0;
39 if (!i)
40 i = t1->tv_usec < t2->tv_usec ? -1 : t1->tv_usec > t2->tv_usec ? 1 : 0;
41 return i;
42 }
43
44 /*
45 * add t2 to t1 (i.e. t1 += t2)
46 */
__P2(vtime *,t1,vtime *,t2)47 void add_vtime __P2 (vtime *,t1, vtime *,t2)
48 {
49 t1->tv_sec += t2->tv_sec;
50 if ((t1->tv_usec += t2->tv_usec) >= uSEC_PER_SEC) {
51 t1->tv_sec += t1->tv_usec / uSEC_PER_SEC;
52 t1->tv_usec %= uSEC_PER_SEC;
53 }
54 }
55
56 /*
57 * Return t1 - t2, in milliseconds
58 */
__P2(vtime *,t1,vtime *,t2)59 long diff_vtime __P2 (vtime *,t1, vtime *,t2)
60 {
61 return (t1->tv_sec - t2->tv_sec) * mSEC_PER_SEC +
62 (t1->tv_usec - t2->tv_usec) / uSEC_PER_mSEC;
63 }
64
__P2(defnode *,node1,defnode *,node2)65 int rev_sort __P2 (defnode *,node1, defnode *,node2)
66 {
67 return -1;
68 }
69
70 /*
71 * standard ASCII comparison between nodes
72 */
__P2(defnode *,node1,defnode *,node2)73 int ascii_sort __P2 (defnode *,node1, defnode *,node2)
74 {
75 return strcmp(node1->sortfield, node2->sortfield);
76 }
77
__P2(defnode *,node1,defnode *,node2)78 int rev_ascii_sort __P2 (defnode *,node1, defnode *,node2)
79 {
80 return strcmp(node2->sortfield, node1->sortfield);
81 }
82
83
84 /*
85 * comparison between times of execution of nodes
86 * (return -1 if node1->when < node2->when)
87 */
__P2(defnode *,node1,defnode *,node2)88 int time_sort __P2 (defnode *,node1, defnode *,node2)
89 {
90 return cmp_vtime(&((delaynode *)node1)->when, &((delaynode *)node2)->when);
91 }
92
93 /*
94 * reverse comparison between times of execution of nodes
95 * (return -1 if node1->when > node2->when)
96 */
__P2(defnode *,node1,defnode *,node2)97 int rev_time_sort __P2 (defnode *,node1, defnode *,node2)
98 {
99 return cmp_vtime(&((delaynode *)node2)->when, &((delaynode *)node1)->when);
100 }
101
102 /*
103 * compute the hash value of a name
104 */
__P2(char *,name,int,optlen)105 int hash __P2 (char *,name, int,optlen)
106 {
107 int h = 0, i = 0;
108 if (optlen < 0)
109 optlen = strlen(name);
110 while (optlen-- > 0) {
111 h += ((*name++) ^ i) << i;
112 if (++i == LOG_MAX_HASH)
113 i = 0;
114 }
115 return (h + (h >> LOG_MAX_HASH) + (h >> (2*LOG_MAX_HASH))) & (MAX_HASH-1);
116 }
117
118 /*
119 * generic list node adding routine
120 */
__P3(defnode *,newnode,defnode **,base,function_sort,sort)121 void add_node __P3 (defnode *,newnode, defnode **,base, function_sort,sort)
122 {
123 while((*base) && (!sort || (*sort)(newnode, *base) > 0))
124 base = &(*base)->next;
125 newnode->next = *base;
126 *base = newnode;
127 }
128
__P3(sortednode *,newnode,sortednode **,base,function_sort,sort)129 static void add_sortednode __P3 (sortednode *,newnode, sortednode **,base, function_sort,sort)
130 {
131 while((*base) && (!sort || (*sort)((defnode *)newnode, (defnode *)*base) > 0))
132 base = &(*base)->snext;
133 newnode->snext = *base;
134 *base = newnode;
135 }
136
__P1(defnode **,base)137 void reverse_list __P1 (defnode **,base)
138 {
139 defnode *node = *base, *list = NULL, *tmp;
140 while (node) {
141 tmp = node->next;
142 node->next = list;
143 list = node;
144 node = tmp;
145 }
146 *base = list;
147 }
148
__P1(sortednode **,base)149 void reverse_sortedlist __P1 (sortednode **,base)
150 {
151 sortednode *node = *base, *list = NULL, *tmp;
152 while (node) {
153 tmp = node->snext;
154 node->snext = list;
155 list = node;
156 node = tmp;
157 }
158 *base = list;
159 }
160
__P2(sortednode *,self,sortednode **,base)161 static sortednode **selflookup_sortednode __P2 (sortednode *,self, sortednode **,base)
162 {
163 sortednode **p = base;
164 while (*p && *p != self)
165 p = &(*p)->snext;
166 if (!*p) {
167 PRINTF("#internal error, selflookup_sortednode(\"%s\") failed!\n", self->sortfield);
168 error = INTERNAL_ERROR;
169 }
170 return p;
171 }
172
173 /*
174 * add a node to the alias list
175 */
__P2(char *,name,char *,subst)176 void add_aliasnode __P2 (char *,name, char *,subst)
177 {
178 aliasnode *new = (aliasnode*)malloc(sizeof(aliasnode));
179 if (!new) {
180 errmsg("malloc");
181 return;
182 }
183
184 new->group = NULL;
185 new->active = 1;
186 new->name = my_strdup(name);
187 new->subst = my_strdup(subst);
188 if ((name && !new->name) || (subst && !new->subst)) {
189 errmsg("malloc");
190 if (new->name)
191 free(new->name);
192 if (new->subst)
193 free(new->subst);
194 free(new);
195 return;
196 }
197 add_node((defnode*)new, (defnode**)&aliases[hash(name,-1)], rev_sort);
198 add_sortednode((sortednode*)new, (sortednode**)&sortedaliases, rev_ascii_sort);
199 }
200
201 /*
202 * add a node to the marker list
203 */
__P4(char *,pattern,int,attrcode,char,mbeg,char,wild)204 void add_marknode __P4 (char *,pattern, int,attrcode, char,mbeg, char,wild)
205 {
206 marknode **p, *new = (marknode*)malloc(sizeof(marknode));
207 int i;
208 if (!new) {
209 errmsg("malloc");
210 return;
211 }
212 new->pattern = my_strdup(pattern);
213 new->attrcode = attrcode;
214 new->start = new->end = NULL;
215 new->mbeg = mbeg;
216 new->wild = wild;
217 if (!new->pattern) {
218 errmsg("malloc");
219 free(new);
220 return;
221 }
222 #ifdef DO_SORT
223 add_node((defnode*)new, (defnode**)&markers, ascii_sort);
224 #else
225 for (p=&markers, i=1; *p && (a_nice==0 || i<a_nice); p = &(*p)->next, i++)
226 ;
227 new->next = *p;
228 *p = new;
229 #endif
230 }
231
232 /*
233 * add a node to the action list
234 */
__P6(char *,pattern,char *,command,char *,label,int,active,int,type,void *,vregexp)235 void add_actionnode __P6 (char *,pattern, char *,command, char *,label, int,active, int,type, void *,vregexp)
236 {
237 actionnode **p, *new = (actionnode*)malloc(sizeof(actionnode));
238 int i;
239 if (!new) {
240 errmsg("malloc");
241 return;
242 }
243
244 new->group = NULL;
245 new->pattern = my_strdup(pattern);
246 new->command = my_strdup(command);
247 new->label = my_strdup(label);
248 new->active = active;
249 new->type = type;
250 #ifdef USE_REGEXP
251 new->regexp = vregexp;
252 #endif
253 if (!new->pattern || (command && !new->command) || (label && !new->label)) {
254 errmsg("malloc");
255 if (new->pattern)
256 free(new->pattern);
257 if (new->command)
258 free(new->command);
259 if (new->label)
260 free(new->label);
261 free(new);
262 return;
263 }
264 #ifdef DO_SORT
265 add_node((defnode*)new, (defnode**)&actions, ascii_sort);
266 #else
267 for (p=&actions, i=1; *p && (a_nice==0 || i<a_nice); p = &(*p)->next, i++)
268 ;
269 new->next = *p;
270 *p = new;
271 #endif
272 }
273
274 /*
275 * add a node to the prompt list
276 */
__P6(char *,pattern,char *,command,char *,label,int,active,int,type,void *,vregexp)277 void add_promptnode __P6 (char *,pattern, char *,command, char *,label, int,active, int,type, void *,vregexp)
278 {
279 promptnode **p, *new = (promptnode*)malloc(sizeof(promptnode));
280 int i;
281 if (!new) {
282 errmsg("malloc");
283 return;
284 }
285
286 new->pattern = my_strdup(pattern);
287 new->command = my_strdup(command);
288 new->label = my_strdup(label);
289 new->active = active;
290 new->type = type;
291 #ifdef USE_REGEXP
292 new->regexp = vregexp;
293 #endif
294 if (!new->pattern || (command && !new->command) || (label && !new->label)) {
295 errmsg("malloc");
296 if (new->pattern)
297 free(new->pattern);
298 if (new->command)
299 free(new->command);
300 if (new->label)
301 free(new->label);
302 free(new);
303 return;
304 }
305 #ifdef DO_SORT
306 add_node((defnode*)new, (defnode**)&prompts, ascii_sort);
307 #else
308 for (p=&prompts, i=1; *p && (a_nice==0 || i<a_nice); p = &(*p)->next, i++)
309 ;
310 new->next = *p;
311 *p = new;
312 #endif
313 }
314
315 /*
316 * add a node to the keydef list
317 */
__P5(char *,name,char *,sequence,int,seqlen,function_str,funct,char *,call_data)318 void add_keynode __P5 (char *,name, char *,sequence, int,seqlen, function_str,funct, char *,call_data)
319 {
320 keynode *new = (keynode*)malloc(sizeof(keynode));
321 if (!new) {
322 errmsg("malloc");
323 return;
324 }
325 new->name = my_strdup(name);
326 if (!seqlen) seqlen = strlen(sequence);
327 new->sequence = (char *)malloc(seqlen + 1);
328 memmove(new->sequence, sequence, seqlen);
329 new->seqlen = seqlen;
330 new->funct = funct;
331 new->call_data = my_strdup(call_data);
332 if (!new->name || !new->sequence || (call_data && !new->call_data)) {
333 errmsg("malloc");
334 if (new->name)
335 free(new->name);
336 if (new->sequence)
337 free(new->sequence);
338 if (new->call_data)
339 free(new->call_data);
340 free(new);
341 return;
342 }
343 add_node((defnode*)new, (defnode**)&keydefs, ascii_sort);
344 }
345
346 /*
347 * add a node to the delayed command list
348 * is_dead == 1 means when < now (and so cannot be executed anymore)
349 */
__P4(char *,name,char *,command,vtime *,when,int,is_dead)350 delaynode *add_delaynode __P4 (char *,name, char *,command, vtime *,when, int,is_dead)
351 {
352 delaynode *new = (delaynode*)malloc(sizeof(delaynode));
353 if (!new) {
354 errmsg("malloc");
355 return NULL;
356 }
357 new->name = my_strdup(name);
358 new->command = my_strdup(command);
359 if (!new->name || (command && !new->command)) {
360 errmsg("malloc");
361 if (new->name)
362 free(new->name);
363 if (new->command)
364 free(new->command);
365 free(new);
366 return NULL;
367 }
368
369 new->when.tv_sec = when->tv_sec;
370 new->when.tv_usec = when->tv_usec;
371 if (is_dead)
372 add_node((defnode*)new, (defnode**)&dead_delays, rev_time_sort);
373 else
374 add_node((defnode*)new, (defnode**)&delays, time_sort);
375
376 return new;
377 }
378
379 /*
380 * add a node to named variables list
381 *
382 * do NOT allocate a ptr!
383 */
__P2(char *,name,int,type)384 varnode *add_varnode __P2 (char *,name, int,type)
385 {
386 varnode *new;
387 int m, n;
388
389 if (type)
390 type = 1;
391
392 if (num_named_vars[type] >= max_named_vars) {
393 /* we are running low on var pointers. try to enlarge */
394 m = NUMTOT + max_named_vars;
395 n = NUMTOT + max_named_vars * 2;
396 if (n < 0) {
397 /* overflow */
398 print_error(error=OUT_OF_VAR_SPACE_ERROR);
399 return NULL;
400 }
401 else {
402 vars *newvar;
403 if ((newvar = (vars *)realloc(var, n*sizeof(vars) )))
404 ;
405 else if ((newvar = (vars *)malloc( n*sizeof(vars) ))) {
406 memmove(newvar, var, m * sizeof(vars));
407 free((void *)var);
408 } else {
409 errmsg("malloc");
410 return NULL;
411 }
412 var = newvar;
413 max_named_vars += n-m;
414 memzero(var + m, (n-m)*sizeof(vars));
415 }
416 }
417
418 new = (varnode*)malloc(sizeof(varnode));
419 if (!new) {
420 errmsg("malloc");
421 return NULL;
422 }
423 new->name = my_strdup(name);
424 if (name && !new->name) {
425 errmsg("malloc");
426 free(new);
427 return NULL;
428 }
429 new->num = 0;
430 new->str = (ptr)0;
431 new->index = m = NUMPARAM + num_named_vars[type];
432
433 if (type)
434 VAR[m].str = &new->str;
435 else
436 VAR[m].num = &new->num;
437 num_named_vars[type]++;
438
439 add_node((defnode*)new, (defnode**)&named_vars[type][hash(name,-1)], rev_sort);
440 add_sortednode((sortednode*)new, (sortednode**)&sortednamed_vars[type], rev_ascii_sort);
441 return new;
442 }
443
444 /*
445 * look up an alias node by name:
446 * return pointer to pointer to node or a pointer to NULL if nothing found
447 */
__P1(char *,name)448 aliasnode **lookup_alias __P1 (char *,name)
449 {
450 aliasnode **p = &aliases[hash(name,-1)];
451 while (*p && strcmp(name, (*p)->name))
452 p = &(*p)->next;
453 return p;
454 }
455
456 /*
457 * look up an action node by label:
458 * return pointer to pointer to node or a pointer to NULL if nothing found
459 */
__P1(char *,label)460 actionnode **lookup_action __P1 (char *,label)
461 {
462 actionnode **p = &actions;
463 while (*p && strcmp(label, (*p)->label))
464 p = &(*p)->next;
465 return p;
466 }
467
468 /*
469 * look up an action node by pattern:
470 * return pointer to pointer to node or a pointer to NULL if nothing found
471 */
__P1(char *,pattern)472 actionnode **lookup_action_pattern __P1 (char *,pattern)
473 {
474 actionnode **p = &actions;
475 while (*p && strcmp(pattern, (*p)->pattern))
476 p = &(*p)->next;
477 return p;
478 }
479
480 /*
481 * look up a prompt node by label:
482 * return pointer to pointer to node or a pointer to NULL if nothing found
483 */
__P1(char *,label)484 actionnode **lookup_prompt __P1 (char *,label)
485 {
486 promptnode **p = &prompts;
487 while (*p && strcmp(label, (*p)->label))
488 p = &(*p)->next;
489 return p;
490 }
491
492 /*
493 * look up an marker node by pattern:
494 * return pointer to pointer to node or a pointer to NULL if nothing found
495 */
__P2(char *,pattern,char,mbeg)496 marknode **lookup_marker __P2 (char *,pattern, char,mbeg)
497 {
498 marknode **p = &markers;
499 while (*p && (mbeg != (*p)->mbeg || strcmp(pattern, (*p)->pattern)))
500 p = &(*p)->next;
501 return p;
502 }
503
504 /*
505 * look up a key node by name:
506 * return pointer to pointer to node or a pointer to NULL if nothing found
507 */
__P1(char *,name)508 keynode **lookup_key __P1 (char *,name)
509 {
510 keynode **p = &keydefs;
511
512 while (*p && strcmp(name, (*p)->name))
513 p = &(*p)->next;
514 return p;
515 }
516
517 /*
518 * look up a delayed command node by label:
519 * return pointer to pointer to node or a pointer to NULL if nothing found
520 */
__P2(char *,name,int,is_dead)521 delaynode **lookup_delay __P2 (char *,name, int,is_dead)
522 {
523 delaynode **p = (is_dead ? &dead_delays : &delays);
524 while (*p && strcmp(name, (*p)->name))
525 p = &(*p)->next;
526 return p;
527 }
528
529 /*
530 * look up a named variable node by name:
531 * return pointer to pointer to node or a pointer to NULL if nothing found
532 */
__P2(char *,name,int,type)533 varnode **lookup_varnode __P2 (char *,name, int,type)
534 {
535 varnode **p = &named_vars[type][hash(name,-1)];
536 while (*p && strcmp(name, (*p)->name))
537 p = &(*p)->next;
538 return p;
539 }
540
541 /*
542 * delete an alias node, given a pointer to its precessor's pointer
543 */
__P1(aliasnode **,base)544 void delete_aliasnode __P1 (aliasnode **,base)
545 {
546 aliasnode *p = *base;
547 *base = p->next;
548 if (*(base = (aliasnode**)selflookup_sortednode
549 ((sortednode*)p, (sortednode**)&sortedaliases)))
550 *base = p->snext;
551 else
552 return;
553 if (p->name) free(p->name);
554 if (p->subst) free(p->subst);
555 free((void*)p);
556 }
557
558 /*
559 * delete an action node, given a pointer to its precessor's pointer
560 */
__P1(actionnode **,base)561 void delete_actionnode __P1 (actionnode **,base)
562 {
563 actionnode *p = *base;
564 if (p->pattern) free(p->pattern);
565 if (p->command) free(p->command);
566 if (p->label) free(p->label);
567 #ifdef USE_REGEXP
568 if (p->type == ACTION_REGEXP && p->regexp) {
569 regfree((regex_t *)p->regexp);
570 free(p->regexp);
571 }
572 #endif
573 *base = p->next;
574 free((void*)p);
575 }
576
577 /*
578 * delete an prompt node, given a pointer to its precessor's pointer
579 */
__P1(promptnode **,base)580 void delete_promptnode __P1 (promptnode **,base)
581 {
582 promptnode *p = *base;
583 if (p->pattern) free(p->pattern);
584 if (p->command) free(p->command);
585 if (p->label) free(p->label);
586 #ifdef USE_REGEXP
587 if (p->type == ACTION_REGEXP && p->regexp) {
588 regfree((regex_t *)p->regexp);
589 free(p->regexp);
590 }
591 #endif
592 *base = p->next;
593 free((void*)p);
594 }
595
596 /*
597 * delete an marker node, given a pointer to its precessor's pointer
598 */
__P1(marknode **,base)599 void delete_marknode __P1 (marknode **,base)
600 {
601 marknode *p = *base;
602 if (p->pattern) free(p->pattern);
603 *base = p->next;
604 free((void*)p);
605 }
606
607 /*
608 * delete a keydef node, given a pointer to its precessor's pointer
609 */
__P1(keynode **,base)610 void delete_keynode __P1 (keynode **,base)
611 {
612 keynode *p = *base;
613 if (p->name) free(p->name);
614 if (p->sequence) free(p->sequence);
615 if (p->call_data) free(p->call_data);
616 *base = p->next;
617 free((void*)p);
618 }
619
620 /*
621 * delete a delayed command node, given a pointer to its precessor's pointer
622 */
__P1(delaynode **,base)623 void delete_delaynode __P1 (delaynode **,base)
624 {
625 delaynode *p = *base;
626 if (p->name) free(p->name);
627 if (p->command) free(p->command);
628 *base = p->next;
629 free((void*)p);
630 }
631
632 /*
633 * delete a named variable node, given a pointer to its precessor's pointer
634 */
__P2(varnode **,base,int,type)635 void delete_varnode __P2 (varnode **,base, int,type)
636 {
637 varnode *p = *base;
638 int idx = p->index, i, n;
639
640 *base = p->next;
641 if (*(base = (varnode**)selflookup_sortednode
642 ((sortednode*)p, (sortednode**)&sortednamed_vars[type])))
643 *base = p->snext;
644 else
645 return;
646 if (p->name) free(p->name);
647 if (type && p->str) ptrdel(p->str);
648 free((void*)p);
649
650 i = NUMPARAM + --num_named_vars[type];
651
652 if (idx == i)
653 return;
654
655 /* now I must fill the hole in var[idx].*** */
656
657 for (n = 0; n < MAX_HASH; n++)
658 for (p = named_vars[type][n]; p; p = p->next)
659 if (p->index == i) {
660 n = MAX_HASH;
661 break;
662 }
663
664 if (!p) { /* should NEVER happen */
665 print_error(error=UNDEFINED_VARIABLE_ERROR);
666 return;
667 }
668
669 p->index = idx;
670
671 if (type) {
672 VAR[idx].str = &p->str;
673 VAR[ i ].str = NULL;
674 } else {
675 VAR[idx].num = &p->num;
676 VAR[ i ].num = NULL;
677 }
678 }
679