src/shared/store_op.c

   1 /* @(#) $Id: ./src/shared/store_op.c, 2011/09/08 dcid Exp $
   2  */
   3
   4 /* Copyright (C) 2009 Trend Micro Inc.
   5  * All right reserved.
   6  *
   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
  10  * Foundation
  11  */
  12
  13 /* Common API for dealing with ordered lists.
  14  * Provides a fast search on average (n/2).
  15  */
  16
  17
  18 #include "shared.h"
  19
  20
  21 /* Create the list storage
  22  * Return NULL on error
  23  */
  24 OSStore *OSStore_Create()
  25 {
  26     OSStore *my_list;
  27
  28     my_list = calloc(1, sizeof(OSStore));
  29     if(!my_list)
  30         return(NULL);
  31
  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;
  38
  39     return(my_list);
  40 }
  41
  42
  43
  44 /* Deletes the list storage
  45  * Return NULL on error
  46  */
  47 OSStore *OSStore_Free(OSStore *list)
  48 {
  49     OSStoreNode *delnode;
  50     list->cur_node = list->first_node;
  51
  52     while(list->cur_node)
  53     {
  54         if(list->cur_node->key)
  55         {
  56             free(list->cur_node->key);
  57             list->cur_node->key = NULL;
  58         }
  59         if(list->cur_node->data)
  60         {
  61             free(list->cur_node->data);
  62             list->cur_node->data = NULL;
  63         }
  64
  65         /* Deleting each node. */
  66         delnode = list->cur_node;
  67         list->cur_node = list->cur_node->next;
  68         free(delnode);
  69     }
  70
  71     list->first_node = NULL;
  72     list->last_node = NULL;
  73
  74     free(list);
  75     list = NULL;
  76
  77     return(list);
  78 }
  79
  80
  81
  82 /* Set the maximum number of elements
  83  * in the storage. Returns 0 on error or
  84  * 1 on success.
  85  */
  86 int OSStore_SetMaxSize(OSStore *list, int max_size)
  87 {
  88     if(!list)
  89     {
  90         return(0);
  91     }
  92
  93     /* Minimum size is 1 */
  94     if(max_size <= 1)
  95     {
  96         return(0);
  97     }
  98
  99     list->max_size = max_size;
 100
 101     return(1);
 102 }
 103
 104
 105
 106 /* Set the pointer to the function to free the memory
 107  * data.
 108  */
 109 int OSStore_SetFreeDataPointer(OSStore *list, void *free_data_function)
 110 {
 111     if(!list)
 112     {
 113         return(0);
 114     }
 115
 116     list->free_data_function = free_data_function;
 117     return(1);
 118 }
 119
 120
 121
 122 /* Sorts the storage by size.
 123  *
 124  */
 125 int OSStore_Sort(OSStore *list, void*(sort_data_function)(void *d1, void *d2))
 126 {
 127     OSStoreNode *newnode = NULL;
 128     OSStoreNode *movenode = NULL;
 129     list->cur_node = list->first_node;
 130
 131     while(list->cur_node)
 132     {
 133         movenode = list->cur_node->prev;
 134
 135         /* Here we check for all the previous entries, using the sort . */
 136         while(movenode)
 137         {
 138
 139             if(sort_data_function(list->cur_node->data, movenode->data))
 140             {
 141                 movenode = movenode->prev;
 142             }
 143
 144             /* In here, this node should stay where it is. */
 145             else if(movenode == list->cur_node->prev)
 146             {
 147                 break;
 148             }
 149
 150             /* In here we need to replace the nodes. */
 151             else
 152             {
 153                 newnode = list->cur_node;
 154
 155                 if(list->cur_node->prev)
 156                     list->cur_node->prev->next = list->cur_node->next;
 157
 158                 if(list->cur_node->next)
 159                     list->cur_node->next->prev = list->cur_node->prev;
 160                 else
 161                     list->last_node = list->cur_node->prev;
 162
 163                 list->cur_node = list->cur_node->prev;
 164
 165
 166                 newnode->next = movenode->next;
 167                 newnode->prev = movenode;
 168
 169                 if(movenode->next)
 170                     movenode->next->prev = newnode;
 171
 172                 movenode->next = newnode;
 173
 174
 175                 break;
 176             }
 177         }
 178
 179
 180         /* If movenode is not set, we need to put the current node in first.*/
 181         if(!movenode && (list->cur_node != list->first_node))
 182         {
 183             newnode = list->cur_node;
 184
 185             if(list->cur_node->prev)
 186                 list->cur_node->prev->next = list->cur_node->next;
 187
 188             if(list->cur_node->next)
 189                 list->cur_node->next->prev = list->cur_node->prev;
 190             else
 191                 list->last_node = list->cur_node->prev;
 192
 193             list->cur_node = list->cur_node->prev;
 194
 195             newnode->prev = NULL;
 196             newnode->next = list->first_node;
 197             list->first_node->prev = newnode;
 198
 199             list->first_node = newnode;
 200         }
 201
 202         list->cur_node = list->cur_node->next;
 203     }
 204
 205     return(1);
 206 }
 207
 208
 209
 210 /* Get key position from storage
 211  * Returns 0 if not present or the key
 212  * if available.
 213  * (position may change after each PUT)
 214  */
 215 int OSStore_GetPosition(OSStore *list, char *key)
 216 {
 217     int chk_rc, pos = 1;
 218     list->cur_node = list->first_node;
 219
 220     while(list->cur_node)
 221     {
 222         if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
 223         {
 224             /* Found */
 225             if(chk_rc == 0)
 226                 return(pos);
 227
 228             /* Not found */
 229             return(0);
 230         }
 231
 232         list->cur_node = list->cur_node->next;
 233         pos++;
 234     }
 235     return(0);
 236 }
 237
 238
 239
 240 /* Get first node from storage.
 241  * Returns NULL if not present.
 242  */
 243 OSStoreNode *OSStore_GetFirstNode(OSStore *list)
 244 {
 245     return(list->first_node);
 246 }
 247
 248
 249
 250 /* Get data from storage.
 251  * Returns NULL if not present.
 252  */
 253 void *OSStore_Get(OSStore *list, char *key)
 254 {
 255     int chk_rc;
 256     list->cur_node = list->first_node;
 257
 258     while(list->cur_node)
 259     {
 260         if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
 261         {
 262             /* Found */
 263             if(chk_rc == 0)
 264                 return(list->cur_node->data);
 265
 266             /* Not found */
 267             return(NULL);
 268         }
 269
 270         list->cur_node = list->cur_node->next;
 271     }
 272     return(NULL);
 273 }
 274
 275
 276
 277 /* Check if key is present on storage.
 278  * Returns 0 if not present.
 279  */
 280 int OSStore_Check(OSStore *list, char *key)
 281 {
 282     int chk_rc;
 283     list->cur_node = list->first_node;
 284
 285     while(list->cur_node)
 286     {
 287         if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
 288         {
 289             /* Found */
 290             if(chk_rc == 0)
 291                 return(1);
 292
 293             /* Not found */
 294             return(0);
 295         }
 296
 297         list->cur_node = list->cur_node->next;
 298     }
 299     return(0);
 300 }
 301
 302
 303
 304 /* Check if key is present on storage (using strncmp).
 305  * Returns 0 if not present.
 306  */
 307 int OSStore_NCheck(OSStore *list, char *key)
 308 {
 309     int chk_rc;
 310     list->cur_node = list->first_node;
 311
 312     while(list->cur_node)
 313     {
 314         if((chk_rc = strncmp(list->cur_node->key, key,
 315                              list->cur_node->key_size)) >= 0)
 316         {
 317             /* Found */
 318             if(chk_rc == 0)
 319                 return(1);
 320
 321             /* Not found */
 322             return(0);
 323         }
 324
 325         list->cur_node = list->cur_node->next;
 326     }
 327     return(0);
 328 }
 329
 330
 331
 332 /* Check if key is present on storage (case insensitive).
 333  * Returns 0 if not present.
 334  */
 335 int OSStore_NCaseCheck(OSStore *list, char *key)
 336 {
 337     int chk_rc;
 338     list->cur_node = list->first_node;
 339
 340     while(list->cur_node)
 341     {
 342         if((chk_rc = strncasecmp(list->cur_node->key, key,
 343                                  list->cur_node->key_size)) == 0)
 344         {
 345             return(1);
 346         }
 347
 348         list->cur_node = list->cur_node->next;
 349     }
 350     return(0);
 351 }
 352
 353
 354
 355 /* Delete this node from list
 356  * Pointer goes to the next node available.
 357  */
 358 void OSStore_Delete(OSStore *list, char *key)
 359 {
 360     return;
 361 }
 362
 363
 364
 365 /* Add data to the list
 366  * Returns 1 on success and 0 on failure
 367  */
 368 int OSStore_Put(OSStore *list, char *key, void *data)
 369 {
 370     int chk_rc;
 371     OSStoreNode *newnode;
 372
 373
 374     /* Allocating memory for new node */
 375     newnode = calloc(1, sizeof(OSStoreNode));
 376     if(!newnode)
 377     {
 378         merror(MEM_ERROR, __local_name);
 379         return(0);
 380     }
 381
 382     newnode->prev = NULL;
 383     newnode->next = NULL;
 384     newnode->data = data;
 385     newnode->key = key;
 386     newnode->key_size = strlen(key);
 387
 388
 389     /* If we don't have first node, assign it */
 390     if(!list->first_node)
 391     {
 392         list->first_node = newnode;
 393         list->last_node = newnode;
 394     }
 395
 396
 397     /* Store the data in order */
 398     else
 399     {
 400         list->cur_node = list->first_node;
 401         while(list->cur_node)
 402         {
 403             if((chk_rc = strcmp(list->cur_node->key, key)) >= 0)
 404             {
 405                 /* Duplicated entry */
 406                 if(chk_rc == 0)
 407                 {
 408                     return(1);
 409                 }
 410
 411                 /* If there is no prev node, it is because
 412                  * this is the first node.
 413                  */
 414                 if(list->cur_node->prev)
 415                     list->cur_node->prev->next = newnode;
 416                 else
 417                     list->first_node = newnode;
 418
 419
 420                 newnode->prev = list->cur_node->prev;
 421
 422                 list->cur_node->prev = newnode;
 423                 newnode->next = list->cur_node;
 424                 break;
 425             }
 426
 427             list->cur_node = list->cur_node->next;
 428         }
 429
 430         /* New node is the higher key */
 431         if(!newnode->next)
 432         {
 433             list->last_node->next = newnode;
 434             newnode->prev = list->last_node;
 435             list->last_node = newnode;
 436         }
 437     }
 438
 439
 440     /* Increment list size */
 441     list->currently_size++;
 442
 443     return(1);
 444 }
 445
 446 /* EOF */