mirror of https://code.videolan.org/videolan/vlc
237 lines
8.1 KiB
C
237 lines
8.1 KiB
C
/******************************************************************************
|
|
* vlc_diffutil.h
|
|
******************************************************************************
|
|
* Copyright (C) 2022 VLC authors and VideoLAN
|
|
*
|
|
* This program is free software; you can redistribute it and/or modify it
|
|
* under the terms of the GNU Lesser General Public License as published by
|
|
* the Free Software Foundation; either version 2.1 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* This program is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU Lesser General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU Lesser General Public License
|
|
* along with this program; if not, write to the Free Software Foundation,
|
|
* Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
|
|
*****************************************************************************/
|
|
#ifndef VLC_DIFFUTIL_H
|
|
#define VLC_DIFFUTIL_H
|
|
|
|
#include <vlc_common.h>
|
|
#include <vlc_vector.h>
|
|
|
|
/**
|
|
* this structure defines callback to access and compare elements from
|
|
* the old and the new list
|
|
*/
|
|
typedef struct {
|
|
/// return the size of the old list @a list
|
|
uint32_t (*getOldSize)(const void* list);
|
|
/// return the size of the new list @a list
|
|
uint32_t (*getNewSize)(const void* list);
|
|
/// compare 2 elements
|
|
bool (*isSame)(const void* listOld, uint32_t oldIndex, const void* listNew, uint32_t newIndex);
|
|
} vlc_diffutil_callback_t;
|
|
|
|
typedef struct {
|
|
/**
|
|
* notify that the item from @a listNew at position @a posNew is inserted in list @a listOld at position @a posOld
|
|
*
|
|
* @param opaque user data from function vlc_diffutil_walk_snake
|
|
* @param listOld pointer to the old model
|
|
* @param posOld position of the element inserted in the old model (before removal)
|
|
* @param listNew pointer to the new model
|
|
* @param posNew position of the element inserted in the new model
|
|
*/
|
|
void (*insert)(void* opaque, const void* listOld, uint32_t posOld, const void* listNew, uint32_t posNew);
|
|
/**
|
|
* notify that the item from @a listOld at position @a posOld is removed
|
|
* @param opaque user data from function vlc_diffutil_walk_snake
|
|
* @param listOld pointer to the old model
|
|
* @param posOld position of the element removed in the old model
|
|
* @param listNew pointer to the new model
|
|
* @param posNew position of the element removed in the new model (before removal)
|
|
*/
|
|
void (*remove)(void* opaque, const void* listOld, uint32_t posOld, const void* listNew, uint32_t posNew);
|
|
/**
|
|
* notify that the item as @a posOld from the old list @a listOld is unchanged, the respective item
|
|
* position in the new list is at the position @a posNew in @a listNew
|
|
*/
|
|
void (*equal)(void* opaque, const void* listOld, uint32_t posOld, const void* listNew, uint32_t posNew);
|
|
} vlc_diffutil_snake_callback_t;
|
|
|
|
typedef struct diffutil_snake_t diffutil_snake_t;
|
|
|
|
enum vlc_diffutil_op_type {
|
|
///items have been added to the list
|
|
VLC_DIFFUTIL_OP_INSERT,
|
|
///items have been removed from the list
|
|
VLC_DIFFUTIL_OP_REMOVE,
|
|
///items have been moved within the list
|
|
VLC_DIFFUTIL_OP_MOVE,
|
|
///current change should be ignored
|
|
VLC_DIFFUTIL_OP_IGNORE,
|
|
};
|
|
|
|
|
|
/**
|
|
* The data positioned at newModel[ y ] is inserted at position index
|
|
* in the current model.
|
|
*
|
|
* @code
|
|
* model = "abcdefg"
|
|
* newModel[3] = 'X'
|
|
* after operation insert(y=3, index = 3), model will be
|
|
* model = "abcXdefg"
|
|
* @endcode
|
|
*/
|
|
struct vlc_diffutil_insert {
|
|
/// data position in the old model
|
|
uint32_t x;
|
|
/// data position in the new model
|
|
uint32_t y;
|
|
/// insertion position in the updated model
|
|
uint32_t index;
|
|
};
|
|
|
|
|
|
/**
|
|
* The data positioned at oldModel[ y ] is removed at position index
|
|
* in the current model.
|
|
*
|
|
* @code
|
|
* model = "abCdefg"
|
|
* oldModel[4] = 'C'
|
|
* after operation remove(x=4, index = 2), model will be
|
|
* model = "abdefg"
|
|
* @endcode
|
|
*/
|
|
struct vlc_diffutil_remove {
|
|
/// data position in the old model
|
|
uint32_t x;
|
|
/// data position in the new model
|
|
uint32_t y;
|
|
/// removal position in the updated model
|
|
uint32_t index;
|
|
};
|
|
|
|
|
|
/**
|
|
* Moves the data from position model[ from ] to model[ to ]
|
|
* the data is available either at newModel[ y ] or oldModel[ x ]
|
|
*
|
|
* the positions @a from and @a to are given in the referenrial before the operation
|
|
*
|
|
* @code
|
|
* model = "aBCdefg"
|
|
* after operation move(from=1, to=5, count=2), model will be
|
|
* model = "adeCBfg"
|
|
* @endcode
|
|
*/
|
|
struct vlc_diffutil_move {
|
|
/// move origin
|
|
uint32_t from;
|
|
/// move destination
|
|
uint32_t to;
|
|
/// data position in the old model
|
|
uint32_t x;
|
|
/// data position in the new model
|
|
uint32_t y;
|
|
};
|
|
|
|
|
|
|
|
/**
|
|
* represent a change to the model, each change assumes that previous changes
|
|
* have already been applied
|
|
*
|
|
* for instance with a model "aBcDef", the operations [remove(index=1, count=1), remove(index=2, count=1)]
|
|
* will result in "acef" (with "acDef" as intermediary step)
|
|
*/
|
|
typedef struct {
|
|
union {
|
|
struct vlc_diffutil_insert insert;
|
|
struct vlc_diffutil_remove remove;
|
|
struct vlc_diffutil_move move;
|
|
} op;
|
|
|
|
/// type of change operation
|
|
enum vlc_diffutil_op_type type;
|
|
|
|
/// number of elements to be inserted/removed/moved
|
|
uint32_t count;
|
|
} vlc_diffutil_change_t;
|
|
|
|
typedef struct VLC_VECTOR(vlc_diffutil_change_t) vlc_diffutil_changelist_t;
|
|
|
|
enum vlc_diffutil_result_flag {
|
|
/// try to transform an insertion with a matching suppression into a move operation
|
|
VLC_DIFFUTIL_RESULT_MOVE = 0x1,
|
|
/**
|
|
* aggregate similar consecutive operations into a single operation
|
|
* for instance this:
|
|
* [{INSERT, i=5}{INSERT, x=6}{REMOVE, i=10}{REMOVE, i=10}{REMOVE, i=10}]
|
|
* would be transformed into:
|
|
* [{INSERT, i=5, count=2}{REMOVE, i=10, count=3}]
|
|
*/
|
|
VLC_DIFFUTIL_RESULT_AGGREGATE = 0x2,
|
|
};
|
|
|
|
/**
|
|
* vlc_diffutil_build_snake compute a diff model
|
|
* between the @a dataOld model and the @a dataNew model. This model can be
|
|
* processed manually using vlc_diffutil_walk_snake or translated into a change list using
|
|
* vlc_diffutil_build_change_list
|
|
*
|
|
* @param diffOp callback to compare the elements from the old and new model
|
|
* @param dataOld old model
|
|
* @param dataNew new model
|
|
* @return the diff model, NULL on error
|
|
*/
|
|
VLC_API struct diffutil_snake_t* vlc_diffutil_build_snake(const vlc_diffutil_callback_t* diffOp, const void* dataOld, const void* dataNew);
|
|
|
|
/// free the snake created by vlc_diffutil_build_snake
|
|
VLC_API void vlc_diffutil_free_snake(struct diffutil_snake_t* snake);
|
|
|
|
/**
|
|
* iterate over the changelist and callback user on each operation (keep/insert/remove)
|
|
*
|
|
* @param snake the snake created with vlc_diffutil_build_snake
|
|
* @param snakeOp snake callback
|
|
* @param cbData user data for snake callbacks
|
|
* @param diffOp callbacks used in vlc_diffutil_build_snake
|
|
* @param dataOld old model
|
|
* @param dataNew new model
|
|
* @return false on error
|
|
*
|
|
* @warning @a dataOld and @a dataNew should not be altered during the operation
|
|
*/
|
|
VLC_API bool vlc_diffutil_walk_snake(
|
|
const diffutil_snake_t* snake,
|
|
const vlc_diffutil_snake_callback_t* snakeOp, void* cbData,
|
|
const vlc_diffutil_callback_t* diffOp, const void* dataOld, const void* dataNew);
|
|
|
|
/**
|
|
* vlc_diffutil_build_change_list creates a list of changes to apply to transform @a dataOld into @a dataNew
|
|
*
|
|
* @param snake the snake created with vlc_diffutil_build_snake
|
|
* @param diffOp callbacks used in vlc_diffutil_build_snake
|
|
* @param dataOld old model
|
|
* @param dataNew new model
|
|
* @param flags vlc_diffutil_result_flag flags
|
|
* @return the list of changes, NULL on error
|
|
*/
|
|
VLC_API vlc_diffutil_changelist_t* vlc_diffutil_build_change_list(
|
|
const struct diffutil_snake_t* snake,
|
|
const vlc_diffutil_callback_t* diffOp, const void* dataOld, const void* dataNew,
|
|
int flags);
|
|
|
|
/// free the changelist created by vlc_diffutil_build_change_list
|
|
VLC_API void vlc_diffutil_free_change_list(vlc_diffutil_changelist_t* changelist);
|
|
|
|
|
|
#endif // VLC_DIFFUTIL_H
|