1/*
2Copyright (c) 2012, Broadcom Europe Ltd
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are met:
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9 * Redistributions in binary form must reproduce the above copyright
10 notice, this list of conditions and the following disclaimer in the
11 documentation and/or other materials provided with the distribution.
12 * Neither the name of the copyright holder nor the
13 names of its contributors may be used to endorse or promote products
14 derived from this software without specific prior written permission.
15
16THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
20DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26*/
27
28#include <stdlib.h>
29#include <string.h>
30
31#include "containers/containers.h"
32#include "containers/core/containers_index.h"
33
34typedef struct {
35 int64_t file_offset;
36 int64_t time;
37} VC_CONTAINER_INDEX_POS_T;
38
39struct VC_CONTAINER_INDEX_T {
40 int len; // log2 of length of entry array
41 int next; // next array entry to write into
42 int gap; // log2 of the passes through entry array to build the full list
43 int mgap; // len-gap, stored for convenience
44 int count; // number of calls to index_add since last entry added
45 int max_count; // log2 of the number of calls to discard between each entry added
46 int64_t max_time; // time of the latest entry
47 VC_CONTAINER_INDEX_POS_T entry[0]; // array of position/time pairs
48};
49
50// We have a fixed length list, and when it is full we want to discard half the entries.
51// This is done without coping data by mapping the entry number to the index to the array,
52// in the following way:
53// Length is a power of two, so the entry number is a fixed constant bit width. The highest gap
54// bits are used as a direct offset into the array (o), the lowest mgap bits are right shifted by
55// gap to increment this (S). Each time we double the number of passes through the actual array.
56// So if len=3, we start off with mgap=3, gap=0, we have a single pass with the trivial mapping:
57// |S|S|S| [0 1 2 3 4 5 6 7]
58// when this is full we change to mgap=2, gap=1, so we iterate this way:
59// |o|S|S| [0 2 4 6] [1 3 5 7]
60// when this is full we change to mgap=1, gap=2
61// |o|o|S| [0 4] [1 5] [2 6] [3 7]
62// when this is full we change to this, which is equivalent to where we started
63// |o|o|o| [0] [1] [2] [3] [4] [5] [6] [7]
64
65#define ENTRY(x, i) ((x)->gap == 0 ? (i) : ((i)>>(x)->mgap) + (((i) & ((1<<(x)->mgap)-1)) << (x)->gap))
66
67VC_CONTAINER_STATUS_T vc_container_index_create( VC_CONTAINER_INDEX_T **index, int length )
68{
69 VC_CONTAINER_STATUS_T status = VC_CONTAINER_ERROR_OUT_OF_MEMORY;
70 VC_CONTAINER_INDEX_T *id = NULL;
71 int len = 0;
72
73 if(length < 16) length = 16;
74 if(length > 4096) length = 4096;
75 while((length >>= 1) != 0)
76 len++;
77
78 id = malloc(sizeof(VC_CONTAINER_INDEX_T) + (sizeof(VC_CONTAINER_INDEX_POS_T)<<len));
79 if(id == NULL) { goto error; }
80
81 memset(id, 0, sizeof(VC_CONTAINER_INDEX_T));
82
83 id->len = id->mgap = len;
84
85 *index = id;
86 return VC_CONTAINER_SUCCESS;
87
88 error:
89 return status;
90}
91
92VC_CONTAINER_STATUS_T vc_container_index_free( VC_CONTAINER_INDEX_T *index )
93{
94 if(index == NULL)
95 return VC_CONTAINER_ERROR_FAILED;
96
97 free(index);
98 return VC_CONTAINER_SUCCESS;
99}
100
101VC_CONTAINER_STATUS_T vc_container_index_add( VC_CONTAINER_INDEX_T *index, int64_t time, int64_t file_offset )
102{
103 if(index == NULL)
104 return VC_CONTAINER_ERROR_FAILED;
105
106 // reject entries if they are in part of the time covered
107 if(index->next != 0 && time <= index->max_time)
108 return VC_CONTAINER_SUCCESS;
109
110 index->count++;
111 if(index->count == (1<<index->max_count))
112 {
113 int entry;
114 if(index->next == (1<<index->len))
115 {
116 // New entry doesn't fit, we discard every other index record
117 // by changing how we map index positions to array entry indexes.
118 index->next >>= 1;
119 index->gap++;
120 index->mgap--;
121 index->max_count++;
122
123 if(index->gap == index->len)
124 {
125 index->gap = 0;
126 index->mgap = index->len;
127 }
128 }
129
130 entry = ENTRY(index, index->next);
131
132 index->entry[entry].file_offset = file_offset;
133 index->entry[entry].time = time;
134 index->count = 0;
135 index->next++;
136 index->max_time = time;
137 }
138
139 return VC_CONTAINER_SUCCESS;
140}
141
142VC_CONTAINER_STATUS_T vc_container_index_get( VC_CONTAINER_INDEX_T *index, int later, int64_t *time, int64_t *file_offset, int *past )
143{
144 int guess, start, end, entry;
145
146 if(index == NULL || index->next == 0)
147 return VC_CONTAINER_ERROR_FAILED;
148
149 guess = start = 0;
150 end = index->next-1;
151
152 *past = *time > index->max_time;
153
154 while(end-start > 1)
155 {
156 int64_t gtime;
157 guess = (start+end)>>1;
158 gtime = index->entry[ENTRY(index, guess)].time;
159
160 if(*time < gtime)
161 end = guess;
162 else if(*time > gtime)
163 start = guess;
164 else
165 break;
166 }
167
168 if (*time != index->entry[ENTRY(index, guess)].time)
169 {
170 if(later)
171 {
172 if(*time <= index->entry[ENTRY(index, start)].time)
173 guess = start;
174 else
175 guess = end;
176 }
177 else
178 {
179 if(*time >= index->entry[ENTRY(index, end)].time)
180 guess = end;
181 else
182 guess = start;
183 }
184 }
185
186 entry = ENTRY(index, guess);
187 *time = index->entry[entry].time;
188 *file_offset = index->entry[entry].file_offset;
189
190 return VC_CONTAINER_SUCCESS;
191}
192
193