"Fossies" - the Fresh Open Source Software Archive

Member "sarg-2.4.0/dichotomic.c" (30 Jan 2017, 4716 Bytes) of package /linux/privat/sarg-2.4.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "dichotomic.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 2.3.11_vs_2.4.0.

    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 }