2011년 7월 19일 화요일

Double linked list in c language

* data type double linkage

struct dlink {
  void *object;
  struct dlink *prev;
  struct dlink *next;
};

typedef struct dlink dlink_t;

- object : reference pointer indicating the address for any-type user-data using casting to void type pointer.
- prev : previous pointer for double-linked component
- next : next pointer for double-linked component

* data type double linked list

typedef struct {
  int count;
  dlink_t *head;
  dlink_t *tail;
} dlist_t;

- count : the number of components contained by the list.
- head, tail : the start and end linkage for data- inport and outport.

----------------------------------- dlink.h -------------------------------------------

/* Double linked list

 Copyright 2011 Hoyoung Yi.

 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 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, please visit www.gnu.org.
*/

#ifndef __DLINK_H__
#define __DLINK_H__

struct dlink {
  void *object;
  void *private;
  struct dlink *prev;
  struct dlink *next;
};

typedef struct dlink dlink_t;

dlink_t *dlink_new(void);
void dlink_prepend(dlink_t *obj, dlink_t *at);
void dlink_append(dlink_t *obj, dlink_t *at);
void dlink_cutoff(dlink_t *obj);
void dlink_substitute(dlink_t *dummy, dlink_t *at);
void dlink_exchange(dlink_t *a, dlink_t *b);
void dlink_destroy(dlink_t *dlink);

typedef struct {
  int reference;
  int count;
  void *private;
  dlink_t *head;
  dlink_t *tail;
} dlist_t;

dlist_t *dlist_new(void);
void dlist_push(dlink_t *link, dlist_t *list);
dlink_t *dlist_pop(dlist_t *list);
void dlist_insert(dlink_t *link, dlist_t *list);
dlink_t *dlist_extract(dlist_t *list);
dlink_t *dlist_glimpse(int index, dlist_t *list);
dlink_t *dlist_pick(int index, dlist_t *list);
void dlist_put(dlink_t *link, int i, dlist_t *list);
void dlist_exchange(int i, int j, dlist_t *list);
void dlist_destroy(dlist_t *list);

#endif /* __DLINK_H__ */
----------------------------------- dlink.c -------------------------------------------

/* Double linked list

 Copyright 2011 Hoyoung Yi.

 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 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, please visit www.gnu.org.
*/

#include
#include
#include
#include "dlink.h"

dlink_t *dlink_new(void)
{
  dlink_t *dlink;

  dlink = malloc(sizeof(dlink_t));
  assert(dlink);
  memset(dlink, 0, sizeof(dlink_t));

  return dlink;
}

void dlink_prepend(dlink_t *obj, dlink_t *at)
{
  assert(obj);
  assert(at);

  obj->prev = at->prev;
  obj->next = at;

  at->prev->next = obj;
  at->prev = obj;
}

void dlink_append(dlink_t *obj, dlink_t *at)
{
  assert(obj);
  assert(at);

  obj->prev = at;
  obj->next = at->next;

  at->next->prev = obj;
  at->next = obj;
}

void dlink_cutoff(dlink_t *obj)
{
  assert(obj);

  obj->prev->next = obj->next;
  obj->next->prev = obj->prev;
}

void dlink_substitute(dlink_t *dummy, dlink_t *at)
{
  assert(dummy);
  assert(at);

  at->prev->next = dummy;
  at->next->prev = dummy;
  dummy->prev = at->prev;
  dummy->next = at->next;
}

void dlink_exchange(dlink_t *a, dlink_t *b)
{
  dlink_t *dummy;

  assert(a);
  assert(b);

  dummy = dlink_new();

  dlink_substitute(dummy, a);
  dlink_substitute(a, b);
  dlink_substitute(b, dummy);

  dlink_destroy(dummy);
}

void dlink_destroy(dlink_t *dlink)
{
  assert(dlink);
  free(dlink);
}

dlist_t *dlist_new(void)
{
  dlist_t *dlist;

  dlist = malloc(sizeof(dlist_t)+2*sizeof(dlink_t));
  assert(dlist);

  memset(dlist, 0, sizeof(dlist_t)+2*sizeof(dlink_t));

  dlist->head = (dlink_t *)(dlist+1);
  dlist->tail = dlist->head+1;

  dlist->head->next = NULL;
  dlist->head->prev = dlist->tail;

  dlist->tail->next = dlist->head;
  dlist->tail->prev = NULL;

  return dlist;
}

void dlist_push(dlink_t *link, dlist_t *list)
{
  assert(list);
  assert(link);

  dlink_append(link, list->tail);
  //dlink_prepend(link, list->head);
  list->count++;
}

dlink_t *dlist_pop(dlist_t *list)
{
  dlink_t *link;
  assert(list);

  //link = list->head->prev;
  link = list->tail->next;
  dlink_cutoff(link);
  list->count--;

  return link;
}

void dlist_insert(dlink_t *link, dlist_t *list)
{
  assert(list);
  assert(link);

  dlink_prepend(link, list->head);
  list->count++;
}

dlink_t *dlist_extract(dlist_t *list)
{
  dlink_t *link;

  assert(list);

  if (list->count == 0) return NULL;

  //link = list->tail->next;
  link = list->head->prev;
  dlink_cutoff(link);
  list->count--;

  return link;
}

dlink_t *dlist_glimpse(int index, dlist_t *list)
{
  dlink_t *link;

  assert(list);
  assert(index >= 0 && index < list->count);

  link = list->tail->next;
  while (index--) link = link->next;

  return link;
}

dlink_t *dlist_pick(int index, dlist_t *list)
{
  dlink_t *link;

  assert(list);
  assert(index >= 0 && index < list->count);

  link = list->tail->next;
  while (index--) link = link->next;
  dlink_cutoff(link);
  list->count--;

  return link;
}

void dlist_put(dlink_t *link, int i, dlist_t *list)
{
  dlink_t *ilink;

  assert(link);
  assert(i >= 0 && i < list->count);

  ilink = list->tail->next;
  while (i--) ilink = ilink->next;
  dlink_prepend(link, ilink);
}

void dlist_exchange(int i, int j, dlist_t *list)
{
  dlink_t *ilink, *jlink;

  assert(list);
  assert(i >= 0 && i < list->count);
  assert(j >= 0 && j < list->count);

  ilink = list->tail->next;
  while (i--) ilink = ilink->next;

  jlink = list->tail->next;
  while (j--) jlink = jlink->next;

  dlink_exchange(ilink, jlink);
}

void dlist_destroy(dlist_t *list)
{
  dlink_t *link;

  assert(list);

  if (list->reference == 0) {
    while (list->count > 0) {
      link = dlist_extract(list);
      dlink_destroy(link);
    }
    free(list);
  } else list->reference--;
}

댓글 1개:

  1. I think so this post is very interesting and usefull for all us. We must follow this every time.

    답글삭제