1 /* @(#) $Id: ./src/shared/store_op.c, 2011/09/08 dcid Exp $
4 /* Copyright (C) 2009 Trend Micro Inc.
7 * This program is a free software; you can redistribute it
8 * and/or modify it under the terms of the GNU General Public
9 * License (version 2) as published by the FSF - Free Software
13 /* Common API for dealing with ordered lists.
14 * Provides a fast search on average (n/2).
21 /* Create the list storage
22 * Return NULL on error
24 OSStore *OSStore_Create()
28 my_list = calloc(1, sizeof(OSStore));
32 my_list->first_node = NULL;
33 my_list->last_node = NULL;
34 my_list->cur_node = NULL;
35 my_list->currently_size = 0;
36 my_list->max_size = 0;
37 my_list->free_data_function = NULL;
44 /* Deletes the list storage
45 * Return NULL on error
47 OSStore *OSStore_Free(OSStore *list)
50 list->cur_node = list->first_node;
54 if(list->cur_node->key)
56 free(list->cur_node->key);
57 list->cur_node->key = NULL;
59 if(list->cur_node->data)
61 free(list->cur_node->data);
62 list->cur_node->data = NULL;
65 /* Deleting each node. */
66 delnode = list->cur_node;
67 list->cur_node = list->cur_node->next;
71 list->first_node = NULL;
72 list->last_node = NULL;
82 /* Set the maximum number of elements
83 * in the storage. Returns 0 on error or
86 int OSStore_SetMaxSize(OSStore *list, int max_size)
93 /* Minimum size is 1 */
99 list->max_size = max_size;
106 /* Set the pointer to the function to free the memory
109 int OSStore_SetFreeDataPointer(OSStore *list, void *free_data_function)
116 list->free_data_function = free_data_function;
122 /* Sorts the storage by size.
125 int OSStore_Sort(OSStore *list, void*(sort_data_function)(void *d1, void *d2))
127 OSStoreNode *newnode = NULL;
128 OSStoreNode *movenode = NULL;
129 list->cur_node = list->first_node;
131 while(list->cur_node)
133 movenode = list->cur_node->prev;
135 /* Here we check for all the previous entries, using the sort . */
139 if(sort_data_function(list->cur_node->data, movenode->data))
141 movenode = movenode->prev;
144 /* In here, this node should stay where it is. */
145 else if(movenode == list->cur_node->prev)
150 /* In here we need to replace the nodes. */
153 newnode = list->cur_node;
155 if(list->cur_node->prev)
156 list->cur_node->prev->next = list->cur_node->next;
158 if(list->cur_node->next)
159 list->cur_node->next->prev = list->cur_node->prev;
161 list->last_node = list->cur_node->prev;
163 list->cur_node = list->cur_node->prev;
166 newnode->next = movenode->next;
167 newnode->prev = movenode;
170 movenode->next->prev = newnode;
172 movenode->next = newnode;
180 /* If movenode is not set, we need to put the current node in first.*/
181 if(!movenode && (list->cur_node != list->first_node))
183 newnode = list->cur_node;
185 if(list->cur_node->prev)
186 list->cur_node->prev->next = list->cur_node->next;
188 if(list->cur_node->next)
189 list->cur_node->next->prev = list->cur_node->prev;
191 list->last_node = list->cur_node->prev;
193 list->cur_node = list->cur_node->prev;
195 newnode->prev = NULL;
196 newnode->next = list->first_node;
197 list->first_node->prev = newnode;
199 list->first_node = newnode;
202 list->cur_node = list->cur_node->next;
210 /* Get key position from storage
211 * Returns 0 if not present or the key
213 * (position may change after each PUT)
215 int OSStore_GetPosition(OSStore *list, char *key)
218 list->cur_node = list->first_node;
220 while(list->cur_node)
222 if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
232 list->cur_node = list->cur_node->next;
240 /* Get first node from storage.
241 * Returns NULL if not present.
243 OSStoreNode *OSStore_GetFirstNode(OSStore *list)
245 return(list->first_node);
250 /* Get data from storage.
251 * Returns NULL if not present.
253 void *OSStore_Get(OSStore *list, char *key)
256 list->cur_node = list->first_node;
258 while(list->cur_node)
260 if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
264 return(list->cur_node->data);
270 list->cur_node = list->cur_node->next;
277 /* Check if key is present on storage.
278 * Returns 0 if not present.
280 int OSStore_Check(OSStore *list, char *key)
283 list->cur_node = list->first_node;
285 while(list->cur_node)
287 if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
297 list->cur_node = list->cur_node->next;
304 /* Check if key is present on storage (using strncmp).
305 * Returns 0 if not present.
307 int OSStore_NCheck(OSStore *list, char *key)
310 list->cur_node = list->first_node;
312 while(list->cur_node)
314 if((chk_rc = strncmp(list->cur_node->key, key,
315 list->cur_node->key_size)) >= 0)
325 list->cur_node = list->cur_node->next;
332 /* Check if key is present on storage (case insensitive).
333 * Returns 0 if not present.
335 int OSStore_NCaseCheck(OSStore *list, char *key)
338 list->cur_node = list->first_node;
340 while(list->cur_node)
342 if((chk_rc = strncasecmp(list->cur_node->key, key,
343 list->cur_node->key_size)) == 0)
348 list->cur_node = list->cur_node->next;
355 /* Delete this node from list
356 * Pointer goes to the next node available.
358 void OSStore_Delete(OSStore *list, char *key)
365 /* Add data to the list
366 * Returns 1 on success and 0 on failure
368 int OSStore_Put(OSStore *list, char *key, void *data)
371 OSStoreNode *newnode;
374 /* Allocating memory for new node */
375 newnode = calloc(1, sizeof(OSStoreNode));
378 merror(MEM_ERROR, __local_name);
382 newnode->prev = NULL;
383 newnode->next = NULL;
384 newnode->data = data;
386 newnode->key_size = strlen(key);
389 /* If we don't have first node, assign it */
390 if(!list->first_node)
392 list->first_node = newnode;
393 list->last_node = newnode;
397 /* Store the data in order */
400 list->cur_node = list->first_node;
401 while(list->cur_node)
403 if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
405 /* Duplicated entry */
411 /* If there is no prev node, it is because
412 * this is the first node.
414 if(list->cur_node->prev)
415 list->cur_node->prev->next = newnode;
417 list->first_node = newnode;
420 newnode->prev = list->cur_node->prev;
422 list->cur_node->prev = newnode;
423 newnode->next = list->cur_node;
427 list->cur_node = list->cur_node->next;
430 /* New node is the higher key */
433 list->last_node->next = newnode;
434 newnode->prev = list->last_node;
435 list->last_node = newnode;
440 /* Increment list size */
441 list->currently_size++;