1 /*
2 * The Sleuth Kit
3 *
4 * Brian Carrier [carrier <at> sleuthkit [dot] org]
5 * Copyright (c) 2007-2011 Brian Carrier. All Rights reserved
6 *
7 * This software is distributed under the Common Public License 1.0
8 */
9 #include "tsk_base_i.h"
10
11 /** \file tsk_list.c
12 * tsk_lists are a linked list of buckets that store a key in REVERSE sorted order.
13 * They are used to keep track of data as we walk along and prevent loops
14 * from data corruption. Note that the len value is actually negative. An entry
15 * with a key of 6 and a length of 2 covers the range of 5 to 6.
16 */
17
18 /*
19 * Create a list with teh first entry defined
20 * @param a_key Key for initial entry
21 * @returns newly created entry
22 */
23 static TSK_LIST *
tsk_list_create(uint64_t a_key)24 tsk_list_create(uint64_t a_key)
25 {
26 TSK_LIST *ent;
27 if ((ent = (TSK_LIST *) tsk_malloc(sizeof(TSK_LIST))) == NULL) {
28 return NULL;
29 }
30
31 ent->key = a_key;
32 ent->next = NULL;
33 ent->len = 1;
34
35 return ent;
36 }
37
38 /**
39 * \ingroup baselib
40 * Add an entry to a TSK_LIST (and create one if one does not exist)
41 * @param a_tsk_list_head Pointer to pointer for head of list (can point to NULL if no list exists).
42 * @param a_key Value to add to list
43 * @returns 1 on error
44 */
45 uint8_t
tsk_list_add(TSK_LIST ** a_tsk_list_head,uint64_t a_key)46 tsk_list_add(TSK_LIST ** a_tsk_list_head, uint64_t a_key)
47 {
48 TSK_LIST *tmp;
49
50 /* If the head is NULL, then create an entry */
51 if (*a_tsk_list_head == NULL) {
52 TSK_LIST *ent;
53 /*
54 if (tsk_verbose)
55 fprintf(stderr, "entry %" PRIu64 " is first on list\n", a_key);
56 */
57 if ((ent = tsk_list_create(a_key)) == NULL)
58 return 1;
59
60 *a_tsk_list_head = ent;
61 return 0;
62 }
63
64 /* If the new key is larger than the head, make it the head */
65 if (a_key > (*a_tsk_list_head)->key) {
66 /*
67 if (tsk_verbose)
68 fprintf(stderr,
69 "entry %" PRIu64 " added to head before %" PRIu64 "\n",
70 a_key, (*a_tsk_list_head)->key);
71 */
72
73 // If we can, update the length of the existing list entry
74 if (a_key == (*a_tsk_list_head)->key + 1) {
75 (*a_tsk_list_head)->key++;
76 (*a_tsk_list_head)->len++;
77 }
78 else {
79 TSK_LIST *ent;
80 if ((ent = tsk_list_create(a_key)) == NULL)
81 return 1;
82 ent->next = *a_tsk_list_head;
83 *a_tsk_list_head = ent;
84 }
85 return 0;
86 }
87 // get rid of duplicates
88 else if (a_key == (*a_tsk_list_head)->key) {
89 return 0;
90 }
91
92 /* At the start of this loop each time, we know that the key to add
93 * is smaller than the entry being considered (tmp) */
94 tmp = *a_tsk_list_head;
95 while (tmp != NULL) {
96
97 /* First check if this is a duplicate and contained in tmp */
98 if (a_key > (tmp->key - tmp->len)) {
99 return 0;
100 }
101 /* Can we append it to the end of tmp? */
102 else if (a_key == (tmp->key - tmp->len)) {
103 // do a sanity check on the next entry
104 if ((tmp->next) && (tmp->next->key == a_key)) {
105 // @@@ We could fix this situation and remove the next entry...
106 return 0;
107 }
108 tmp->len++;
109 return 0;
110 }
111
112 /* The key is less than the current bucket and can't be added to it.
113 * check if we are at the end of the list yet */
114 else if (tmp->next == NULL) {
115 TSK_LIST *ent;
116
117 /*
118 if (tsk_verbose)
119 fprintf(stderr, "entry %" PRIu64 " added to tail\n",
120 a_key);
121 */
122
123 if ((ent = tsk_list_create(a_key)) == NULL)
124 return 1;
125 tmp->next = ent;
126
127 return 0;
128 }
129 // can we prepend it to the next bucket?
130 else if (a_key == tmp->next->key + 1) {
131 tmp->next->key++;
132 tmp->next->len++;
133 return 0;
134 }
135 // do we need a new bucket in between?
136 else if (a_key > tmp->next->key) {
137 TSK_LIST *ent;
138
139 /*
140 if (tsk_verbose)
141 fprintf(stderr,
142 "entry %" PRIu64 " added before %" PRIu64 "\n",
143 a_key, tmp->next->key);
144 */
145
146 if ((ent = tsk_list_create(a_key)) == NULL)
147 return 1;
148
149 ent->next = tmp->next;
150 tmp->next = ent;
151 return 0;
152 }
153 else if (a_key == tmp->next->key) {
154 return 0;
155 }
156 tmp = tmp->next;
157 }
158 return 0;
159 }
160
161 /**
162 * \ingroup baselib
163 * Search a TSK_LIST for the existence of a value.
164 * @param a_tsk_list_head Head of list to search
165 * @param a_key Value to search for
166 * @returns 1 if value is found and 0 if not
167 */
168 uint8_t
tsk_list_find(TSK_LIST * a_tsk_list_head,uint64_t a_key)169 tsk_list_find(TSK_LIST * a_tsk_list_head, uint64_t a_key)
170 {
171 TSK_LIST *tmp;
172
173 tmp = a_tsk_list_head;
174 while (tmp != NULL) {
175 // check this bucket
176 // use the key+1 and then subtract for unsigned cases when key-len == -1
177 if ((a_key <= tmp->key) && (a_key >= tmp->key + 1 - tmp->len))
178 return 1;
179
180 // Have we passed any potential buckets?
181 else if (a_key > tmp->key)
182 return 0;
183
184 tmp = tmp->next;
185 }
186 return 0;
187 }
188
189 /**
190 * \ingroup baselib
191 * Free a TSK_LIST.
192 * @param a_tsk_list_head Head of list to free
193 */
194 void
tsk_list_free(TSK_LIST * a_tsk_list_head)195 tsk_list_free(TSK_LIST * a_tsk_list_head)
196 {
197 TSK_LIST *tmp;
198
199 while (a_tsk_list_head) {
200 tmp = a_tsk_list_head->next;
201 free(a_tsk_list_head);
202 a_tsk_list_head = tmp;
203 }
204 }
205