id_server/framework/linked_map.h at master · adan830/id_server · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

/*
 * linked_map.h
 *
 *      Author: lixingyi (lxyfirst@163.com)
 */

#ifndef LINKED_MAP_H
#define LINKED_MAP_H

#include <map>
#include <tr1/unordered_map>

namespace framework
{

template <typename K , typename V>
class LinkedMap
{
public:
    typedef K key_type ;
    typedef V value_type ;

    class node_type
    {
    friend class LinkedMap ;
    public:
        value_type& value() { return m_value ;} ;
    private:
        node_type* m_prev ;
        node_type* m_next ;
        value_type m_value ;
    } ;

    //typedef std::map<key_type,node_type > node_container ;
    typedef std::tr1::unordered_map<key_type,node_type > node_container ;
    typedef typename node_container::iterator iterator ;
    typedef typename node_container::const_iterator const_iterator ;

public:
    LinkedMap()
    {
        m_head.m_next = m_head.m_prev = &m_head ;
    };

    iterator get_node(const key_type& key,bool touch=false)
    {
        iterator it = m_container.find(key) ;
        if(it != m_container.end() && touch )
        {
            list_node_remove(&it->second) ;
            list_node_insert(&m_head,&it->second,m_head.m_next) ;
        }

        return it ;
    }

    void erase_node(iterator it)
    {
        node_type& node = it->second ;
        list_node_remove(&node) ;
        m_container.erase(it) ;
    }


    iterator begin() { return m_container.begin() ; } ;
    const_iterator begin() const { return m_container.begin() ; } ;

    int  size() const { return m_container.size(); } ;

    iterator end() { return m_container.end() ; } ;
    const_iterator end() const { return m_container.end() ; } ;

    value_type* get(const key_type& key,bool touch=false)
    {
        iterator it = get_node(key,touch) ;
        if(it!= m_container.end() ) return &it->second.m_value ;
        return NULL ;
    }

    value_type* insert(const key_type& key)
    {
        iterator it = m_container.find(key);
        if(it == m_container.end())
        {
            node_type& node = m_container[key] ;
            list_node_insert(&m_head,&node,m_head.m_next) ;
            return &node.m_value ;
        }

        return NULL ;
    }

    value_type* insert(const key_type& key,const value_type& value)
    {
        value_type* obj = insert(key) ;
        if(obj) *obj = value ;
        return obj ;
    }

    void erase(const key_type& key)
    {
        iterator it = m_container.find(key) ;
        if(it != m_container.end() ) erase_node(it);

    }

    void clear()
    {
        m_head.m_next = m_head.m_prev = &m_head ;
        m_container.clear() ;
    }

    value_type* tail()
    {
        if(&m_head == m_head.m_prev) return NULL ;
        return &m_head.m_prev->m_value ;
    }

    value_type* head()
    {
        if(&m_head == m_head.m_next) return NULL ;
        return &m_head.m_next->m_value ;
    }

private:
    void list_node_insert(node_type* prev,node_type* curr,node_type* next)
    {
        prev->m_next = curr ;

        curr->m_prev = prev ;
        curr->m_next = next ;

        next->m_prev = curr ;
    }

    void list_node_remove(node_type* node)
    {
        node->m_prev->m_next = node->m_next ;
        node->m_next->m_prev = node->m_prev ;

        node->m_next = node->m_prev = NULL ;
    }

private:
    node_container m_container ;
    node_type m_head ;

} ;

}

#endif