Add a cache to store the resolved IP addresses

[thirdparty/sarg.git] / dichotomic.c

diff --git a/dichotomic.c b/dichotomic.c
new file mode 100644 (file)
index 0000000..b81129e
--- /dev/null
+++ b/dichotomic.c
@@ -0,0 +1,202 @@
+/*
+ * SARG Squid Analysis Report Generator      http://sarg.sourceforge.net
+ *                                                            1998, 2012
+ *
+ * SARG donations:
+ *      please look at http://sarg.sourceforge.net/donations.php
+ * Support:
+ *     http://sourceforge.net/projects/sarg/forums/forum/363374
+ * ---------------------------------------------------------------------
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
+ *
+ */
+
+#include "include/conf.h"
+#include "include/defs.h"
+#include "include/dichotomic.h"
+
+/*!
+One key/value pair stored in the sorted list.
+*/
+struct DichotomicItemStruct
+{
+       //! The key.
+       const char *Key;
+       //! The value.
+       const char *Value;
+};
+
+struct DichotomicStruct
+{
+       //! The array containing the sorted pairs.
+       struct DichotomicItemStruct *Items;
+       //! The number of pairs in the array.
+       int NItems;
+       //! The size of the array.
+       int NAllocated;
+};
+
+/*!
+Create an object to store key/value pairs and
+retrieve them.
+
+\return The object to pass to the functions in this module.
+The returned pointer is NULL if there is not enough memory
+to allocate the object. The object must be freed with a call
+to Dichotomic_Destroy().
+*/
+DichotomicObject Dichotomic_Create(void)
+{
+       DichotomicObject Obj;
+       
+       Obj=malloc(sizeof(*Obj));
+       if (!Obj)
+       {
+               return(NULL);
+       }
+       memset(Obj,0,sizeof(*Obj));
+       return(Obj);
+}
+
+/*!
+Destroy an object created by Dichotomic_Create().
+
+\param ObjPtr The pointer to the variable containing
+the object to destroy. The pointer is reset to NULL
+by this function. It is safe to pass NULL or a NULL
+pointer.
+*/
+void Dichotomic_Destroy(DichotomicObject *ObjPtr)
+{
+       DichotomicObject Obj;
+       int i;
+       
+       if (!ObjPtr || !*ObjPtr) return;
+       Obj=*ObjPtr;
+       *ObjPtr=NULL;
+       if (Obj->Items)
+       {
+               for (i=0 ; i<Obj->NItems ; i++)
+               {
+                       free((void*)Obj->Items[i].Key);
+                       free((void*)Obj->Items[i].Value);
+               }
+               free(Obj->Items);
+       }
+       free(Obj);
+}
+
+static int Dichotomic_FindKeyPos(DichotomicObject Obj,const char *key,bool *Found)
+{
+       int down,up;
+       int middle=0;
+       int cmp=0;
+       
+       down=0;
+       up=Obj->NItems-1;
+       while (up>=down)
+       {
+               middle=(down+up)/2;
+               cmp=strcasecmp(key,Obj->Items[middle].Key);
+               if (!cmp) 
+               {
+                       *Found=true;
+                       return(middle);
+               }
+               if (cmp<0)
+                       up=middle-1;
+               else
+                       down=middle+1;
+       }
+       *Found=false;
+       if (cmp>0) middle++;
+       return(middle);
+}
+
+/*!
+Insert a key/value pair into the array.
+
+\param Obj The object created by Dichotomic_Create().
+\param key The key of the pair.
+\param value The value of the pair.
+
+\return \c True if the pair was inserted or \c false if
+it failed.
+*/
+bool Dichotomic_Insert(DichotomicObject Obj,const char *key, const char *value)
+{
+       int Position;
+       bool Found;
+       int i;
+       
+       if (!Obj) return(false);
+       if (Obj->Items)
+       {
+               Position=Dichotomic_FindKeyPos(Obj,key,&Found);
+               if (Found) return(false);
+       }
+       else
+               Position=0;
+       
+       if (Obj->NItems>=Obj->NAllocated)
+       {
+               struct DichotomicItemStruct *Items;
+               Obj->NAllocated+=25;
+               Items=realloc(Obj->Items,Obj->NAllocated*sizeof(*Items));
+               if (!Items)
+               {
+                       debuga(_("Not enough memory to store the key/value pair %s/%s\n"),key,value);
+                       exit(EXIT_FAILURE);
+               }
+               Obj->Items=Items;
+       }
+       
+       for (i=Obj->NItems ; i>Position ; i--)
+       {
+               Obj->Items[i].Key=Obj->Items[i-1].Key;
+               Obj->Items[i].Value=Obj->Items[i-1].Value;
+       }
+       Obj->Items[Position].Key=strdup(key);
+       Obj->Items[Position].Value=strdup(value);
+       if (!Obj->Items[Position].Key || !Obj->Items[Position].Value)
+       {
+               debuga(_("Not enough memory to store the key/value pair %s/%s\n"),key,value);
+               exit(EXIT_FAILURE);
+       }
+       Obj->NItems++;
+       
+       return(true);
+}
+
+/*!
+Search for the value of a key.
+
+\param Obj The object created by Dichotomic_Create().
+\param key The key to search for.
+
+\return The value of the key or NULL if the key was not found.
+*/
+const char *Dichotomic_Search(DichotomicObject Obj,const char *key)
+{
+       int Position;
+       bool Found;
+       
+       if (!Obj) return(NULL);
+       if (Obj->NItems==0 || !Obj->Items) return(NULL);
+       Position=Dichotomic_FindKeyPos(Obj,key,&Found);
+       if (!Found) return(NULL);
+       return(Obj->Items[Position].Value);
+}