common/list.c

   1 /*****************************************************************************
   2  * list.c
   3  *****************************************************************************
   4  * Copyright (C) 2010-2014 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 void lsmash_init_entry_list( lsmash_entry_list_t *list )
  28 {
  29     list->head                 = NULL;
  30     list->tail                 = NULL;
  31     list->last_accessed_entry  = NULL;
  32     list->last_accessed_number = 0;
  33     list->entry_count          = 0;
  34 }
  35
  36 lsmash_entry_list_t *lsmash_create_entry_list( void )
  37 {
  38     lsmash_entry_list_t *list = lsmash_malloc( sizeof(lsmash_entry_list_t) );
  39     if( !list )
  40         return NULL;
  41     lsmash_init_entry_list( list );
  42     return list;
  43 }
  44
  45 int lsmash_add_entry( lsmash_entry_list_t *list, void *data )
  46 {
  47     if( !list )
  48         return LSMASH_ERR_FUNCTION_PARAM;
  49     lsmash_entry_t *entry = lsmash_malloc( sizeof(lsmash_entry_t) );
  50     if( !entry )
  51         return LSMASH_ERR_MEMORY_ALLOC;
  52     entry->next = NULL;
  53     entry->prev = list->tail;
  54     entry->data = data;
  55     if( list->head )
  56         list->tail->next = entry;
  57     else
  58         list->head = entry;
  59     list->tail = entry;
  60     list->entry_count += 1;
  61     return 0;
  62 }
  63
  64 int lsmash_remove_entry_direct_orig( lsmash_entry_list_t *list, lsmash_entry_t *entry, lsmash_entry_data_eliminator eliminator )
  65 {
  66     if( !list || !entry )
  67         return LSMASH_ERR_FUNCTION_PARAM;
  68     if( !eliminator )
  69         eliminator = lsmash_free;
  70     lsmash_entry_t *next = entry->next;
  71     lsmash_entry_t *prev = entry->prev;
  72     if( entry == list->head )
  73         list->head = next;
  74     else
  75         prev->next = next;
  76     if( entry == list->tail )
  77         list->tail = prev;
  78     else
  79         next->prev = prev;
  80     if( entry->data )
  81         eliminator( entry->data );
  82     if( entry == list->last_accessed_entry )
  83     {
  84         if( next )
  85             list->last_accessed_entry = next;
  86         else if( prev )
  87         {
  88             list->last_accessed_entry   = prev;
  89             list->last_accessed_number -= 1;
  90         }
  91         else
  92         {
  93             list->last_accessed_entry  = NULL;
  94             list->last_accessed_number = 0;
  95         }
  96     }
  97     else
  98     {
  99         /* We can't know the current entry number immediately,
 100          * so discard the last accessed entry info because time is wasted to know it. */
 101         list->last_accessed_entry  = NULL;
 102         list->last_accessed_number = 0;
 103     }
 104     lsmash_free( entry );
 105     list->entry_count -= 1;
 106     return 0;
 107 }
 108
 109 int lsmash_remove_entry_orig( lsmash_entry_list_t *list, uint32_t entry_number, lsmash_entry_data_eliminator eliminator )
 110 {
 111     lsmash_entry_t *entry = lsmash_get_entry( list, entry_number );
 112     return lsmash_remove_entry_direct( list, entry, eliminator );
 113 }
 114
 115 int lsmash_remove_entry_tail_orig( lsmash_entry_list_t *list, lsmash_entry_data_eliminator eliminator )
 116 {
 117     return lsmash_remove_entry_direct( list, list->tail, eliminator );
 118 }
 119
 120 void lsmash_remove_entries_orig( lsmash_entry_list_t *list, lsmash_entry_data_eliminator eliminator )
 121 {
 122     if( !list )
 123         return;
 124     if( !eliminator )
 125         eliminator = lsmash_free;
 126     for( lsmash_entry_t *entry = list->head; entry; )
 127     {
 128         lsmash_entry_t *next = entry->next;
 129         if( entry->data )
 130             eliminator( entry->data );
 131         lsmash_free( entry );
 132         entry = next;
 133     }
 134     lsmash_init_entry_list( list );
 135 }
 136
 137 void lsmash_remove_list_orig( lsmash_entry_list_t *list, lsmash_entry_data_eliminator eliminator )
 138 {
 139     if( !list )
 140         return;
 141     lsmash_remove_entries( list, eliminator );
 142     lsmash_free( list );
 143 }
 144
 145 lsmash_entry_t *lsmash_get_entry( lsmash_entry_list_t *list, uint32_t entry_number )
 146 {
 147     if( !list || !entry_number || entry_number > list->entry_count )
 148         return NULL;
 149     int shortcut = 1;
 150     lsmash_entry_t *entry = NULL;
 151     if( list->last_accessed_entry )
 152     {
 153         if( entry_number == list->last_accessed_number )
 154             entry = list->last_accessed_entry;
 155         else if( entry_number == list->last_accessed_number + 1 )
 156             entry = list->last_accessed_entry->next;
 157         else if( entry_number == list->last_accessed_number - 1 )
 158             entry = list->last_accessed_entry->prev;
 159         else
 160             shortcut = 0;
 161     }
 162     else
 163         shortcut = 0;
 164     if( !shortcut )
 165     {
 166         if( entry_number <= (list->entry_count >> 1) )
 167         {
 168             /* Look for from the head. */
 169             uint32_t distance_plus_one = entry_number;
 170             for( entry = list->head; entry && --distance_plus_one; entry = entry->next );
 171         }
 172         else
 173         {
 174             /* Look for from the tail. */
 175             uint32_t distance = list->entry_count - entry_number;
 176             for( entry = list->tail; entry && distance--; entry = entry->prev );
 177         }
 178     }
 179     if( entry )
 180     {
 181         list->last_accessed_entry  = entry;
 182         list->last_accessed_number = entry_number;
 183     }
 184     return entry;
 185 }
 186
 187 void *lsmash_get_entry_data( lsmash_entry_list_t *list, uint32_t entry_number )
 188 {
 189     lsmash_entry_t *entry = lsmash_get_entry( list, entry_number );
 190     return entry ? entry->data : NULL;
 191 }