dichotomic.c

   1 /*
   2  * SARG Squid Analysis Report Generator      http://sarg.sourceforge.net
   3  *                                                            1998, 2015
   4  *
   5  * SARG donations:
   6  *      please look at http://sarg.sourceforge.net/donations.php
   7  * Support:
   8  *     http://sourceforge.net/projects/sarg/forums/forum/363374
   9  * ---------------------------------------------------------------------
  10  *
  11  *  This program is free software; you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License as published by
  13  *  the Free Software Foundation; either version 2 of the License, or
  14  *  (at your option) any later version.
  15  *
  16  *  This program is distributed in the hope that it will be useful,
  17  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  *  GNU General Public License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License
  22  *  along with this program; if not, write to the Free Software
  23  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  24  *
  25  */
  26
  27 #include "include/conf.h"
  28 #include "include/defs.h"
  29 #include "include/dichotomic.h"
  30
  31 /*!
  32 One key/value pair stored in the sorted list.
  33 */
  34 struct DichotomicItemStruct
  35 {
  36         //! The key.
  37         const char *Key;
  38         //! The value.
  39         const char *Value;
  40 };
  41
  42 struct DichotomicStruct
  43 {
  44         //! The array containing the sorted pairs.
  45         struct DichotomicItemStruct *Items;
  46         //! The number of pairs in the array.
  47         int NItems;
  48         //! The size of the array.
  49         int NAllocated;
  50 };
  51
  52 /*!
  53 Create an object to store key/value pairs and
  54 retrieve them.
  55
  56 \return The object to pass to the functions in this module.
  57 The returned pointer is NULL if there is not enough memory
  58 to allocate the object. The object must be freed with a call
  59 to Dichotomic_Destroy().
  60 */
  61 DichotomicObject Dichotomic_Create(void)
  62 {
  63         DichotomicObject Obj;
  64
  65         Obj=malloc(sizeof(*Obj));
  66         if (!Obj)
  67         {
  68                 return(NULL);
  69         }
  70         memset(Obj,0,sizeof(*Obj));
  71         return(Obj);
  72 }
  73
  74 /*!
  75 Destroy an object created by Dichotomic_Create().
  76
  77 \param ObjPtr The pointer to the variable containing
  78 the object to destroy. The pointer is reset to NULL
  79 by this function. It is safe to pass NULL or a NULL
  80 pointer.
  81 */
  82 void Dichotomic_Destroy(DichotomicObject *ObjPtr)
  83 {
  84         DichotomicObject Obj;
  85         int i;
  86
  87         if (!ObjPtr || !*ObjPtr) return;
  88         Obj=*ObjPtr;
  89         *ObjPtr=NULL;
  90         if (Obj->Items)
  91         {
  92                 for (i=0 ; i<Obj->NItems ; i++)
  93                 {
  94                         free((void*)Obj->Items[i].Key);
  95                         free((void*)Obj->Items[i].Value);
  96                 }
  97                 free(Obj->Items);
  98         }
  99         free(Obj);
 100 }
 101
 102 static int Dichotomic_FindKeyPos(DichotomicObject Obj,const char *key,bool *Found)
 103 {
 104         int down,up;
 105         int middle=0;
 106         int cmp=0;
 107
 108         down=0;
 109         up=Obj->NItems-1;
 110         while (up>=down)
 111         {
 112                 middle=(down+up)/2;
 113                 cmp=strcasecmp(key,Obj->Items[middle].Key);
 114                 if (!cmp)
 115                 {
 116                         *Found=true;
 117                         return(middle);
 118                 }
 119                 if (cmp<0)
 120                         up=middle-1;
 121                 else
 122                         down=middle+1;
 123         }
 124         *Found=false;
 125         if (cmp>0) middle++;
 126         return(middle);
 127 }
 128
 129 /*!
 130 Insert a key/value pair into the array.
 131
 132 \param Obj The object created by Dichotomic_Create().
 133 \param key The key of the pair.
 134 \param value The value of the pair.
 135
 136 \return \c True if the pair was inserted or \c false if
 137 it failed.
 138 */
 139 bool Dichotomic_Insert(DichotomicObject Obj,const char *key, const char *value)
 140 {
 141         int Position;
 142         bool Found;
 143         int i;
 144
 145         if (!Obj) return(false);
 146         if (Obj->Items)
 147         {
 148                 Position=Dichotomic_FindKeyPos(Obj,key,&Found);
 149                 if (Found) return(false);
 150         }
 151         else
 152                 Position=0;
 153
 154         if (Obj->NItems>=Obj->NAllocated)
 155         {
 156                 struct DichotomicItemStruct *Items;
 157                 Obj->NAllocated+=25;
 158                 Items=realloc(Obj->Items,Obj->NAllocated*sizeof(*Items));
 159                 if (!Items)
 160                 {
 161                         debuga(__FILE__,__LINE__,_("Not enough memory to store the key/value pair %s/%s\n"),key,value);
 162                         exit(EXIT_FAILURE);
 163                 }
 164                 Obj->Items=Items;
 165         }
 166
 167         for (i=Obj->NItems ; i>Position ; i--)
 168         {
 169                 Obj->Items[i].Key=Obj->Items[i-1].Key;
 170                 Obj->Items[i].Value=Obj->Items[i-1].Value;
 171         }
 172         Obj->Items[Position].Key=strdup(key);
 173         Obj->Items[Position].Value=strdup(value);
 174         if (!Obj->Items[Position].Key || !Obj->Items[Position].Value)
 175         {
 176                 debuga(__FILE__,__LINE__,_("Not enough memory to store the key/value pair %s/%s\n"),key,value);
 177                 exit(EXIT_FAILURE);
 178         }
 179         Obj->NItems++;
 180
 181         return(true);
 182 }
 183
 184 /*!
 185 Search for the value of a key.
 186
 187 \param Obj The object created by Dichotomic_Create().
 188 \param key The key to search for.
 189
 190 \return The value of the key or NULL if the key was not found.
 191 */
 192 const char *Dichotomic_Search(DichotomicObject Obj,const char *key)
 193 {
 194         int Position;
 195         bool Found;
 196
 197         if (!Obj) return(NULL);
 198         if (Obj->NItems==0 || !Obj->Items) return(NULL);
 199         Position=Dichotomic_FindKeyPos(Obj,key,&Found);
 200         if (!Found) return(NULL);
 201         return(Obj->Items[Position].Value);
 202 }