← Back to branch summary

~ubuntu-branches/ubuntu/trusty/aide/trusty

« back to all changes in this revision

Viewing changes to src/list.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2010-10-12 16:10:31 UTC
  • mfrom: (1.1.7 upstream) (5.1.8 sid)
  • Revision ID: james.westby@ubuntu.com-20101012161031-42m31lgd5d6yngt0
Tags: 0.15.1-1ubuntu1
* Merge with Debian unstable; remaining Ubuntu changes:
  - debian/aide.conf.d/70_aide_dev: escape another special character in
    filenames. (LP #456710)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/list.c
1
1
/* aide, Advanced Intrusion Detection Environment
2
2
 *
3
 
 * Copyright (C) 1999,2000,2001,2002 Rami Lehti,Pablo Virolainen
 
3
 * Copyright (C) 1999-2002,2005,2006,2010 Rami Lehti,Pablo Virolainen,
 
4
 * Richard van den Berg, Hannes von Haugwitz
4
5
 * $Header$
5
6
 *
6
7
 * This program is free software; you can redistribute it and/or
37
38
 
38
39
 */
39
40
 
 
41
 
 
42
/* list_sorted_insert()
 
43
 * Adds an item in a sorted list:
 
44
 *   - The first argument is the head of the list
 
45
 *   - The second argument is the data to be added
 
46
 *   - The third argument is the function pointer to the compare function to use
 
47
 *   - Returns the head of the list
 
48
 */
 
49
list* list_sorted_insert(list* listp, void* data, int (*compare) (const void*, const void*)) {
 
50
    list* newitem=NULL;
 
51
    list* curitem=NULL;
 
52
    newitem=(list*)malloc(sizeof(list));
 
53
    if (newitem==NULL) {
 
54
        error(0,"Not enough memory to add a new item to list.\n");
 
55
        exit(EXIT_FAILURE);
 
56
    }
 
57
    if (listp==NULL){
 
58
        list_header* header=(list_header*)malloc(sizeof(list_header));
 
59
        if (header==NULL){
 
60
            error(0,"Not enough memory for list header allocation\n");
 
61
            exit(EXIT_FAILURE);
 
62
        }
 
63
        newitem->data=data;
 
64
        newitem->header=header;
 
65
        newitem->next=NULL;
 
66
        newitem->prev=NULL;
 
67
        header->head=newitem;
 
68
        header->tail=newitem;
 
69
        return newitem;
 
70
    } else {
 
71
        /* add element in sorted, non-empty list (use insertion sort) */
 
72
        curitem = listp->header->head;
 
73
        newitem->header=listp->header;
 
74
        newitem->data=data;
 
75
        if (compare(newitem->data,curitem->data) <= 0) {
 
76
            /* new element is the new head */
 
77
            listp->header->head=newitem;
 
78
            curitem->prev=newitem;
 
79
            newitem->next=curitem;
 
80
            newitem->prev=NULL;
 
81
            return newitem;
 
82
        } else {
 
83
            /* find position for new element */
 
84
            while(compare(newitem->data, curitem->data) > 0 && curitem->next != NULL) {
 
85
               curitem=curitem->next;
 
86
            }
 
87
            if (curitem->next == NULL && compare(newitem->data, curitem->data) > 0) {
 
88
                /* new element is the new tail */
 
89
                listp->header->tail=newitem;
 
90
                curitem->next=newitem;
 
91
                newitem->prev=curitem;
 
92
                newitem->next=NULL;
 
93
            } else {
 
94
                /* new element is an inner element */
 
95
                curitem->prev->next=newitem;
 
96
                newitem->prev=curitem->prev;
 
97
                curitem->prev=newitem;
 
98
                newitem->next=curitem;
 
99
            }
 
100
        }
 
101
        return listp;
 
102
    }
 
103
}
 
104
 
40
105
/* list_append()
41
106
 * append an item to list
42
107
 * returns the head