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