src/shared/store_op.c

   1 /* Copyright (C) 2009 Trend Micro Inc.
   2  * All right reserved.
   3  *
   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
   7  * Foundation
   8  */
   9
  10 /* Common API for dealing with ordered lists
  11  * Provides a fast search on average (n/2)
  12  */
  13
  14 #include "shared.h"
  15
  16
  17 /* Create the list storage
  18  * Returns NULL on error
  19  */
  20 OSStore *OSStore_Create()
  21 {
  22     OSStore *my_list;
  23
  24     my_list = (OSStore *) calloc(1, sizeof(OSStore));
  25     if (!my_list) {
  26         return (NULL);
  27     }
  28
  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;
  35
  36     return (my_list);
  37 }
  38
  39 /* Delete the list storage
  40  * Returns NULL on error
  41  */
  42 OSStore *OSStore_Free(OSStore *list)
  43 {
  44     OSStoreNode *delnode;
  45     list->cur_node = list->first_node;
  46
  47     while (list->cur_node) {
  48         if (list->cur_node->key) {
  49             free(list->cur_node->key);
  50             list->cur_node->key = NULL;
  51         }
  52         if (list->cur_node->data) {
  53             free(list->cur_node->data);
  54             list->cur_node->data = NULL;
  55         }
  56
  57         /* Delete each node */
  58         delnode = list->cur_node;
  59         list->cur_node = list->cur_node->next;
  60         free(delnode);
  61     }
  62
  63     list->first_node = NULL;
  64     list->last_node = NULL;
  65
  66     free(list);
  67     list = NULL;
  68
  69     return (list);
  70 }
  71
  72 /* Set the maximum number of elements in the storage
  73  * Returns 0 on error or 1 on success
  74  */
  75 int OSStore_SetMaxSize(OSStore *list, int max_size)
  76 {
  77     if (!list) {
  78         return (0);
  79     }
  80
  81     /* Minimum size is 1 */
  82     if (max_size <= 1) {
  83         return (0);
  84     }
  85
  86     list->max_size = max_size;
  87
  88     return (1);
  89 }
  90
  91 /* Set the pointer to the function to free the memory data */
  92 int OSStore_SetFreeDataPointer(OSStore *list, void (free_data_function)(void *))
  93 {
  94     if (!list) {
  95         return (0);
  96     }
  97
  98     list->free_data_function = free_data_function;
  99     return (1);
 100 }
 101
 102 /* Sort the storage by size */
 103 int OSStore_Sort(OSStore *list, void *(sort_data_function)(void *d1, void *d2))
 104 {
 105     OSStoreNode *newnode = NULL;
 106     OSStoreNode *movenode = NULL;
 107     list->cur_node = list->first_node;
 108
 109     while (list->cur_node) {
 110         movenode = list->cur_node->prev;
 111
 112         /* Check for all the previous entries, using sort */
 113         while (movenode) {
 114
 115             if (sort_data_function(list->cur_node->data, movenode->data)) {
 116                 movenode = movenode->prev;
 117             }
 118
 119             /* This node should stay where it is */
 120             else if (movenode == list->cur_node->prev) {
 121                 break;
 122             }
 123
 124             /* Replace the nodes */
 125             else {
 126                 newnode = list->cur_node;
 127
 128                 if (list->cur_node->prev) {
 129                     list->cur_node->prev->next = list->cur_node->next;
 130                 }
 131
 132                 if (list->cur_node->next) {
 133                     list->cur_node->next->prev = list->cur_node->prev;
 134                 } else {
 135                     list->last_node = list->cur_node->prev;
 136                 }
 137
 138                 list->cur_node = list->cur_node->prev;
 139
 140                 newnode->next = movenode->next;
 141                 newnode->prev = movenode;
 142
 143                 if (movenode->next) {
 144                     movenode->next->prev = newnode;
 145                 }
 146
 147                 movenode->next = newnode;
 148
 149                 break;
 150             }
 151         }
 152
 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;
 156
 157             if (list->cur_node->prev) {
 158                 list->cur_node->prev->next = list->cur_node->next;
 159             }
 160
 161             if (list->cur_node->next) {
 162                 list->cur_node->next->prev = list->cur_node->prev;
 163             } else {
 164                 list->last_node = list->cur_node->prev;
 165             }
 166
 167             if ((list->cur_node = list->cur_node->prev) == NULL) {
 168                 return (1);
 169             }
 170
 171             newnode->prev = NULL;
 172             newnode->next = list->first_node;
 173             list->first_node->prev = newnode;
 174
 175             list->first_node = newnode;
 176         }
 177
 178         list->cur_node = list->cur_node->next;
 179     }
 180
 181     return (1);
 182 }
 183
 184 /* Get key position from storage
 185  * Returns 0 if not present or the key if available
 186  * (position may change after each PUT)
 187  */
 188 int OSStore_GetPosition(OSStore *list, const char *key)
 189 {
 190     int chk_rc, pos = 1;
 191     list->cur_node = list->first_node;
 192
 193     while (list->cur_node) {
 194         if ((chk_rc = strcmp(list->cur_node->key, key)) >= 0) {
 195             /* Found */
 196             if (chk_rc == 0) {
 197                 return (pos);
 198             }
 199
 200             /* Not found */
 201             return (0);
 202         }
 203
 204         list->cur_node = list->cur_node->next;
 205         pos++;
 206     }
 207     return (0);
 208 }
 209
 210 /* Get first node from storage
 211  * Returns NULL if not present
 212  */
 213 OSStoreNode *OSStore_GetFirstNode(OSStore *list)
 214 {
 215     return (list->first_node);
 216 }
 217
 218 /* Get data from storage
 219  * Returns NULL if not present
 220  */
 221 void *OSStore_Get(OSStore *list, const char *key)
 222 {
 223     int chk_rc;
 224     list->cur_node = list->first_node;
 225
 226     while (list->cur_node) {
 227         if ((chk_rc = strcmp(list->cur_node->key, key)) >= 0) {
 228             /* Found */
 229             if (chk_rc == 0) {
 230                 return (list->cur_node->data);
 231             }
 232
 233             /* Not found */
 234             return (NULL);
 235         }
 236
 237         list->cur_node = list->cur_node->next;
 238     }
 239     return (NULL);
 240 }
 241
 242 /* Check if key is present on storage
 243  * Returns 0 if not present
 244  */
 245 int OSStore_Check(OSStore *list, const char *key)
 246 {
 247     int chk_rc;
 248     list->cur_node = list->first_node;
 249
 250     while (list->cur_node) {
 251         if ((chk_rc = strcmp(list->cur_node->key, key)) >= 0) {
 252             /* Found */
 253             if (chk_rc == 0) {
 254                 return (1);
 255             }
 256
 257             /* Not found */
 258             return (0);
 259         }
 260
 261         list->cur_node = list->cur_node->next;
 262     }
 263     return (0);
 264 }
 265
 266 /* Check if key is present on storage (using strncmp)
 267  * Returns 0 if not present
 268  */
 269 int OSStore_NCheck(OSStore *list, const char *key)
 270 {
 271     int chk_rc;
 272     list->cur_node = list->first_node;
 273
 274     while (list->cur_node) {
 275         if ((chk_rc = strncmp(list->cur_node->key, key,
 276                               list->cur_node->key_size)) >= 0) {
 277             /* Found */
 278             if (chk_rc == 0) {
 279                 return (1);
 280             }
 281
 282             /* Not found */
 283             return (0);
 284         }
 285
 286         list->cur_node = list->cur_node->next;
 287     }
 288     return (0);
 289 }
 290
 291 /* Check if key is present on storage (case insensitive)
 292  * Returns 0 if not present
 293  */
 294 int OSStore_NCaseCheck(OSStore *list, const char *key)
 295 {
 296     int chk_rc;
 297     list->cur_node = list->first_node;
 298
 299     while (list->cur_node) {
 300         if ((chk_rc = strncasecmp(list->cur_node->key, key,
 301                                   list->cur_node->key_size)) == 0) {
 302             return (1);
 303         }
 304
 305         list->cur_node = list->cur_node->next;
 306     }
 307     return (0);
 308 }
 309
 310 /* Add data to the list
 311  * Returns 1 on success and 0 on failure
 312  */
 313 int OSStore_Put(OSStore *list, const char *key, void *data)
 314 {
 315     int chk_rc;
 316     OSStoreNode *newnode;
 317
 318     /* Allocate memory for new node */
 319     newnode = (OSStoreNode *) calloc(1, sizeof(OSStoreNode));
 320     if (!newnode) {
 321         merror(MEM_ERROR, __local_name, errno, strerror(errno));
 322         return (0);
 323     }
 324
 325     newnode->prev = NULL;
 326     newnode->next = NULL;
 327     newnode->data = data;
 328     newnode->key = strdup(key);
 329     if (!newnode->key) {
 330         free(newnode);
 331         merror(MEM_ERROR, __local_name, errno, strerror(errno));
 332         return (0);
 333     }
 334     newnode->key_size = strlen(key);
 335
 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;
 340     }
 341
 342     /* Store the data in order */
 343     else {
 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 */
 348                 if (chk_rc == 0) {
 349                     free(newnode->key);
 350                     free(newnode);
 351                     return (1);
 352                 }
 353
 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;
 357                 } else {
 358                     list->first_node = newnode;
 359                 }
 360
 361                 newnode->prev = list->cur_node->prev;
 362
 363                 list->cur_node->prev = newnode;
 364                 newnode->next = list->cur_node;
 365                 break;
 366             }
 367
 368             list->cur_node = list->cur_node->next;
 369         }
 370
 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;
 376         }
 377     }
 378
 379     /* Increment list size */
 380     list->currently_size++;
 381
 382     return (1);
 383 }