git.itanic.dy.fi Git - maemo-mapper/blob - src/hashtable_itr.c

   1 /*
   2  *
   3  * This file is part of Maemo Mapper.
   4  *
   5  * Maemo Mapper is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * Maemo Mapper is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with Maemo Mapper.  If not, see <http://www.gnu.org/licenses/>.
  17  *
  18  *
  19  * Parts of this code have been ported from Xastir by Rob Williams (10 Aug 2008):
  20  *
  21  *  * XASTIR, Amateur Station Tracking and Information Reporting
  22  * Copyright (C) 1999,2000  Frank Giannandrea
  23  * Copyright (C) 2000-2007  The Xastir Group
  24  * Copyright (C) 2002, 2004 Christopher Clark  <firstname.lastname@cl.cam.ac.uk>
  25  *
  26  */
  27
  28 #ifdef HAVE_CONFIG_H
  29 #    include "config.h"
  30 #endif
  31
  32 #ifdef INCLUDE_APRS
  33
  34 #include <stdlib.h> /* defines NULL */
  35 #include <stdio.h>
  36 //#include <string.h>
  37 //#include <math.h>
  38
  39 #include "hashtable.h"
  40 #include "hashtable_private.h"
  41 #include "hashtable_itr.h"
  42
  43 // Must be last include file
  44 //#include "leak_detection.h" /* defines GC_MALLOC/GC_FREE */
  45
  46
  47
  48
  49
  50 /*****************************************************************************/
  51 /* hashtable_iterator    - iterator constructor */
  52
  53 struct hashtable_itr *
  54 hashtable_iterator(struct hashtable *h)
  55 {
  56     unsigned int i, tablelength;
  57     struct hashtable_itr *itr = (struct hashtable_itr *)
  58         malloc(sizeof(struct hashtable_itr));
  59     if (NULL == itr) return NULL;
  60     itr->h = h;
  61     itr->e = NULL;
  62     itr->parent = NULL;
  63     tablelength = h->tablelength;
  64     itr->index = tablelength;
  65     if (0 == h->entrycount) return itr;
  66
  67     for (i = 0; i < tablelength; i++)
  68     {
  69         if (NULL != h->table[i])
  70         {
  71             itr->e = h->table[i];
  72             itr->index = i;
  73             break;
  74         }
  75     }
  76     return itr;
  77 }
  78
  79 /*****************************************************************************/
  80 /* key      - return the key of the (key,value) pair at the current position */
  81 /* value    - return the value of the (key,value) pair at the current position */
  82
  83 void *
  84 hashtable_iterator_key(struct hashtable_itr *i)
  85 {
  86     if (!i)
  87         return NULL;
  88     if (i->e)
  89         return i->e->k;
  90     else
  91         return NULL;
  92 }
  93
  94 void *
  95 hashtable_iterator_value(struct hashtable_itr *i)
  96 {
  97     if (!i)
  98         return NULL;
  99     if (i->e) {
 100         return i->e->v;
 101     } else {
 102         return NULL;
 103     }
 104
 105 }
 106
 107 /*****************************************************************************/
 108 /* advance - advance the iterator to the next element
 109  *           returns zero if advanced to end of table */
 110
 111 int
 112 hashtable_iterator_advance(struct hashtable_itr *itr)
 113 {
 114     unsigned int j,tablelength;
 115     struct entry **table;
 116     struct entry *next;
 117     if (NULL == itr->e) return 0; /* stupidity check */
 118
 119     next = itr->e->next;
 120     if (NULL != next)
 121     {
 122         itr->parent = itr->e;
 123         itr->e = next;
 124         return -1;
 125     }
 126     tablelength = itr->h->tablelength;
 127     itr->parent = NULL;
 128     if (tablelength <= (j = ++(itr->index)))
 129     {
 130         itr->e = NULL;
 131         return 0;
 132     }
 133     table = itr->h->table;
 134     while (NULL == (next = table[j]))
 135     {
 136         if (++j >= tablelength)
 137         {
 138             itr->index = tablelength;
 139             itr->e = NULL;
 140             return 0;
 141         }
 142     }
 143     itr->index = j;
 144     itr->e = next;
 145     return -1;
 146 }
 147
 148 /*****************************************************************************/
 149 /* remove - remove the entry at the current iterator position
 150  *          and advance the iterator, if there is a successive
 151  *          element.
 152  *          If you want the value, read it before you remove:
 153  *          beware memory leaks if you don't.
 154  *          Returns zero if end of iteration. */
 155
 156 int
 157 hashtable_iterator_remove(struct hashtable_itr *itr)
 158 {
 159     struct entry *remember_e, *remember_parent;
 160     int ret;
 161
 162     /* Do the removal */
 163     if (NULL == (itr->parent))
 164     {
 165         /* element is head of a chain */
 166         itr->h->table[itr->index] = itr->e->next;
 167     } else {
 168         /* element is mid-chain */
 169         itr->parent->next = itr->e->next;
 170     }
 171     /* itr->e is now outside the hashtable */
 172     remember_e = itr->e;
 173     itr->h->entrycount--;
 174     freekey(remember_e->k);
 175
 176     /* Advance the iterator, correcting the parent */
 177     remember_parent = itr->parent;
 178     ret = hashtable_iterator_advance(itr);
 179     if (itr->parent == remember_e) { itr->parent = remember_parent; }
 180     free(remember_e);
 181     return ret;
 182 }
 183
 184 /*****************************************************************************/
 185 int /* returns zero if not found */
 186 hashtable_iterator_search(struct hashtable_itr *itr,
 187                           struct hashtable *h, void *k)
 188 {
 189     struct entry *e, *parent;
 190     unsigned int hashvalue, index;
 191
 192     hashvalue = hash(h,k);
 193     index = indexFor(h->tablelength,hashvalue);
 194
 195     e = h->table[index];
 196     parent = NULL;
 197     while (NULL != e)
 198     {
 199         /* Check hash value to short circuit heavier comparison */
 200         if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 201         {
 202             itr->index = index;
 203             itr->e = e;
 204             itr->parent = parent;
 205             itr->h = h;
 206             return -1;
 207         }
 208         parent = e;
 209         e = e->next;
 210     }
 211     return 0;
 212 }
 213
 214
 215 /*
 216  * Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
 217  *
 218  * Permission is hereby granted, free of charge, to any person obtaining a copy
 219  * of this software and associated documentation files (the "Software"), to
 220  * deal in the Software without restriction, including without limitation the
 221  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 222  * sell copies of the Software, and to permit persons to whom the Software is
 223  * furnished to do so, subject to the following conditions:
 224  *
 225  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 226  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 227  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 228  * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 229  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 230  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 231  * */
 232
 233
 234 #endif // INCLUDE_APRS
 235
 236