src/ausearch-int.c

   1 /*
   2 * ausearch-int.c - Minimal linked list library for integers
   3 * Copyright (c) 2005,2008 Red Hat Inc., Durham, North Carolina.
   4 * All Rights Reserved.
   5 *
   6 * This software may be freely redistributed and/or modified under the
   7 * terms of the GNU General Public License as published by the Free
   8 * Software Foundation; either version 2, or (at your option) any
   9 * later version.
  10 *
  11 * This program is distributed in the hope that it will be useful,
  12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 * GNU General Public License for more details.
  15 *
  16 * You should have received a copy of the GNU General Public License
  17 * along with this program; see the file COPYING. If not, write to the
  18 * Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19 *
  20 * Authors:
  21 *   Steve Grubb <sgrubb@redhat.com>
  22 */
  23
  24 #include "config.h"
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include "ausearch-int.h"
  28
  29 void ilist_create(ilist *l)
  30 {
  31         l->head = NULL;
  32         l->cur = NULL;
  33         l->cnt = 0;
  34 }
  35
  36 int_node *ilist_next(ilist *l)
  37 {
  38         if (l->cur == NULL)
  39                 return NULL;
  40         l->cur = l->cur->next;
  41         return l->cur;
  42 }
  43
  44 void ilist_append(ilist *l, int num, unsigned int hits, int aux)
  45 {
  46         int_node* newnode;
  47
  48         newnode = malloc(sizeof(int_node));
  49
  50         newnode->num = num;
  51         newnode->hits = hits;
  52         newnode->aux1 = aux;
  53         newnode->next = NULL;
  54
  55         // if we are at top, fix this up
  56         if (l->head == NULL)
  57                 l->head = newnode;
  58         else    // Otherwise add pointer to newnode
  59                 l->cur->next = newnode;
  60
  61         // make newnode current
  62         l->cur = newnode;
  63         l->cnt++;
  64 }
  65
  66 void ilist_clear(ilist* l)
  67 {
  68         int_node* nextnode;
  69         register int_node* current;
  70
  71         if (l == NULL)
  72                 return;
  73
  74         current = l->head;
  75         while (current) {
  76                 nextnode=current->next;
  77                 free(current);
  78                 current=nextnode;
  79         }
  80         l->head = NULL;
  81         l->cur = NULL;
  82         l->cnt = 0;
  83 }
  84
  85 int ilist_add_if_uniq(ilist *l, int num, int aux)
  86 {
  87         register int_node *cur, *prev;
  88
  89         prev = cur = l->head;
  90         while (cur) {
  91                 if (cur->num == num) {
  92                         cur->hits++;
  93                         return 0;
  94                 } else if (num > cur->num) {
  95                         prev = cur;
  96                         cur = cur->next;
  97                 } else {
  98                         int head = 0;
  99
 100                         // Insert so list is from low to high
 101                         if (cur == l->head) {
 102                                 l->head = NULL;
 103                                 head = 1;
 104                         } else
 105                                 l->cur = prev;
 106                         ilist_append(l, num, 1, aux);
 107                         if (head)
 108                                 l->cur->next = prev;
 109                         else
 110                                 l->cur->next = cur;
 111                         return 1;
 112                 }
 113         }
 114
 115         if (prev)
 116                 l->cur = prev;
 117
 118         /* No matches, append to the end */
 119         ilist_append(l, num, 1, aux);
 120         return 1;
 121 }
 122
 123 void ilist_sort_by_hits(ilist *l)
 124 {
 125         register int_node* cur, *prev = NULL;
 126
 127         if (l->cnt <= 1)
 128                 return;
 129
 130         cur = l->head;
 131
 132         /* Make sure l->cur points to end */
 133         if (l->cur->next != NULL) {
 134                 prev = l->cur->next;
 135                 while (prev->next)
 136                         prev = prev->next;
 137                 l->cur = prev;
 138         }
 139
 140         while (cur && cur->next) {
 141                 /* If the next node is bigger */
 142                 if (cur->hits < cur->next->hits) {
 143                         // detach node
 144                         if (l->head == cur)
 145                                 l->head = cur->next;
 146                         if (prev)
 147                                 prev->next = cur->next;
 148                         else
 149                                 prev = cur->next;
 150
 151                         // append
 152                         ilist_append(l, cur->num, cur->hits, cur->aux1);
 153                         free(cur);
 154
 155                         // start over
 156                         cur = l->head;
 157                         prev = NULL;
 158                         continue;
 159                 }
 160                 prev = cur;
 161                 cur = cur->next;
 162         }
 163 }
 164