LXR linux/tools/perf/util/pstack.c

   1/*
   2 * Simple pointer stack
   3 *
   4 * (c) 2010 Arnaldo Carvalho de Melo <acme@redhat.com>
   5 */
   6
   7#include "util.h"
   8#include "pstack.h"
   9#include "debug.h"
  10#include <linux/kernel.h>
  11#include <stdlib.h>
  12
  13struct pstack {
  14        unsigned short  top;
  15        unsigned short  max_nr_entries;
  16        void            *entries[0];
  17};
  18
  19struct pstack *pstack__new(unsigned short max_nr_entries)
  20{
  21        struct pstack *pstack = zalloc((sizeof(*pstack) +
  22                                       max_nr_entries * sizeof(void *)));
  23        if (pstack != NULL)
  24                pstack->max_nr_entries = max_nr_entries;
  25        return pstack;
  26}
  27
  28void pstack__delete(struct pstack *pstack)
  29{
  30        free(pstack);
  31}
  32
  33bool pstack__empty(const struct pstack *pstack)
  34{
  35        return pstack->top == 0;
  36}
  37
  38void pstack__remove(struct pstack *pstack, void *key)
  39{
  40        unsigned short i = pstack->top, last_index = pstack->top - 1;
  41
  42        while (i-- != 0) {
  43                if (pstack->entries[i] == key) {
  44                        if (i < last_index)
  45                                memmove(pstack->entries + i,
  46                                        pstack->entries + i + 1,
  47                                        (last_index - i) * sizeof(void *));
  48                        --pstack->top;
  49                        return;
  50                }
  51        }
  52        pr_err("%s: %p not on the pstack!\n", __func__, key);
  53}
  54
  55void pstack__push(struct pstack *pstack, void *key)
  56{
  57        if (pstack->top == pstack->max_nr_entries) {
  58                pr_err("%s: top=%d, overflow!\n", __func__, pstack->top);
  59                return;
  60        }
  61        pstack->entries[pstack->top++] = key;
  62}
  63
  64void *pstack__pop(struct pstack *pstack)
  65{
  66        void *ret;
  67
  68        if (pstack->top == 0) {
  69                pr_err("%s: underflow!\n", __func__);
  70                return NULL;
  71        }
  72
  73        ret = pstack->entries[--pstack->top];
  74        pstack->entries[pstack->top] = NULL;
  75        return ret;
  76}
  77
  78void *pstack__peek(struct pstack *pstack)
  79{
  80        if (pstack->top == 0)
  81                return NULL;
  82        return pstack->entries[pstack->top - 1];
  83}
  84