text: /*
   * This program is free software; you can redistribute it and/or
   * modify it under the terms of the GNU General Public License
   * as published by the Free Software Foundation; either version 2
   * 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 General Public License for more details.
   *
   * You should have received a copy of the GNU 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.
   *
   * Peter Schlaile <peter [at] schlaile [dot] de> 2010
   */
  
  /** \file
   * \ingroup bke
   */
  
  #include <stddef.h>
  #include <memory.h>
  
  #include "MEM_guardedalloc.h"
  
  #include "DNA_sequence_types.h"
  #include "DNA_scene_types.h"
  
  #include "IMB_imbuf.h"
  #include "IMB_imbuf_types.h"
  
  #include "BLI_mempool.h"
  #include "BLI_threads.h"
  #include "BLI_listbase.h"
  #include "BLI_ghash.h"
  
  #include "BKE_sequencer.h"
  #include "BKE_scene.h"
  #include "BKE_main.h"
  
  /**
   * Sequencer Cache Design Notes
   * ============================
   *
   * Function:
   * All images created during rendering are added to cache, even if the cache is already full.
   * This is because:
   *  - one image may be needed multiple times during rendering.
   *  - keeping the last rendered frame allows us for faster re-render when user edits strip in stack
   *  - we can decide if we keep frame only when it's completely rendered. Otherwise we risk having
   *    "holes" in the cache, which can be annoying
   * If the cache is full all entries for pending frame will have is_temp_cache set.
   *
   * Linking: We use links to reduce number of iterations over entries needed to manage cache.
   * Entries are linked in order as they are put into cache.
   * Only permanent (is_temp_cache = 0) cache entries are linked.
   * Putting #SEQ_CACHE_STORE_FINAL_OUT will reset linking
   *
   * Only entire frame can be freed to release resources for new entries (recycling).
   * Once again, this is to reduce number of iterations, but also more controllable than removing
   * entries one by one in reverse order to their creation.
   *
   * User can exclude caching of some images. Such entries will have is_temp_cache set.
   */
  
  typedef struct SeqCache {
    struct GHash *hash;
    ThreadMutex iterator_mutex;
    struct BLI_mempool *keys_pool;
    struct BLI_mempool *items_pool;
    struct SeqCacheKey *last_key;
    size_t memory_used;
  } SeqCache;
  
  typedef struct SeqCacheItem {
    struct SeqCache *cache_owner;
    struct ImBuf *ibuf;
  } SeqCacheItem;
  
  typedef struct SeqCacheKey {
    struct SeqCache *cache_owner;
    void *userkey;
    struct SeqCacheKey *link_prev; /* Used for linking intermediate items to final frame */
    struct SeqCacheKey *link_next; /* Used for linking intermediate items to final frame */
    struct Sequence *seq;
    SeqRenderData context;
    float nfra;
    float cost;         /* In short: render time(s) divided by playback frame duration(s) */
    bool is_temp_cache; /* this cache entry will be freed before rendering next frame */
    /* ID of task for asigning temp cache entries to particular task(thread, etc.) */
    eSeqTaskId task_id;
    int type;
  } SeqCacheKey;
  
  static ThreadMutex cache_create_lock = BLI_MUTEX_INITIALIZER;
  
  static bool seq_cmp_render_data(const SeqRenderData *a, const SeqRenderData *b)
  {
    return ((a->preview_render_size != b->preview_render_size) || (a->rectx != b->rectx) ||
            (a->recty != b->recty) || (a->bmain != b->bmain) || (a->scene != b->scene) ||
            (a->motion_blur_shutter != b->motion_blur_shutter) ||
            (a->motion_blur_samples != b->motion_blur_samples) ||
            (a->scene->r.views_format != b->scene->r.views_format) || (a->view_id != b->view_id));
  }
  
  static unsigned int seq_hash_render_data(const SeqRenderData *a)
  {
    unsigned int rval = a->rectx + a->recty;
  
    rval ^= a->preview_render_size;
    rval ^= ((intptr_t)a->bmain) << 6;
    rval ^= ((intptr_t)a->scene) << 6;
    rval ^= (int)(a->motion_blur_shutter * 100.0f) << 10;
    rval ^= a->motion_blur_samples << 16;
    rval ^= ((a->scene->r.views_format * 2) + a->view_id) << 24;
  
    return rval;
  }
  
  static unsigned int seq_cache_hashhash(const void *key_)
  {
    const SeqCacheKey *key = key_;
    unsigned int rval = seq_hash_render_data(&key->context);
  
    rval ^= *(const unsigned int *)&key->nfra;
    rval += key->type;
    rval ^= ((intptr_t)key->seq) << 6;
  
    return rval;
  }
  
  static bool seq_cache_hashcmp(const void *a_, const void *b_)
  {
    const SeqCacheKey *a = a_;
    const SeqCacheKey *b = b_;
  
    return ((a->seq != b->seq) || (a->nfra != b->nfra) || (a->type != b->type) ||
            seq_cmp_render_data(&a->context, &b->context));
  }
  
  static SeqCache *seq_cache_get_from_scene(Scene *scene)
  {
    if (scene && scene->ed && scene->ed->cache) {
      return scene->ed->cache;
    }
  
    return NULL;
  }
  
  static void seq_cache_lock(Scene *scene)
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
  
    if (cache) {
      BLI_mutex_lock(&cache->iterator_mutex);
    }
  }
  
  static void seq_cache_unlock(Scene *scene)
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
  
    if (cache) {
      BLI_mutex_unlock(&cache->iterator_mutex);
    }
  }
  
  static size_t seq_cache_get_mem_total(void)
  {
    return ((size_t)U.memcachelimit) * 1024 * 1024;
  }
  
  static void seq_cache_keyfree(void *val)
  {
    SeqCacheKey *key = val;
    BLI_mempool_free(key->cache_owner->keys_pool, key);
  }
  
  static void seq_cache_valfree(void *val)
  {
    SeqCacheItem *item = (SeqCacheItem *)val;
    SeqCache *cache = item->cache_owner;
  
    if (item->ibuf) {
      cache->memory_used -= IMB_get_size_in_memory(item->ibuf);
      IMB_freeImBuf(item->ibuf);
    }
  
    BLI_mempool_free(item->cache_owner->items_pool, item);
  }
  
  static void seq_cache_put(SeqCache *cache, SeqCacheKey *key, ImBuf *ibuf)
  {
    SeqCacheItem *item;
    item = BLI_mempool_alloc(cache->items_pool);
    item->cache_owner = cache;
    item->ibuf = ibuf;
  
    if (BLI_ghash_reinsert(cache->hash, key, item, seq_cache_keyfree, seq_cache_valfree)) {
      IMB_refImBuf(ibuf);
      cache->last_key = key;
      cache->memory_used += IMB_get_size_in_memory(ibuf);
    }
  }
  
  static ImBuf *seq_cache_get(SeqCache *cache, void *key)
  {
    SeqCacheItem *item = BLI_ghash_lookup(cache->hash, key);
  
    if (item && item->ibuf) {
      IMB_refImBuf(item->ibuf);
  
      return item->ibuf;
    }
  
    return NULL;
  }
  
  static void seq_cache_relink_keys(SeqCacheKey *link_next, SeqCacheKey *link_prev)
  {
    if (link_next) {
      link_next->link_prev = link_prev;
    }
    if (link_prev) {
      link_prev->link_next = link_next;
    }
  }
  
  /* Choose a key out of 2 candidates(leftmost and rightmost items)
   * to recycle based on currently used strategy */
  static SeqCacheKey *seq_cache_choose_key(Scene *scene, SeqCacheKey *lkey, SeqCacheKey *rkey)
  {
    SeqCacheKey *finalkey = NULL;
  
    /* Ideally, cache would not need to check the state of prefetching task
     * that is tricky to do however, because prefetch would need to know,
     * if a key, that is about to be created would be removed by itself.
     *
     * This can happen because only FINAL_OUT item insertion will trigger recycling
     * but that is also the point, where prefetch can be suspended.
     *
     * We could use temp cache as a shield and later untemp entry,
     * but it is not worth of increasing system complexity.
     */
    if (scene->ed->cache_flag & SEQ_CACHE_PREFETCH_ENABLE) {
      int pfjob_start, pfjob_end;
      BKE_sequencer_prefetch_get_time_range(scene, &pfjob_start, &pfjob_end);
  
      if (lkey) {
        int lkey_cfra = lkey->seq->start + lkey->nfra;
        if (lkey_cfra < pfjob_start || lkey_cfra > pfjob_end) {
          return lkey;
        }
      }
  
      if (rkey) {
        int rkey_cfra = rkey->seq->start + rkey->nfra;
        if (rkey_cfra < pfjob_start || rkey_cfra > pfjob_end) {
          return rkey;
        }
      }
  
      return NULL;
    }
  
    if (rkey && lkey) {
      int lkey_cfra = lkey->seq->start + lkey->nfra;
      int rkey_cfra = rkey->seq->start + rkey->nfra;
  
      if (lkey_cfra > rkey_cfra) {
        SeqCacheKey *swapkey = lkey;
        lkey = rkey;
        rkey = swapkey;
      }
  
      int l_diff = scene->r.cfra - lkey_cfra;
      int r_diff = rkey_cfra - scene->r.cfra;
  
      if (l_diff > r_diff) {
        finalkey = lkey;
      }
      else {
        finalkey = rkey;
      }
    }
    else {
      if (lkey) {
        finalkey = lkey;
      }
      else {
        finalkey = rkey;
      }
    }
    return finalkey;
  }
  
  static void seq_cache_recycle_linked(Scene *scene, SeqCacheKey *base)
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
    if (!cache) {
      return;
    }
  
    SeqCacheKey *next = base->link_next;
  
    while (base) {
      SeqCacheKey *prev = base->link_prev;
      BLI_ghash_remove(cache->hash, base, seq_cache_keyfree, seq_cache_valfree);
      base = prev;
    }
  
    base = next;
    while (base) {
      next = base->link_next;
      BLI_ghash_remove(cache->hash, base, seq_cache_keyfree, seq_cache_valfree);
      base = next;
    }
  }
  
  static SeqCacheKey *seq_cache_get_item_for_removal(Scene *scene)
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
    SeqCacheKey *finalkey = NULL;
    /*leftmost key*/
    SeqCacheKey *lkey = NULL;
    /*rightmost key*/
    SeqCacheKey *rkey = NULL;
    SeqCacheKey *key = NULL;
  
    GHashIterator gh_iter;
    BLI_ghashIterator_init(&gh_iter, cache->hash);
    int total_count = 0;
    int cheap_count = 0;
  
    while (!BLI_ghashIterator_done(&gh_iter)) {
      key = BLI_ghashIterator_getKey(&gh_iter);
      SeqCacheItem *item = BLI_ghashIterator_getValue(&gh_iter);
      BLI_ghashIterator_step(&gh_iter);
  
      /* this shouldn't happen, but better be safe than sorry */
      if (!item->ibuf) {
        seq_cache_recycle_linked(scene, key);
        /* can not continue iterating after linked remove */
        BLI_ghashIterator_init(&gh_iter, cache->hash);
        continue;
      }
  
      if (key->is_temp_cache || key->link_next != NULL) {
        continue;
      }
  
      total_count++;
  
      if (key->cost <= scene->ed->recycle_max_cost) {
        cheap_count++;
        if (lkey) {
          if (key->seq->start + key->nfra < lkey->seq->start + lkey->nfra) {
            lkey = key;
          }
        }
        else {
          lkey = key;
        }
        if (rkey) {
          if (key->seq->start + key->nfra > rkey->seq->start + rkey->nfra) {
            rkey = key;
          }
        }
        else {
          rkey = key;
        }
      }
    }
  
    finalkey = seq_cache_choose_key(scene, lkey, rkey);
  
    return finalkey;
  }
  
  /* Find only "base" keys
   * Sources(other types) for a frame must be freed all at once
   */
  bool BKE_sequencer_cache_recycle_item(Scene *scene)
  {
    size_t memory_total = seq_cache_get_mem_total();
    SeqCache *cache = seq_cache_get_from_scene(scene);
    if (!cache) {
      return false;
    }
  
    seq_cache_lock(scene);
  
    while (cache->memory_used > memory_total) {
      SeqCacheKey *finalkey = seq_cache_get_item_for_removal(scene);
  
      if (finalkey) {
        seq_cache_recycle_linked(scene, finalkey);
      }
      else {
        seq_cache_unlock(scene);
        return false;
      }
    }
    seq_cache_unlock(scene);
    return true;
  }
  
  static void seq_cache_set_temp_cache_linked(Scene *scene, SeqCacheKey *base)
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
  
    if (!cache || !base) {
      return;
    }
  
    SeqCacheKey *next = base->link_next;
  
    while (base) {
      SeqCacheKey *prev = base->link_prev;
      base->is_temp_cache = true;
      base = prev;
    }
  
    base = next;
    while (base) {
      next = base->link_next;
      base->is_temp_cache = true;
      base = next;
    }
  }
  
  static void BKE_sequencer_cache_create(Scene *scene)
  {
    BLI_mutex_lock(&cache_create_lock);
    if (scene->ed->cache == NULL) {
      SeqCache *cache = MEM_callocN(sizeof(SeqCache), "SeqCache");
      cache->keys_pool = BLI_mempool_create(sizeof(SeqCacheKey), 0, 64, BLI_MEMPOOL_NOP);
      cache->items_pool = BLI_mempool_create(sizeof(SeqCacheItem), 0, 64, BLI_MEMPOOL_NOP);
      cache->hash = BLI_ghash_new(seq_cache_hashhash, seq_cache_hashcmp, "SeqCache hash");
      cache->last_key = NULL;
      BLI_mutex_init(&cache->iterator_mutex);
      scene->ed->cache = cache;
    }
    BLI_mutex_unlock(&cache_create_lock);
  }
  
  /* ***************************** API ****************************** */
  
  void BKE_sequencer_cache_free_temp_cache(Scene *scene, short id, int cfra)
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
    if (!cache) {
      return;
    }
  
    seq_cache_lock(scene);
  
    GHashIterator gh_iter;
    BLI_ghashIterator_init(&gh_iter, cache->hash);
    while (!BLI_ghashIterator_done(&gh_iter)) {
      SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
      BLI_ghashIterator_step(&gh_iter);
  
      if (key->is_temp_cache && key->task_id == id && key->seq->start + key->nfra != cfra) {
        BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
      }
    }
    seq_cache_unlock(scene);
  }
  
  void BKE_sequencer_cache_destruct(Scene *scene)
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
    if (!cache) {
      return;
    }
  
    BLI_ghash_free(cache->hash, seq_cache_keyfree, seq_cache_valfree);
    BLI_mempool_destroy(cache->keys_pool);
    BLI_mempool_destroy(cache->items_pool);
    BLI_mutex_end(&cache->iterator_mutex);
    MEM_freeN(cache);
    scene->ed->cache = NULL;
  }
  
  void BKE_sequencer_cache_cleanup_all(Main *bmain)
  {
    for (Scene *scene = bmain->scenes.first; scene != NULL; scene = scene->id.next) {
      BKE_sequencer_cache_cleanup(scene);
    }
  }
  void BKE_sequencer_cache_cleanup(Scene *scene)
  {
    BKE_sequencer_prefetch_stop(scene);
  
    SeqCache *cache = seq_cache_get_from_scene(scene);
    if (!cache) {
      return;
    }
  
    seq_cache_lock(scene);
  
    GHashIterator gh_iter;
    BLI_ghashIterator_init(&gh_iter, cache->hash);
    while (!BLI_ghashIterator_done(&gh_iter)) {
      SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
  
      BLI_ghashIterator_step(&gh_iter);
      BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
    }
    cache->last_key = NULL;
    seq_cache_unlock(scene);
  }
  
  void BKE_sequencer_cache_cleanup_sequence(Scene *scene,
                                            Sequence *seq,
                                            Sequence *seq_changed,
                                            int invalidate_types)
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
    if (!cache) {
      return;
    }
  
    seq_cache_lock(scene);
  
    int range_start = seq_changed->startdisp;
    int range_end = seq_changed->enddisp;
  
    if (seq->startdisp > range_start) {
      range_start = seq->startdisp;
    }
  
    if (seq->enddisp < range_end) {
      range_end = seq->enddisp;
    }
  
    int invalidate_composite = invalidate_types & SEQ_CACHE_STORE_FINAL_OUT;
    int invalidate_source = invalidate_types & (SEQ_CACHE_STORE_RAW | SEQ_CACHE_STORE_PREPROCESSED |
                                                SEQ_CACHE_STORE_COMPOSITE);
  
    GHashIterator gh_iter;
    BLI_ghashIterator_init(&gh_iter, cache->hash);
    while (!BLI_ghashIterator_done(&gh_iter)) {
      SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
      BLI_ghashIterator_step(&gh_iter);
  
      int key_cfra = key->seq->start + key->nfra;
  
      /* clean all final and composite in intersection of seq and seq_changed */
      if (key->type & invalidate_composite && key_cfra >= range_start && key_cfra <= range_end) {
        if (key->link_next || key->link_prev) {
          seq_cache_relink_keys(key->link_next, key->link_prev);
        }
  
        BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
      }
  
      if (key->type & invalidate_source && key->seq == seq && key_cfra >= seq_changed->startdisp &&
          key_cfra <= seq_changed->enddisp) {
        if (key->link_next || key->link_prev) {
          seq_cache_relink_keys(key->link_next, key->link_prev);
        }
  
        BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
      }
    }
    cache->last_key = NULL;
    seq_cache_unlock(scene);
  }
  
  struct ImBuf *BKE_sequencer_cache_get(const SeqRenderData *context,
                                        Sequence *seq,
                                        float cfra,
                                        int type)
  {
    Scene *scene = context->scene;
  
    if (context->is_prefetch_render) {
      context = BKE_sequencer_prefetch_get_original_context(context);
      scene = context->scene;
      seq = BKE_sequencer_prefetch_get_original_sequence(seq, scene);
    }
  
    if (!scene->ed->cache) {
      BKE_sequencer_cache_create(scene);
      return NULL;
    }
  
    seq_cache_lock(scene);
    SeqCache *cache = seq_cache_get_from_scene(scene);
    ImBuf *ibuf = NULL;
  
    if (cache && seq) {
      SeqCacheKey key;
  
      key.seq = seq;
      key.context = *context;
      key.nfra = cfra - seq->start;
      key.type = type;
  
      ibuf = seq_cache_get(cache, &key);
    }
    seq_cache_unlock(scene);
  
    return ibuf;
  }
  
  bool BKE_sequencer_cache_put_if_possible(
      const SeqRenderData *context, Sequence *seq, float cfra, int type, ImBuf *ibuf, float cost)
  {
    Scene *scene = context->scene;
  
    if (context->is_prefetch_render) {
      context = BKE_sequencer_prefetch_get_original_context(context);
      scene = context->scene;
      seq = BKE_sequencer_prefetch_get_original_sequence(seq, scene);
    }
  
    if (BKE_sequencer_cache_recycle_item(scene)) {
      BKE_sequencer_cache_put(context, seq, cfra, type, ibuf, cost);
      return true;
    }
    else {
      seq_cache_set_temp_cache_linked(scene, scene->ed->cache->last_key);
      scene->ed->cache->last_key = NULL;
      return false;
    }
  }
  
  void BKE_sequencer_cache_put(
      const SeqRenderData *context, Sequence *seq, float cfra, int type, ImBuf *i, float cost)
  {
    Scene *scene = context->scene;
  
    if (context->is_prefetch_render) {
      context = BKE_sequencer_prefetch_get_original_context(context);
      scene = context->scene;
      seq = BKE_sequencer_prefetch_get_original_sequence(seq, scene);
    }
  
    if (i == NULL || context->skip_cache || context->is_proxy_render || !seq) {
      return;
    }
  
    /* Prevent reinserting, it breaks cache key linking */
    ImBuf *test = BKE_sequencer_cache_get(context, seq, cfra, type);
    if (test) {
      IMB_freeImBuf(test);
      return;
    }
  
    if (!scene->ed->cache) {
      BKE_sequencer_cache_create(scene);
    }
  
    seq_cache_lock(scene);
  
    SeqCache *cache = seq_cache_get_from_scene(scene);
    int flag;
  
    if (seq->cache_flag & SEQ_CACHE_OVERRIDE) {
      flag = seq->cache_flag;
      flag |= scene->ed->cache_flag & SEQ_CACHE_STORE_FINAL_OUT;
    }
    else {
      flag = scene->ed->cache_flag;
    }
  
    if (cost > SEQ_CACHE_COST_MAX) {
      cost = SEQ_CACHE_COST_MAX;
    }
  
    SeqCacheKey *key;
    key = BLI_mempool_alloc(cache->keys_pool);
    key->cache_owner = cache;
    key->seq = seq;
    key->context = *context;
    key->nfra = cfra - seq->start;
    key->type = type;
    key->cost = cost;
    key->cache_owner = cache;
    key->link_prev = NULL;
    key->link_next = NULL;
    key->is_temp_cache = true;
    key->task_id = context->task_id;
  
    /* Item stored for later use */
    if (flag & type) {
      key->is_temp_cache = false;
      key->link_prev = cache->last_key;
    }
  
    SeqCacheKey *temp_last_key = cache->last_key;
    seq_cache_put(cache, key, i);
  
    /* Restore pointer to previous item as this one will be freed when stack is rendered */
    if (key->is_temp_cache) {
      cache->last_key = temp_last_key;
    }
  
    /* Set last_key's reference to this key so we can look up chain backwards
     * Item is already put in cache, so cache->last_key points to current key;
     */
    if (flag & type && temp_last_key) {
      temp_last_key->link_next = cache->last_key;
    }
  
    /* Reset linking */
    if (key->type == SEQ_CACHE_STORE_FINAL_OUT) {
      cache->last_key = NULL;
    }
  
    seq_cache_unlock(scene);
  }
  
  void BKE_sequencer_cache_iterate(
      struct Scene *scene,
      void *userdata,
      bool callback(void *userdata, struct Sequence *seq, int nfra, int cache_type, float cost))
  {
    SeqCache *cache = seq_cache_get_from_scene(scene);
    if (!cache) {
      return;
    }
  
    seq_cache_lock(scene);
    GHashIterator gh_iter;
    BLI_ghashIterator_init(&gh_iter, cache->hash);
    bool interrupt = false;
  
    while (!BLI_ghashIterator_done(&gh_iter) && !interrupt) {
      SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
      BLI_ghashIterator_step(&gh_iter);
  
      interrupt = callback(userdata, key->seq, key->nfra, key->type, key->cost);
    }
  
    cache->last_key = NULL;
    seq_cache_unlock(scene);
  }
  
  bool BKE_sequencer_cache_is_full(Scene *scene)
  {
    size_t memory_total = seq_cache_get_mem_total();
    SeqCache *cache = seq_cache_get_from_scene(scene);
    if (!cache) {
      return false;
    }
  
    return memory_total < cache->memory_used;
  }
  