1 /* Copyright (C) 2009 Trend Micro Inc.
4 * This program is a free software; you can redistribute it
5 * and/or modify it under the terms of the GNU General Public
6 * License (version 2) as published by the FSF - Free Software
10 /* Common API for dealing with ordered lists
11 * Provides a fast search on average (n/2)
17 /* Create the list storage
18 * Returns NULL on error
20 OSStore *OSStore_Create()
24 my_list = (OSStore *) calloc(1, sizeof(OSStore));
29 my_list->first_node = NULL;
30 my_list->last_node = NULL;
31 my_list->cur_node = NULL;
32 my_list->currently_size = 0;
33 my_list->max_size = 0;
34 my_list->free_data_function = NULL;
39 /* Delete the list storage
40 * Returns NULL on error
42 OSStore *OSStore_Free(OSStore *list)
45 list->cur_node = list->first_node;
47 while (list->cur_node) {
48 if (list->cur_node->key) {
49 free(list->cur_node->key);
50 list->cur_node->key = NULL;
52 if (list->cur_node->data) {
53 free(list->cur_node->data);
54 list->cur_node->data = NULL;
57 /* Delete each node */
58 delnode = list->cur_node;
59 list->cur_node = list->cur_node->next;
63 list->first_node = NULL;
64 list->last_node = NULL;
72 /* Set the maximum number of elements in the storage
73 * Returns 0 on error or 1 on success
75 int OSStore_SetMaxSize(OSStore *list, int max_size)
81 /* Minimum size is 1 */
86 list->max_size = max_size;
91 /* Set the pointer to the function to free the memory data */
92 int OSStore_SetFreeDataPointer(OSStore *list, void (free_data_function)(void *))
98 list->free_data_function = free_data_function;
102 /* Sort the storage by size */
103 int OSStore_Sort(OSStore *list, void *(sort_data_function)(void *d1, void *d2))
105 OSStoreNode *newnode = NULL;
106 OSStoreNode *movenode = NULL;
107 list->cur_node = list->first_node;
109 while (list->cur_node) {
110 movenode = list->cur_node->prev;
112 /* Check for all the previous entries, using sort */
115 if (sort_data_function(list->cur_node->data, movenode->data)) {
116 movenode = movenode->prev;
119 /* This node should stay where it is */
120 else if (movenode == list->cur_node->prev) {
124 /* Replace the nodes */
126 newnode = list->cur_node;
128 if (list->cur_node->prev) {
129 list->cur_node->prev->next = list->cur_node->next;
132 if (list->cur_node->next) {
133 list->cur_node->next->prev = list->cur_node->prev;
135 list->last_node = list->cur_node->prev;
138 list->cur_node = list->cur_node->prev;
140 newnode->next = movenode->next;
141 newnode->prev = movenode;
143 if (movenode->next) {
144 movenode->next->prev = newnode;
147 movenode->next = newnode;
153 /* If movenode is not set, put the current node in first */
154 if (!movenode && (list->cur_node != list->first_node)) {
155 newnode = list->cur_node;
157 if (list->cur_node->prev) {
158 list->cur_node->prev->next = list->cur_node->next;
161 if (list->cur_node->next) {
162 list->cur_node->next->prev = list->cur_node->prev;
164 list->last_node = list->cur_node->prev;
167 if ((list->cur_node = list->cur_node->prev) == NULL) {
171 newnode->prev = NULL;
172 newnode->next = list->first_node;
173 list->first_node->prev = newnode;
175 list->first_node = newnode;
178 list->cur_node = list->cur_node->next;
184 /* Get key position from storage
185 * Returns 0 if not present or the key if available
186 * (position may change after each PUT)
188 int OSStore_GetPosition(OSStore *list, const char *key)
191 list->cur_node = list->first_node;
193 while (list->cur_node) {
194 if ((chk_rc = strcmp(list->cur_node->key, key)) >= 0) {
204 list->cur_node = list->cur_node->next;
210 /* Get first node from storage
211 * Returns NULL if not present
213 OSStoreNode *OSStore_GetFirstNode(OSStore *list)
215 return (list->first_node);
218 /* Get data from storage
219 * Returns NULL if not present
221 void *OSStore_Get(OSStore *list, const char *key)
224 list->cur_node = list->first_node;
226 while (list->cur_node) {
227 if ((chk_rc = strcmp(list->cur_node->key, key)) >= 0) {
230 return (list->cur_node->data);
237 list->cur_node = list->cur_node->next;
242 /* Check if key is present on storage
243 * Returns 0 if not present
245 int OSStore_Check(OSStore *list, const char *key)
248 list->cur_node = list->first_node;
250 while (list->cur_node) {
251 if ((chk_rc = strcmp(list->cur_node->key, key)) >= 0) {
261 list->cur_node = list->cur_node->next;
266 /* Check if key is present on storage (using strncmp)
267 * Returns 0 if not present
269 int OSStore_NCheck(OSStore *list, const char *key)
272 list->cur_node = list->first_node;
274 while (list->cur_node) {
275 if ((chk_rc = strncmp(list->cur_node->key, key,
276 list->cur_node->key_size)) >= 0) {
286 list->cur_node = list->cur_node->next;
291 /* Check if key is present on storage (case insensitive)
292 * Returns 0 if not present
294 int OSStore_NCaseCheck(OSStore *list, const char *key)
297 list->cur_node = list->first_node;
299 while (list->cur_node) {
300 if ((chk_rc = strncasecmp(list->cur_node->key, key,
301 list->cur_node->key_size)) == 0) {
305 list->cur_node = list->cur_node->next;
310 /* Add data to the list
311 * Returns 1 on success and 0 on failure
313 int OSStore_Put(OSStore *list, const char *key, void *data)
316 OSStoreNode *newnode;
318 /* Allocate memory for new node */
319 newnode = (OSStoreNode *) calloc(1, sizeof(OSStoreNode));
321 merror(MEM_ERROR, __local_name, errno, strerror(errno));
325 newnode->prev = NULL;
326 newnode->next = NULL;
327 newnode->data = data;
328 newnode->key = strdup(key);
331 merror(MEM_ERROR, __local_name, errno, strerror(errno));
334 newnode->key_size = strlen(key);
336 /* If we don't have first node, assign it */
337 if (!list->first_node) {
338 list->first_node = newnode;
339 list->last_node = newnode;
342 /* Store the data in order */
344 list->cur_node = list->first_node;
345 while (list->cur_node) {
346 if ((chk_rc = strcmp(list->cur_node->key, key)) >= 0) {
347 /* Duplicate entry */
354 /* If there is no prev node, this is the first node */
355 if (list->cur_node->prev) {
356 list->cur_node->prev->next = newnode;
358 list->first_node = newnode;
361 newnode->prev = list->cur_node->prev;
363 list->cur_node->prev = newnode;
364 newnode->next = list->cur_node;
368 list->cur_node = list->cur_node->next;
371 /* New node is the higher key */
372 if (!newnode->next) {
373 list->last_node->next = newnode;
374 newnode->prev = list->last_node;
375 list->last_node = newnode;
379 /* Increment list size */
380 list->currently_size++;