Line data Source code
1 : /*********************************************************************
2 : *
3 : * File : $Source: /cvsroot/ijbswa/current/list.c,v $
4 : *
5 : * Purpose : Declares functions to handle lists.
6 : *
7 : * Copyright : Written by and Copyright (C) 2001-2007 members of the
8 : * Privoxy team. https://www.privoxy.org/
9 : *
10 : * Based on the Internet Junkbuster originally written
11 : * by and Copyright (C) 1997 Anonymous Coders and
12 : * Junkbusters Corporation. http://www.junkbusters.com
13 : *
14 : * This program is free software; you can redistribute it
15 : * and/or modify it under the terms of the GNU General
16 : * Public License as published by the Free Software
17 : * Foundation; either version 2 of the License, or (at
18 : * your option) any later version.
19 : *
20 : * This program is distributed in the hope that it will
21 : * be useful, but WITHOUT ANY WARRANTY; without even the
22 : * implied warranty of MERCHANTABILITY or FITNESS FOR A
23 : * PARTICULAR PURPOSE. See the GNU General Public
24 : * License for more details.
25 : *
26 : * The GNU General Public License should be included with
27 : * this file. If not, you can view it at
28 : * http://www.gnu.org/copyleft/gpl.html
29 : * or write to the Free Software Foundation, Inc., 59
30 : * Temple Place - Suite 330, Boston, MA 02111-1307, USA.
31 : *
32 : *********************************************************************/
33 :
34 :
35 : #include "config.h"
36 :
37 : #ifndef _WIN32
38 : /* FIXME: The following headers are not needed for Win32. Are they
39 : * needed on other platforms?
40 : */
41 : #include <stdio.h>
42 : #include <sys/types.h>
43 : #include <stdlib.h>
44 : #include <ctype.h>
45 : #endif
46 : #include <string.h>
47 :
48 : #if !defined(_WIN32)
49 : #include <unistd.h>
50 : #endif
51 :
52 : #include <assert.h>
53 :
54 : #include "project.h"
55 : #include "list.h"
56 : #include "miscutil.h"
57 :
58 : static int list_is_valid (const struct list *the_list);
59 :
60 :
61 : /*********************************************************************
62 : *
63 : * Function : init_list
64 : *
65 : * Description : Create a new, empty list in user-allocated memory.
66 : * Caller should allocate a "struct list" variable,
67 : * then pass it to this function.
68 : * (Implementation note: Rather than calling this
69 : * function, you can also just memset the memory to
70 : * zero, e.g. if you have a larger structure you
71 : * want to initialize quickly. However, that isn't
72 : * really good design.)
73 : *
74 : * Parameters :
75 : * 1 : the_list = pointer to list
76 : *
77 : * Returns : N/A
78 : *
79 : *********************************************************************/
80 67016 : void init_list(struct list *the_list)
81 : {
82 67016 : memset(the_list, '\0', sizeof(*the_list));
83 67016 : }
84 :
85 :
86 : /*********************************************************************
87 : *
88 : * Function : destroy_list
89 : *
90 : * Description : Destroy a string list (opposite of list_init).
91 : * On return, the memory used by the list entries has
92 : * been freed, but not the memory used by the_list
93 : * itself. You should not re-use the_list without
94 : * calling list_init().
95 : *
96 : * (Implementation note: You *can* reuse the_list
97 : * without calling list_init(), but please don't.
98 : * If you want to remove all entries from a list
99 : * and still have a usable list, then use
100 : * list_remove_all().)
101 : *
102 : * Parameters :
103 : * 1 : the_list = pointer to list
104 : *
105 : * Returns : N/A
106 : *
107 : *********************************************************************/
108 1766188 : void destroy_list (struct list *the_list)
109 : {
110 : struct list_entry *cur_entry, *next_entry;
111 :
112 1766188 : assert(the_list);
113 :
114 2795531 : for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
115 : {
116 1029343 : next_entry = cur_entry->next;
117 1029343 : freez(cur_entry->str);
118 1029343 : free(cur_entry);
119 : }
120 :
121 1766188 : the_list->first = NULL;
122 1766188 : the_list->last = NULL;
123 1766188 : }
124 :
125 :
126 : /*********************************************************************
127 : *
128 : * Function : list_is_valid
129 : *
130 : * Description : Check that a string list is valid. The intended
131 : * usage is "assert(list_is_valid(the_list))".
132 : * Currently this checks that "the_list->last"
133 : * is correct, and that the list doesn't contain
134 : * circular references. It is likely to crash if
135 : * it's passed complete garbage.
136 : *
137 : * Parameters :
138 : * 1 : the_list = pointer to list. Must be non-null.
139 : *
140 : * Returns : 1 if list is valid, 0 otherwise.
141 : *
142 : *********************************************************************/
143 13594983 : static int list_is_valid (const struct list *the_list)
144 : {
145 : /*
146 : * If you don't want this check, just change the line below
147 : * from "#if 1" to "#if 0".
148 : */
149 : #if 1
150 : const struct list_entry *cur_entry;
151 13594983 : const struct list_entry *last_entry = NULL;
152 13594983 : int entry = 0;
153 :
154 13594983 : assert(the_list);
155 :
156 102311916 : for (cur_entry = the_list->first; cur_entry ; cur_entry = cur_entry->next)
157 : {
158 88716933 : last_entry = cur_entry;
159 :
160 88716933 : if (cur_entry->str)
161 : {
162 : /*
163 : * Just check that this string can be accessed - i.e. it's a valid
164 : * pointer.
165 : */
166 88324658 : (void)strlen(cur_entry->str);
167 : }
168 :
169 : /*
170 : * Check for looping back to first
171 : */
172 88716933 : if ((entry++ != 0) && (cur_entry == the_list->first))
173 : {
174 0 : return 0;
175 : }
176 :
177 : /*
178 : * Arbitrarily limit list length to prevent infinite loops.
179 : * Note that the 1000 limit was hit by a real user in tracker 911950;
180 : * removing it for now. Real circular references should eventually
181 : * be caught by the check above, anyway.
182 : */
183 : /*
184 : if (entry > 1000)
185 : {
186 : return 0;
187 : }
188 : */
189 :
190 : /*
191 : * Check this isn't marked as the last entry, unless of course it's
192 : * *really* the last entry.
193 : */
194 88716933 : if ((the_list->last == cur_entry) && (cur_entry->next != NULL))
195 : {
196 : /* This is the last entry, but there's data after it !!?? */
197 0 : return 0;
198 : }
199 : }
200 :
201 13594983 : return (the_list->last == last_entry);
202 : #else
203 : return 1;
204 : #endif
205 : }
206 :
207 : /*********************************************************************
208 : *
209 : * Function : enlist
210 : *
211 : * Description : Append a string into a specified string list.
212 : *
213 : * Parameters :
214 : * 1 : the_list = pointer to list
215 : * 2 : str = string to add to the list (maybe NULL)
216 : *
217 : * Returns : JB_ERR_OK on success
218 : * JB_ERR_MEMORY on out-of-memory error.
219 : * On error, the_list will be unchanged.
220 : *
221 : *********************************************************************/
222 1969220 : jb_err enlist(struct list *the_list, const char *str)
223 : {
224 : struct list_entry *cur;
225 :
226 1969220 : assert(the_list);
227 1969220 : assert(list_is_valid(the_list));
228 :
229 1969220 : if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
230 : {
231 0 : return JB_ERR_MEMORY;
232 : }
233 :
234 1969220 : if (str)
235 : {
236 1969220 : if (NULL == (cur->str = strdup(str)))
237 : {
238 0 : free(cur);
239 0 : return JB_ERR_MEMORY;
240 : }
241 : }
242 : /* else { cur->str = NULL; } - implied by zalloc */
243 :
244 : /* cur->next = NULL; - implied by zalloc */
245 :
246 1969220 : if (the_list->last)
247 : {
248 1538868 : the_list->last->next = cur;
249 1538868 : the_list->last = cur;
250 : }
251 : else
252 : {
253 430352 : the_list->first = cur;
254 430352 : the_list->last = cur;
255 : }
256 :
257 1969220 : assert(list_is_valid(the_list));
258 1969220 : return JB_ERR_OK;
259 : }
260 :
261 :
262 : /*********************************************************************
263 : *
264 : * Function : enlist_first
265 : *
266 : * Description : Append a string as first element into a specified
267 : * string list.
268 : *
269 : * Parameters :
270 : * 1 : the_list = pointer to list
271 : * 2 : str = string to add to the list (maybe NULL)
272 : *
273 : * Returns : JB_ERR_OK on success
274 : * JB_ERR_MEMORY on out-of-memory error.
275 : * On error, the_list will be unchanged.
276 : *
277 : *********************************************************************/
278 26436 : jb_err enlist_first(struct list *the_list, const char *str)
279 : {
280 : struct list_entry *cur;
281 :
282 26436 : assert(the_list);
283 26436 : assert(list_is_valid(the_list));
284 :
285 26436 : if (NULL == (cur = (struct list_entry *)zalloc(sizeof(*cur))))
286 : {
287 0 : return JB_ERR_MEMORY;
288 : }
289 :
290 26436 : if (str)
291 : {
292 26436 : if (NULL == (cur->str = strdup(str)))
293 : {
294 0 : free(cur);
295 0 : return JB_ERR_MEMORY;
296 : }
297 : }
298 : /* else { cur->str = NULL; } - implied by zalloc */
299 :
300 26436 : cur->next = the_list->first;
301 :
302 26436 : the_list->first = cur;
303 26436 : if (the_list->last == NULL)
304 : {
305 0 : the_list->last = cur;
306 : }
307 :
308 26436 : assert(list_is_valid(the_list));
309 26436 : return JB_ERR_OK;
310 : }
311 :
312 :
313 : /*********************************************************************
314 : *
315 : * Function : enlist_unique
316 : *
317 : * Description : Append a string into a specified string list,
318 : * if & only if it's not there already.
319 : * If the num_significant_chars argument is nonzero,
320 : * only compare up to the nth character.
321 : *
322 : * Parameters :
323 : * 1 : the_list = pointer to list
324 : * 2 : str = string to add to the list
325 : * 3 : num_significant_chars = number of chars to use
326 : * for uniqueness test, or 0 to require an exact match.
327 : *
328 : * Returns : JB_ERR_OK on success
329 : * JB_ERR_MEMORY on out-of-memory error.
330 : * On error, the_list will be unchanged.
331 : * "Success" does not indicate whether or not the
332 : * item was already in the list.
333 : *
334 : *********************************************************************/
335 997409 : jb_err enlist_unique(struct list *the_list, const char *str,
336 : size_t num_significant_chars)
337 : {
338 : struct list_entry *cur_entry;
339 :
340 997409 : assert(the_list);
341 997409 : assert(list_is_valid(the_list));
342 997409 : assert(str);
343 : assert(num_significant_chars >= 0);
344 997409 : assert(num_significant_chars <= strlen(str));
345 :
346 997409 : if (num_significant_chars > 0)
347 : {
348 1557782 : for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
349 : {
350 1313340 : if ((cur_entry->str != NULL)
351 1312879 : && (0 == strncmp(str, cur_entry->str, num_significant_chars)))
352 : {
353 : /* Already there */
354 1709 : return JB_ERR_OK;
355 : }
356 : }
357 : }
358 : else
359 : {
360 : /* Test whole string */
361 3610198 : for (cur_entry = the_list->first; cur_entry != NULL; cur_entry = cur_entry->next)
362 : {
363 2886328 : if ((cur_entry->str != NULL) && (0 == strcmp(str, cur_entry->str)))
364 : {
365 : /* Already there */
366 27388 : return JB_ERR_OK;
367 : }
368 : }
369 : }
370 :
371 968312 : return enlist(the_list, str);
372 : }
373 :
374 :
375 : /*********************************************************************
376 : *
377 : * Function : enlist_unique_header
378 : *
379 : * Description : Make a HTTP header from the two strings name and value,
380 : * and append the result into a specified string list,
381 : * if & only if there isn't already a header with that name.
382 : *
383 : * Parameters :
384 : * 1 : the_list = pointer to list
385 : * 2 : name = HTTP header name (e.g. "Content-type")
386 : * 3 : value = HTTP header value (e.g. "text/html")
387 : *
388 : * Returns : JB_ERR_OK on success
389 : * JB_ERR_MEMORY on out-of-memory error.
390 : * On error, the_list will be unchanged.
391 : * "Success" does not indicate whether or not the
392 : * header was already in the list.
393 : *
394 : *********************************************************************/
395 223738 : jb_err enlist_unique_header(struct list *the_list, const char *name,
396 : const char *value)
397 : {
398 223738 : jb_err result = JB_ERR_MEMORY;
399 : char *header;
400 : size_t header_size;
401 :
402 223738 : assert(the_list);
403 223738 : assert(list_is_valid(the_list));
404 223738 : assert(name);
405 223738 : assert(value);
406 :
407 : /* + 2 for the ': ', + 1 for the \0 */
408 223738 : header_size = strlen(name) + 2 + strlen(value) + 1;
409 223738 : header = (char *)malloc(header_size);
410 :
411 223738 : if (NULL != header)
412 : {
413 223738 : const size_t bytes_to_compare = strlen(name) + 2;
414 223738 : char *p = header;
415 :
416 223738 : snprintf(header, header_size, "%s: %s", name, value);
417 : /*
418 : * The trailing "\r\n" is added by list_to_text(),
419 : * if the caller passed them anyway, cut the header
420 : * at the first one or dump core if this is a debug
421 : * build.
422 : */
423 : do
424 : {
425 7861285 : if ((*p == '\r') || (*p == '\n'))
426 : {
427 0 : assert(*p != '\r');
428 0 : assert(*p != '\n');
429 0 : *p = '\0';
430 : }
431 7861285 : } while (*p++);
432 223738 : result = enlist_unique(the_list, header, bytes_to_compare);
433 223738 : free(header);
434 223738 : assert(list_is_valid(the_list));
435 : }
436 :
437 223738 : return result;
438 :
439 : }
440 :
441 :
442 : /*********************************************************************
443 : *
444 : * Function : list_remove_all
445 : *
446 : * Description : Remove all entries from a list. On return, the_list
447 : * is a valid, empty list. Note that this is similar
448 : * to destroy_list(), but the difference is that this
449 : * function guarantees that the list structure is still
450 : * valid after the call.
451 : *
452 : * Parameters :
453 : * 1 : the_list = pointer to list
454 : *
455 : * Returns : N/A
456 : *
457 : *********************************************************************/
458 86736 : void list_remove_all(struct list *the_list)
459 : {
460 : struct list_entry *cur_entry;
461 : struct list_entry *next_entry;
462 :
463 86736 : assert(the_list);
464 86736 : assert(list_is_valid(the_list));
465 :
466 815753 : for (cur_entry = the_list->first; cur_entry ; cur_entry = next_entry)
467 : {
468 729017 : next_entry = cur_entry->next;
469 729017 : freez(cur_entry->str);
470 729017 : free(cur_entry);
471 : }
472 :
473 86736 : the_list->first = the_list->last = NULL;
474 :
475 86736 : assert(list_is_valid(the_list));
476 86736 : }
477 :
478 :
479 : /*********************************************************************
480 : *
481 : * Function : list_to_text
482 : *
483 : * Description : "Flatten" a string list into 1 long \r\n delimited string,
484 : * adding an empty line at the end. NULL entries are ignored.
485 : * This function does not change the_list.
486 : *
487 : * XXX: Should probably be renamed as it's only
488 : * useful (and used) to flatten header lists.
489 : *
490 : * Parameters :
491 : * 1 : the_list = pointer to list
492 : *
493 : * Returns : NULL on malloc error, else new long string.
494 : * Caller must free() it.
495 : *
496 : *********************************************************************/
497 43519 : char *list_to_text(const struct list *the_list)
498 : {
499 : struct list_entry *cur_entry;
500 : char *text;
501 : size_t text_length;
502 : char *cursor;
503 : size_t bytes_left;
504 :
505 43519 : assert(the_list);
506 43519 : assert(list_is_valid(the_list));
507 :
508 : /*
509 : * Calculate the length of the final text.
510 : * '2' because of the '\r\n' at the end of
511 : * each string and at the end of the text.
512 : */
513 43519 : text_length = 2;
514 531031 : for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
515 : {
516 487512 : if (cur_entry->str)
517 : {
518 479630 : text_length += strlen(cur_entry->str) + 2;
519 : }
520 : }
521 :
522 43519 : bytes_left = text_length + 1;
523 :
524 43519 : text = (char *)malloc(bytes_left);
525 43519 : if (NULL == text)
526 : {
527 0 : return NULL;
528 : }
529 :
530 43519 : cursor = text;
531 :
532 531031 : for (cur_entry = the_list->first; cur_entry; cur_entry = cur_entry->next)
533 : {
534 487512 : if (cur_entry->str)
535 : {
536 479630 : const int written = snprintf(cursor, bytes_left, "%s\r\n", cur_entry->str);
537 :
538 479630 : assert(written > 0);
539 479630 : assert(written < bytes_left);
540 :
541 479630 : bytes_left -= (size_t)written;
542 479630 : cursor += (size_t)written;
543 : }
544 : }
545 :
546 43519 : assert(bytes_left == 3);
547 :
548 43519 : *cursor++ = '\r';
549 43519 : *cursor++ = '\n';
550 43519 : *cursor = '\0';
551 :
552 43519 : assert(text_length == cursor - text);
553 43519 : assert(text[text_length] == '\0');
554 :
555 43519 : return text;
556 : }
557 :
558 :
559 : /*********************************************************************
560 : *
561 : * Function : list_remove_item
562 : *
563 : * Description : Remove a string from a specified string list.
564 : *
565 : * Parameters :
566 : * 1 : the_list = pointer to list
567 : * 2 : str = string to remove from the list - non-NULL
568 : *
569 : * Returns : Number of times it was removed.
570 : *
571 : *********************************************************************/
572 88717 : int list_remove_item(struct list *the_list, const char *str)
573 : {
574 88717 : struct list_entry *prev = NULL;
575 : struct list_entry *cur;
576 : struct list_entry *next;
577 88717 : int count = 0;
578 :
579 88717 : assert(the_list);
580 88717 : assert(list_is_valid(the_list));
581 88717 : assert(str);
582 :
583 88717 : cur = the_list->first;
584 :
585 89198 : while (cur != NULL)
586 : {
587 481 : next = cur->next;
588 :
589 481 : if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
590 : {
591 45 : count++;
592 :
593 45 : if (prev != NULL)
594 : {
595 19 : prev->next = next;
596 : }
597 : else
598 : {
599 26 : the_list->first = next;
600 : }
601 45 : free((char *)cur->str);
602 45 : free(cur);
603 : }
604 : else
605 : {
606 436 : prev = cur;
607 : }
608 481 : cur = next;
609 : }
610 :
611 88717 : the_list->last = prev;
612 :
613 88717 : assert(list_is_valid(the_list));
614 :
615 88717 : return count;
616 : }
617 :
618 :
619 : /*********************************************************************
620 : *
621 : * Function : list_remove_list
622 : *
623 : * Description : Remove all strings in one list from another list.
624 : * This is currently a brute-force algorithm
625 : * (it compares every pair of strings).
626 : *
627 : * Parameters :
628 : * 1 : dest = list to change
629 : * 2 : src = list of strings to remove
630 : *
631 : * Returns : Total number of strings removed.
632 : *
633 : *********************************************************************/
634 798799 : int list_remove_list(struct list *dest, const struct list *src)
635 : {
636 : struct list_entry *cur;
637 798799 : int count = 0;
638 :
639 798799 : assert(src);
640 798799 : assert(dest);
641 798799 : assert(list_is_valid(src));
642 798799 : assert(list_is_valid(dest));
643 :
644 798799 : for (cur = src->first; cur != NULL; cur = cur->next)
645 : {
646 0 : if (cur->str != NULL)
647 : {
648 0 : count += list_remove_item(dest, cur->str);
649 : }
650 : }
651 :
652 798799 : assert(list_is_valid(src));
653 798799 : assert(list_is_valid(dest));
654 :
655 798799 : return count;
656 : }
657 :
658 :
659 : /*********************************************************************
660 : *
661 : * Function : list_duplicate
662 : *
663 : * Description : Copy a string list
664 : *
665 : * Parameters :
666 : * 1 : dest = Destination list. Must be a valid list.
667 : * All existing entries will be removed.
668 : * 1 : src = pointer to source list for copy.
669 : *
670 : * Returns : JB_ERR_OK on success
671 : * JB_ERR_MEMORY on out-of-memory error.
672 : * On error, dest will be empty.
673 : *
674 : *********************************************************************/
675 2489 : jb_err list_duplicate(struct list *dest, const struct list *src)
676 : {
677 : struct list_entry * cur_src;
678 : struct list_entry * cur_dest;
679 :
680 2489 : assert(src);
681 2489 : assert(dest);
682 2489 : assert(list_is_valid(src));
683 2489 : assert(list_is_valid(dest));
684 :
685 2489 : list_remove_all(dest);
686 :
687 : /* Need to process first entry specially so we can set dest->first */
688 2489 : cur_src = src->first;
689 2489 : if (cur_src)
690 : {
691 0 : cur_dest = dest->first = (struct list_entry *)zalloc(sizeof(*cur_dest));
692 0 : if (cur_dest == NULL)
693 : {
694 0 : destroy_list(dest);
695 :
696 0 : assert(list_is_valid(src));
697 0 : assert(list_is_valid(dest));
698 :
699 0 : return JB_ERR_MEMORY;
700 : }
701 :
702 0 : if (cur_src->str)
703 : {
704 0 : cur_dest->str = strdup(cur_src->str);
705 0 : if (cur_dest->str == NULL)
706 : {
707 0 : destroy_list(dest);
708 :
709 0 : assert(list_is_valid(src));
710 0 : assert(list_is_valid(dest));
711 :
712 0 : return JB_ERR_MEMORY;
713 : }
714 : }
715 : /* else { cur_dest->str = NULL; } - implied by zalloc */
716 :
717 : /* Now process the rest */
718 0 : for (cur_src = cur_src->next; cur_src; cur_src = cur_src->next)
719 : {
720 0 : cur_dest = cur_dest->next = (struct list_entry *)zalloc(sizeof(*cur_dest));
721 0 : if (cur_dest == NULL)
722 : {
723 0 : destroy_list(dest);
724 :
725 0 : assert(list_is_valid(src));
726 0 : assert(list_is_valid(dest));
727 :
728 0 : return JB_ERR_MEMORY;
729 : }
730 0 : if (cur_src->str)
731 : {
732 0 : cur_dest->str = strdup(cur_src->str);
733 0 : if (cur_dest->str == NULL)
734 : {
735 0 : destroy_list(dest);
736 :
737 0 : assert(list_is_valid(src));
738 0 : assert(list_is_valid(dest));
739 :
740 0 : return JB_ERR_MEMORY;
741 : }
742 : }
743 : /* else { cur_dest->str = NULL; } - implied by zalloc */
744 : }
745 :
746 0 : dest->last = cur_dest;
747 : }
748 :
749 2489 : assert(list_is_valid(src));
750 2489 : assert(list_is_valid(dest));
751 :
752 2489 : return JB_ERR_OK;
753 : }
754 :
755 :
756 : /*********************************************************************
757 : *
758 : * Function : list_append_list_unique
759 : *
760 : * Description : Append a string list to another list.
761 : * Duplicate items are not added.
762 : *
763 : * Parameters :
764 : * 1 : dest = pointer to destination list for merge.
765 : * 2 : src = pointer to source for merge.
766 : *
767 : * Returns : JB_ERR_OK on success
768 : * JB_ERR_MEMORY on out-of-memory error.
769 : * On error, some (but not all) of src might have
770 : * been copied into dest.
771 : *
772 : *********************************************************************/
773 918793 : jb_err list_append_list_unique(struct list *dest, const struct list *src)
774 : {
775 : struct list_entry * cur;
776 :
777 918793 : assert(src);
778 918793 : assert(dest);
779 918793 : assert(list_is_valid(src));
780 918793 : assert(list_is_valid(dest));
781 :
782 1583679 : for (cur = src->first; cur; cur = cur->next)
783 : {
784 664886 : if (cur->str)
785 : {
786 664886 : if (enlist_unique(dest, cur->str, 0))
787 : {
788 0 : assert(list_is_valid(src));
789 0 : assert(list_is_valid(dest));
790 :
791 0 : return JB_ERR_MEMORY;
792 : }
793 : }
794 : }
795 :
796 918793 : assert(list_is_valid(src));
797 918793 : assert(list_is_valid(dest));
798 :
799 918793 : return JB_ERR_OK;
800 : }
801 :
802 :
803 : /*********************************************************************
804 : *
805 : * Function : list_is_empty
806 : *
807 : * Description : Test whether a list is empty. Does not change the list.
808 : *
809 : * Parameters :
810 : * 1 : the_list = pointer to list to test.
811 : *
812 : * Returns : Nonzero if the list contains no entries.
813 : *
814 : *********************************************************************/
815 851388 : int list_is_empty(const struct list *the_list)
816 : {
817 851388 : assert(the_list);
818 851388 : assert(list_is_valid(the_list));
819 :
820 851388 : return (the_list->first == NULL);
821 : }
822 :
823 :
824 : /*********************************************************************
825 : *
826 : * Function : list_contains_item
827 : *
828 : * Description : Tests whether a list item is already set.
829 : * Does not change the list.
830 : *
831 : * Parameters :
832 : * 1 : the_list = list to search in
833 : * 2 : str = string to search for
834 : *
835 : * Returns : TRUE if the item was found,
836 : * FALSE otherwise.
837 : *
838 : *********************************************************************/
839 32649 : int list_contains_item(const struct list *the_list, const char *str)
840 : {
841 : struct list_entry *entry;
842 :
843 32649 : assert(the_list);
844 32649 : assert(list_is_valid(the_list));
845 32649 : assert(str);
846 :
847 44412 : for (entry = the_list->first; entry != NULL; entry = entry->next)
848 : {
849 22723 : if (entry->str == NULL)
850 : {
851 : /*
852 : * NULL pointers are allowed in some lists.
853 : * For example for csp->headers in case a
854 : * header was removed.
855 : */
856 0 : continue;
857 : }
858 :
859 22723 : if (0 == strcmp(str, entry->str))
860 : {
861 : /* Item found */
862 10960 : return TRUE;
863 : }
864 : }
865 :
866 21689 : return FALSE;
867 : }
868 :
869 :
870 : /*********************************************************************
871 : *
872 : * Function : new_map
873 : *
874 : * Description : Create a new, empty map.
875 : * Causes program exit if the memory allocation fails.
876 : *
877 : * Parameters : N/A
878 : *
879 : * Returns : A new, empty map
880 : *
881 : *********************************************************************/
882 103117 : struct map *new_map(void)
883 : {
884 103117 : struct map *empty_map = zalloc(sizeof(struct map));
885 :
886 103117 : if (NULL == empty_map)
887 : {
888 0 : exit(1);
889 : }
890 :
891 103117 : return empty_map;
892 :
893 : }
894 :
895 :
896 : /*********************************************************************
897 : *
898 : * Function : free_map
899 : *
900 : * Description : Free the memory occupied by a map and its
901 : * dependent strings
902 : *
903 : * Parameters :
904 : * 1 : the_map = map to be freed. May be NULL.
905 : *
906 : * Returns : N/A
907 : *
908 : *********************************************************************/
909 103117 : void free_map(struct map *the_map)
910 : {
911 : struct map_entry *cur_entry;
912 : struct map_entry *next_entry;
913 :
914 103117 : if (the_map == NULL)
915 : {
916 0 : return;
917 : }
918 :
919 1013049 : for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry)
920 : {
921 909932 : freez(cur_entry->name);
922 909932 : freez(cur_entry->value);
923 :
924 909932 : next_entry = cur_entry->next;
925 909932 : free(cur_entry);
926 : }
927 :
928 103117 : the_map->first = the_map->last = NULL;
929 :
930 103117 : free(the_map);
931 : }
932 :
933 :
934 : /*********************************************************************
935 : *
936 : * Function : map
937 : *
938 : * Description : Add a mapping from given name to given value to a
939 : * given map.
940 : *
941 : * Note: Since all strings will be free()d in free_map()
942 : * later, set the copy flags for constants or
943 : * strings that will be independently free()d.
944 : *
945 : * Note2: This function allows NULL parameters - it
946 : * returns JB_ERR_MEMORY in that case.
947 : *
948 : * Note3: If this function returns JB_ERR_MEMORY,
949 : * it will free(name) unless you specify
950 : * name_needs_copying, and similarly it will
951 : * free(value) unless you specify
952 : * value_needs_copying.
953 : *
954 : * Due to Note2 and Note3 above, the following code
955 : * is legal, and will never crash or leak memory even
956 : * if the system runs out of memory:
957 : *
958 : * err = map(mymap, "xyz", 1, html_encode(somestring), 0);
959 : *
960 : * err will be set to JB_ERR_MEMORY if either call runs
961 : * out-of-memory. Without these features, you would
962 : * need to check the return value of html_encode in the
963 : * above example for NULL, which (at least) doubles the
964 : * amount of error-checking code needed.
965 : *
966 : * Parameters :
967 : * 1 : the_map = map to add to
968 : * 2 : name = name to add
969 : * 3 : name_needs_copying = flag set if a copy of name should be used
970 : * 4 : value = value to add
971 : * 5 : value_needs_copying = flag set if a copy of value should be used
972 : *
973 : * Returns : JB_ERR_OK on success
974 : * JB_ERR_MEMORY on out-of-memory error.
975 : *
976 : *********************************************************************/
977 910187 : jb_err map(struct map *the_map,
978 : const char *name, int name_needs_copying,
979 : const char *value, int value_needs_copying)
980 : {
981 : struct map_entry *new_entry;
982 :
983 910187 : assert(the_map);
984 :
985 910187 : if ( (NULL == value)
986 910079 : || (NULL == name)
987 910079 : || (NULL == (new_entry = zalloc(sizeof(*new_entry)))))
988 : {
989 108 : if ((name != NULL) && (!name_needs_copying))
990 : {
991 0 : free((char *)name);
992 : }
993 108 : if ((value != NULL) && (!value_needs_copying))
994 : {
995 0 : free((char *)value);
996 : }
997 108 : return JB_ERR_MEMORY;
998 : }
999 :
1000 910079 : if (name_needs_copying)
1001 : {
1002 831879 : if (NULL == (name = strdup(name)))
1003 : {
1004 0 : free(new_entry);
1005 0 : if (!value_needs_copying)
1006 : {
1007 0 : free((char *)value);
1008 : }
1009 0 : return JB_ERR_MEMORY;
1010 : }
1011 : }
1012 :
1013 910079 : if (value_needs_copying)
1014 : {
1015 508112 : if (NULL == (value = strdup(value)))
1016 : {
1017 0 : free((char *)name);
1018 0 : free(new_entry);
1019 0 : return JB_ERR_MEMORY;
1020 : }
1021 : }
1022 :
1023 910079 : new_entry->name = name;
1024 910079 : new_entry->value = value;
1025 : /* new_entry->next = NULL; - implied by zalloc */
1026 :
1027 910079 : if (the_map->last)
1028 : {
1029 817011 : the_map->last->next = new_entry;
1030 817011 : the_map->last = new_entry;
1031 : }
1032 : else
1033 : {
1034 93068 : the_map->first = new_entry;
1035 93068 : the_map->last = new_entry;
1036 : }
1037 :
1038 910079 : return JB_ERR_OK;
1039 : }
1040 :
1041 :
1042 : /*********************************************************************
1043 : *
1044 : * Function : unmap
1045 : *
1046 : * Description : Remove all map_entry structs with a given name from
1047 : * a given map.
1048 : *
1049 : * Parameters :
1050 : * 1 : the_map = map to look in
1051 : * 2 : name = name to unmap
1052 : *
1053 : * Returns : JB_ERR_OK
1054 : *
1055 : *********************************************************************/
1056 246 : jb_err unmap(struct map *the_map, const char *name)
1057 : {
1058 : struct map_entry *cur_entry, *last_entry;
1059 :
1060 246 : assert(the_map);
1061 246 : assert(name);
1062 :
1063 246 : last_entry = NULL;
1064 :
1065 996 : for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1066 : {
1067 827 : if (!strcmp(name, cur_entry->name))
1068 : {
1069 : /*
1070 : * Update the incoming pointer
1071 : */
1072 147 : if (cur_entry == the_map->first)
1073 : {
1074 77 : the_map->first = cur_entry->next;
1075 : }
1076 : else
1077 : {
1078 70 : last_entry->next = cur_entry->next;
1079 : }
1080 :
1081 : /*
1082 : * Update the map's last pointer
1083 : */
1084 147 : if (cur_entry == the_map->last)
1085 : {
1086 81 : the_map->last = last_entry;
1087 : }
1088 :
1089 : /*
1090 : * Free the map_entry
1091 : */
1092 147 : freez(cur_entry->name);
1093 147 : freez(cur_entry->value);
1094 147 : freez(cur_entry);
1095 147 : if (last_entry == NULL)
1096 : {
1097 : /* The map only had a single entry which has just been removed. */
1098 77 : break;
1099 : }
1100 70 : cur_entry = last_entry;
1101 : }
1102 : else
1103 : {
1104 680 : last_entry = cur_entry;
1105 : }
1106 : }
1107 246 : return JB_ERR_OK;
1108 : }
1109 :
1110 :
1111 : /*********************************************************************
1112 : *
1113 : * Function : lookup
1114 : *
1115 : * Description : Look up an item with a given name in a map, and
1116 : * return its value
1117 : *
1118 : * Parameters :
1119 : * 1 : the_map = map to look in
1120 : * 2 : name = name parameter to look for
1121 : *
1122 : * Returns : the value if found, else the empty string.
1123 : * Return value is allocated as part of the map, so
1124 : * it is freed when the map is destroyed. Caller
1125 : * must not free or modify it.
1126 : *
1127 : *********************************************************************/
1128 60133 : const char *lookup(const struct map *the_map, const char *name)
1129 : {
1130 : const struct map_entry *cur_entry;
1131 :
1132 60133 : assert(the_map);
1133 60133 : assert(name);
1134 :
1135 2304792 : for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = cur_entry->next)
1136 : {
1137 2267783 : if (!strcmp(name, cur_entry->name))
1138 : {
1139 23124 : return cur_entry->value;
1140 : }
1141 : }
1142 37009 : return "";
1143 : }
1144 :
1145 :
1146 : /*
1147 : Local Variables:
1148 : tab-width: 3
1149 : end:
1150 : */
|
