00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2005--2009 Petter Urkedal <urkedal@nbi.dk> 00003 * 00004 * This program is free software: you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation, either version 3 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 #ifndef CUCON_RBMAP_H 00019 #define CUCON_RBMAP_H 00020 00021 /** \defgroup cucon_rbmap_h cucon/rbmap.h: Maps, Red-Black Tree Implementation 00022 ** @{ \ingroup cucon_maps_and_sets_mod 00023 ** 00024 ** \see cucon_rbset_h 00025 ** \see cucon_pmap_h 00026 **/ 00027 #include <cucon/rbtree.h> 00028 #include <cu/inherit.h> 00029 00030 CU_BEGIN_DECLARATIONS 00031 00032 /** A sorted map implemented as a red-black tree. */ 00033 struct cucon_rbmap 00034 { 00035 cu_inherit (cucon_rbtree); 00036 cu_clop(cmp, int, void *, void *); 00037 }; 00038 00039 /** Construct \a map as an empty map where keps are totally ordered according 00040 ** to \a cmp, where <code>\a cmp(\a x, \a y)</code> shall return 00041 ** - negative to indicate that \e x precedes \e y 00042 ** - positive to indicate that \e x succeeds \e y 00043 ** - zero to indicate that \e x = \e y. */ 00044 void cucon_rbmap_init(cucon_rbmap_t map, cu_clop(cmp, int, void *, void *)); 00045 00046 /** Return a map where keys are ordered according to \a cmp. 00047 ** \see cucon_rbmap_init for the meaning of \a cmp. */ 00048 cucon_rbmap_t cucon_rbmap_new(cu_clop(cmp, int, void *, void *)); 00049 00050 /** The number of elements in \a map. */ 00051 CU_SINLINE size_t cucon_rbmap_size(cucon_rbmap_t map) 00052 { return cucon_rbtree_size(cu_to(cucon_rbtree, map)); } 00053 00054 /** Return the slot for \a key in \a map, or \c NULL if not found. */ 00055 void *cucon_rbmap_find_mem(cucon_rbmap_t map, void *key); 00056 00057 /** Return the pointer value of the slot of \a key in \a map, or \c NULL if not 00058 ** found. */ 00059 void *cucon_rbmap_find_ptr(cucon_rbmap_t map, void *key); 00060 00061 /** If \a key is not in \a map, then insert it with an associated slot of \a 00062 ** slot_size bytes. Returns true iff \a key was inserted. In any case, 00063 ** return the slot in \c *\a slot. */ 00064 cu_bool_t cucon_rbmap_insert_mem(cucon_rbmap_t map, void *key, 00065 size_t slot_size, cu_ptr_ptr_t slot); 00066 00067 /** If \a key is not in \a map, then insert it with a pointer-valued slot set 00068 ** to \a val. Returns true iff \a key was inserted. */ 00069 cu_bool_t cucon_rbmap_insert_ptr(cucon_rbmap_t map, void *key, void *val); 00070 00071 /** If \a key is in \a map, erase it and return true, else return false. */ 00072 cu_bool_t cucon_rbmap_erase(cucon_rbmap_t map, void *key); 00073 00074 /** Sequentially conjunct \a cb over (key, slotptr)-pairs of \a map in order as 00075 ** given by the ordering operator of \a map. */ 00076 cu_bool_t cucon_rbmap_conj_mem(cucon_rbmap_t map, 00077 cu_clop(cb, cu_bool_t, void *key, void *val)); 00078 00079 /** Sequantially conjunct \a cb over pairs of keys and defererenced pointer 00080 ** slots of \a map in order as given by the ordering operator of \a map. */ 00081 cu_bool_t cucon_rbmap_conj_ptr(cucon_rbmap_t map, 00082 cu_clop(cb, cu_bool_t, void *key, void *val)); 00083 00084 CU_END_DECLARATIONS 00085 /** @} */ 00086 #endif