src/strset.c

   1 /*
   2  * Copyright (C) 2003-2009 The Music Player Daemon Project
   3  * http://www.musicpd.org
   4  *
   5  * This program 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 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program 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 along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  */
  19
  20 #include "strset.h"
  21
  22 #include <assert.h>
  23 #include <string.h>
  24 #include <stdlib.h>
  25
  26 #define NUM_SLOTS 16384
  27
  28 struct strset_slot {
  29         struct strset_slot *next;
  30         const char *value;
  31 };
  32
  33 struct strset {
  34         unsigned size;
  35
  36         struct strset_slot *current_slot;
  37         unsigned next_slot;
  38
  39         struct strset_slot slots[NUM_SLOTS];
  40 };
  41
  42 static unsigned calc_hash(const char *p) {
  43         unsigned hash = 5381;
  44
  45         assert(p != NULL);
  46
  47         while (*p != 0)
  48                 hash = (hash << 5) + hash + *p++;
  49
  50         return hash;
  51 }
  52
  53 G_GNUC_MALLOC struct strset *strset_new(void)
  54 {
  55         struct strset *set = g_new0(struct strset, 1);
  56         return set;
  57 }
  58
  59 void strset_free(struct strset *set)
  60 {
  61         unsigned i;
  62
  63         for (i = 0; i < NUM_SLOTS; ++i) {
  64                 struct strset_slot *slot = set->slots[i].next, *next;
  65
  66                 while (slot != NULL) {
  67                         next = slot->next;
  68                         g_free(slot);
  69                         slot = next;
  70                 }
  71         }
  72
  73         g_free(set);
  74 }
  75
  76 void strset_add(struct strset *set, const char *value)
  77 {
  78         struct strset_slot *base_slot
  79                 = &set->slots[calc_hash(value) % NUM_SLOTS];
  80         struct strset_slot *slot = base_slot;
  81
  82         if (base_slot->value == NULL) {
  83                 /* empty slot - put into base_slot */
  84                 assert(base_slot->next == NULL);
  85
  86                 base_slot->value = value;
  87                 ++set->size;
  88                 return;
  89         }
  90
  91         for (slot = base_slot; slot != NULL; slot = slot->next)
  92                 if (strcmp(slot->value, value) == 0)
  93                         /* found it - do nothing */
  94                         return;
  95
  96         /* insert it into the slot chain */
  97         slot = g_new(struct strset_slot, 1);
  98         slot->next = base_slot->next;
  99         slot->value = value;
 100         base_slot->next = slot;
 101         ++set->size;
 102 }
 103
 104 int strset_get(const struct strset *set, const char *value)
 105 {
 106         const struct strset_slot *slot = &set->slots[calc_hash(value)];
 107
 108         if (slot->value == NULL)
 109                 return 0;
 110
 111         for (slot = slot->next; slot != NULL; slot = slot->next)
 112                 if (strcmp(slot->value, value) == 0)
 113                         /* found it - do nothing */
 114                         return 1;
 115
 116         return 0;
 117 }
 118
 119 unsigned strset_size(const struct strset *set)
 120 {
 121         return set->size;
 122 }
 123
 124 void strset_rewind(struct strset *set)
 125 {
 126         set->current_slot = NULL;
 127         set->next_slot = 0;
 128 }
 129
 130 const char *strset_next(struct strset *set)
 131 {
 132         if (set->current_slot != NULL && set->current_slot->next != NULL) {
 133                 set->current_slot = set->current_slot->next;
 134                 return set->current_slot->value;
 135         }
 136
 137         while (set->next_slot < NUM_SLOTS &&
 138                set->slots[set->next_slot].value == NULL)
 139                 ++set->next_slot;
 140
 141         if (set->next_slot >= NUM_SLOTS)
 142                 return NULL;
 143
 144         set->current_slot = &set->slots[set->next_slot++];
 145         return set->current_slot->value;
 146 }
 147