1/*
2 *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#include "map_no_stl.h"
12
13#include "critical_section_wrapper.h"
14#include "trace.h"
15
16namespace webrtc {
17MapNoStlItem::MapNoStlItem(int id, void* item)
18    : next_(0),
19      prev_(0),
20      item_id_(id),
21      item_ptr_(item)
22{
23}
24
25MapNoStlItem::~MapNoStlItem()
26{
27}
28
29void* MapNoStlItem::GetItem()
30{
31    return item_ptr_;
32}
33
34int MapNoStlItem::GetId()
35{
36    return item_id_;
37}
38
39unsigned int MapNoStlItem::GetUnsignedId()
40{
41    return static_cast<unsigned int>(item_id_);
42}
43
44void MapNoStlItem::SetItem(void* ptr)
45{
46    item_ptr_ = ptr;
47}
48
49MapNoStl::MapNoStl()
50    : critical_section_(CriticalSectionWrapper::CreateCriticalSection()),
51      first_(0),
52      last_(0),
53      size_(0)
54{
55}
56
57MapNoStl::~MapNoStl()
58{
59    if (First())
60    {
61        WEBRTC_TRACE(kTraceMemory, kTraceUtility, -1,
62                   "Potential memory leak in MapNoStl");
63        while (Erase(First()) == 0)
64        {}
65    }
66    delete critical_section_;
67}
68
69int MapNoStl::Size() const
70{
71    return size_;
72}
73
74int MapNoStl::Insert(int id, void* ptr)
75{
76    MapNoStlItem* new_item = new MapNoStlItem(id, ptr);
77
78    CriticalSectionScoped lock(critical_section_);
79    MapNoStlItem* item = first_;
80    size_++;
81    if (!item)
82    {
83        first_ = new_item;
84        last_ = new_item;
85        return 0;
86    }
87    while(item->next_)
88    {
89        // Three scenarios
90        // 1. Item should be inserted first.
91        // 2. Item should be inserted between two items
92        // 3. Item should be inserted last
93        if (item->GetId() > id)
94        {
95            new_item->next_ = item;
96            item->prev_ = new_item;
97            if (item == first_)
98            {
99                first_ = new_item;
100            }
101            else
102            {
103                new_item->prev_ = item->prev_;
104                new_item->prev_->next_ = new_item;
105            }
106            return 0;
107        }
108        item = item->next_;
109    }
110    // 3
111    item->next_ = new_item;
112    new_item->prev_ = item;
113    last_ = new_item;
114    return 0;
115}
116
117MapNoStlItem* MapNoStl::First() const
118{
119    return first_;
120}
121
122MapNoStlItem* MapNoStl::Last() const
123{
124    return last_;
125}
126
127MapNoStlItem* MapNoStl::Next(MapNoStlItem* item) const
128{
129    if (!item)
130    {
131        return 0;
132    }
133    return item->next_;
134}
135
136MapNoStlItem* MapNoStl::Previous(MapNoStlItem* item) const
137{
138    if (!item)
139    {
140        return 0;
141    }
142    return item->prev_;
143}
144
145MapNoStlItem* MapNoStl::Find(int id) const
146{
147    CriticalSectionScoped lock(critical_section_);
148    MapNoStlItem* item = Locate(id);
149    return item;
150}
151
152int MapNoStl::Erase(MapNoStlItem* item)
153{
154    if(!item)
155    {
156        return -1;
157    }
158    CriticalSectionScoped lock(critical_section_);
159    return Remove(item);
160}
161
162int MapNoStl::Erase(const int id)
163{
164    CriticalSectionScoped lock(critical_section_);
165    MapNoStlItem* item = Locate(id);
166    if(!item)
167    {
168        return -1;
169    }
170    return Remove(item);
171}
172
173MapNoStlItem* MapNoStl::Locate(int id) const
174{
175    MapNoStlItem* item = first_;
176    while(item)
177    {
178        if (item->GetId() == id)
179        {
180            return item;
181        }
182        item = item->next_;
183    }
184    return 0;
185}
186
187int MapNoStl::Remove(MapNoStlItem* item)
188{
189    if (!item)
190    {
191        return -1;
192    }
193    size_--;
194    MapNoStlItem* previous_item = item->prev_;
195    MapNoStlItem* next_item = item->next_;
196    if (!previous_item)
197    {
198        next_item->prev_ = 0;
199        first_ = next_item;
200    }
201    else
202    {
203        previous_item->next_ = next_item;
204    }
205    if (!next_item)
206    {
207        previous_item->next_ = 0;
208        last_ = previous_item;
209    }
210    else
211    {
212        next_item->prev_ = previous_item;
213    }
214    delete item;
215    return 0;
216}
217} // namespace webrtc
218