common/list.c

   1 /*****************************************************************************
   2  * list.c
   3  *****************************************************************************
   4  * Copyright (C) 2010-2017 L-SMASH project
   5  *
   6  * Authors: Yusuke Nakamura <muken.the.vfrmaniac@gmail.com>
   7  *
   8  * Permission to use, copy, modify, and/or distribute this software for any
   9  * purpose with or without fee is hereby granted, provided that the above
  10  * copyright notice and this permission notice appear in all copies.
  11  *
  12  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  13  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  14  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  15  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  16  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  17  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  18  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  19  *****************************************************************************/
  20
  21 /* This file is available under an ISC license. */
  22
  23 #include "internal.h" /* must be placed first */
  24
  25 #include <string.h>
  26
  27 static void lsmash_list_clear
  28 (
  29     lsmash_entry_list_t *list
  30 )
  31 {
  32     list->head                 = NULL;
  33     list->tail                 = NULL;
  34     list->last_accessed_entry  = NULL;
  35     list->last_accessed_number = 0;
  36     list->entry_count          = 0;
  37     list->eliminator           = NULL;
  38 }
  39
  40 void lsmash_list_init_orig
  41 (
  42     lsmash_entry_list_t         *list,
  43     lsmash_entry_data_eliminator eliminator
  44 )
  45 {
  46     assert( eliminator != NULL );
  47     list->head                 = NULL;
  48     list->tail                 = NULL;
  49     list->last_accessed_entry  = NULL;
  50     list->last_accessed_number = 0;
  51     list->entry_count          = 0;
  52     list->eliminator           = eliminator;
  53 }
  54
  55 lsmash_entry_list_t *lsmash_list_create_orig
  56 (
  57     lsmash_entry_data_eliminator eliminator
  58 )
  59 {
  60     lsmash_entry_list_t *list = lsmash_malloc( sizeof(lsmash_entry_list_t) );
  61     if( !list )
  62         return NULL;
  63     lsmash_list_init( list, eliminator );
  64     return list;
  65 }
  66
  67 void lsmash_list_destroy
  68 (
  69     lsmash_entry_list_t *list
  70 )
  71 {
  72     lsmash_list_remove_entries( list );
  73     lsmash_free( list );
  74 }
  75
  76 int lsmash_list_add_entry
  77 (
  78     lsmash_entry_list_t *list,
  79     void                *data
  80 )
  81 {
  82     if( !list )
  83         return LSMASH_ERR_FUNCTION_PARAM;
  84     lsmash_entry_t *entry = lsmash_malloc( sizeof(lsmash_entry_t) );
  85     if( !entry )
  86         return LSMASH_ERR_MEMORY_ALLOC;
  87     entry->next = NULL;
  88     entry->prev = list->tail;
  89     entry->data = data;
  90     if( list->head )
  91         list->tail->next = entry;
  92     else
  93         list->head = entry;
  94     list->tail = entry;
  95     list->entry_count += 1;
  96     return 0;
  97 }
  98
  99 int lsmash_list_remove_entry_direct
 100 (
 101     lsmash_entry_list_t *list,
 102     lsmash_entry_t      *entry
 103 )
 104 {
 105     if( !list || !entry )
 106         return LSMASH_ERR_FUNCTION_PARAM;
 107     assert( !entry->data || list->eliminator );
 108     lsmash_entry_t *next = entry->next;
 109     lsmash_entry_t *prev = entry->prev;
 110     if( entry == list->head )
 111         list->head = next;
 112     else
 113         prev->next = next;
 114     if( entry == list->tail )
 115         list->tail = prev;
 116     else
 117         next->prev = prev;
 118     if( entry->data )
 119         list->eliminator( entry->data );
 120     if( entry == list->last_accessed_entry )
 121     {
 122         if( next )
 123             list->last_accessed_entry = next;
 124         else if( prev )
 125         {
 126             list->last_accessed_entry   = prev;
 127             list->last_accessed_number -= 1;
 128         }
 129         else
 130         {
 131             list->last_accessed_entry  = NULL;
 132             list->last_accessed_number = 0;
 133         }
 134     }
 135     else
 136     {
 137         /* We can't know the current entry number immediately,
 138          * so discard the last accessed entry info because time is wasted to know it. */
 139         list->last_accessed_entry  = NULL;
 140         list->last_accessed_number = 0;
 141     }
 142     lsmash_free( entry );
 143     list->entry_count -= 1;
 144     return 0;
 145 }
 146
 147 int lsmash_list_remove_entry
 148 (
 149     lsmash_entry_list_t *list,
 150     uint32_t             entry_number
 151 )
 152 {
 153     lsmash_entry_t *entry = lsmash_list_get_entry( list, entry_number );
 154     return lsmash_list_remove_entry_direct( list, entry );
 155 }
 156
 157 int lsmash_list_remove_entry_tail
 158 (
 159     lsmash_entry_list_t *list
 160 )
 161 {
 162     return lsmash_list_remove_entry_direct( list, list->tail );
 163 }
 164
 165 void lsmash_list_remove_entries
 166 (
 167     lsmash_entry_list_t *list
 168 )
 169 {
 170     if( !list )
 171         return;
 172     /* Note that it's valid that list contain no entries or no data to be eliminated. */
 173     for( lsmash_entry_t *entry = list->head; entry; )
 174     {
 175         lsmash_entry_t *next = entry->next;
 176         if( entry->data )
 177             list->eliminator( entry->data );
 178         lsmash_free( entry );
 179         entry = next;
 180     }
 181     lsmash_entry_data_eliminator eliminator = list->eliminator;
 182     lsmash_list_clear( list );
 183     list->eliminator = eliminator;
 184 }
 185
 186 void lsmash_list_move_entries
 187 (
 188     lsmash_entry_list_t *dst,
 189     lsmash_entry_list_t *src
 190 )
 191 {
 192     *dst = *src;
 193     lsmash_entry_data_eliminator eliminator = src->eliminator;
 194     lsmash_list_clear( src );
 195     src->eliminator = eliminator;
 196 }
 197
 198 lsmash_entry_t *lsmash_list_get_entry
 199 (
 200     lsmash_entry_list_t *list,
 201     uint32_t             entry_number
 202 )
 203 {
 204     if( !list || !entry_number || entry_number > list->entry_count )
 205         return NULL;
 206     int shortcut = 1;
 207     lsmash_entry_t *entry = NULL;
 208     if( list->last_accessed_entry )
 209     {
 210         if( entry_number == list->last_accessed_number )
 211             entry = list->last_accessed_entry;
 212         else if( entry_number == list->last_accessed_number + 1 )
 213             entry = list->last_accessed_entry->next;
 214         else if( entry_number == list->last_accessed_number - 1 )
 215             entry = list->last_accessed_entry->prev;
 216         else
 217             shortcut = 0;
 218     }
 219     else
 220         shortcut = 0;
 221     if( !shortcut )
 222     {
 223         if( entry_number <= (list->entry_count >> 1) )
 224         {
 225             /* Look for from the head. */
 226             uint32_t distance_plus_one = entry_number;
 227             for( entry = list->head; entry && --distance_plus_one; entry = entry->next );
 228         }
 229         else
 230         {
 231             /* Look for from the tail. */
 232             uint32_t distance = list->entry_count - entry_number;
 233             for( entry = list->tail; entry && distance--; entry = entry->prev );
 234         }
 235     }
 236     if( entry )
 237     {
 238         list->last_accessed_entry  = entry;
 239         list->last_accessed_number = entry_number;
 240     }
 241     return entry;
 242 }
 243
 244 void *lsmash_list_get_entry_data
 245 (
 246     lsmash_entry_list_t *list,
 247     uint32_t             entry_number
 248 )
 249 {
 250     lsmash_entry_t *entry = lsmash_list_get_entry( list, entry_number );
 251     return entry ? entry->data : NULL;
 252 }