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