1 /* @(#) $Id: store_op.c,v 1.11 2009/06/24 18:53:09 dcid Exp $ */
3 /* Copyright (C) 2009 Trend Micro Inc.
6 * This program is a free software; you can redistribute it
7 * and/or modify it under the terms of the GNU General Public
8 * License (version 3) as published by the FSF - Free Software
12 /* Common API for dealing with ordered lists.
13 * Provides a fast search on average (n/2).
20 /* Create the list storage
21 * Return NULL on error
23 OSStore *OSStore_Create()
27 my_list = calloc(1, sizeof(OSStore));
31 my_list->first_node = NULL;
32 my_list->last_node = NULL;
33 my_list->cur_node = NULL;
34 my_list->currently_size = 0;
35 my_list->max_size = 0;
36 my_list->free_data_function = NULL;
43 /* Deletes the list storage
44 * Return NULL on error
46 OSStore *OSStore_Free(OSStore *list)
49 list->cur_node = list->first_node;
53 if(list->cur_node->key)
55 free(list->cur_node->key);
56 list->cur_node->key = NULL;
58 if(list->cur_node->data)
60 free(list->cur_node->data);
61 list->cur_node->data = NULL;
64 /* Deleting each node. */
65 delnode = list->cur_node;
66 list->cur_node = list->cur_node->next;
70 list->first_node = NULL;
71 list->last_node = NULL;
81 /* Set the maximum number of elements
82 * in the storage. Returns 0 on error or
85 int OSStore_SetMaxSize(OSStore *list, int max_size)
92 /* Minimum size is 1 */
98 list->max_size = max_size;
105 /* Set the pointer to the function to free the memory
108 int OSStore_SetFreeDataPointer(OSStore *list, void *free_data_function)
115 list->free_data_function = free_data_function;
121 /* Sorts the storage by size.
124 int OSStore_Sort(OSStore *list, void*(sort_data_function)(void *d1, void *d2))
126 OSStoreNode *newnode = NULL;
127 OSStoreNode *movenode = NULL;
128 list->cur_node = list->first_node;
130 while(list->cur_node)
132 movenode = list->cur_node->prev;
134 /* Here we check for all the previous entries, using the sort . */
138 if(sort_data_function(list->cur_node->data, movenode->data))
140 movenode = movenode->prev;
143 /* In here, this node should stay where it is. */
144 else if(movenode == list->cur_node->prev)
149 /* In here we need to replace the nodes. */
152 newnode = list->cur_node;
154 if(list->cur_node->prev)
155 list->cur_node->prev->next = list->cur_node->next;
157 if(list->cur_node->next)
158 list->cur_node->next->prev = list->cur_node->prev;
160 list->last_node = list->cur_node->prev;
162 list->cur_node = list->cur_node->prev;
165 newnode->next = movenode->next;
166 newnode->prev = movenode;
169 movenode->next->prev = newnode;
171 movenode->next = newnode;
179 /* If movenode is not set, we need to put the current node in first.*/
180 if(!movenode && (list->cur_node != list->first_node))
182 newnode = list->cur_node;
184 if(list->cur_node->prev)
185 list->cur_node->prev->next = list->cur_node->next;
187 if(list->cur_node->next)
188 list->cur_node->next->prev = list->cur_node->prev;
190 list->last_node = list->cur_node->prev;
192 list->cur_node = list->cur_node->prev;
194 newnode->prev = NULL;
195 newnode->next = list->first_node;
196 list->first_node->prev = newnode;
198 list->first_node = newnode;
201 list->cur_node = list->cur_node->next;
209 /* Get key position from storage
210 * Returns 0 if not present or the key
212 * (position may change after each PUT)
214 int OSStore_GetPosition(OSStore *list, char *key)
217 list->cur_node = list->first_node;
219 while(list->cur_node)
221 if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
231 list->cur_node = list->cur_node->next;
239 /* Get first node from storage.
240 * Returns NULL if not present.
242 OSStoreNode *OSStore_GetFirstNode(OSStore *list)
244 return(list->first_node);
249 /* Get data from storage.
250 * Returns NULL if not present.
252 void *OSStore_Get(OSStore *list, char *key)
255 list->cur_node = list->first_node;
257 while(list->cur_node)
259 if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
263 return(list->cur_node->data);
269 list->cur_node = list->cur_node->next;
276 /* Check if key is present on storage.
277 * Returns 0 if not present.
279 int OSStore_Check(OSStore *list, char *key)
282 list->cur_node = list->first_node;
284 while(list->cur_node)
286 if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
296 list->cur_node = list->cur_node->next;
303 /* Check if key is present on storage (using strncmp).
304 * Returns 0 if not present.
306 int OSStore_NCheck(OSStore *list, char *key)
309 list->cur_node = list->first_node;
311 while(list->cur_node)
313 if((chk_rc = strncmp(list->cur_node->key, key,
314 list->cur_node->key_size)) >= 0)
324 list->cur_node = list->cur_node->next;
331 /* Check if key is present on storage (case insensitive).
332 * Returns 0 if not present.
334 int OSStore_NCaseCheck(OSStore *list, char *key)
337 list->cur_node = list->first_node;
339 while(list->cur_node)
341 if((chk_rc = strncasecmp(list->cur_node->key, key,
342 list->cur_node->key_size)) == 0)
347 list->cur_node = list->cur_node->next;
354 /* Delete this node from list
355 * Pointer goes to the next node available.
357 void OSStore_Delete(OSStore *list, char *key)
364 /* Add data to the list
365 * Returns 1 on success and 0 on failure
367 int OSStore_Put(OSStore *list, char *key, void *data)
370 OSStoreNode *newnode;
373 /* Allocating memory for new node */
374 newnode = calloc(1, sizeof(OSStoreNode));
377 merror(MEM_ERROR, __local_name);
381 newnode->prev = NULL;
382 newnode->next = NULL;
383 newnode->data = data;
385 newnode->key_size = strlen(key);
388 /* If we don't have first node, assign it */
389 if(!list->first_node)
391 list->first_node = newnode;
392 list->last_node = newnode;
396 /* Store the data in order */
399 list->cur_node = list->first_node;
400 while(list->cur_node)
402 if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
404 /* Duplicated entry */
410 /* If there is no prev node, it is because
411 * this is the first node.
413 if(list->cur_node->prev)
414 list->cur_node->prev->next = newnode;
416 list->first_node = newnode;
419 newnode->prev = list->cur_node->prev;
421 list->cur_node->prev = newnode;
422 newnode->next = list->cur_node;
426 list->cur_node = list->cur_node->next;
429 /* New node is the higher key */
432 list->last_node->next = newnode;
433 newnode->prev = list->last_node;
434 list->last_node = newnode;
439 /* Increment list size */
440 list->currently_size++;