include/su/cs-dict.h

   1 /*@ Dictionary with char* keys.
   2  *
   3  * Copyright (c) 2001 - 2019 Steffen (Daode) Nurpmeso <steffen@sdaoden.eu>.
   4  * SPDX-License-Identifier: ISC
   5  *
   6  * Permission to use, copy, modify, and/or distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18 #ifndef su_CS_DICT_H
  19 #define su_CS_DICT_H
  20 #include <su/code.h>
  21 #define su_HEADER
  22 #include <su/code-in.h>
  23 C_DECL_BEGIN
  24 struct su_cs_dict;
  25 struct su_cs_dict_view;
  26 enum su_cs_dict_flags{
  27    su_CS_DICT_POW2_SPACED = 1u<<0,
  28    su_CS_DICT_OWNS = 1u<<1,
  29    su_CS_DICT_CASE = 1u<<2,
  30    su_CS_DICT_HEAD_RESORT = 1u<<3,
  31    su_CS_DICT_AUTO_SHRINK = 1u<<4,
  32    su_CS_DICT_FROZEN = 1u<<5,
  33    su_CS_DICT_ERR_PASS = su_STATE_ERR_PASS,
  34    su_CS_DICT_NIL_IS_VALID_OBJECT = su_STATE_ERR_NIL_IS_VALID_OBJECT,
  35    su_CS_DICT_NILISVALO = su_CS_DICT_NIL_IS_VALID_OBJECT,
  36    su__CS_DICT_CREATE_MASK = su_CS_DICT_POW2_SPACED |
  37          su_CS_DICT_OWNS | su_CS_DICT_CASE |
  38          su_CS_DICT_HEAD_RESORT | su_CS_DICT_AUTO_SHRINK | su_CS_DICT_FROZEN |
  39          su_CS_DICT_ERR_PASS | su_CS_DICT_NIL_IS_VALID_OBJECT
  40 };
  41 #ifdef su_SOURCE_CS_DICT
  42 CTA((su_STATE_ERR_MASK & ~0xFF00u) == 0,
  43    "Reuse of low order bits impossible, or mask excesses storage");
  44 #endif
  45 struct su_cs_dict{
  46    struct su__cs_dict_node **csd_array;
  47    u16 csd_flags;
  48    u8 csd_tshift;
  49    u8 csd__pad[su_6432(5,1)];
  50    u32 csd_count;
  51    u32 csd_size;
  52    struct su_toolbox const *csd_tbox;
  53 };
  54 struct su__cs_dict_node{
  55    struct su__cs_dict_node *csdn_next;
  56    void *csdn_data;
  57    uz csdn_khash;
  58    u32 csdn_klen;
  59    char csdn_key[su_VFIELD_SIZE(4)];
  60 };
  61 /* "The const is preserved logically" */
  62 EXPORT struct su__cs_dict_node *su__cs_dict_lookup(
  63       struct su_cs_dict const *self, char const *key, void *lookarg_or_nil);
  64 /* *lookarg_or_nil is always updated */
  65 EXPORT s32 su__cs_dict_insrep(struct su_cs_dict *self, char const *key,
  66       void *value, up replace_and_view_or_nil);
  67 #if DVLOR(1, 0)
  68 EXPORT void su__cs_dict_stats(struct su_cs_dict const *self);
  69 #endif
  70 #define su_CS_DICT_FOREACH(SELF,VIEWNAME) \
  71    for(su_cs_dict_view_begin(su_cs_dict_view_setup(VIEWNAME, SELF));\
  72          su_cs_dict_view_is_valid(VIEWNAME);\
  73          su_cs_dict_view_next(VIEWNAME))
  74 EXPORT struct su_cs_dict *su_cs_dict_create(struct su_cs_dict *self,
  75       u16 flags, struct su_toolbox const *tbox_or_nil);
  76 EXPORT SHADOW struct su_cs_dict *su_cs_dict_create_copy(
  77       struct su_cs_dict *self, struct su_cs_dict const *t);
  78 EXPORT void su_cs_dict_gut(struct su_cs_dict *self);
  79 EXPORT s32 su_cs_dict_assign(struct su_cs_dict *self,
  80       struct su_cs_dict const *t);
  81 EXPORT s32 su_cs_dict_assign_elems(struct su_cs_dict *self,
  82       struct su_cs_dict const *t);
  83 EXPORT struct su_cs_dict *su_cs_dict_clear(struct su_cs_dict *self);
  84 EXPORT struct su_cs_dict *su_cs_dict_clear_elems(struct su_cs_dict *self);
  85 EXPORT struct su_cs_dict *su_cs_dict_swap(struct su_cs_dict *self,
  86       struct su_cs_dict *t);
  87 INLINE u16 su_cs_dict_flags(struct su_cs_dict const *self){
  88    ASSERT(self);
  89    return self->csd_flags;
  90 }
  91 INLINE struct su_cs_dict *su_cs_dict_add_flags(struct su_cs_dict *self,
  92       u16 flags){
  93    ASSERT(self);
  94    flags &= su__CS_DICT_CREATE_MASK;
  95    self->csd_flags |= flags;
  96    return self;
  97 }
  98 INLINE struct su_cs_dict *su_cs_dict_clear_flags(struct su_cs_dict *self,
  99       u16 flags){
 100    ASSERT(self);
 101    flags &= su__CS_DICT_CREATE_MASK;
 102    self->csd_flags &= ~flags;
 103    return self;
 104 }
 105 INLINE u8 su_cs_dict_treshold_shift(struct su_cs_dict const *self){
 106    ASSERT(self);
 107    return self->csd_tshift;
 108 }
 109 INLINE struct su_cs_dict *su_cs_dict_set_treshold_shift(
 110       struct su_cs_dict *self, u8 ntshift){
 111    ASSERT(self);
 112    self->csd_tshift = CLIP(ntshift, 1, 8);
 113    return self;
 114 }
 115 INLINE struct su_toolbox const *su_cs_dict_toolbox(
 116       struct su_cs_dict const *self){
 117    ASSERT(self);
 118    return self->csd_tbox;
 119 }
 120 INLINE struct su_cs_dict *su_cs_dict_set_toolbox(struct su_cs_dict *self,
 121       struct su_toolbox const *tbox_or_nil){
 122    ASSERT(self);
 123    ASSERT(!(su_cs_dict_flags(self) & su_CS_DICT_OWNS) ||
 124       (tbox_or_nil != NIL && tbox_or_nil->tb_clone != NIL &&
 125        tbox_or_nil->tb_delete != NIL && tbox_or_nil->tb_assign != NIL));
 126    self->csd_tbox = tbox_or_nil;
 127    return self;
 128 }
 129 INLINE u32 su_cs_dict_count(struct su_cs_dict const *self){
 130    ASSERT(self);
 131    return self->csd_count;
 132 }
 133 EXPORT struct su_cs_dict *su_cs_dict_balance(struct su_cs_dict *self);
 134 INLINE boole su_cs_dict_has_key(struct su_cs_dict const *self,
 135       char const *key){
 136    ASSERT(self);
 137    ASSERT_RET(key != NIL, FAL0);
 138    return (su__cs_dict_lookup(self, key, NIL) != NIL);
 139 }
 140 INLINE void *su_cs_dict_lookup(struct su_cs_dict *self, char const *key){
 141    struct su__cs_dict_node *csdnp;
 142    ASSERT(self != NIL);
 143    ASSERT_RET(key != NIL, NIL);
 144    csdnp = su__cs_dict_lookup(self, key, NIL);
 145    return (csdnp != NIL) ? csdnp->csdn_data : NIL;
 146 }
 147 INLINE s32 su_cs_dict_insert(struct su_cs_dict *self, char const *key,
 148       void *value){
 149    ASSERT(self);
 150    ASSERT_RET(key != NIL, 0);
 151    return su__cs_dict_insrep(self, key, value, FAL0);
 152 }
 153 INLINE s32 su_cs_dict_replace(struct su_cs_dict *self, char const *key,
 154       void *value){
 155    ASSERT(self);
 156    ASSERT_RET(key != NIL, 0);
 157    return su__cs_dict_insrep(self, key, value, TRU1);
 158 }
 159 EXPORT boole su_cs_dict_remove(struct su_cs_dict *self, char const *key);
 160 INLINE void su_cs_dict_statistics(struct su_cs_dict const *self){
 161    UNUSED(self);
 162 #if DVLOR(1, 0)
 163    su__cs_dict_stats(self);
 164 #endif
 165 }
 166 enum su__cs_dict_view_move_types{
 167    su__CS_DICT_VIEW_MOVE_BEGIN,
 168    su__CS_DICT_VIEW_MOVE_HAS_NEXT,
 169    su__CS_DICT_VIEW_MOVE_NEXT
 170 };
 171 struct su_cs_dict_view{
 172    struct su_cs_dict *csdv_parent;
 173    struct su__cs_dict_node *csdv_node;
 174    u32 csdv_index;
 175    /* Those only valid after _move(..HAS_NEXT) */
 176    u32 csdv_next_index;
 177    struct su__cs_dict_node *csdv_next_node;
 178 };
 179 /* "The const is preserved logically" */
 180 EXPORT struct su_cs_dict_view *su__cs_dict_view_move(
 181       struct su_cs_dict_view *self, u8 type);
 182 #define su_CS_DICT_VIEW_FOREACH(SELF) \
 183    for(su_cs_dict_view_begin(SELF); su_cs_dict_view_is_valid(SELF);\
 184          su_cs_dict_view_next(SELF))
 185 INLINE struct su_cs_dict_view *su_cs_dict_view_setup(
 186       struct su_cs_dict_view *self, struct su_cs_dict *parent){
 187    ASSERT(self);
 188    self->csdv_parent = parent;
 189    self->csdv_node = NIL;
 190    ASSERT_RET(parent != NIL, self);
 191    return self;
 192 }
 193 INLINE struct su_cs_dict *su_cs_dict_view_parent(
 194       struct su_cs_dict_view const *self){
 195    ASSERT(self);
 196    return self->csdv_parent;
 197 }
 198 INLINE boole su_cs_dict_view_is_valid(struct su_cs_dict_view const *self){
 199    ASSERT(self);
 200    return (self->csdv_node != NIL);
 201 }
 202 INLINE struct su_cs_dict_view *su_cs_dict_view_reset(
 203       struct su_cs_dict_view *self){
 204    ASSERT(self);
 205    self->csdv_node = NIL;
 206    return self;
 207 }
 208 INLINE char const *su_cs_dict_view_key(struct su_cs_dict_view const *self){
 209    ASSERT(self);
 210    ASSERT_RET(su_cs_dict_view_is_valid(self), NIL);
 211    return self->csdv_node->csdn_key;
 212 }
 213 INLINE u32 su_cs_dict_view_key_len(struct su_cs_dict_view const *self){
 214    ASSERT(self);
 215    ASSERT_RET(su_cs_dict_view_is_valid(self), 0);
 216    return self->csdv_node->csdn_klen;
 217 }
 218 INLINE uz su_cs_dict_view_key_hash(struct su_cs_dict_view const *self){
 219    ASSERT(self);
 220    ASSERT_RET(su_cs_dict_view_is_valid(self), 0);
 221    return self->csdv_node->csdn_khash;
 222 }
 223 INLINE void *su_cs_dict_view_data(struct su_cs_dict_view const *self){
 224    ASSERT(self);
 225    ASSERT_RET(su_cs_dict_view_is_valid(self), NIL);
 226    return self->csdv_node->csdn_data;
 227 }
 228 EXPORT s32 su_cs_dict_view_set_data(struct su_cs_dict_view *self, void *value);
 229 INLINE struct su_cs_dict_view *su_cs_dict_view_begin(
 230       struct su_cs_dict_view *self){
 231    ASSERT(self);
 232    return su__cs_dict_view_move(self, su__CS_DICT_VIEW_MOVE_BEGIN);
 233 }
 234 INLINE boole su_cs_dict_view_has_next(struct su_cs_dict_view const *self){
 235    ASSERT(self);
 236    ASSERT_RET(su_cs_dict_view_is_valid(self), FAL0);
 237    return (su__cs_dict_view_move(C(struct su_cs_dict_view*,self),
 238       su__CS_DICT_VIEW_MOVE_HAS_NEXT)->csdv_next_node != NIL);
 239 }
 240 INLINE struct su_cs_dict_view *su_cs_dict_view_next(
 241       struct su_cs_dict_view *self){
 242    ASSERT(self);
 243    ASSERT_RET(su_cs_dict_view_is_valid(self), self);
 244    return su__cs_dict_view_move(self, su__CS_DICT_VIEW_MOVE_NEXT);
 245 }
 246 EXPORT boole su_cs_dict_view_find(struct su_cs_dict_view *self,
 247       char const *key);
 248 INLINE s32 su_cs_dict_view_reset_insert(struct su_cs_dict_view *self,
 249       char const *key, void *value){
 250    ASSERT(self);
 251    ASSERT_RET(key != NIL, 0);
 252    return su__cs_dict_insrep(self->csdv_parent, key, value, FAL0 | R(up,self));
 253 }
 254 INLINE s32 su_cs_dict_view_reset_replace(struct su_cs_dict_view *self,
 255       char const *key, void *value){
 256    ASSERT(self);
 257    ASSERT_RET(key != NIL, 0);
 258    return su__cs_dict_insrep(self->csdv_parent, key, value, TRU1 | R(up,self));
 259 }
 260 EXPORT struct su_cs_dict_view *su_cs_dict_view_remove(
 261       struct su_cs_dict_view *self);
 262 INLINE sz su_cs_dict_view_cmp(struct su_cs_dict_view const *self,
 263       struct su_cs_dict_view const *t){
 264    ASSERT_RET(self, -(t != NIL));
 265    ASSERT_RET(t, 1);
 266    return (self->csdv_node == t->csdv_node);
 267 }
 268 C_DECL_END
 269 #include <su/code-ou.h>
 270 #if !su_C_LANG || defined CXX_DOXYGEN
 271 # include <su/view.h>
 272 # define su_CXX_HEADER
 273 # include <su/code-in.h>
 274 NSPC_BEGIN(su)
 275 template<class T,boole OWNS> class cs_dict;
 276 template<class T, boole OWNS=type_traits<T>::ownguess>
 277 class cs_dict : private su_cs_dict{
 278    class gview;
 279    class gview : private su_cs_dict_view{
 280    public:
 281       // xxx clang 5.0.1 BUG: needed this-> to find superclass field
 282       gview(void) {this->csdv_parent = NIL; this->csdv_node = NIL;}
 283       gview(gview const &t) {*this = t;}
 284       ~gview(void) {}
 285       gview &operator=(gview const &t){
 286          SELFTHIS_RET(*S(su_cs_dict_view*,this) =
 287                *S(su_cs_dict_view const*,&t));
 288       }
 289       gview &setup(su_cs_dict &parent){
 290          SELFTHIS_RET(su_cs_dict_view_setup(this, &parent));
 291       }
 292       boole is_setup(void) const {return su_cs_dict_view_parent(this) != NIL;}
 293       boole is_same_parent(gview const &t) const{
 294          return su_cs_dict_view_parent(this) == su_cs_dict_view_parent(&t);
 295       }
 296       boole is_valid(void) const {return su_cs_dict_view_is_valid(this);}
 297       gview &reset(void){
 298          SELFTHIS_RET(su_cs_dict_view_reset(this));
 299       }
 300       char const *key(void) const {return su_cs_dict_view_key(this);}
 301       void *data(void) {return su_cs_dict_view_data(this);}
 302       void const *data(void) const {return su_cs_dict_view_data(this);}
 303       s32 set_data(void *value) {return su_cs_dict_view_set_data(this, value);}
 304       gview &begin(void) {SELFTHIS_RET(su_cs_dict_view_begin(this));}
 305       boole has_next(void) const {return su_cs_dict_view_has_next(this);}
 306       gview &next(void) {SELFTHIS_RET(su_cs_dict_view_next(this));}
 307       boole find(void const *key){
 308          return su_cs_dict_view_find(this, S(char const*,key));
 309       }
 310       s32 reset_insert(void const *key, void *value){
 311          return su_cs_dict_view_reset_insert(this, S(char const*,key), value);
 312       }
 313       s32 reset_replace(void const *key, void *value){
 314          return su_cs_dict_view_reset_replace(this, S(char const*,key), value);
 315       }
 316       gview &remove(void) {SELFTHIS_RET(su_cs_dict_view_remove(this));}
 317       sz cmp(gview const &t) const {return su_cs_dict_view_cmp(this, &t);}
 318    };
 319 public:
 320    enum flags{
 321       f_none,
 322       f_pow2_spaced = su_CS_DICT_POW2_SPACED,
 323       f_case = su_CS_DICT_CASE,
 324       f_head_resort = su_CS_DICT_HEAD_RESORT,
 325       f_auto_shrink = su_CS_DICT_AUTO_SHRINK,
 326       f_frozen = su_CS_DICT_FROZEN,
 327       f_err_pass = su_CS_DICT_ERR_PASS,
 328       f_nil_is_valid_object = su_CS_DICT_NIL_IS_VALID_OBJECT,
 329       f_nilisvalo = su_CS_DICT_NILISVALO
 330    };
 331    typedef NSPC(su)type_traits<T> type_traits;
 332    typedef typename type_traits::type_toolbox type_toolbox;
 333    typedef typename type_traits::auto_type_toolbox auto_type_toolbox;
 334    typedef typename type_traits::tp tp;
 335    typedef typename type_traits::tp_const tp_const;
 336    typedef NSPC(su)view_traits<su_cs_dict,char const *,T>
 337       view_traits;
 338    friend class NSPC(su)view_assoc_unidir<view_traits, gview>;
 339    friend class NSPC(su)view_assoc_unidir_const<view_traits, gview>;
 340    typedef NSPC(su)view_assoc_unidir<view_traits, gview> view;
 341    typedef NSPC(su)view_assoc_unidir_const<view_traits, gview> view_const;
 342    cs_dict(type_toolbox const *ttbox=NIL, u16 flags=f_none){
 343       ASSERT(!OWNS || (ttbox != NIL && ttbox->ttb_clone != NIL &&
 344          ttbox->ttb_delete != NIL && ttbox->ttb_assign != NIL));
 345       flags &= su__CS_DICT_CREATE_MASK & ~su_CS_DICT_OWNS;
 346       if(OWNS)
 347          flags |= su_CS_DICT_OWNS;
 348       su_cs_dict_create(this, flags, R(su_toolbox const*,ttbox));
 349    }
 350    SHADOW cs_dict(cs_dict const &t) {su_cs_dict_create_copy(this, &t);}
 351    ~cs_dict(void) {su_cs_dict_gut(this);}
 352    s32 assign(cs_dict const &t) {return su_cs_dict_assign(this, &t);}
 353    SHADOW cs_dict &operator=(cs_dict const &t) {SELFTHIS_RET(assign(t));}
 354    s32 assign_elems(cs_dict const &t){
 355       return su_cs_dict_assign_elems(this, &t);
 356    }
 357    cs_dict &clear(void) {SELFTHIS_RET(su_cs_dict_clear(this));}
 358    cs_dict &clear_elems(void) {SELFTHIS_RET(su_cs_dict_clear_elems(this));}
 359    cs_dict &swap(cs_dict &t) {SELFTHIS_RET(su_cs_dict_swap(this, &t));}
 360    u16 flags(void) const {return (su_cs_dict_flags(this) & ~su_CS_DICT_OWNS);}
 361    cs_dict &add_flags(u16 flags){
 362       SELFTHIS_RET(su_cs_dict_add_flags(this, flags & ~su_CS_DICT_OWNS));
 363    }
 364    cs_dict &clear_flags(u16 flags){
 365       SELFTHIS_RET(su_cs_dict_clear_flags(this, flags & ~su_CS_DICT_OWNS));
 366    }
 367    u8 treshold_shift(void) const {return su_cs_dict_treshold_shift(this);}
 368    cs_dict &set_treshold_shift(u8 tshift){
 369       SELFTHIS_RET(su_cs_dict_set_treshold_shift(this, tshift));
 370    }
 371    type_toolbox const *toolbox(void) const{
 372       return R(type_toolbox const*,su_cs_dict_toolbox(this));
 373    }
 374    cs_dict &set_toolbox(type_toolbox const *tbox_or_nil){
 375       SELFTHIS_RET(su_cs_dict_set_toolbox(this,
 376          R(su_toolbox const*,tbox_or_nil)));
 377    }
 378    u32 count(void) const {return csd_count;}
 379    boole is_empty(void) const {return (count() == 0);}
 380    cs_dict &balance(void) {SELFTHIS_RET(su_cs_dict_balance(this));}
 381    boole has_key(char const *key) const{
 382       ASSERT_RET(key != NIL, FAL0);
 383       return su_cs_dict_has_key(this, key);
 384    }
 385    tp lookup(char const *key){
 386       ASSERT_RET(key != NIL, NIL);
 387       return type_traits::to_tp(su_cs_dict_lookup(this, key));
 388    }
 389    tp operator[](char const *key) {return lookup(key);}
 390    tp_const lookup(char const *key) const{
 391       ASSERT_RET(key != NIL, NIL);
 392       return type_traits::to_const_tp(su_cs_dict_lookup(C(su_cs_dict*,this),
 393          key));
 394    }
 395    tp_const operator[](char const *key) const {return lookup(key);}
 396    s32 insert(char const *key, tp_const value){
 397       ASSERT_RET(key != NIL, 0);
 398       return su_cs_dict_insert(this, key, type_traits::to_vp(value));
 399    }
 400    s32 replace(char const *key, tp_const value){
 401       ASSERT_RET(key != NIL, 0);
 402       return su_cs_dict_replace(this, key, type_traits::to_vp(value));
 403    }
 404    boole remove(char const *key){
 405       ASSERT_RET(key != NIL, FAL0);
 406       return su_cs_dict_remove(this, key);
 407    }
 408    void statistics(void) const {su_cs_dict_statistics(this);}
 409 };
 410 NSPC_END(su)
 411 # include <su/code-ou.h>
 412 #endif /* !C_LANG || CXX_DOXYGEN */
 413 #endif /* su_CS_DICT_H */
 414 /* s-it-mode */